|
Страница 1 из 2
Выяснение интервала, на котором корень содержится является важной проблемой поиска корня нелинейной функции действительной переменной. Здесь приведен алгоритм поиска такого интервала и ограничения на его применение.
Примем, что корень функции f(x) окружен на интервале [a,b], если f(a) и f(b) имеют противоположные знаки. Чтобы окруженный согласно этому определению корень действительно существовал на этом интервале, достаточно непрерывности f(x), а для его единственности - еще и монотонности. При невыполнении этих свойств возможно отсутствие корня на [a,b] или неопределенность его позиции. При использовании компьютера, всегда имеем дело с дискретным набором возможных представлений чисел (хотя и достаточно плотным). Кроме того, монотонность вычисленной функции может быть слегка нарушена в пределах точности ее вычисления. Это в ряде случаев усложняет вычисление окруженных корней функции, если к их точности предъявляются завышенные требования. Окружение корня функции при гарантии ее определения на неограниченном интервале, производится по следующему итерационному алгоритму.
1. Для начального приближения x0, найти f0=f(x0), задать начальный интервал поиска D и его инкремент d>1.
2. Вычислить a=x0-D, b=x0+D; fa=f(a), fb=f(b).
3. Увеличить интервал поиска: D=D*d. Если интервал превысил некоторый заданный предел, то выйти с индикацией ошибки.
4a. Если знаки fa и f0 отличаются, то считать корень окруженным на [a,x0] -> выход.
4b. Если знаки fb и f0 отличаются, то считать корень окруженным на [x0,b] -> выход.
4c. Если f0>0 (случай меньше нуля делается аналогично) алгоритм продолжается:
5. Проверяется, какое из fa или fb наименьшее. Если оба одинаковы, то переходим к 6a (двусторонний поиск), если fb -- производим поиск вправо 6b, иначе -- поиск влево 6c.
6a. Находим a=a-D, b=b+D, fa=f(a), fb=f(b), идем к пункту 3.
6b. Присваиваем последовательно a=x0, x0=b, fa=f0, f0=fb; находим b=b+D, fb=f(b), идем к пункту 3.
6c. Аналогично 6b, только направление поиска -- влево. Так как интервал поиска постоянно расширяется, то в конце концов используя указанный алгоритм корень будет окружен. Возможны модификации алгоритма в двух направлениях:
1) Увеличивать интервал не в геометрической прогрессии, а в арифметической либо по заданному сценарию;
2) Если область определения функции заведомо ограничена, то расширение интервала поиска также следует ограничивать имеющимися пределами, либо доопределять функцию там, где ее оригинал не определен. |