Метод Галлея
Метод Галлея — алгоритм знаходження кореня рівнянь з однією змінною з неперервною другою похідною. Він названий на честь свого винахідника Едмонда Галлея.
Алгоритм є другим у класі методів Гаусголдера[en] після методу Ньютона. Як і останній, він дає послідовність наближень до кореня, але має вищу швидкість збіжності - кубічну. Існують багатовимірні версії цього методу.
Метод Галлея точно знаходить корені апроксимації Паде до функції, на відміну від методу Ньютона або методу хорд, які наближають функцію лінійно, або методу Мюллера[en], який наближає функцію квадратично[1].
Метод ред.
Метод Галлея — чисельний алгоритм розв’язування нелінійного рівняння f (x) = 0. У цьому випадку функція f має бути функцією однієї дійсної змінної. Метод складається з послідовності ітерацій:
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a7376b96e994659020372736e3d9f588420eb2f)
починаючи з початкового припущення x0[2].
Якщо f є тричі неперервно диференційованою функцією, а a є нулем функції f, але не її похідної, то в околиці a ітерації xn задовольняють нерівності:
Це означає, що ітерації збігаються до нуля, якщо початкове припущення достатньо близьке, і що збіжність є кубічною[3].
Наступне альтернативне формулювання показує подібність між методом Галлея та методом Ньютона. Вираз обчислюється лише один раз, і це особливо корисно, коли можна спростити:
![{\displaystyle x_{n+1}=x_{n}-{\frac {2f(x_{n})f'(x_{n})}{2{[f'(x_{n})]}^{2}-f(x_{n})f''(x_{n})}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/142614c0378a1d61cb623c1352bf85b6b7bc4397)
Коли друга похідна близька до нуля, ітерація методу Галлея майже така ж, як ітерація методу Ньютона.
Виведення ред.
Розглянемо функцію
Будь-який корінь f, який не є коренем його похідної, є коренем g, а будь-який корінь r від g повинен бути коренем f за умови, що похідна f в точці r не є нескінченною. Застосування методу Ньютона до g дає
- ,
де
![{\displaystyle g'(x)={\frac {2[f'(x)]^{2}-f(x)f''(x)}{2f'(x){\sqrt {|f'(x)|}}}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c085ce12340c020ac47e39817c419ee2a399975e)
що й дає потрібний результат. Зауважте, що якщо f′ (c) = 0, то не можна застосувати це до c, оскільки g (c) буде невизначеним.
Кубічна збіжність ред.
Припустимо, що a є коренем f, але не його похідної. Також припустимо, що третя похідна f існує і є неперервною в околиці a, а xn знаходиться в цій околиці. Тоді з теореми Тейлора випливає:
а також
де ξ і η — числа, що лежать між a і xn. Помножимо перше рівняння на і віднімемо від нього друге рівняння . Отримаємо
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b11fafcca794e0330b586fe7b414959719d1e5db)
Скорочуючи і перегруповуючи члени, отримуємо:
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d39babcab23c817d06919c6afbe3d64326c2c844)
Переносимо другий доданок ліворуч і ділимо на
- .
![{\displaystyle 2[f'(x_{n})]^{2}-f(x_{n})f''(x_{n})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d0d50d182f7fb57cccb3c59590995479c606a6f)
Отримуємо
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/315da495c3271ca6600186e17ed902317094944c)
Таким чином,
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74f14fc87234a57c203f95fc074180b61811e5f0)
Границя коефіцієнта в правій частині при xn → a дорівнює
![{\displaystyle -{\frac {2f'(a)f'''(a)-3f''(a)f''(a)}{12[f'(a)]^{2}}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/463f77065d5dd93cc1ed4ddbcbf604a5b7519682)
Якщо ми беремо K трохи більшим за абсолютне значення цієї величини, ми можемо взяти абсолютні значення обох сторін формули та замінити абсолютне значення коефіцієнта його верхньою межею біля a, отримуючи:
- ,
що й треба було довести.
В підсумку,
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a88e6cae15ea9f1e0a8f980380a515a28209a60)
Примітки ред.
- ↑ Boyd, J. P. (2013). Finding the Zeros of a Univariate Equation: Proxy Rootfinders, Chebyshev Interpolation, and the Companion Matrix. SIAM Review. 55 (2): 375—396. doi:10.1137/110838297.
- ↑ Scavo, T. R.; Thoo, J. B. (1995). On the geometry of Halley's method. American Mathematical Monthly. 102 (5): 417—426. doi:10.2307/2975033. JSTOR 2975033.
- ↑ Alefeld, G. (1981). On the convergence of Halley's method. American Mathematical Monthly. 88 (7): 530—536. doi:10.2307/2321760. JSTOR 2321760.
- ↑ Proinov, Petko D.; Ivanov, Stoil I. (2015). On the convergence of Halley's method for simultaneous computation of polynomial zeros. J. Numer. Math. 23 (4): 379—394. doi:10.1515/jnma-2015-0026.
Посилання ред.
- Weisstein, Eric W. Halley’s method(англ.) на сайті Wolfram MathWorld.
- Newton's method and high order iterations, Pascal Sebah and Xavier Gourdon, 2001