Окружение и локализация корня нелинейной функции действительной переменной

СОДЕРЖАНИЕ: Окружение и локализация корня нелинейной функции действительной переменной Важной проблемой поиска корня нелинейной функции действительной переменной является выяснение интервала, на котором корень содержится. Ниже приведен алгоритм поиска такого интервала и ограничения на его применение.

Окружение и локализация корня нелинейной функции действительной переменной

Важной проблемой поиска корня нелинейной функции действительной переменной является выяснение интервала, на котором корень содержится. Ниже приведен алгоритм поиска такого интервала и ограничения на его применение.

Будем говорить, что корень функции f(x) окружен на интервале [a,b], если f(a) и f(b) имеют противоположные знаки. Для того, чтобы окруженный согласно этому определению корень действительно существовал на этом интервале, достаточно непрерывности f(x), а для его единственности - еще и монотонности. При невыполнении этих свойств возможно отсутствие корня на [a,b] или неопределенность его позиции.

При использовании компьютера мы всегда имеем дело с дискретным набором возможных представлений чисел (хотя и достаточно плотным). Кроме того, монотонность вычисленной функции может быть слегка нарушена в пределах точности ее вычисления. Это в ряде случаев усложняет вычисление окруженных корней функции, если к их точности предъявляются завышенные требования.

Окружение корня функции при гарантии ее определения на неограниченном интервале, производится по следующему итерационному алгоритму.

Алгоритм

Назначение: окружение корня функции, если ф-я определена на неограниченном интервале

Вход:

Начальное приближение (input guess) x0

начальный интервал поиска D

инкремент начального интервала поиска d1

максимальное значение интервала 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 f00:

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 fafb then: /* the right side search */

let a=x0, x0=b, fa=f0, f0=fb;

let b=b+D, fb=f(b)

end of if fafb

11. if fafb then: /* the right side search */

/* Analogically */

end of if fafb

end of compare

end of case

end of repeat

Случай f00 (строка 7) аналогичен.

Так как интервал поиска постоянно расширяется, то в конце концов используя указанный алгоритм корень будет окружен. Возможны модификации алгоритма в двух направлениях:

1) увеличивать интервал не в геометрической прогрессии, а в арифметической либо по заданному сценарию;

2) Если область определения функции заведомо ограничена, то расширение интервала поиска также следует ограничивать имеющимися пределами, либо доопределять функцию там, где ее оригинал не определен.

Ниже расположена программа окружения корня нелинейной функции, реализующая данный алгоритм.

/* Bracketing functions 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 f00. */

if(f0=0.) {

if(fa0.) {*b=x0;return(1);}

if(fb0.) {*a=x0;return(1);}

/* else, compare fa and fb, choose the direction of search. The

right search case. */

if(fafb) {*a=x0; x0=(*b); *b+=d0; fa=f0; f0=fb; fb=(*fun)(*b);}

/* the left search case */

else if(fafb) {*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 f00 */

else if(f00.) {

if(fa=0.) {*b=x0;return(1);}

else if(fb=0.) {*a=x0;return(1);}