метод Галлея

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

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

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

Метод

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

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

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

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

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

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

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

$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}.$

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

Вывод

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

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

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

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

с

$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 находится в этой окрестности. Тогда из теоремы Тейлора следует:

$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}$

а также

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

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

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

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

$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}.$

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

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

получить:

$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}.$

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

$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 равен:

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

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

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

что и предстояло доказать.

Подводя итог,

$\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.$

Иррациональный метод Галлея

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

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

Эта итерация была «заслуженно предпочтена» рациональному методу Галлея. на том основании, что знаменатель меньше, что упрощает деление. Второе преимущество состоит в том, что он имеет тенденцию иметь примерно половину ошибки рационального метода, и это преимущество увеличивается по мере его повторения. На компьютере это может показаться медленнее, поскольку он имеет две медленные операции (деление и квадратный корень) вместо одной, но на современных компьютерах обратная величина знаменателя может быть вычислена одновременно с квадратным корнем посредством конвейерной обработки команд . поэтому задержка каждой итерации отличается очень мало.

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

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