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

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

Обоснование

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

Шаблон:Теорема

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

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

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

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

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

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

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

f (x) = 0 . (1)

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

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

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

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

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

s i g n (f (x_{L})) \neq s i g n (f (x_{R})), (2.2)

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

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

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

x_{M} = (x_{L} + x_{R}) / 2, (3)

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

x_{D} = (x_{R} - x_{L}),

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

x_{M} = x_{L} + x_{D} .

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

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

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

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

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

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

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

Псевдокод

;Пусть

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

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

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

Поиск значения корня монотонной дискретной функции

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

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

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

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

Псевдокод:

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Викиучебник

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

↑ Ю. Губарь, Курс "Введение в математическое моделирование" Лекция 4: Численные методы решения нелинейных уравнений: Метод половинного деления // Интуит.ру, 15.03.2007

[1] Ю. Губарь, Курс "Введение в математическое моделирование" Лекция 4: Численные методы решения нелинейных уравнений: Метод половинного деления // Интуит.ру, 15.03.2007

[1]