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

Алгоритм нахождения нуля функции

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

В математике метод деления пополам — это метод поиска корня , который применяется к любой непрерывной функции , для которой известны два значения с противоположными знаками. Метод заключается в многократном делении пополам интервала , определенного этими значениями, а затем выборе подинтервала, в котором функция меняет знак и, следовательно, должна содержать корень . Это очень простой и надежный метод, но он также относительно медленный. По этой причине его часто используют для получения грубого приближения к решению, которое затем используется в качестве отправной точки для более быстро сходящихся методов. ^[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 ). Значения функции имеют противоположный знак (в пределах интервала имеется хотя бы одно пересечение нуля). Каждая итерация выполняет следующие шаги:

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 .

Алгоритм

Метод можно записать в псевдокоде следующим образом: ^[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  , тогда  // решение Found Output( c ) Остановить  конец if  N ← N + 1 // увеличить счетчик шагов  if Sign( f ( c )) = Sign( f ( a )) then  a ← c  else  b ← c  // Конец нового интервала while
Output( «Метод не выполнен.») // превышено максимальное количество шагов

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

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

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

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

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

и

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

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

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

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

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

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

Анализ

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

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

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

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

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

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

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

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

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

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

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

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

• Знак f( A) = (-,-), т. е. f ₁ (A)<0, f ₂ (A)<0.
• Знак f (B) = (-,+), то есть f ₁ (B)<0, f ₂ (B)>0.
• Знак f (C) = (+,-), то есть f ₁ (C)>0, f ₂ (C)<0.
• Знак f (D) = (+,+), то есть f ₁ (D)>0, f ₂ (D)>0.

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

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

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

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

Смотрите также

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

Рекомендации

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
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.
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.
19. Врахатис, Миннесота; Иорданидис, К.И. (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 из Института целостных численных методов.