Окружение и локализация корня нелинейной функции действительной переменной
Окружение и локализация корня нелинейной функции действительной переменной
применение.
Будем говорить, что корень функции f(x) окружен на интервале [a,b], если f(a) и f(b) имеют противоположные знаки. Для того, чтобы окруженный согласно этому определению корень действительно существовал на этом интервале, достаточно непрерывности f(x), а для его единственности - еще и монотонности. При невыполнении этих свойств возможно отсутствие корня на [a,b] или неопределенность его позиции.
При использовании компьютера мы всегда имеем дело с дискретным набором возможных представлений чисел (хотя и достаточно плотным). Кроме того, монотонность вычисленной функции может быть слегка нарушена в пределах точности ее вычисления. Это в ряде случаев усложняет вычисление окруженных корней функции, если к их точности предъявляются завышенные требования.
Алгоритм
Назначение: окружение корня функции, если ф-я определена на неограниченном интервале
Вход:
Начальное приближение (input guess) x0
начальный интервал поиска D
инкремент начального интервала поиска d>1
максимальное значение интервала M
интервал окружения [a,x0], либо
сообщение об ошибке
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:
break the cycle
7. case f0>0:
9. if fa=fb then: /* both sides search */
end of if fa=fb
10. if fa>fb then: /* the right side search */
let a=x0, x0=b, fa=f0, f0=fb;
>fb
11. if fa<fb then: /* the right side search */
/* Analogically */
<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;
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 */
/* while the increased search interval is less than maximal,
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. */
>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 */
<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 */
}
}
/* if we get there, the search failed */
return(0);
}
| 
