Оригинальный DVD-ROM: eXeL@B DVD !
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
выпущен 2 июня!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

ПРОГРАММИРОВАНИЕ НА C и С++



Возможности языков семейства Си по истине безграничны, однако, в этой свободе кроются и недостатки: всегда нужно программисту держать ухо востро и контроллировать "переполнение буфера", чтобы потом программа не вылетала в "синий экран" на массе разнообразных версий Windows и железа у пользователей. Те же крэкеры и реверсеры специально ищут в коде программ на Си уязвимости, куда можно подсадить любой вирусный код, об этом более подробно автор рассказывал в своём видеокурсе здесь. Я там многое узнал и теперь мой код стал значительно более безопасный.

Окружение и локализация корня функции

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

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

 
 /* 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);
 
 }
 
 
 
 

Скачать текст программы brakroot.c

<< ВЕРНУТЬСЯ В ПОДРАЗДЕЛ

<< ВЕРНУТЬСЯ В ОГЛАВЛЕНИЕ




Материалы находятся на сайте https://exelab.ru/pro/



Оригинальный DVD-ROM: eXeL@B DVD !


Вы находитесь на EXELAB.rU
Проект ReactOS