Сегодня речь пойдет о численном методе поиска корня уравнения. Для этого мы будем использовать итеративный метод, который основан на делении отрезка на две части, которые в дальнейшем подвергаются анализу.

Условие

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

Локализация корней

В первом же пункте мы оговорим важную деталь, а именно количество корней на отрезке исследования [a,b]. Мы должны самостоятельно выделить произвольный отрезок на котором находится один корень и значение функции на краях отрезка различного знака. В таких случаях произносят сокровенную фразу: "Графически отделим корни уравнения", а именно попытаемся построить примерный график функции и выбрать необходимые нам интервалы.

Следствие из Теоремы Больцано — Коши

Все наши исследования будут основываться на теореме Больцано — Коши, которая утверждает, что если функция f(x) непрерывна на отрезке [a,b] и на концах отрезков функция принимает значения разных знаков (f(a)<0<f(b) или f(b)<0<f(b)), то существует по крайней мере одна точка, в которой функция обращается в ноль.
Примечание: Теорема Больцано — Коши утверждает, что функция, непрерывная на отрезке, принимает все промежуточные значения.

Необходимые знания
Для дальнейшего диалога нам потребуется вспомнить основные моменты из геометрии, а именно:

Длина отрезка [a,b] — L = (b - a)

Середина отрезка [a,b] — M = (a + b)/2

Алгоритм

Описание

Возьмем отрезок разбиения [a,b], такой, что f(a)<0<f(b) (или f(b)<0<f(a)). До тех пор пока длина отрезка [a,b]>2eps будем выполнять циклично следующие операции:

найдем среднюю точку отрезка [a,b] c = (a+b)/2
Если f(c)=0, то корень найден, КОНЕЦ
Если f(a)*f(c)<0, тогда b=c, иначе a=c

Примечание: f(a)*f(c)<, если f(a) и f(c) имеют разные знаки.

Реализация

C++

#include <iostream>
using namespace std;
double f(double x){
    return x*x+2*x-3;
}
int main(){
    double 
        a = 0,
        b = 4,
        c = 0,
        eps = 0.01;
    while( (b-a)>2*eps ){
        c = (a+b)/2;
        if (f(c)==0)
            break;
        if (f(a)*f(c)<0)
            b = c;
        else
            a = c;
    }
    cout << "x=" << c;
    return 0;
}

Pascal

var a,b,c,eps:real;
function f(x:real):real;
begin
  f := x*x+2*x-3;
end;  
begin
  a := 0;
  b := 4;
  while ((b-a)>2*eps) do
  begin
    c := (a+b)/2;
    if (f(c)=0) then
      break;
    if (f(a)*f(c)<0) then
      b := c
    else
      a := c;
  end;
  writeln('x=',c);
end.

Решение на WolframMathematica 9

Исходный код: bisection_method.nb

Возможная ошибка

Зачастую, при описании этого алгоритма, жертвуют проверкой F(c)=0, а эта небольшая оплошность может привести к некорректной работе алгоритма. Если в нашем примере убрать проверку на F(c)=0, то на отрезке [0,4] значение корня уравнения f(x)=x^2+2x-3 будет стремиться к двум. (трассировка некорректного алгоритма.pdf)

Анализ алгоритма

В случае выполнения условий, описанных ранее, справедлива следующая оценка:

(x_n - приближение к корню x с заданной eps, а n - число шагов метода).

Число шагов метода можно получить из формулы |x_n-x|<=eps, а так как (b-a)/2^(n+1)<=eps, то получаем неравенство:

Метод бисекции