Метод дихотомии

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

а) f(а)f(с) < 0; б) f(с)f(b) < 0; в) f(с) = 0. Применительно к рассматриваемой задаче их можно интерпретировать так:

а) корень находится на интервале (а; с);

б) корень находится на интервале (с; b);

в) точка c является искомым корнем.

Таким образом, одно вычисление значения функции позволяет уменьшить промежуток [а; b] существования корня (ситуация а) или б)) или указать его значение (ситуация в), маловероятная в смысле «прямого попадания» пробной точкой с в корень, но вполне реальная в смысле выполнения приближенного равенства f(с) » 0, когда длина промежутка существования корня близка к длине промежутка его неопределенности). Ясно, что в зависимости от того, имеет место ситуация а) или б), описанная процедура одного шага сужения промежутка существования нуля непрерывной функции f(x) может быть применена к промежутку [a; c] Ì [a; b] или к [c; b] Ì [a; b] соответственно и далее повторяться циклически. Такой простой и легко программируемый процесс называется методом дихотомии. Если способ задания пробных точек с определен так, что последовательность длин получающихся в этом процессе промежутков существования корня стремится к нулю, то методом дихотомии можно найти какой-либо корень уравнения (1) с наперед заданной точностью.

Наиболее употребительным частным случаем метода дихотомии является метод половинного деления, реализующий самый простой способ выбора пробной точки — деление промежутка существования корня пополам. Выполнить приближенное вычисление с точностью ε корня уравнения (1) методом половинного деления при условии, что f(x) непрерывна на [а; b] и f(а)f(b) < 0, можно, например, по следующей схеме:

Шаг 0. Задать концы отрезка а и b, функцию f, малое число ε > 0 (допустимую абсолютную погрешность корня или полудлину его промежутка неопределенности), малое число d > 0 (допуск, связанный с реальной точностью вычисления значений данной функции); вычислить (или ввести) f(а).

Шаг 1. Вычислить с = 0.5(а + b).

Шаг 2. Если b – a < 2e, положить ξ » a (ξ — корень) и остановиться.

Шаг 3. Вычислить f(с).

Шаг 4. Если |f(с)| < δ, положить ξ » c и остановиться.

Шаг 5. Если f(а)f(с) < 0, положить b = с и вернуться к шагу 1; иначе положить а = с, f(a) = f(c) и вернуться к шагу 1.

За один шаг метода половинного деления промежуток существования корня сокращается ровно вдвое. Поэтому, если за k-e приближение этим методом к корню ξ уравнения (1) примем точку x_k, являющуюся серединой полученного на k-м шаге отрезка [a_k, b_k] в результате последовательного сужения данного отрезка [а, b], полагая a₁ = а, b₁ = b, то придем к неравенству

"k Î N (3)

(априори, ξ — любая точка интервала (a_k, b_k), и расстояние от нее до середины этого интервала не превосходит половины его длины. Это как раз и видим в (3) при k = 1).

Неравенство (3), с одной стороны, позволяет утверждать, что последовательность (x_k) имеет предел — искомый корень ξ уравнения (1); с другой стороны, являясь априорной оценкой абсолютной погрешности приближенного равенства x_k » ξ, дает возможность подсчитать число шагов (итераций) метода половинного деления, достаточное для получения корня ξ с заданной точностью ε, для чего нужно лишь найти наименьшее натуральное k, удовлетворяющее неравенству

Используемый в методе половинного деления способ фиксирования пробной точки можно охарактеризовать как пассивный, ибо он осуществляется по заранее жестко заданному плану и никак не учитывает вычисляемые на каждом шаге значения функции. Логично предположить, что в семействе методов дихотомии можно достичь несколько лучших результатов, если отрезок [а; b] делить точкой c на части не пополам, а пропорционально величинам ординат f(a) и f(b) графика данной функции f(x). Это означает, что точку с есть смысл находить как абсциссу точки пересечения оси Ox с прямой, проходящей через точки A(а; f(a)) и B(b; f(b)), иначе, с хордой АВ дуги ΑξΒ (Рис. 1).

Рис. 1. Дуга графика функции f(x) и стягивающая ее хорда

Запишем уравнение прямой, проходящей через две данные точки A к B:

Отсюда, полагая у = 0 (уравнение оси Ох), x = с (обозначение искомой точки пересечения прямой АВ с осью Ох), находим

(4)

Метод, получающийся в развитие метода дихотомии таким фиксированием пробной точки, называют методом хорд.