Метод хорд

Метод хорд (іноді метод лінійного інтерполювання або метод пропорційних частин) — ітераційний числовий метод знаходження наближених коренів нелінійного алгебраїчного рівняння.

В цьому методі нелінійна функція на виділеному інтервалі

$[a;b]$

замінюється лінійною (хордою) — прямою, що з'єднує кінці нелінійної функції.

Перші три ітерації методу хорд. Синім намальована функція f(x), червоним — хорди.

Метод

Метод хорд визначається наступним рекурентним співвідношенням:

$x_n=x_{n-1}-f(x_{n-1})\frac{x_{n-1}-x_{n-2}}{f(x_{n-1})-f(x_{n-2})}$

Як видно з цього відношення, метод хорд вимагає двох початкових точок, $x_0$ і $x_1$, які в ідеалі мають бути вибрані в околі розв'язку.

Збіжність

Скажімо, $x_n=x^{*}+e_n,x_{n+1}=x^{*}+e_{n+1}$ де $x^{*}$ є коренем $f(x)=0,$ а $e_n,e_{n+1}$ це похибки на n та n+1 ітераціях і $x_n,x_{n+1}$ це наближення $x^{*}$ на n та n+1 ітераціях. Якщо $e_{n+1}=K{e}_n^p,$ де $K$ це деяка стала , тоді швидкість збіжності метода який генерує $\{x_n\}$ становить $p.$

Ми покажемо, що метод хорд має надлінійну збіжність.

Доведення: Ітераційна схема для метода хорд така: Шаблон:NumBlk Шаблон:NumBlk

Нехай $f(x^{*})=0$ і $e_n=(x^{*}-x_n)$ тоді помилка на n ітерації в оцінюванні $x^{*}$ становить: Шаблон:NumBlk

Використовуючи (Шаблон:EquationNote) і (Шаблон:EquationNote) ми маємо Шаблон:NumBlk

По теоремі Лагранжа, $\mathrm{\exists }{\xi }_n\in int(x_n,x^{*})$ таке, що

$f^{\prime }({\xi }_n)=\frac{f(x_n)-f(x^{*})}{x_n-x^{*}}$

$\because f(x^{*})=0,x_n-x^{*}=e_n$

Ми маємо Шаблон:NumBlk Аналогічно Шаблон:NumBlk Підставляючи (Шаблон:EquationNote) і (Шаблон:EquationNote) у (Шаблон:EquationNote) ми отримуємо

$e_{n+1}=e_n{e}_{n-1}\frac{f^{\prime }({\xi }_n)-f^{\prime }({\xi }_{n-1})}{f(x_n)-f(x_{n-1})},$

Шаблон:NumBlk За визначенням швидкості збіжності порядку $p$ Шаблон:NumBlk З (Шаблон:EquationNote) і (Шаблон:EquationNote) випливає

$e_n^p\propto e_{n-1}^p{e}_{n-1}$

Шаблон:NumBlk З (Шаблон:EquationNote) і (Шаблон:EquationNote) маємо

$p=(p+1)/p$

тоді $p^2-p-1=0,$ отже $p=\frac{1\pm \sqrt{5}}{2}.$

Тобто $p>0,p=1.618$ і значить $e_{n+1}\propto e_n^{1.618}.$ Отже збіжність надлінійна.

Див. також

• Метод Ньютона