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

Не следует путать с Двоичный поиск.

Не следует путать с Дихотомия.

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

Несколько шагов метода деления пополам применяются к начальному диапазону [a₁;b₁]. Большая красная точка — это корень функции.

ОбоснованиеПравить

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

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

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

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

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

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

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

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

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

$f(x)=0.(1)$$f(x)=0.\qquad (1)$ 

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

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

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

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

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

$sign(f(x_L))\ne <!--\; \ne \; -->sign(f(x_R)),(2.2)$$sign(f(x_{L}))\neq sign(f(x_{R})),\qquad (2.2)$ 

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

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

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

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

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

$x_D=(x_R-<!--\; -\; -->x_L),$$x_{D}=(x_{R}-x_{L}),$ 

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

$x_M=x_L+x_D.$$x_{M}=x_{L}+x_{D}.$ 

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

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

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

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

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

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

В дискретных функциях $x_L,x_M$$x_{L},x_{M}$  и $x_R$$x_{R}$  — это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия останова вычислений, разность $(x_R-<!--\; -\; -->x_L)$$(x_{R}-x_{L})$  не может быть меньше ${\mathrm{\epsilon <!--\; \epsilon \; -->}}_x=1$$\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
• Использование метода бисекции в программировании свободно распространяемая программа для вычисления изоэлектрической точки.