Метод деления пополам
Алгоритм нахождения нуля функции
Несколько шагов метода бисекции, примененных к начальному диапазону [a 1 ;b 1 ]. Большая красная точка — корень функции.

В математике метод бисекции — это метод нахождения корня , который применяется к любой непрерывной функции , для которой известны два значения с противоположными знаками. Метод состоит из многократного деления пополам интервала , определяемого этими значениями, и последующего выбора подынтервала, в котором функция меняет знак и, следовательно, должна содержать корень . Это очень простой и надежный метод, но он также относительно медленный. Из-за этого его часто используют для получения грубого приближения к решению, которое затем используют в качестве отправной точки для более быстро сходящихся методов. [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 как новое a . В обоих случаях новые 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 , толерантность TOL , Максимальные итерации 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 // новая средняя точка  if  f ( c ) = 0 or ( b – a )/2 < TOL  then  // решение найдено Output( c ) Stop  end if  N ← N + 1 // увеличить счетчик шагов  if sign( f ( c )) = sign( f ( a )) then  a ← c  else  b ← c  // новый интервал end while
Output("Метод не выполнен.") // превышено максимальное количество шагов

Пример: Нахождение корня многочлена

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

ф ( х ) = х 3 − х − 2 . {\displaystyle f(x)=x^{3}-x-2\,.}

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

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

и

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

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

В первой итерации конечные точки интервала, который охватывает корень, — это и , поэтому средняя точка — это а 1 = 1 {\displaystyle а_{1}=1} б 1 = 2 {\displaystyle b_{1}=2}

с 1 = 2 + 1 2 = 1.5 {\displaystyle c_{1}={\frac {2+1}{2}}=1,5}

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

Итерация а н {\displaystyle а_{н}} б н {\displaystyle b_{n}} с н {\displaystyle c_{n}} ф ( с н ) {\displaystyle f(c_{n})}
1121.5−0,125
21.521.751.6093750
31.51.751.6250,6660156
41.51.6251.56250,2521973
51.51.56251.53125000,0591125
61.51.53125001.5156250−0,0340538
71.51562501.53125001.52343750,0122504
81.51562501.52343751.5195313−0,0109712
91.51953131.52343751.52148440,0006222
101.51953131.52148441.5205078−0,0051789
111.52050781.52148441.5209961−0,0022794
121.52099611.52148441.5212402−0,0008289
131.52124021.52148441.5213623−0,0001034
141.52136231.52148441.52142330,0002594
151.52136231.52142331.52139280.0000780

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

Анализ

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

| с н − с | ≤ | б − а | 2 н . {\displaystyle |c_{n}-c|\leq {\frac {|ba|}{2^{n}}}.}

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

н ≤ н 1 / 2 ≡ ⌈ бревно 2 ⁡ ( ϵ 0 ϵ ) ⌉ , {\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] ϵ 0 = | б − а | {\displaystyle \epsilon _{0}=|ba|} ϵ ≤ ϵ 0 . {\displaystyle \epsilon \leq \epsilon _ {0}.} ϵ {\displaystyle \epsilon}

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

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

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

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

Некоторые из этих методов основаны на вычислении топологической степени , которая для ограниченной области и дифференцируемой функции определяется как сумма по ее корням: Ω ⊆ Р н {\displaystyle \Omega \subseteq \mathbb {R} ^{n}} ф : Р н → Р н {\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}

градус ⁡ ( ф , Ω ) := ∑ у ∈ ф − 1 ( 0 ) знак ⁡ дет ( Д ф ( у ) ) {\displaystyle \deg(f,\Omega):=\sum _{y\in f^{-1}(\mathbf {0})}\operatorname {sgn} \det(Df(y))} ,

где — матрица Якоби , , и Д ф ( у ) {\displaystyle Df(y)} 0 = ( 0 , 0 , . . . , 0 ) Т {\displaystyle \mathbf {0} =(0,0,...,0)^{T}}

знак ⁡ ( х ) = { 1 , х > 0 0 , х = 0 − 1 , х < 0 {\displaystyle \operatorname {sgn}(x)={\begin{cases}1,&x>0\\0,&x=0\\-1,&x<0\\\end{cases}}}

— знаковая функция . [17] Для того чтобы корень существовал, достаточно, чтобы , и это можно проверить с помощью поверхностного интеграла по границе . [18] градус ⁡ ( ф , Ω ) ≠ 0 {\displaystyle \deg(f,\Omega)\neq 0} Ω {\displaystyle \Омега}

Характерный метод деления пополам

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

  • ⁠ ⁠ знак ⁡ ф ( А ) = ( − , − ) {\displaystyle \operatorname {sgn} f(A)=(-,-)} , то есть f 1 (A)<0, f 2 (A)<0.
  • ⁠ ⁠ знак ⁡ ф ( Б ) = ( − , + ) {\displaystyle \operatorname {sgn} f(B)=(-,+)} , то есть f 1 (B)<0, f 2 (B)>0.
  • ⁠ ⁠ знак ⁡ ф ( С ) = ( + , − ) {\displaystyle \operatorname {sgn} f(C)=(+,-)} , то есть f 1 (C)>0, f 2 (C)<0.
  • ⁠ ⁠ знак ⁡ ф ( Д ) = ( + , + ) {\displaystyle \operatorname {sgn} f(D)=(+,+)} , то есть f 1 (D)>0, f 2 (D)>0.

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

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

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

Предположим, что диаметр (= длина самого длинного собственного ребра) исходного характеристического многогранника равен D. Тогда требуется по крайней мере деление ребер пополам, чтобы диаметр оставшегося многоугольника был не больше ε . [20] : 11, Лемма.4.7  Если топологическая степень исходного многогранника не равна нулю, то существует процедура, которая может выбрать ребро таким образом, что следующий многогранник также будет иметь ненулевую степень. [21] [22] бревно 2 ⁡ ( Д / ε ) {\displaystyle \log _{2}(D/\varepsilon)}

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

Ссылки

  1. ^ Берден и Фейрес 1985, стр. 31
  2. ^ "Деление интервала пополам (бисекция)". Архивировано из оригинала 2013-05-19 . Получено 2013-11-07 .
  3. ^ Берден и Фейрес 1985, стр. 28
  4. ^ "Метод дихотомии - Энциклопедия математики". www.encyclopediaofmath.org . Получено 21.12.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 . doi :10.1007/BF01459080. ISSN  0945-3245. S2CID  119952605.
  10. ^ Сикорский, К (1 декабря 1985 г.). «Оптимальное решение нелинейных уравнений». Журнал сложности . 1 (2): 197– 209. doi :10.1016/0885-064X(85)90011-1. ISSN  0885-064X.
  11. ^ Граф, Зигфрид; Новак, Эрих; Папагеоргиу, Анаргирос (1 июля 1989 г.). «В среднем бисекция не оптимальна». Числовая математика . 55 (4): 481–491 . doi : 10.1007/BF01396051. ISSN  0945-3245. S2CID  119546369.
  12. ^ Новак, Эрих (1989-12-01). "Средние результаты для нулевого обнаружения". Журнал сложности . 5 (4): 489– 501. doi : 10.1016/0885-064X(89)90022-8 . ISSN  0885-064X.
  13. ^ ab Oliveira, IFD; Takahashi, RHC (2020-12-06). "Улучшение средней производительности метода бисекции, сохраняющее оптимальность Minmax". ACM Transactions on Mathematical Software . 47 (1): 5:1–5:24. doi :10.1145/3423597. ISSN  0098-3500. S2CID  230586635.
  14. ^ Иво, Оливейра (14.12.2020). «Улучшенный метод деления пополам». doi : 10.1145/3423597. S2CID  230586635.
  15. ^ Mourrain, B.; Vrahatis, MN; Yakoubsohn, JC (2002-06-01). «О сложности изоляции действительных корней и вычислении с уверенностью топологической степени». Journal of Complexity . 18 (2): 612– 640. doi : 10.1006/jcom.2001.0636 . ISSN  0885-064X.
  16. ^ Vrahatis, Michael N. (2020). «Обобщения теоремы о промежуточном значении для аппроксимации неподвижных точек и нулей непрерывных функций». В Sergeyev, Yaroslav D.; Kvasov, Дмитрий E. (ред.). Numerical Computations: Theory and Algorithms . Lecture Notes in Computer Science. Vol. 11974. Cham: Springer International Publishing. pp.  223– 238. doi :10.1007/978-3-030-40616-5_17. ISBN 978-3-030-40616-5. S2CID  211160947.
  17. ^ Polymilis, C.; Servizi, G.; Turchetti, G.; Skokos, Ch.; Vrahatis, MN (май 2003 г.). «Определение периодических орбит с помощью топологической теории степеней». Libration Point Orbits and Applications : 665– 676. arXiv : nlin/0211044 . doi :10.1142/9789812704849_0031. ISBN 978-981-238-363-1.
  18. ^ Кирфотт, Бейкер (1979-06-01). "Эффективный метод вычисления степени для обобщенного метода деления пополам". Numerische Mathematik . 32 (2): 109– 127. doi :10.1007/BF01404868. ISSN  0945-3245. S2CID  122058552.
  19. ^ Врахатис, Майкл Н. (1995-06-01). «Эффективный метод поиска и вычисления периодических орбит нелинейных отображений». Журнал вычислительной физики . 119 (1): 105– 119. Bibcode : 1995JCoPh.119..105V. doi : 10.1006/jcph.1995.1119. ISSN  0021-9991.
  20. ^ ab Vrahatis, MN; Iordanidis, KI (1986-03-01). "Быстрый обобщенный метод деления пополам для решения систем нелинейных уравнений". Numerische Mathematik . 49 (2): 123– 138. doi :10.1007/BF01389620. ISSN  0945-3245. S2CID  121771945.
  21. ^ ab Vrahatis, MN; Perdiou, AE; Kalantonis, VS; Perdios, EA; Papadakis, K.; Prosmiti, R.; Farantos, SC (июль 2001 г.). "Применение метода характеристического деления пополам для определения местоположения и вычисления периодических орбит в молекулярных системах". Computer Physics Communications . 138 (1): 53– 68. Bibcode :2001CoPhC.138...53V. doi :10.1016/S0010-4655(01)00190-4.
  22. ^ Врахатис, Майкл Н. (декабрь 1988 г.). «Решение систем нелинейных уравнений с использованием ненулевого значения топологической степени». Труды ACM по математическому программному обеспечению . 14 (4): 312– 329. doi :10.1145/50063.214384.
  • Берден, Ричард Л.; Фейрес, Дж. Дуглас (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-е изд.), архивировано из оригинала 2009-04-13
В Викиверситете есть обучающие ресурсы по методу деления пополам
В Wikibook Numerical Methods есть страница по теме: Решение уравнений
Взято с "https://en.wikipedia.org/w/index.php?title=Метод_разделения&oldid=1271311237"