(И10) Решение уравнений. Метод деления отрезка пополам.

Метод бисекции или метод деления отрезка пополам — простейший численный метод для решения нелинейных уравнений вида f(x)=0. Предполагается только непрерывность функции f(x). Поиск основывается на теореме о промежуточных значениях.

Обоснование

Алгоритм основан на следующем следствии из теоремы Больцано — Коши:

Пусть непрерывная функция , тогда, если , то .

Таким образом, если мы ищем ноль, то на концах отрезка функция должна быть противоположных знаков. Разделим отрезок пополам и возьмём ту из половинок, на концах которой функция по-прежнему принимает значения противоположных знаков. Если значение функции в серединной точке оказалось искомым нулём, то процесс завершается.

Точность вычислений задаётся одним из двух способов:

1.  по оси , что ближе к условию  из описания алгоритма; или
2. , по оси , что может оказаться удобным в некоторых случаях.

Процедуру следует продолжать до достижения заданной точности.

Для поиска произвольного значения достаточно вычесть из значения функции искомое значение и искать ноль получившейся функции.

Описание алгоритма

Задача заключается в нахождении корней нелинейного уравнения

Для начала итераций необходимо знать отрезок  значений , на концах которого функция принимает значения противоположных знаков.

Противоположность знаков значений функции на концах отрезка можно определить множеством способов. Один из множества этих способов — умножение значений функции на концах отрезка и определение знака произведения путём сравнения результата умножения с нулём:

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

Для устранения переполнения и уменьшения затрат времени, то есть для увеличения быстродействия, на некоторых программно-компьютерных комплексах противоположность знаков значений функции на концах отрезка нужно определять по формуле:

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

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

Найдём значение  в середине отрезка:

в действительных вычислениях, для уменьшения числа операций, в начале, вне цикла, вычисляют длину отрезка по формуле:

а в цикле вычисляют длину очередных новых отрезков по формуле:  и новую середину по формуле:

Вычислим значение функции  в середине отрезка :

• Если  или, в действительных вычислениях, , где  — заданная точность по оси , то корень найден.
• Иначе  или, в действительных вычислениях, , то разобьём отрезок  на два равных отрезка:  и .

Теперь найдём новый отрезок, на котором функция меняет знак:

• Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке,  или , то, соответственно, корень находится внутри левого отрезка . Тогда возьмём левый отрезок присвоением , и повторим описанную процедуру до достижения требуемой точности  по оси .
• Иначе значения функции на концах отрезка имеют противоположные знаки на правом отрезке,  или , то, соответственно, корень находится внутри правого отрезка . Тогда возьмём правый отрезок присвоением , и повторим описанную процедуру до достижения требуемой точности  по оси .

За количество итераций  деление пополам осуществляется  раз, поэтому длина конечного отрезка в  раз меньше длины исходного отрезка.

Существует похожий метод, но с критерием останова вычислений  по оси ^[1], в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси : . В этом методе отрезок на оси  может достичь заданной величины , а значения функций  (особенно крутых) на оси  могут очень далеко отстоять от нуля, при пологих же функциях  этот метод приводит к большому числу лишних вычислений.

В дискретных функциях  и  — это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия останова вычислений, разность  не может быть меньше .

Псевдокод

Пусть

• x_n — начало отрезка по х;
• x_k — конец отрезка по х;
• x_i — середина отрезка по х;
• eps_y — требуемая точность вычислений по y (заданное приближение |F(x_i)| к нулю).

Тогда алгоритм метода бисекции можно записать в псевдокоде следующим образом:

1. Начало.
2. Ввод x_n, x_k, eps_y.
3. Если F(x_n) = 0, то Вывод (корень уравнения — x_n).
4. Если F(x_k) = 0, то Вывод (корень уравнения — x_k).
5. dx := x_k — x_n.
6. Пока |F(x_i)| > eps_y повторять:
7. dx := dx / 2;
8. x_i := x_n + dx;
9. если sign(F(x_n)) ≠ sign(F(x_i)), то x_k := x_i;
10. иначе x_n := x_i.
11. конец повторять
12. Вывод (Найден корень уравнения — x_i с точностью по y — eps_y).
13. Конец.