метод Галлея

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

Алгоритм является вторым в классе методов Хаусхолдера после метода Ньютона . Как и последний, он итеративно создает последовательность приближений к корню; их скорость сходимости к корню кубическая. Существуют многомерные версии этого метода. ^{[ нужна цитата ]}

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

Метод

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

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

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

Если f — трижды непрерывно дифференцируемая функция и a — нуль f , но не ее производной, то в окрестности a итерации x _n удовлетворяют:

${\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)|}}}.}$

Любой корень r из f , который не является корнем своей производной, является корнем g (т.е., когда ), и любой корень r из g должен быть корнем f при условии, что производная f в r не бесконечна. Применение метода Ньютона к g дает ${\displaystyle g(r)=0}$ ${\displaystyle f(r)=0\neq {\sqrt {|f'(r)|}}}$

${\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)|}}}},}$

и результат следует. Обратите внимание, что если f ′( c ) = 0 , то это нельзя применить к c , потому что g ( c ) будет неопределенным. ^{[ нужны дальнейшие объяснения ]}

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

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

${\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},}$

где ξ и η — числа, лежащие _между a и xn . Умножьте первое уравнение на и вычтите из него время второго уравнения , чтобы получить: ${\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}.}$

Предел коэффициента в правой части при x _n → a равен:

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

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

${\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. Бойд, JP (2013). «Нахождение нулей одномерного уравнения: прокси-корневики, интерполяция Чебышева и вспомогательная матрица». Обзор СИАМ . 55 (2): 375–396. дои : 10.1137/110838297.
2. Скаво, ТР; Ту, Джей Би (1995). «О геометрии метода Галлея». Американский математический ежемесячник . 102 (5): 417–426. дои : 10.2307/2975033. JSTOR  2975033.
3. Алефельд, Г. (1981). «О сходимости метода Галлея». Американский математический ежемесячник . 88 (7): 530–536. дои : 10.2307/2321760. JSTOR  2321760.
4. Проинов, Петко Д.; Иванов, Стоил И. (2015). «О сходимости метода Галлея для одновременного вычисления полиномиальных нулей». Дж. Нумер. Математика . 23 (4): 379–394. дои : 10.1515/jnma-2015-0026. S2CID  10356202.

Внешние ссылки

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