Метод Галлея

Метод численного нахождения корней функции

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

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

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

Метод

Метод Галлея — это численный алгоритм решения нелинейного уравнения 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 ₀ . ^[3]

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

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

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

Следующая альтернативная формулировка показывает сходство между методом Галлея и методом Ньютона. Выражение вычисляется только один раз, и оно особенно полезно, когда его можно упростить: ${\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 и x _n . Умножьте первое уравнение на и вычтите из него второе уравнение раз, чтобы получить: ${\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.}$^[5]

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

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

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

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

Ссылки

1. Gundersen, Geir; Steihaug, Trond (2010). «О задачах оптимизации без ограничений в больших масштабах и методах более высокого порядка» (PDF) . Методы оптимизации и программное обеспечение . 25 (3): 337–358. doi :10.1080/10556780903239071 . Получено 2 сентября 2024 г. .
2. Бойд, Джон П. (2013). «Нахождение нулей уравнения с одной переменной: поиск прокси-корней, интерполяция Чебышева и сопутствующая матрица». Обзор SIAM . 55 (2): 375–396. doi :10.1137/110838297.
3. Скаво, ТР; Ту, Дж. Б. (1995). «О геометрии метода Галлея». American Mathematical Monthly . 102 (5): 417–426. doi :10.2307/2975033. JSTOR  2975033.
4. Алефельд, Г. (1981). «О сходимости метода Галлея». American Mathematical Monthly . 88 (7): 530–536. doi :10.2307/2321760. JSTOR  2321760.
5. Пройнов, Петко Д.; Иванов, Стоил И. (2015). «О сходимости метода Галлея для одновременного вычисления нулей полиномов». J. Numer. Math . 23 (4): 379–394. doi :10.1515/jnma-2015-0026. S2CID  10356202.
6. Бейтман, Гарри (январь 1938 г.). «Методы Галлея для решения уравнений». The American Mathematical Monthly . 45 (1): 11–17. doi :10.2307/2303467. JSTOR  2303467.
7. Галлей, Эдмонд (май 1694 г.). «Methodus nova Accurata & Facilis Inveniendi radices æqnationum quarumcumque Generaliter, sine Praviæ Reduction». Философские труды Королевского общества (на латыни). 18 (210): 136–148. дои : 10.1098/rstl.1694.0029 . Английский перевод был опубликован как Halley, Edmond (1809) [май 1694]. «Новый, точный и простой метод нахождения корней любых уравнений вообще, и без какой-либо предварительной редукции». В C. Hutton; G. Shaw; R. Pearson (ред.). The Philosophical Transactions of the Royal Society of London, from their beginningment, in 1665, to the year 1800. Vol. III from 1683 to 1694. pp. 640–649.
8. Лерой, Робин (21 июня 2021 г.). Правильно округленный кубический корень binary64 (PDF) (Технический отчет).

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

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