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

Эта статья о поиске нулей непрерывных функций. Для поиска конечного отсортированного массива см. Алгоритм двоичного поиска . О методе определения того, какое изменение программного обеспечения вызвало изменение поведения, см. Bisection (программная инженерия) .

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

В математике метод деления пополам — это метод поиска корня , который применяется к любой непрерывной функции , для которой известны два значения с противоположными знаками. Метод заключается в многократном делении пополам интервала , определенного этими значениями, а затем выборе подинтервала, в котором функция меняет знак и, следовательно, должна содержать корень . Это очень простой и надежный метод, но он также относительно медленный. По этой причине его часто используют для получения грубого приближения к решению, которое затем используется в качестве отправной точки для более быстро сходящихся методов. Этот метод еще называют методом деления интервала пополам . метод двоичного поиска , или метод дихотомии .

Для многочленов существуют более сложные методы проверки существования корня в интервале ( правило знаков Декарта , теорема Штурма , теорема Будана ). Они позволяют расширить метод деления пополам до эффективных алгоритмов поиска всех действительных корней многочлена; см . Изоляция реального корня .

Метод

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

На каждом этапе метод делит интервал на две части/половины, вычисляя среднюю точку c = ( a + b )/2 интервала и значение функции f ( c ) в этой точке. Если c сам является корнем, то процесс завершился успешно и остановился. В противном случае теперь есть только две возможности: либо f ( a ) и f ( c ) имеют противоположные знаки и заключают в скобки корень, либо f ( c ) и f ( b ) имеют противоположные знаки и заключают в скобки корень. Метод выбирает подинтервал, который гарантированно будет скобкой, в качестве нового интервала, который будет использоваться на следующем шаге. Таким образом, интервал, содержащий ноль f, уменьшается на 50% на каждом шаге. Процесс продолжается до тех пор, пока интервал не станет достаточно малым.

Явно, если f ( c )=0, то c можно принять за решение, и процесс останавливается. В противном случае, если f ( a ) и f ( c ) имеют противоположные знаки, то метод устанавливает c как новое значение для b , а если f ( b ) и f ( c ) имеют противоположные знаки, то метод устанавливает c как новое значение. а . В обоих случаях новые f ( a ) и f ( b ) имеют противоположные знаки, поэтому метод применим к этому меньшему интервалу.

Итерационные задачи

Входными данными для метода является непрерывная функция f , интервал [ a , b ] и значения функции f ( a ) и f ( b ). Значения функции имеют противоположный знак (в пределах интервала имеется хотя бы одно пересечение нуля). Каждая итерация выполняет следующие шаги:

1. Вычислите c , середину интервала, c = ⁠ а + б / 2 ⁠ .
2. Вычислите значение функции в средней точке f ( c ).
3. Если сходимость удовлетворительная (т. е. c − a достаточно мала или | f ( c ) | достаточно мала), верните c и прекратите итерацию.
4. Проверьте знак f ( c ) и замените либо ( a , f ( a )) или ( b , f ( b )) на ( c , f ( c )) так, чтобы в новом интервале произошло пересечение нуля. Я = бфе

При реализации метода на компьютере могут возникнуть проблемы с конечной точностью, поэтому часто существуют дополнительные тесты на сходимость или ограничения на количество итераций. Хотя f является непрерывным, конечная точность может помешать тому, чтобы значение функции когда-либо было равным нулю. Например, рассмотрим f ( x ) = cos x ; не существует значения с плавающей запятой, аппроксимирующего x = π /2 , которое давало бы ровно ноль. Кроме того, разница между a и b ограничена точностью чисел с плавающей запятой; т. е. по мере уменьшения разницы между a и b в какой-то момент средняя точка [ a , b ] будет численно идентична (в пределах точности с плавающей запятой) либо a, либо b .

Алгоритм

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

input: Function f, 
       endpoint values a, b, 
       tolerance TOL, 
       maximum iterations NMAX
conditions: a < b, 
            either f(a) < 0 and f(b) > 0 or f(a) > 0 and f(b) < 0
output: value which differs from a root of f(x) = 0 by less than TOL
 
N ← 1
while N ≤ NMAX do // limit iterations to prevent infinite loop
    c ← (a + b)/2 // new midpoint
    if f(c) = 0 or (b – a)/2 < TOL then // solution found
        Output(c)
        Stop
    end if
    N ← N + 1 // increment step counter
    if sign(f(c)) = sign(f(a)) then a ← c else b ← c // new interval
end while
Output("Method failed.") // max number of steps exceeded

Пример: поиск корня многочлена

Предположим, что метод деления пополам используется для нахождения корня многочлена

$f(x)=x^{3}-x-2\,.$

Сначала два числа $a$ и $b$ надо найти такое, что $f(a)$ и $f(b)$ имеют противоположные знаки. Для вышеуказанной функции $a=1$ и $b=2$ удовлетворяют этому критерию, так как

$f(1)=(1)^{3}-(1)-2=-2$

и

$f(2)=(2)^{3}-(2)-2=+4\,.$

Поскольку функция непрерывна, в интервале [1, 2] должен быть корень.

В первой итерации конечные точки интервала, заключающего в скобки корень, равны $a_{1}=1$ и $b_{1}=2$, поэтому середина

$c_{1}={\frac {2+1}{2}}=1.5$

Значение функции в средней точке равно $f(c_{1})=(1.5)^{3}-(1.5)-2=-0.125$. Потому что $f(c_{1})$ является отрицательным, $a=1$ заменяется на $a=1.5$ для следующей итерации, чтобы гарантировать, что $f(a)$ и $f(b)$ имеют противоположные знаки. Поскольку это продолжается, интервал между $a$ и $b$ будет становиться все меньше, сходясь к корню функции. Посмотрите, как это происходит, в таблице ниже.

Итерация	$a_{n}$	$b_{n}$	$c_{n}$	$f(c_{n})$
1	1	2	1.5	−0.125
2	1.5	2	1.75	1.6093750
3	1.5	1.75	1.625	0.6660156
4	1.5	1.625	1.5625	0.2521973
5	1.5	1.5625	1.5312500	0.0591125
6	1.5	1.5312500	1.5156250	−0.0340538
7	1.5156250	1.5312500	1.5234375	0.0122504
8	1.5156250	1.5234375	1.5195313	−0.0109712
9	1.5195313	1.5234375	1.5214844	0.0006222
10	1.5195313	1.5214844	1.5205078	−0.0051789
11	1.5205078	1.5214844	1.5209961	−0.0022794
12	1.5209961	1.5214844	1.5212402	−0.0008289
13	1.5212402	1.5214844	1.5213623	−0.0001034
14	1.5213623	1.5214844	1.5214233	0.0002594
15	1.5213623	1.5214233	1.5213928	0.0000780

После 13 итераций становится очевидным, что наблюдается сходимость примерно до 1,521: корня многочлена.

Анализ

Метод гарантированно сходится к корню f, если f — непрерывная функция на интервале [ a , b ] и f ( a ) и f ( b ) имеют противоположные знаки. Абсолютная ошибка уменьшается вдвое на каждом шаге, поэтому метод сходится линейно . В частности, если c ₁ = ⁠ a + b / 2 ⁠ — середина начального интервала, а c _n — середина интервала на n -м шаге, то разность между c _n и решением c ограничена соотношением

$|c_{n}-c|\leq {\frac {|b-a|}{2^{n}}}.$

Эту формулу можно использовать для заранее определения верхней границы числа итераций, необходимых методу деления пополам для сходимости к корню с точностью до определенного допуска. Число n итераций, необходимых для достижения требуемого допуска ε (т. е. ошибки, гарантированно не превышающей ε), ограничено

$n\leq n_{1/2}\equiv \left\lceil \log _{2}\left({\frac {\epsilon _{0}}{\epsilon }}\right)\right\rceil ,$

где начальный размер кронштейна $\epsilon _{0}=|b-a|$ и необходимый размер кронштейна $\epsilon \leq \epsilon _{0}.$ Основная мотивация использования метода деления пополам заключается в том, что на множестве непрерывных функций ни один другой метод не может гарантировать получение оценки c _n для решения c, которое в худшем случае имеет $\epsilon$ абсолютная ошибка с менее чем n _1/2 итерациями. Это также верно при нескольких общих предположениях о функции f и поведении функции в окрестности корня.

Однако, несмотря на то, что метод деления пополам является оптимальным в отношении производительности в худшем случае при критериях абсолютной ошибки, он неоптимален в отношении средней производительности при стандартных предположениях. а также асимптотическая производительность . Популярные альтернативы методу деления пополам, такие как метод секущего , метод Риддерса или метод Брента (среди прочих), обычно работают лучше, поскольку они идут на компромисс с производительностью в худшем случае для достижения более высоких порядков сходимости к корню. И строгое улучшение метода деления пополам может быть достигнуто с более высоким порядком сходимости без ущерба для производительности в худшем случае с помощью метода ITP .

Обобщение на более высокие измерения

Метод деления пополам был обобщен на многомерные функции. Такие методы называются обобщенными методами деления пополам .

Методы, основанные на вычислении степеней

Некоторые из этих методов основаны на вычислении топологической степени .

Метод характеристического деления пополам

Метод характеристического деления пополам использует только знаки функции в разных точках. Пусть f — функция из R ^д в Р ^д , для некоторого целого d ≥ 2. Характеристический многогранник (также называемый допустимым многоугольником ) f R является многогранником в ^д , имея 2 ^д вершины, такие, что в каждой вершине v комбинация знаков f ( v ) единственна. Например, для d = 2 характеристический многогранник f представляет собой четырехугольник с вершинами (скажем) A, B, C, D, такой что:

• ⁠ $\operatorname {sgn} f(A)=(-,-)$⁠ , то есть f ₁ (A)<0, f ₂ (A)<0.
• ⁠ $\operatorname {sgn} f(B)=(-,+)$⁠ , то есть f ₁ (B)<0, f ₂ (B)>0.
• ⁠ $\operatorname {sgn} f(C)=(+,-)$⁠ , то есть f ₁ (C)>0, f ₂ (C)<0.
• ⁠ $\operatorname {sgn} f(D)=(+,+)$⁠ , то есть f ₁ (D)>0, f ₂ (D)>0.

Правильное ребро характеристического многоугольника — это ребро между парой вершин, вектор знаков которого отличается только одним знаком. В приведенном выше примере собственные ребра характеристического четырехугольника — это AB, AC, BD и CD. Диагональю d пара вершин, вектор знаков которой отличается всеми называется знаками. В приведенном выше примере диагонали — AD и BC.

На каждой итерации алгоритм выбирает правильное ребро многогранника (скажем, A-B) и вычисляет знаки f в его средней точке (скажем, M). Дальше все происходит следующим образом:

• Если ⁠ $\operatorname {sgn} f(M)=\operatorname {sgn}(A)$⁠ , то A заменяется на M, и мы получаем характеристический многогранник меньшего размера.
• Если ⁠ $\operatorname {sgn} f(M)=\operatorname {sgn}(B)$⁠ , то B заменяется на M, и мы получаем характеристический многогранник меньшего размера.
• В противном случае мы выбираем новое правильное ребро и пробуем еще раз.

Предположим, что диаметр (= длина самого длинного собственного ребра) исходного характеристического многогранника равен D . Тогда, по крайней мере $\log _{2}(D/\varepsilon )$ необходимо разделить ребра пополам так, чтобы диаметр оставшегося многоугольника был не более ε .

См. также

• Алгоритм двоичного поиска
• Алгоритм Лемера–Шура , обобщение метода деления пополам на комплексной плоскости
• Вложенные интервалы

Ссылки

• Берден, Ричард Л.; Фейрес, Дж. Дуглас (1985), «2.1 Алгоритм деления пополам», Численный анализ (3-е изд.), PWS Publishers, ISBN  0-87150-857-5

Дальнейшее чтение

• Корлисс, Джордж (1977), «Какой корень находит алгоритм деления пополам?», SIAM Review , 19 (2): 325–327, doi : 10.1137/1019044 , ISSN   1095-7200
• Кау, Аутар; Калу, Эгву (2008), Численные методы с приложениями (1-е изд.), заархивировано из оригинала 13 апреля 2009 г.

Внешние ссылки

• Вайсштейн, Эрик В. «Двустороннее сечение» . Математический мир .
• Примечания к методу бисекции , PPT, Mathcad, Maple, Matlab, Mathematica из Института целостных численных методов.