Окружение и локализация корня нелинейной функции
действительной переменной
Важной проблемой поиска корня нелинейной функции
действительной переменной является выяснение интервала, на котором корень
содержится. Ниже приведен алгоритм поиска такого интервала и ограничения на его
применение.
Будем говорить, что корень функции 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