Метод хорд

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

В цьому методі нелінійна функція на виділеному інтервалі [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} = Ke^p_n, де K це деяка стала , тоді швидкість збіжності метода який генерує \{x_n\} становить p.

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

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

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

 

 

 

 

(1)

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

 

 

 

 

(2)

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

\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) ми маємо

e_{n+1} = \frac{e_{n-1}f(x_n) - f(x_{n-1})e_n}{f(x_n)-f(x_{n-1})}

 

 

 

 

(4)

По теоремі Лагранжа, \exists \xi_n \in int(x_n, x^*) таке, що

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

Ми маємо

f'(\xi_n)=\frac{f(x_n)}{e_n} тоді f(x_n)=e_n f'(\xi_n)

 

 

 

 

(5)

Аналогічно

f(x_{n-1})=e_{n-1} f'(\xi_{n-1})

 

 

 

 

(6)

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

e_{n+1} = e_ne_{n-1}\frac{f'(\xi_n)-f'(\xi_{n-1})}{f(x_n)-f(x_{n-1})},

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

 

 

 

 

(7)

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

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

 

 

 

 

(8)

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

e_n^p\propto e_{n-1}^p e_{n-1}

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

 

 

 

 

(9)

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

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}. Отже збіжність надлінійна.

Див. також[ред.ред. код]

Посилання[ред.ред. код]

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