2.3 Метод деления отрезка пополам (метод дихотомии, метод бисекции)

Метод деления отрезка пополам является самым простым и надежным способом решения нелинейного уравнения.

Пусть из предварительного анализа известно, что корень уравнения (2.1) находится на отрезке [a₀, b₀], т. е. x^*[a₀, b₀], так, что f(x^*) = 0.

Пусть функция f(x) непрерывна на отрезке [a₀, b₀] и принимает на концах отрезка значения разных знаков, т.е.

f(a₀)f(b₀) < 0. (2.2)

Разделим отрезок [a₀, b₀] пополам. Получим точку x₀ = . Вычислим значение функции в этой точке: f(x₀). Если f(x₀) = 0, то x₀ - искомый корень, и задача решена. Если f(x₀)0, то f(x₀) - число определенного знака: f(x₀) > 0, либо f(x₀) < 0. Тогда либо на концах отрезка [a₀, x₀], либо на концах отрезка [x₀, b₀] значения функции f(x) имеют разные знаки. Обозначим такой отрезок [a₁, b₁]. Очевидно, что x^*[a₁, b₁], и длина отрезка [a₁, b₁] в два раза меньше, чем длина отрезка [a₀, b₀]. Поступим аналогично с отрезком [a₁, b₁]. В результате получим либо корень x^*, либо новый отрезок [a₂, b₂], и т.д. (рис. 2.2).

Рис. 2.2

Середина n-го отрезка x_n = . Очевидно, что длина отрезка [a_n, b_n] будет равна , а т. к. x^*[a_n, b_n], то

| x_n - x^*| . (2.3)

Погрешность метода. Оценка (2.3) характеризует погрешность метода деления отрезка пополам и указывает на скорость сходимости: метод сходится со скоростью геометрической прогрессии, знаменатель которой q = 1/2. Заметим, что оценка (2.3) является априорной.

Критерий окончания. Из соотношения (2.3) следует, что при заданной точности приближения вычисления заканчиваются, когда будет выполнено неравенство b_n - a_n < 2 или неравенство n > log₂((b₀ - a₀)/) - 1. Таким образом, количество итераций можно определить заранее. За приближенное значение корня берется величина x_n.

Пример 2.1.

Найдем приближенно x = с точностью ??= 0.01. Эта задача эквивалентна решению уравнения x⁵ - 2 = 0, или нахождению нуля функции f(x) = x⁵ - 2. В качестве начального отрезка [a₀, b₀] возьмем отрезок [1, 2]. На концах этого отрезка функция принимает значения с разными знаками: f(1) < 0, f(2) > 0.

Найдем число n делений отрезка [1, 2], необходимых для достижения требуемой точности. Имеем:

| x_n - x^*| = 10^-2,

n6.

Следовательно, не позднее 6-го деления найдем с требуемой точностью, 1.1484. Результаты вычислений представлены в таблице 2.1.

Таблица 2.1