Метод хорд

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

В цьому методі нелінійна функція на виділеному інтервалі ${\displaystyle [a;b]}$ замінюється лінійною (хордою) — прямою, що з'єднує кінці нелінійної функції.

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

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

Як видно з цього відношення, метод хорд вимагає двох початкових точок, ${\displaystyle x_{0}$ і ${\displaystyle x_{1}$, які в ідеалі мають бути вибрані в околі розв'язку.

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

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

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

${\displaystyle x_{n+1}={\frac {f(x_{n})x_{n-1}-f(x_{n-1})x_{n}{f(x_{n})-f(x_{n-1})}$

(1)

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})(x_{n}-x_{n-1})}{f(x_{n})-f(x_{n-1})}.}$

(2)

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

${\displaystyle {\begin{matrix}x_{n+1}=e_{n+1}+x^{*}\\x_{n}=e_{n}+x^{*}\\x_{n-1}=e_{n-1}+x^{*}\end{matrix}$

(3)

Використовуючи (3) і (2) ми маємо

${\displaystyle e_{n+1}={\frac {e_{n-1}f(x_{n})-f(x_{n-1})e_{n}{f(x_{n})-f(x_{n-1})}$

(4)

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

${\displaystyle f'(\xi _{n})={\frac {f(x_{n})-f(x^{*})}{x_{n}-x^{*}$

${\displaystyle \because f(x^{*})=0,x_{n}-x^{*}=e_{n}$

Ми маємо

${\displaystyle f'(\xi _{n})={\frac {f(x_{n})}{e_{n}$ тоді ${\displaystyle f(x_{n})=e_{n}f'(\xi _{n})}$

(5)

Аналогічно

${\displaystyle f(x_{n-1})=e_{n-1}f'(\xi _{n-1})}$

(6)

Підставляючи (5) і (6) у (4) ми отримуємо

${\displaystyle e_{n+1}=e_{n}e_{n-1}{\frac {f'(\xi _{n})-f'(\xi _{n-1})}{f(x_{n})-f(x_{n-1})},}$

тобто ${\displaystyle e_{n+1}\propto e_{n}e_{n-1}$

(7)

За визначенням швидкості збіжності порядку ${\displaystyle p}$

${\displaystyle {\begin{matrix}e_{n}\propto e_{n-1}^{p}\\e_{n+1}\propto e_{n}^{p}\end{matrix}$

(8)

З (7) і (8) випливає

${\displaystyle e_{n}^{p}\propto e_{n-1}^{p}e_{n-1}$

${\displaystyle e_{n}\propto e_{n-1}^{(p+1)/p}$

(9)

З (8) і (9) маємо

${\displaystyle p=(p+1)/p}$

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

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

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

Weisstein, Eric W. Метод хорд(англ.) на сайті Wolfram MathWorld.