Метод Мюллера

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

Метод Мюллера — это алгоритм нахождения корня , численный метод решения уравнений вида f ( x ) = 0. Впервые он был представлен Дэвидом Э. Мюллером в 1956 году.

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

Рекуррентное соотношение

Метод Мюллера — это рекурсивный метод, который генерирует новое приближение корня ξ функции f на каждой итерации, используя три предыдущих итерации. Начиная с трех начальных значений x ₀ , x ₋₁ и x ₋₂ , первая итерация вычисляет приближение x ₁ с использованием этих трех, вторая итерация вычисляет приближение x ₂ с использованием x ₁ , x ₀ и x ₋₁ , третья итерация вычисляет приближение x ₃ с использованием x ₂ , x ₁ и x ₀ , и так далее: k ^-я итерация генерирует приближение x _k с использованием x _k-1 , x _k-2 и x _k-3 . Каждая итерация принимает в качестве входных данных последние три сгенерированных приближения и значение f при этих приближениях: значения x _{k -1} , x _{k -2} и x _{k -3} и значения функции f ( x _{k -1} ), f ( x _{k -2} ) и f ( x _{k -3} ). Приближение x _k вычисляется следующим образом из этих шести значений.

Сначала парабола y _k ( x ) строится путем интерполяции через три точки ( x _{k -1} ,  f ( x _{k -1} )), ( x _{k -2} ,  f ( x _{k -2} )) и ( x _{k -3} ,  f ( x _{k -3} )) с использованием полинома Ньютона . y _k ( x ) равен

${\displaystyle y_{k}(x)=f(x_{k-1})+(x-x_{k-1})f[x_{k-1},x_{k-2}]+(x-x_{k-1})(x-x_{k-2})f[x_{k-1},x_{k-2},x_{k-3}],\,}$

где f [ x _{k -1} , x _{k -2} ] и f [ x _{k -1} , x _{k -2} , x _{k -3} ] обозначают разделенные разности . Это можно переписать как

${\displaystyle y_{k}(x)=f(x_{k-1})+w(x-x_{k-1})+f[x_{k-1},x_{k-2},x_{k-3}]\,(x-x_{k-1})^{2}\,}$

где

${\displaystyle w=f[x_{k-1},x_{k-2}]+f[x_{k-1},x_{k-3}]-f[x_{k-2},x_{k-3}].\,}$

Итерация x _k затем задается как решение квадратного уравнения y _k ( x ) = 0, ближайшее к x _{k -1} . В целом это подразумевает общее нелинейное рекуррентное соотношение третьего порядка ^[1]

${\displaystyle x_{k}=x_{k-1}-{\frac {2f(x_{k-1})}{w\pm {\sqrt {w^{2}-4f(x_{k-1})f[x_{k-1},x_{k-2},x_{k-3}]}}}},}$

где знак квадратного корня следует выбирать таким образом, чтобы общий знаменатель был как можно больше по величине.

Обратите внимание, что x _k может быть комплексным, даже если все предыдущие итерации были действительными. Это контрастирует с другими алгоритмами поиска корней, такими как метод секущих , обобщенный метод секущих Сиди или метод Ньютона , чьи итерации останутся действительными, если начать с действительных чисел. Наличие комплексных итераций может быть преимуществом (если ищутся комплексные корни) или недостатком (если известно, что все корни действительны), в зависимости от задачи.

Скорость сближения

Для хорошо ведущих себя функций порядок сходимости метода Мюллера составляет приблизительно 1,84 и точно равен постоянной трибоначчи . Это можно сравнить с приблизительно 1,62, точно золотым сечением , для метода секущих и точно 2 для метода Ньютона . Таким образом, метод секущих дает меньший прогресс за итерацию, чем метод Мюллера, а метод Ньютона дает больший прогресс.

Точнее, если ξ обозначает единственный корень f (то есть f (ξ) = 0 и f '(ξ) ≠ 0), f трижды непрерывно дифференцируема, а начальные приближения x ₀ , x ₁ и x ₂ взяты достаточно близко к ξ, то итерации удовлетворяют

${\displaystyle \lim _{k\to \infty }{\frac {|x_{k}-\xi |}{|x_{k-1}-\xi |^{\mu }}}=\left|{\frac {f'''(\xi )}{6f'(\xi )}}\right|^{(\mu -1)/2},}$

где μ ≈ 1,84 — положительное решение уравнения , определяющего константу трибоначчи. ${\displaystyle x^{3}-x^{2}-x-1=0}$

Обобщения и родственные методы

Метод Мюллера подгоняет параболу, т. е. многочлен второго порядка , к последним трем полученным точкам f ( x _{k -1} ), f ( x _{k -2} ) и f ( x _{k -3} ) в каждой итерации. Можно обобщить это и подгонять многочлен p _k,m ( x ) степени m к последним m +1 точкам в k ^-й итерации. Наша парабола y _k записывается как p _{k ,2} в этой нотации. Степень m должна быть 1 или больше. Следующее приближение x _k теперь является одним из корней p _k,m , т. е. одним из решений p _k,m ( x )=0. Взяв m = 1, мы получаем метод секущих, тогда как m = 2 дает метод Мюллера.

Мюллер вычислил, что последовательность { x _k }, сгенерированная таким образом, сходится к корню ξ с порядком μ _m , где μ _m — положительное решение уравнения . ${\displaystyle x^{m+1}-x^{m}-x^{m-1}-\dots -x-1=0}$

Однако этот метод гораздо сложнее для m >2, чем для m =1 или m =2, поскольку гораздо сложнее определить корни многочлена степени 3 или выше. Другая проблема заключается в том, что, по-видимому, нет предписания, какой из корней p _k,m выбрать в качестве следующего приближения x _k для m >2.

Эти трудности преодолеваются обобщенным методом секущих Сиди , который также использует многочлен p _k,m . Вместо того, чтобы пытаться решить p _k,m ( x )=0, следующее приближение x _k вычисляется с помощью производной p _k,m при x _{k -1} в этом методе.

Пример расчета

Ниже метод Мюллера реализован на языке программирования Python . Затем он применяется для нахождения корня функции f ( x ) = x ² − 612 .

из  ввода  import  * из  cmath  import  sqrt  # Используйте комплексный sqrt, так как мы можем генерировать комплексные числаNum  =  Union [ float ,  complex ] Func  =  Callable [[ Num ],  Num ]def  div_diff ( f :  Func ,  xs :  list [ Num ]): """Вычислить разделенную разность f[x0, x1, ...].""" if len ( xs ) == 2 : a , b = xs return ( f ( a ) - f ( b )) / ( a - b ) else : return ( div_diff ( f , xs [ 1 :]) - div_diff ( f , xs [ 0 : - 1 ])) / ( xs [ - 1 ] - xs [ 0 ])                            def  mullers_method ( f :  Func ,  xs :  ( Num ,  Num ,  Num ),  iterations :  int )  ->  float : """Возвращает корень, вычисленный с помощью метода Мюллера.""" x0 , x1 , x2 = xs for _ in range ( iterations ): w = div_diff ( f , ( x2 , x1 )) + div_diff ( f , ( x2 , x0 )) - div_diff ( f , ( x2 , x1 )) s_delta = sqrt ( w ** 2-4 * f ( x2 ) * div_diff ( f , ( x2 , x1 , x0 ) )) denoms = [ w + s_delta , w - s_delta ] # Берем знаменатель большей величины x3 = x2-2 * f ( x2 ) / max ( denoms , key = abs ) # Продвижение x0 , x1 , x2 = x1 , x2 , x3 возврат x3                                                                  def  f_example ( x :  Num )  ->  Num : """Пример функции. При использовании более дорогой функции может быть полезно запоминание последних 4 вызванных точек.""" return x ** 2 - 612       root  =  mullers_method ( f_example ,  ( 10 ,  20 ,  30 ),  5 ) print ( "Корень: {} " . format ( root ))  # Корень: (24.738633317099097+0j)

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

• Метод Галлея с кубической сходимостью
• Метод Хаусхолдера , включает в себя сходимость Ньютона, Галлея и более высокого порядка.

Ссылки

1. Мюллер, Дэвид Э. (1956). «Метод решения алгебраических уравнений с использованием автоматического компьютера». Математические таблицы и другие вспомогательные средства для вычислений . 10 (56): 208–215. doi : 10.1090/S0025-5718-1956-0083822-0 . JSTOR  2001916. MR  0083822.

• Аткинсон, Кендалл Э. (1989). Введение в численный анализ , 2-е издание, раздел 2.4. John Wiley & Sons, Нью-Йорк. ISBN 0-471-50023-2 . 
• Бёрден, Р. Л. и Фейрес, Д. Д. Численный анализ , 4-е издание, стр. 77 и далее.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Раздел 9.5.2. Метод Мюллера". Numerical Recipes: The Art of Scientific Computing (3-е изд.). Нью-Йорк: Cambridge University Press. ISBN 978-0-521-88068-8.

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

• Вариант скобок с глобальной сходимостью: Costabile, F.; Gualtieri, MI; Luceri, R. (март 2006 г.). «Модификация метода Мюллера». Calcolo . 43 (1): 39–50. doi :10.1007/s10092-006-0113-9. S2CID  124772103.