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

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

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

Метод

Метод применим для численного решения уравнения 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 ) имеют противоположные знаки и заключают в скобки корень. ^[5] Метод выбирает подинтервал, который гарантированно будет скобкой, в качестве нового интервала, который будет использоваться на следующем шаге. Таким образом, интервал, содержащий ноль f, уменьшается на 50% на каждом шаге. Процесс продолжается до тех пор, пока интервал не станет достаточно малым.

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

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

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

Вычислите c , середину интервала, c = ⁠ а + б / 2 ⁠ .
Вычислите значение функции в средней точке f ( c ).
Если сходимость удовлетворительная (т. е. c − a достаточно мала или | f ( c ) | достаточно мала), верните c и прекратите итерацию.
Проверьте знак 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 .

Алгоритм

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

ввод:  Функция  f  ,        значения конечных точек  a  ,  b  ,        толерантность  ТОЛ  ,        максимальное количество итераций  Условия NMAX  :   a  <  b  ,             либо  f  (  a  ) <0 и  f  (  b  ) > 0, либо  f  (  a  ) > 0 и  f  (  b  ) <0 вывод:  значение, которое отличается от корня  f  (  x  ) = 0 менее чем на  TOL   N  ← 1 while   N  ≤  NMAX   do   // ограничиваем итерации, чтобы предотвратить бесконечный цикл      c  ← (  a  +  b  )/2  // новая средняя точка      , если   f  (  c  ) = 0 или (  b  –  a  )/2 <  TOL   , тогда   // решение найдено         Выход(  с  )         Остановить      конец, если      N  ←  N  + 1  // увеличить счетчик шагов      , если  знак (  f  (  c  )) = знак (  f  (  a  ))  then   a  ←  c   else   b  ←  c   нового интервала  // конец  whileOutput("Метод не выполнен.")  // превышено максимальное количество шагов

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

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

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 ограничена соотношением ^[8]

|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 итерациями. ^[9] Это также верно при нескольких общих предположениях о функции f и поведении функции в окрестности корня. ^[9]^[10]

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

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

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

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

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

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

Метод характеристического деления пополам использует только знаки функции в разных точках. Пусть f — функция из R ^д в Р ^д, для некоторого целого d ≥ 2. Характеристический многогранник ^[18] (также называемый допустимым многоугольником ) ^[19] 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 )$ необходимо разделить ребра пополам, чтобы диаметр оставшегося многоугольника был не более $ε$ . ^[19]^{: 11, Лемма.4.7.}

См. также

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

Ссылки

^ Burden & Faires 1985 , с. 31
^ «Интервальное сокращение пополам (бисекция)» . Архивировано из оригинала 19 мая 2013 г. Проверено 7 ноября 2013 г.
^ Burden & Faires 1985 , с. 28
^ «Метод дихотомии — Математическая энциклопедия» . www.энциклопедияofmath.org . Проверено 21 декабря 2015 г.
^ Если функция имеет одинаковый знак в конечных точках интервала, конечные точки могут или не могут заключать в скобки корни функции.
^ Burden & Faires 1985 , с. 28 для раздела
^ Burden & Faires 1985 , с. 29. Эта версия пересчитывает значения функции на каждой итерации, а не переносит их на следующие итерации.
^ Burden & Faires 1985 , с. 31, теорема 2.1
^ Перейти обратно: ^а ^б Сикорский, К. (1 февраля 1982 г.). «Биссекция оптимальна» . Численная математика . 40 (1): 111–117. дои : 10.1007/BF01459080 . ISSN 0945-3245 . S2CID 119952605 .
^ Сикорский, К. (1 декабря 1985 г.). «Оптимальное решение нелинейных уравнений». Журнал сложности . 1 (2): 197–209. дои : 10.1016/0885-064X(85)90011-1 . ISSN 0885-064X .
^ Граф, Зигфрид; Новак, Эрик; Папагеоргиу, Анаргирос (1 июля 1989 г.). «В среднем бисекция не оптимальна» . Численная математика . 55 (4): 481–491. дои : 10.1007/BF01396051 . ISSN 0945-3245 . S2CID 119546369 .
^ Новак, Эрих (1 декабря 1989 г.). «Результаты среднего случая для нулевого результата» . Журнал сложности . 5 (4): 489–501. дои : 10.1016/0885-064X(89)90022-8 . ISSN 0885-064X .
^ Перейти обратно: ^а ^б Оливейра, IFD; Такахаши, RHC (06 декабря 2020 г.). «Улучшение средней производительности метода бисекции с сохранением минмаксной оптимальности» . Транзакции ACM в математическом программном обеспечении . 47 (1): 5:1–5:24. дои : 10.1145/3423597 . ISSN 0098-3500 . S2CID 230586635 .
^ Иво, Оливейра (14 декабря 2020 г.). «Улучшенный метод деления пополам» . дои : 10.1145/3423597 . S2CID 230586635 .
^ Моррен, Б.; Врахатис, Миннесота; Якубсон, JC (1 июня 2002 г.). «О сложности выделения действительных корней и достоверного вычисления топологической степени» . Журнал сложности . 18 (2): 612–640. дои : 10.1006/jcom.2001.0636 . ISSN 0885-064X .
^ Врахатис, Майкл Н. (2020). «Обобщения теоремы о промежуточном значении для аппроксимации неподвижных точек и нулей непрерывных функций» . У Сергеева Ярослав Д.; Квасов, Дмитрий Евгеньевич (ред.). Численные вычисления: теория и алгоритмы . Конспекты лекций по информатике. Том. 11974. Чам: Springer International Publishing. стр. 223–238. дои : 10.1007/978-3-030-40616-5_17 . ISBN 978-3-030-40616-5 . S2CID 211160947 .
^ Кирфотт, Бейкер (1 июня 1979 г.). «Эффективный метод вычисления степени для обобщенного метода деления пополам» . Нумерическая математика . 32 (2): 109–127. дои : 10.1007/BF01404868 . ISSN 0945-3245 . S2CID 122058552 .
^ Врахатис, Майкл Н. (1 июня 1995 г.). «Эффективный метод поиска и вычисления периодических орбит нелинейных отображений» . Журнал вычислительной физики . 119 (1): 105–119. Бибкод : 1995JCoPh.119..105V . дои : 10.1006/jcph.1995.1119 . ISSN 0021-9991 .
^ Перейти обратно: ^а ^б Врахатис, Миннесота; Иорданидис, К.И. (1 марта 1986 г.). «Быстрый обобщенный метод деления пополам для решения систем нелинейных уравнений» . Нумерическая математика . 49 (2): 123–138. дои : 10.1007/BF01389620 . ISSN 0945-3245 . S2CID 121771945 .

Берден, Ричард Л.; Фейрес, Дж. Дуглас (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 из Института целостных численных методов.

[1] Burden & Faires 1985 , с. 31

[2] «Интервальное сокращение пополам (бисекция)» . Архивировано из оригинала 19 мая 2013 г. Проверено 7 ноября 2013 г.

[3] Burden & Faires 1985 , с. 28

[4] «Метод дихотомии — Математическая энциклопедия» . www.энциклопедияofmath.org . Проверено 21 декабря 2015 г.

[5] Если функция имеет одинаковый знак в конечных точках интервала, конечные точки могут или не могут заключать в скобки корни функции.

[6] Burden & Faires 1985 , с. 28 для раздела

[7] Burden & Faires 1985 , с. 29. Эта версия пересчитывает значения функции на каждой итерации, а не переносит их на следующие итерации.

[8] Burden & Faires 1985 , с. 31, теорема 2.1

[:0-9] Перейти обратно: ^а ^б Сикорский, К. (1 февраля 1982 г.). «Биссекция оптимальна» . Численная математика . 40 (1): 111–117. дои : 10.1007/BF01459080 . ISSN 0945-3245 . S2CID 119952605 .

[10] Сикорский, К. (1 декабря 1985 г.). «Оптимальное решение нелинейных уравнений». Журнал сложности . 1 (2): 197–209. дои : 10.1016/0885-064X(85)90011-1 . ISSN 0885-064X .

[11] Граф, Зигфрид; Новак, Эрик; Папагеоргиу, Анаргирос (1 июля 1989 г.). «В среднем бисекция не оптимальна» . Численная математика . 55 (4): 481–491. дои : 10.1007/BF01396051 . ISSN 0945-3245 . S2CID 119546369 .

[12] Новак, Эрих (1 декабря 1989 г.). «Результаты среднего случая для нулевого результата» . Журнал сложности . 5 (4): 489–501. дои : 10.1016/0885-064X(89)90022-8 . ISSN 0885-064X .

[:1-13] Перейти обратно: ^а ^б Оливейра, IFD; Такахаши, RHC (06 декабря 2020 г.). «Улучшение средней производительности метода бисекции с сохранением минмаксной оптимальности» . Транзакции ACM в математическом программном обеспечении . 47 (1): 5:1–5:24. дои : 10.1145/3423597 . ISSN 0098-3500 . S2CID 230586635 .

[14] Иво, Оливейра (14 декабря 2020 г.). «Улучшенный метод деления пополам» . дои : 10.1145/3423597 . S2CID 230586635 .

[15] Моррен, Б.; Врахатис, Миннесота; Якубсон, JC (1 июня 2002 г.). «О сложности выделения действительных корней и достоверного вычисления топологической степени» . Журнал сложности . 18 (2): 612–640. дои : 10.1006/jcom.2001.0636 . ISSN 0885-064X .

[16] Врахатис, Майкл Н. (2020). «Обобщения теоремы о промежуточном значении для аппроксимации неподвижных точек и нулей непрерывных функций» . У Сергеева Ярослав Д.; Квасов, Дмитрий Евгеньевич (ред.). Численные вычисления: теория и алгоритмы . Конспекты лекций по информатике. Том. 11974. Чам: Springer International Publishing. стр. 223–238. дои : 10.1007/978-3-030-40616-5_17 . ISBN 978-3-030-40616-5 . S2CID 211160947 .

[17] Кирфотт, Бейкер (1 июня 1979 г.). «Эффективный метод вычисления степени для обобщенного метода деления пополам» . Нумерическая математика . 32 (2): 109–127. дои : 10.1007/BF01404868 . ISSN 0945-3245 . S2CID 122058552 .

[18] Врахатис, Майкл Н. (1 июня 1995 г.). «Эффективный метод поиска и вычисления периодических орбит нелинейных отображений» . Журнал вычислительной физики . 119 (1): 105–119. Бибкод : 1995JCoPh.119..105V . дои : 10.1006/jcph.1995.1119 . ISSN 0021-9991 .

[:2-19] Перейти обратно: ^а ^б Врахатис, Миннесота; Иорданидис, К.И. (1 марта 1986 г.). «Быстрый обобщенный метод деления пополам для решения систем нелинейных уравнений» . Нумерическая математика . 49 (2): 123–138. дои : 10.1007/BF01389620 . ISSN 0945-3245 . S2CID 121771945 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

v т и Алгоритмы поиска корня
Брекетинг (без производной)	Метод бисекции Подделки правил метод ИТП
Домохозяин	метод Ньютона метод Галлея
Квазиньютон	метод Бройдена Метод секущего метод Стеффенсена
Гибридные методы	метод Брента Метод рыцарей
Полиномиальные методы	Жертва не удалась Метод Бэрстоу Метод Дюрана – Кернера метод Греффе Алгоритм Дженкинса – Трауба Алгоритм Лемера – Шура метод Лагерра Метод расщепления круга
Другие методы	Итерация с фиксированной точкой Обратная квадратичная интерполяция метод Мюллера Обобщенный метод секущих Сиди