Метод половинного деления (бисекции, дихотомии)

Пусть корни уравнения (2.1) локализованы и на некотором отрезке имеется корень, который необходимо уточнить с погрешностью . В качестве его начального приближения примем середину отрезка : (рис. 2.5).

Рис. 2.5. Метод половинного деления.

Исследуем значения функции на концах отрезков и . Тот из отрезков, на концах которого принимает значения разных знаков, содержит искомый корень, поэтому его принимаем в качестве нового отрезка (на рис. 2.5 это отрезок ). Вторую половину отрезка , на которой не меняет знак, отбрасываем (на рис. 2.5 исключен из рассмотрения отрезок ). В качестве первого приближения корня принимаем середину нового отрезка и повторяем действия, представленные выше для отрезка . Выбирая на каждой итерации тот отрезок, на котором функция меняет знак, и продолжая процесс половинного деления, можно получить сколь угодно малый (ограниченный возможностями ЭВМ) отрезок, содержащий корень уравнения.

В результате получим следующую последовательность вложенных отрезков: . Таким образом, очередное приближение с номером при условии вычисляется по формуле

.

После каждой итерации отрезок , на котором расположен корень, уменьшается вдвое, следовательно, после итераций он сократится в раз:

, (2.2)

откуда . Последовательности и монотонны и ограничены, поэтому существуют пределы и предел разности равен разности пределов . Поэтому , где – корень уравнения.

Действительно, так как , то в силу непрерывности получим , .

Итерационный процесс следует прекратить, когда будет достигнута заданная точность, то есть при выполнении условия

. (2.3)

Поскольку корень принадлежит отрезку , а – середина этого отрезка, то величина всегда будет меньше половины длины отрезка (рис. 2.5), то есть

.

Следовательно, условие (2.3) будет выполнено, если

. (2.4)

Таким образом, итерационный процесс следует продолжать до тех пор, пока не будет выполнено условие (2.4). В отличие от большинства других методов уточнения корней, метод половинного деления сходится всегда, то есть обладает безусловной сходимостью. Кроме этого он чрезвычайно прост, поскольку требует вычисления лишь значений функции , и поэтому применим для решения любых уравнений. Однако метод половинного деления довольно медленный, с каждым шагом погрешность приближенного значения корня уменьшается вдвое,

,

поэтому данный метод обладает линейной сходимостью.

Вычислим количество итераций , необходимое для достижения заданной точности вычисления значения корня. Пользуясь выражением (2.2) можно выяснить, для каких значений будет выполнено условие (2.4), и принять за наименьшее из них:

, ,

где – целая часть числа (при и получим ).

Замечание. При реализации метода половинного деления следует учитывать, что функция вычисляется с некоторой абсолютной погрешностью . Вблизи корня значения функции малы по абсолютной величине и могут оказаться сравнимы с погрешностью ее вычисления. Другими словами, при непосредственном приближении к корню метод может попасть в так называемую полосу шумов и дальнейшее уточнение корня окажется невозможным. Поэтому целесообразно задать ширину полосы шумов и прекратить итерационный процесс при попадании в нее. Если принять , то итерационный процесс можно завершать, когда значение функции после итерации станет по абсолютному значению меньшим, чем , то есть

. (2.5)

Соотношения (2.4) и (2.5) могут рассматриваться как условия прекращения итерационного процесса. Также необходимо иметь ввиду, что при уменьшении отрезка увеличиваются погрешности вычисления его длины за счет вычитания близких чисел.

Зададимся вопросом, почему среди всех возможных вариантов деления отрезка локализации корня выбран вариант половинного деления? Обоснованием целесообразности его использования может быть доказательство максимальной эффективности данного варианта в вычислительном плане. Пусть задан некоторый отрезок локализации корня, обозначим через точку деления данного отрезка, а через – длину того из отрезков и , на котором локализован корень. Исходя из постановки задачи, значение требуется минимизировать, при этом следует полагать, что . Минимальное значение может быть достигнуто в том случае, если , откуда . На рис. 2.6. приведен пример геометрической интерпретации обоснования наибольшей эффективности половинного деления отрезка локализации корня. Заметим, что аналогичное утверждение можно получить исходя из геометрического определняия вероятности. Если рассматривать отрезок как интервал неопределенности, положение корня уравнения на котором не известно, то выбирая способ его половинного деления, мы обеспечиваем равновероятность случаев положения корня на каждом из получаемых отрезков.

Рис. 2.6. Обоснование оптимальности половинного деления отрезка локализации корня.