Метод Галлея — алгоритм знаходження кореня рівнянь з однією змінною з неперервною другою похідною. Він названий на честь свого винахідника Едмонда Галлея.

Алгоритм є другим у класі методів Гаусголдера^[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}.}$

починаючи з початкового припущення 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 {2f(x_{n})f'(x_{n})}{2{[f'(x_{n})]}^{2}-f(x_{n})f''(x_{n})}}}$

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

Розглянемо функцію

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

Будь-який корінь f, який не є коренем його похідної, є коренем g, а будь-який корінь r від g повинен бути коренем f за умови, що похідна f в точці r не є нескінченною. Застосування методу Ньютона до g дає

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

Якщо ми беремо 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. ↑ 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.
2. ↑ 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.
3. ↑ Alefeld, G. (1981). On the convergence of Halley's method. American Mathematical Monthly. 88 (7): 530—536. doi:10.2307/2321760. JSTOR 2321760.
4. ↑ 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