Вы здесь

Метод половинного деления

Исходный код на C++: 

Теория

Пусть функция f(x) определена и непрерывна на промежутке [a,b] и меняет знак т. е. f(a)*f(b)<0. Тогда можно утверждать что функция f(x) имеет хотя бы один корень на промежутке [a,b]. Идея метода половинного деления очень проста.

  1. Вычисляем k=(a+b)/2;
  2. Если b-a<2*E функция возвращает k, где E- допустимая погрешность;
  3. Вычислим f(k);
  4. Если |f(k)|<Q функция возвращает k, где Q- допуск;
  5. Если f(a)*f(c)<0 тогда b=c иначе a=c;
  6. вернуться на шаг 1.

Программная реализация

double bisection(double a, double b, double (*f)(double x), bool *ok = NULL) // деления отрезка пополам
{
    if (f(a) * f(b) &lt; 0) {
        if (ok != NULL)
            *ok = true;
    } else {
        if (ok != NULL)
            *ok = false;
        return 0.;
    }
    double k, y;
    while (1) {
        k = (a + b) / 2;
        if (fabs(b - a) &lt; 2 * E)
            return k;
        y = f(k);
        if (fabs(y) &lt; Q)
            return k;
        f(a)*f(k) &lt; 0 ? b = k : a = k;
    }
}