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

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

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

Обоснование

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

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

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

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

<math>\varepsilon_{f(x)}</math> по оси <math>y</math>, что ближе к условию <math>f(x)=0</math> из описания алгоритма; или
<math>\varepsilon_x</math>, по оси <math>x</math>, что может оказаться удобным в некоторых случаях.

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

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

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

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

<math>f(x)=0. \qquad ( 1 )</math>

Для начала итераций необходимо знать отрезок <math>[x_L,x_R]</math> значений <math>x</math>, на концах которого функция принимает значения противоположных знаков.

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

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

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

<math>sign(f(x_L)) \ne sign(f(x_R)), \qquad ( 2.2 )</math>

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

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

Найдём значение <math>x</math> в середине отрезка:

<math>x_M=(x_L+x_R)/2, \qquad ( 3 )</math>

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

а в цикле вычисляют длину очередных новых отрезков по формуле: <math>x_D=x_D/2</math> и новую середину по формуле:

Вычислим значение функции <math>f(x_M)</math> в середине отрезка <math>x_M</math>:

Если <math>f(x_M)=0</math> или, в действительных вычислениях, <math>|f(x_M)|\leq\varepsilon_{f(x)}</math>, где <math>\varepsilon_{f(x)}</math> — заданная точность по оси <math>y</math>, то корень найден.
Иначе <math>f(x_M)\ne 0</math> или, в действительных вычислениях, <math>|f(x_M)|>\varepsilon_{f(x)}</math>, то разобьём отрезок <math>[x_L,x_R]</math> на два равных отрезка: <math>[x_L,x_M]</math> и <math>[x_M,x_R]</math>.

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

Если значения функции на концах отрезка имеют противоположные знаки на левом отрезке, <math>f(x_L)\cdot f(x_M)<0</math> или <math>sign(f(x_L)) \ne sign(f(x_M))</math>, то, соответственно, корень находится внутри левого отрезка <math>[x_L,x_M]</math>. Тогда возьмём левый отрезок присвоением <math>x_R=x_M</math>, и повторим описанную процедуру до достижения требуемой точности <math>\varepsilon_{f(x)}</math> по оси <math>y</math>.
Иначе значения функции на концах отрезка имеют противоположные знаки на правом отрезке, <math>f(x_M)\cdot f(x_R)<0</math> или <math>sign(f(x_M)) \ne sign(f(x_R))</math>, то, соответственно, корень находится внутри правого отрезка <math>[x_M,x_R]</math>. Тогда возьмём правый отрезок присвоением <math>x_L=x_M</math>, и повторим описанную процедуру до достижения требуемой точности <math>\varepsilon_{f(x)}</math> по оси <math>y</math>.

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

Существует похожий метод, но с критерием останова вычислений <math>\varepsilon_x</math> по оси <math>x</math><ref>Ю. Губарь, Курс "Введение в математическое моделирование" Лекция 4: Численные методы решения нелинейных уравнений: Метод половинного деления // Интуит.ру, 15.03.2007</ref>, в этом методе вычисления продолжаются до тех пор, пока, после очередного деления пополам, новый отрезок больше заданной точности по оси <math>x</math>: <math>(x_R-x_L)>\varepsilon_x</math>. В этом методе отрезок на оси <math>x</math> может достичь заданной величины <math>\varepsilon_x</math>, а значения функций <math>f(x)</math> (особенно крутых) на оси <math>y</math> могут очень далеко отстоять от нуля, при пологих же функциях <math>f(x)</math> этот метод приводит к большому числу лишних вычислений.

В дискретных функциях <math>x_L, x_M</math> и <math>x_R</math> — это номера элементов массива, которые не могут быть дробными, и, в случае второго критерия останова вычислений, разность <math>(x_R-x_L)</math> не может быть меньше <math>\varepsilon_x=1</math>.

Псевдокод

;Пусть

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).
Конец.

На языке программирования Python алгоритм будет выглядеть следующим образом:

# Метод биссекции
def F(dx):
    return dx**2 - 6*dx + 8
xn = 0
xk = 10
epsy = 0.01
print (xn, xk, epsy)
if F(xn) == 0:
    print (f"xn")
    exit()
if F(xk) == 0:
    print (f"xk")
    exit()
while xk - xn > epsy:
    dx = (xk - xn)/2;
    xi = xn + dx;
    if (F(xn)<0 and F(xi)>0)or (F(xn)>0 and F(xi)<0):
        xk = xi
    else:
        xn = xi
    print (f"Найден корень уравнения — xi: {xi}")
    print (f"Найден c точностью по y — epsy: {F(xi)}")

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

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

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

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

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

Псевдокод: <source lang="C"> леваяГраница = левГран праваяГраница = правГран while (праваяГраница - леваяГраница > 1) {

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

} printf середина </source>

См. также

Примечания

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

Литература

Ссылки

Шаблон:Родственный проект{{#if:||{{#if:Программные реализации метода бисекции||}}}}

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