Метод Галлея — алгоритм знаходження кореня рівнянь з однією змінною з неперервною другою похідною. Він названий на честь свого винахідника Едмонда Галлея.
Алгоритм є другим у класі після методу Ньютона. Як і останній, він дає послідовність наближень до кореня, але має вищу швидкість збіжності — кубічну. Існують багатовимірні версії цього методу.
Метод Галлея точно знаходить корені апроксимації Паде до функції, на відміну від методу Ньютона або методу хорд, які наближають функцію лінійно, або , який наближає функцію квадратично.
Метод Метод Галлея — чисельний алгоритм розв'язування нелінійного рівняння f (x) = 0. У цьому випадку функція f має бути функцією однієї дійсної змінної. Метод складається з послідовності ітерацій:
починаючи з початкового припущення x0.
Якщо f є тричі неперервно диференційованою функцією, а a є нулем функції f, але не її похідної, то в околиці a ітерації xn задовольняють нерівності:
Це означає, що ітерації збігаються до нуля, якщо початкове припущення достатньо близьке, і що збіжність є кубічною.
Наступне альтернативне формулювання показує подібність між методом Галлея та методом Ньютона. Вираз обчислюється лише один раз, і це особливо корисно, коли можна спростити:
Коли друга похідна близька до нуля, ітерація методу Галлея майже така ж, як ітерація методу Ньютона.
Виведення Розглянемо функцію
Будь-який корінь f, який не є коренем його похідної, є коренем g, а будь-який корінь r від g повинен бути коренем f за умови, що похідна f в точці r не є нескінченною. Застосування методу Ньютона до g дає
,
де
що й дає потрібний результат. Зауважте, що якщо f′ (c) = 0, то не можна застосувати це до c, оскільки g (c) буде невизначеним.
Кубічна збіжність Припустимо, що a є коренем f, але не його похідної. Також припустимо, що третя похідна f існує і є неперервною в околиці a, а xn знаходиться в цій околиці. Тоді з теореми Тейлора випливає:
а також
де ξ і η — числа, що лежать між a і xn. Помножимо перше рівняння на і віднімемо від нього друге рівняння . Отримаємо
Скорочуючи і перегруповуючи члени, отримуємо:
Переносимо другий доданок ліворуч і ділимо на
.
Отримуємо
Таким чином,
Границя коефіцієнта в правій частині при дорівнює
Якщо ми беремо K трохи більшим за абсолютне значення цієї величини, ми можемо взяти абсолютні значення обох сторін формули та замінити абсолютне значення коефіцієнта його верхньою межею біля a, отримуючи:
,
що й треба було довести.
В підсумку,
Примітки
Джерела
Newton's method and high order iterations, Pascal Sebah and Xavier Gourdon, 2001