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

Обоснование

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

Пусть непрерывная функция ${\displaystyle f(x)\in \mathrm {C} ([a,\;b])}$ , тогда, если ${\displaystyle sign(f(a))\neq sign(f(b))}$ , то ${\displaystyle \exists c\in [a,\;b]:\;f(c)=0}$ .

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

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

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}$ , в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси ${\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", (3rd ed.), PWS Publishers, ISBN 0-87150-857-5

Ссылки

	Имеется викиучебник по теме « »

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