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

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

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

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

1. ${\displaystyle \varepsilon _{f(x)}}$ по оси ${\displaystyle y}$, что ближе к условию ${\displaystyle f(x)=0}$ из описания алгоритма; или
2. ${\displaystyle \varepsilon _{x}}$, по оси ${\displaystyle x}$, что может оказаться удобным в некоторых случаях.

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

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

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

${\displaystyle f(x)=0.\qquad (1)}$

Для начала итераций необходимо знать отрезок ${\displaystyle [x_{L},x_{R}]}$ значений ${\displaystyle x}$, на концах которого функция принимает значения противоположных знаков.

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

${\displaystyle f(x_{L})\cdot f(x_{R})<0,\qquad (2.1)}$

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

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

${\displaystyle sign(f(x_{L}))\neq sign(f(x_{R})),\qquad (2.2)}$

так как одна операция сравнения двух знаков двух чисел требует меньшего времени, чем две операции: умножение двух чисел (особенно с плавающей запятой и двойной длины) и сравнение результата с нулём. При данном сравнении, значения функции ${\displaystyle f(x)}$ в точках ${\displaystyle x_{L}}$ и ${\displaystyle x_{R}}$ можно не вычислять, достаточно вычислить только знаки функции ${\displaystyle f(x)}$ в этих точках, что требует меньшего машинного времени.

Из непрерывности функции ${\displaystyle f(x)}$ и условия (2.2) следует, что на отрезке ${\displaystyle [x_{L},x_{R}]}$ существует хотя бы один корень уравнения (в случае не монотонной функции ${\displaystyle f(x)}$ функция имеет несколько корней и метод приводит к нахождению одного из них).

Найдём значение ${\displaystyle x}$ в середине отрезка:

${\displaystyle x_{M}=(x_{L}+x_{R})/2,\qquad (3)}$

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

${\displaystyle x_{D}=(x_{R}-x_{L}),}$

а в цикле вычисляют длину очередных новых отрезков по формуле: ${\displaystyle x_{D}=x_{D}/2}$ и новую середину по формуле:

${\displaystyle x_{M}=x_{L}+x_{D}.}$

Вычислим значение функции ${\displaystyle f(x_{M})}$ в середине отрезка ${\displaystyle x_{M}}$:

• Если ${\displaystyle f(x_{M})=0}$ или, в действительных вычислениях, ${\displaystyle |f(x_{M})|\leq \varepsilon _{f(x)}}$, где ${\displaystyle \varepsilon _{f(x)}}$ — заданная точность по оси ${\displaystyle y}$, то корень найден.
• Иначе ${\displaystyle f(x_{M})\neq 0}$ или, в действительных вычислениях, ${\displaystyle |f(x_{M})|>\varepsilon _{f(x)}}$, то разобьём отрезок ${\displaystyle [x_{L},x_{R}]}$ на два равных отрезка: ${\displaystyle [x_{L},x_{M}]}$ и ${\displaystyle [x_{M},x_{R}]}$.

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

• Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке, ${\displaystyle f(x_{L})\cdot f(x_{M})<0}$ или ${\displaystyle sign(f(x_{L}))\neq sign(f(x_{M}))}$, то, соответственно, корень находится внутри левого отрезка ${\displaystyle [x_{L},x_{M}]}$. Тогда возьмём левый отрезок присвоением ${\displaystyle x_{R}=x_{M}}$, и повторим описанную процедуру до достижения требуемой точности ${\displaystyle \varepsilon _{f(x)}}$ по оси ${\displaystyle y}$.
• Иначе значения функции на концах отрезка имеют противоположные знаки на правом отрезке, ${\displaystyle f(x_{M})\cdot f(x_{R})<0}$ или ${\displaystyle sign(f(x_{M}))\neq sign(f(x_{R}))}$, то, соответственно, корень находится внутри правого отрезка ${\displaystyle [x_{M},x_{R}]}$. Тогда возьмём правый отрезок присвоением ${\displaystyle x_{L}=x_{M}}$, и повторим описанную процедуру до достижения требуемой точности ${\displaystyle \varepsilon _{f(x)}}$ по оси ${\displaystyle y}$.

За количество итераций ${\displaystyle N}$ деление пополам осуществляется ${\displaystyle N}$ раз, поэтому длина конечного отрезка в ${\displaystyle 2^{N}}$ раз меньше длины исходного отрезка.

Существует похожий метод, но с критерием останова вычислений ${\displaystyle \varepsilon _{x}}$ по оси ${\displaystyle x}$[1], в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси ${\displaystyle x}$: ${\displaystyle (x_{R}-x_{L})>\varepsilon _{x}}$. В этом методе отрезок на оси ${\displaystyle x}$ может достичь заданной величины ${\displaystyle \varepsilon _{x}}$, а значения функций ${\displaystyle f(x)}$ (особенно крутых) на оси ${\displaystyle y}$ могут очень далеко отстоять от нуля, при пологих же функциях ${\displaystyle f(x)}$ этот метод приводит к большому числу лишних вычислений.

В дискретных функциях ${\displaystyle x_{L},x_{M}}$ и ${\displaystyle x_{R}}$ — это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия останова вычислений, разность ${\displaystyle (x_{R}-x_{L})}$ не может быть меньше ${\displaystyle \varepsilon _{x}=1}$.

;Пусть

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

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

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

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

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

Если знаки значений массива массив[леваяГраница] и массив[середина] противоположны, то приближение к корню ищут в левой половине массива, то есть значением праваяГраница становится середина и на следующей итерации исследуется только левая половина массива. Если знаки значений массив[леваяГраница] и массив[середина] одинаковы, то осуществляется переход к поиску приближения к корню в правой половине массива, то есть значением переменной леваяГраница становится середина и на следующей итерации исследуется только правая половина массива. Т.о., в результате каждой проверки область поиска сужается вдвое.

Например, если длина массива равна 1023, то после первого сравнения область сужается до 511 элементов, а после второго — до 255. Т.о. для поиска приближения к корню в массиве из 1023 элементов достаточно 10 проходов (итераций).

Псевдокод:

леваяГраница = левГран
праваяГраница = правГран
while (праваяГраница - леваяГраница > 1) {
   длинаОтрезка = правГран - левГран
   половинаОтрезка = int(длинаОтрезка / 2) 
   середина = леваяГраница + половинаОтрезка
   if (sign(массив[леваяГраница]) ≠ sign(массив[середина]))
      праваяГраница = середина
   else
      леваяГраница = середина
}
printf середина

• Линейный поиск
• Двоичный поиск
• Метод дихотомии
• Метод золотого сечения
• Троичный поиск
• Метод Ньютона

• Волков Е. А. Глава 4. Методы решения нелинейных уравнений и систем. § 26. Метод деления отрезка пополам // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр.. — М.: Наука, 1987. — С. 190. — 248 с.
• Burden, Richard L. & Faires, J. Douglas (1985), 2.1 The Bisection Algorithm, Numerical Analysis (3rd ed.), PWS Publishers, ISBN 0-87150-857-5, <https://archive.org/details/numericalanalys00burd>

• Метод бисекции на сервере применения Mathcad.
• Метод бисекции Mathcad, Maple, Matlab, Mathematica
• Использование метода бисекции в программировании свободно распространяемая программа для вычисления изоэлектрической точки.