Метод Галлея

Матеріал з testwiki
Перейти до навігації Перейти до пошуку

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

Алгоритм є другим у класі Шаблон:Не перекладено після методу Ньютона. Як і останній, він дає послідовність наближень до кореня, але має вищу швидкість збіжності - кубічну. Існують багатовимірні версії цього методу.

Метод Галлея точно знаходить корені апроксимації Паде до функції, на відміну від методу Ньютона або методу хорд, які наближають функцію лінійно, або Шаблон:Не перекладено, який наближає функцію квадратично[1].

Метод

Метод Галлея — чисельний алгоритм розв’язування нелінійного рівняння f (x) = 0. У цьому випадку функція f має бути функцією однієї дійсної змінної. Метод складається з послідовності ітерацій:

xn+1=xn−f(xn)f′(xn)−f(xn)f′(xn)f″(xn)2=xn−f(xn)f′(xn)[1−f(xn)f′(xn)⋅f″(xn)2f′(xn)]−1.

починаючи з початкового припущення x0[2].

Якщо f є тричі неперервно диференційованою функцією, а a є нулем функції f, але не її похідної, то в околиці a ітерації xn задовольняють нерівності:

|xn+1−a|≤K⋅|xn−a|3, for some K>0.

Це означає, що ітерації збігаються до нуля, якщо початкове припущення достатньо близьке, і що збіжність є кубічною[3].

Наступне альтернативне формулювання показує подібність між методом Галлея та методом Ньютона. Вираз f(xn)/f′(xn) обчислюється лише один раз, і це особливо корисно, коли f″(xn)/f′(xn) можна спростити:

xn+1=xn−2f(xn)f′(xn)2[f′(xn)]2−f(xn)f″(xn)

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

Виведення

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

g(x)=f(x)|f′(x)|.

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

xn+1=xn−g(xn)g′(xn),

де

g′(x)=2[f′(x)]2−f(x)f″(x)2f′(x)|f′(x)|,

що й дає потрібний результат. Зауважте, що якщо f′ (c) = 0, то не можна застосувати це до c, оскільки g (c) буде невизначеним.

Кубічна збіжність

Припустимо, що a є коренем f, але не його похідної. Також припустимо, що третя похідна f існує і є неперервною в околиці a, а xn знаходиться в цій околиці. Тоді з теореми Тейлора випливає:

0=f(a)=f(xn)+f′(xn)(a−xn)+f″(xn)2(a−xn)2+f‴(ξ)6(a−xn)3

а також

0=f(a)=f(xn)+f′(xn)(a−xn)+f″(η)2(a−xn)2,

де ξ і η — числа, що лежать між a і xn. Помножимо перше рівняння на 2f′(xn) і віднімемо від нього друге рівняння f″(xn)(a−xn). Отримаємо

0=2f(xn)f′(xn)+2[f′(xn)]2(a−xn)+f′(xn)f″(xn)(a−xn)2+f′(xn)f‴(ξ)3(a−xn)3−f(xn)f″(xn)(a−xn)−f′(xn)f″(xn)(a−xn)2−f″(xn)f″(η)2(a−xn)3.

Скорочуючи f′(xn)f″(xn)(a−xn)2 і перегруповуючи члени, отримуємо:

0=2f(xn)f′(xn)+(2[f′(xn)]2−f(xn)f″(xn))(a−xn)+(f′(xn)f‴(ξ)3−f″(xn)f″(η)2)(a−xn)3.

Переносимо другий доданок ліворуч і ділимо на

2[f′(xn)]2−f(xn)f″(xn).

Отримуємо

a−xn=−2f(xn)f′(xn)2[f′(xn)]2−f(xn)f″(xn)−2f′(xn)f‴(ξ)−3f″(xn)f″(η)6(2[f′(xn)]2−f(xn)f″(xn))(a−xn)3.

Таким чином,

a−xn+1=−2f′(xn)f‴(ξ)−3f″(xn)f″(η)12[f′(xn)]2−6f(xn)f″(xn)(a−xn)3.

Границя коефіцієнта в правій частині при Шаблон:Math дорівнює

−2f′(a)f‴(a)−3f″(a)f″(a)12[f′(a)]2.

Якщо ми беремо K трохи більшим за абсолютне значення цієї величини, ми можемо взяти абсолютні значення обох сторін формули та замінити абсолютне значення коефіцієнта його верхньою межею біля a, отримуючи:

|a−xn+1|≤K|a−xn|3,

що й треба було довести.

В підсумку,

Δxi+1=3(f″)2−2f′f‴12(f′)2(Δxi)3+O[Δxi]4,Δxi≜xi−a. [4]

Примітки

  1. ↑ Шаблон:Cite journal
  2. ↑ Шаблон:Cite journal
  3. ↑ Шаблон:Cite journal
  4. ↑ Шаблон:Cite journal

Посилання

Отримано з https://uk.wiki.beta.math.wmflabs.org/w/index.php?title=Метод_Галлея&oldid=10380