Важной проблемой поиска корня нелинейной функции действительной переменной является выяснение интервала, на котором корень содержится. Ниже приведен алгоритм поиска такого интервала и ограничения на его применение.
Будем говорить, что корень функции f(x) окружен на интервале [a,b], если f(a) и f(b) имеют противоположные знаки. Для того, чтобы окруженный согласно этому определению корень действительно существовал на этом интервале, достаточно непрерывности f(x), а для его единственности - еще и монотонности. При невыполнении этих свойств возможно отсутствие корня на [a,b] или неопределенность его позиции.
При использовании компьютера мы всегда имеем дело с дискретным набором возможных представлений чисел (хотя и достаточно плотным). Кроме того, монотонность вычисленной функции может быть слегка нарушена в пределах точности ее вычисления. Это в ряде случаев усложняет вычисление окруженных корней функции, если к их точности предъявляются завышенные требования.
Окружение корня функции при гарантии ее определения на неограниченном интервале, производится по следующему итерационному алгоритму.
Алгоритм
Назначение: окружение корня функции, если ф-я определена на неограниченном интервале
Вход:
Начальное приближение (input guess) x0
начальный интервал поиска D
инкремент начального интервала поиска d>1
максимальное значение интервала M
Выход:
интервал окружения [a,x0], либо
интервал окружения [x0,b], либо
сообщение об ошибке
Инициализация:
calculate f0=f(x0)
Шаги:
1. calculate (a=x0-D,b=x0+D;
fa=f(a), fb=f(b))
2. repeat
3. increase search interval: D=D*d
4. if search interval ≥ M then break the cycle with error message
5. if sign(fa)≠sign(f0) then:
a root is bracketed on [a,x0] interval
break the cycle
end of if
6. if sign(fb)≠sign(f0) then:
a root is bracketed on [x0, b] interval
break the cycle
end of if
7. case f0>0:
8. compare(fa,fb):
9. if fa=fb then: /* both sides search */
let a=a-D, b=b+D, fa=f(a), fb=f(b)
end of if fa=fb
10. if fa>fb then: /* the right side search */
let a=x0, x0=b, fa=f0, f0=fb;
let b=b+D, fb=f(b)
end of if fa>fb
11. if fa<fb then: /* the right side search */
/* Analogically */
end of if fa<fb
end of compare
end of case
end of repeat
Случай f0<0 (строка 7) аналогичен.
Так как интервал поиска постоянно расширяется, то в конце концов используя указанный алгоритм корень будет окружен. Возможны модификации алгоритма в двух направлениях:
1) увеличивать интервал не в геометрической прогрессии, а в арифметической либо по заданному сценарию;
2) Если область определения функции заведомо ограничена, то расширение интервала поиска также следует ограничивать имеющимися пределами, либо доопределять функцию там, где ее оригинал не определен.
Ниже расположена программа окружения корня нелинейной функции, реализующая данный алгоритм.
/* Bracketing function''s root. The function is supposed to have unlimited
domain and be continuous.
int BracketRoot(double x0,double *a,double *b,double d0,
double di, double dmax,double (*fun)(double));
Parameters:
x0 - initial guess on input;
a - left bound on output;
b - right bound on output;
d0 - initial interval of hunting;
di - interval increment (geometric progression multiplier);
dmax - maximal interval;
fun - pointer to the function.
Returns:
1 - if a root is bracketed;
0 - on failure
*/
int BracketRoot(double x0,double *a,double *b,double d0,
double di, double dmax,double (*fun)(double)) {
double fa,fb,f0;
/* get initial function guess, initial a,b,fa,fb */
f0=(*fun)(x0); *a=x0-d0; *b=x0+d0; fa=(*fun)(*a); fb=(*fun)(*b);
/* while the increased search interval is less than maximal,
process cycle */
while((d0*=di)<dmax) {
/* check up the bracketing success. Case f0>0. */
if(f0>=0.) {
if(fa<0.) {*b=x0;return(1);}
if(fb<0.) {*a=x0;return(1);}
/* else, compare fa and fb, choose the direction of search. The
right search case. */
if(fa>fb) {*a=x0; x0=(*b); *b+=d0; fa=f0; f0=fb; fb=(*fun)(*b);}
/* the left search case */
else if(fa<fb) {*b=x0; x0=(*a); *a-=d0; fb=f0; f0=fa; fa=(*fun)(*a);}
/* both sides search */
else {*a-=d0; *b+=d0; fa=(*fun(*a);fb=(*fun)(*b);}
}
/* Analogically, case when f0>0 */
else if(f0<0.) {
if(fa>=0.) {*b=x0;return(1);}
else if(fb>=0.) {*a=x0;return(1);}
/* else, compare fa and fb, choose the direction of search. The
right search case. */
if(fa<fb) {*a=x0; x0=(*b); *b+=d0; fa=f0; f0=fb; fb=(*fun)(*b);}
/* the left search case */
else if(fa>fb) {*b=x0; x0=(*a); *a-=d0; fb=f0; f0=fa; fa=(*fun)(*a);}
/* both sides search */
else {*a-=d0; *b+=d0; fa=(*fun(*a);fb=(*fun)(*b);}
}
}
/* if we get there, the search failed */
return(0);
}
Другие работы по теме:
Планирование и прогнозирование в условиях рынка
Выравнивание заданного динамического ряда по линейной зависимости. Определение параметров и тесноты связи меду ними. Построение графика зависимости переменной и коэффициента корреляции для линейной зависимости. Расчет критериев автокорреляции остатков.
Мое поведение при пожаре
Мое поведение при пожаре План 1. Причины возникновения пожара. 2. Мое поведение при пожаре. 3. Ликвидация и локализация пожара. 4. Последствия пожара.
Мое поведение при пожаре
План 1. Причины возникновения пожара. 2. Мое поведение при пожаре. 3. Ликвидация и локализация пожара. 4. Последствия пожара. 1. Причины возникновения пожара.
Преобразование случайных процессов в безынерционной нелинейной цепи
Железновой Светланы СС0701 ЛАБОРАТОРНАЯ РАБОТА № 13 «Преобразование случайных процессов в безынерционной нелинейной цепи» Цель работы: изучить теорию преобразования статистических характеристик стационарных случайных процессов в безынерционной нелинейной цепи и подтвердить ее основные положения результатами , полученными в ходе машинного эксперимента, где нелинейным элементом является двухсторонний симметричный ограничитель.
Актиномикоз
Актиномикоз лучистогрибковое заболевание, вызываемое различного вида актиномицетами, сапрофитирующими в полости рта.
Растительный препарат фитолизин
Фитолизин как комбинированный растительный препарат, обладающий мочегонным, противовоспалительным, спазмолитическим действием, его назначение и функциональные особенности, показания и противопоказания. Способы приема, дозы, особенности применения детьми.
Крипторхизм
Крипторхизм - неопущение яичка, оно может задержаться на задней стенке брюшной полости, в паховом канале, у наружного отверстия пахового канала.
Функционально-графический подход к решению задач с параметрами
Выполнение алгебраических преобразований, логическая культура и техника исследования. Основные типы задач с параметрами, нахождение количества решений в зависимости от значения параметра. Основные методы решения задач, методы построения графиков функций.
Дифференцирование. Интегрирование
Методика и основные этапы нахождения производной функции. Исследование методами дифференциального исчисления и построение графика функции. Порядок определения экстремумов функции. Вычисление неопределенных и определенных интегралов заменой переменной.
Поиск нулей функции. Итерационные методы
Поиск нулей функции - исследование и построение различных функций зависимостей. Исследование непрерывных процессов. Метод простой итерации. Итерационный процесс Ньютона, аналитическое задание системы уравнений и локализация области нахождения корня.
Дуальные числа
Определение дуальных чисел. Свойства дуальных чисел. Функция и дифференциал функции. Аналог уравнений Коши-Римана. Оператор дифференцирования в области дуальных чисел.
Вычисление корней нелинейного уравнения
Нахождение нулей функции графическим методом. Вычисление корней уравнения при помощи вычислительных блоков Givel и Root. Поиск экстремумов функции. Разложение функции в степенной ряд.
Нелинейное уравнение и интервал изоляции корня
Изучение методов уточнения корней нелинейных уравнений (половинного деления, хорд, касательных, простой итерации). Метод хорд и касательных дает высокую скорость сходимости при решении уравнений, и небольшую - метод половинного деления и простой итерации.
Задача по Математике
Исследовать абсолютную устойчивость нелинейной системы: 1. Определить K = Kгр, при котором система находится на границе устойчивости: Параметры реле:
Приближённое решение алгебраических и трансцендентных уравнений
1. Общая постановка задачи. Найти действительные корни уравнения , где - алгебраическая или трансцендентная функция. Точные методы решения уравнений подходят только к узкому классу уравнений (квадратные, биквадратные, некоторые тригонометрические, показательные, логарифмические).
Мини-сочинение Обломов и его окружение
Мини-сочинение "Обломов и его окружение" Автор: Гончаров И.А. Обломов – это отсталость, мешающая историческому прогрессу. Обломов – чистосердечен, мягок, у него не потеряна совесть; субъективно он не способен сотворить зло. Сюжетная линия рисует духовное запустение героя, в нем есть барство и рабство – он раб своего дивана, лени.
Тейлор, Брук
Сэр Брук Тэйлор (англ. Sir Brook Taylor, 1685—1731) — английский математик, именем которого называется найденная им известная формула, выражающая приращение функции в виде ряда, расположенного по возрастающим степеням приращения независимой переменной.
Решение нелинейных уравнений
ЧИСЛЕННОЕ . 1п. Общий вид нелинейного уравнения F(x)=0 Нелинейные уравнения могут быть двух видов: Алгебраические anxn + an-1xn-1 +… + a0 = 0 Трансцендентные- это уравнения в которых х является аргументом
Расчетно-графическая работа
§1. ЧИСЛЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ. 1п. Общий вид нелинейного уравнения F(x)=0 Нелинейные уравнения могут быть двух видов: Алгебраические
Лабораторная работа №7
Цель работы: Получение навыков реализации циклических алгоритмов с неизвестным числом повторений цикла, операторов цикла с предусловием и постусловием и итерационных циклических алгоритмов.
Интегрирование методом Симпсона
Московский Авиационный Институт Расчетно графическая работа по: алгоритмическим языкам и программированию. кафедра 403 Выполнил: Гуренков Дмитрий гр. 04-109 /____________/
Аналоговые и гибридные машины
Методика и основные этапы исследования физических процессов и сложных динамических систем, которые описываются системами дифференциальных уравнений высшего порядка с большим количеством нелинейностей с помощью специальных аналоговых вычислительных машин.
ГИА алгебра 2009 кодификатор
Государственная (итоговая) аттестация выпускников IX классов общеобразовательных учреждений 2009 г. (в новой форме) по АЛГЕБРЕ Кодификатор элементов содержания по алгебре