Метод Халлея - Halleys method

В числовой анализ, Метод Галлея это алгоритм поиска корней используется для функций одной действительной переменной с непрерывной второй производной. Он назван в честь своего изобретателя. Эдмонд Галлей.

Алгоритм второй в классе Методы домохозяина, после Метод Ньютона. Подобно последнему, он итеративно производит последовательность приближений к корню; их скорость сходимости к корню кубический. Существуют многомерные версии этого метода.

Метод Галлея точно находит корни линейно-линейного Приближение Паде функции, в отличие от Метод Ньютона или Секущий метод которые аппроксимируют функцию линейно, или Метод Мюллера который аппроксимирует функцию квадратично.^[1]

Метод

Эдмонд Галлей был английским математиком, который представил метод, который теперь носит его имя. Метод Галлея - это численный алгоритм решения нелинейного уравнения ж(Икс) = 0. В этом случае функция ж должен быть функцией одной реальной переменной. Метод состоит из последовательности итераций:

${\displaystyle x_{n+1}=x_{n}-{\frac {2f(x_{n})f'(x_{n})}{2{[f'(x_{n})]}^{2}-f(x_{n})f''(x_{n})}}}$

начиная с первоначального предположения Икс₀.^[2]

Если ж является трижды непрерывно дифференцируемой функцией и а это ноль ж но не его производной, то в окрестности а, повторяется Икс_п удовлетворить:

${\displaystyle |x_{n+1}-a|\leq K\cdot {|x_{n}-a|}^{3},{\text{ for some }}K>0.}$

Это означает, что итерации сходятся к нулю, если первоначальное предположение достаточно близко, и что сходимость кубическая.^[3]

Следующая альтернативная формулировка показывает сходство между методом Галлея и методом Ньютона. Выражение ${\displaystyle f(x_{n})/f'(x_{n})}$ вычисляется только один раз, и это особенно полезно, когда ${\displaystyle f''(x_{n})/f'(x_{n})}$ можно упростить:

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})-{\frac {f(x_{n})}{f'(x_{n})}}{\frac {f''(x_{n})}{2}}}}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\left[1-{\frac {f(x_{n})}{f'(x_{n})}}\cdot {\frac {f''(x_{n})}{2f'(x_{n})}}\right]^{-1}.}$

Когда вторая производная очень близко к нулю, итерация метода Галлея почти такая же, как итерация метода Ньютона.

Вывод

Рассмотрим функцию

${\displaystyle g(x)={\frac {f(x)}{\sqrt {|f'(x)|}}}.}$

Любой корень ж который нет корень его производной является корнем грамм; и любой корень р из грамм должен быть корнем ж при условии производной от ж в р не бесконечно. Применение Метод Ньютона к грамм дает

${\displaystyle x_{n+1}=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}}$

с

${\displaystyle g'(x)={\frac {2[f'(x)]^{2}-f(x)f''(x)}{2f'(x){\sqrt {|f'(x)|}}}},}$

и результат следует. Обратите внимание, что если ж′(c) = 0, то это нельзя применить при c потому что грамм(c) будет неопределенным.

Кубическая конвергенция

Предполагать а это корень ж но не производной. И предположим, что третья производная от ж существует и непрерывен в окрестности а и Икс_п находится в этом районе. потом Теорема Тейлора подразумевает:

${\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(x_{n})}{2}}(a-x_{n})^{2}+{\frac {f'''(\xi )}{6}}(a-x_{n})^{3}}$

а также

${\displaystyle 0=f(a)=f(x_{n})+f'(x_{n})(a-x_{n})+{\frac {f''(\eta )}{2}}(a-x_{n})^{2},}$

где ξ и η - числа, лежащие между а и Икс_п. Умножьте первое уравнение на ${\displaystyle 2f'(x_{n})}$ и вычтите из него второе уравнение, умноженное на ${\displaystyle f''(x_{n})(a-x_{n})}$ давать:

${\displaystyle {\begin{aligned}0&=2f(x_{n})f'(x_{n})+2[f'(x_{n})]^{2}(a-x_{n})+f'(x_{n})f''(x_{n})(a-x_{n})^{2}+{\frac {f'(x_{n})f'''(\xi )}{3}}(a-x_{n})^{3}\\&\qquad -f(x_{n})f''(x_{n})(a-x_{n})-f'(x_{n})f''(x_{n})(a-x_{n})^{2}-{\frac {f''(x_{n})f''(\eta )}{2}}(a-x_{n})^{3}.\end{aligned}}}$

Отмена ${\displaystyle f'(x_{n})f''(x_{n})(a-x_{n})^{2}}$ и реорганизация условий дает:

${\displaystyle 0=2f(x_{n})f'(x_{n})+\left(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})\right)(a-x_{n})+\left({\frac {f'(x_{n})f'''(\xi )}{3}}-{\frac {f''(x_{n})f''(\eta )}{2}}\right)(a-x_{n})^{3}.}$

Поместите второй член слева и разделите на

${\displaystyle 2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}$

получить:

${\displaystyle a-x_{n}={\frac {-2f(x_{n})f'(x_{n})}{2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}}-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{6(2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n}))}}(a-x_{n})^{3}.}$

Таким образом:

${\displaystyle a-x_{n+1}=-{\frac {2f'(x_{n})f'''(\xi )-3f''(x_{n})f''(\eta )}{12[f'(x_{n})]^{2}-6f(x_{n})f''(x_{n})}}(a-x_{n})^{3}.}$

Предел коэффициента в правой части при Икс_п → а является:

${\displaystyle -{\frac {2f'(a)f'''(a)-3f''(a)f''(a)}{12[f'(a)]^{2}}}.}$

Если мы возьмем K чтобы быть немного больше, чем абсолютное значение этого, мы можем взять абсолютные значения обеих сторон формулы и заменить абсолютное значение коэффициента его верхней границей около а получить:

${\displaystyle |a-x_{n+1}|\leq K|a-x_{n}|^{3}}$

что и требовалось доказать.

Подвести итоги,

${\displaystyle \Delta x_{i+1}={\frac {3(f'')^{2}-2f'f'''}{12(f')^{2}}}(\Delta x_{i})^{3}+O[\Delta x_{i}]^{4},\qquad \Delta x_{i}\triangleq x_{i}-a.}$^[4]

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

1. Бойд, Дж. П. (2013). «Нахождение нулей одномерного уравнения: прокси-кортежи, чебышевская интерполяция и сопутствующая матрица». SIAM Обзор. 55 (2): 375–396. Дои:10.1137/110838297.
2. Scavo, T. R .; Ту, Дж. Б. (1995). «О геометрии метода Галлея». Американский математический ежемесячный журнал. 102 (5): 417–426. Дои:10.2307/2975033. JSTOR  2975033.
3. Алефельд, Г. (1981). «О сходимости метода Галлея». Американский математический ежемесячный журнал. 88 (7): 530–536. Дои:10.2307/2321760. JSTOR  2321760.
4. Пройнов, Петко Д .; Иванов, Стойл И. (2015). «О сходимости метода Галлея для одновременного вычисления полиномиальных нулей». J. Numer. Математика. 23 (4): 379–394. Дои:10.1515 / jnma-2015-0026.

Петко Д. Пройнов, Стоил И. Иванов, О сходимости метода Галлея для кратных полиномиальных нулей, Mediterranean J. Math. 12, 555 - 572 (2015)

внешняя ссылка

• Вайсштейн, Эрик В. «Метод Галлея». MathWorld.
• Метод Ньютона и итерации высокого порядка, Паскаль Себа и Ксавье Гурдон, 2001 (на сайте есть ссылка на версию Postscript для лучшего отображения формул)