Метод хорд (іноді метод лінійного інтерполювання або метод пропорційних частин ) — ітераційний числовий метод знаходження наближених коренів нелінійного алгебраїчного рівняння .
В цьому методі нелінійна функція на виділеному інтервалі [ a ; b ] {\displaystyle [a;b]} замінюється лінійною (хордою) — прямою, що з'єднує кінці нелінійної функції.
Перші три ітерації методу хорд. Синім намальована функція f(x), червоним — хорди. Метод хорд визначається наступним рекурентним співвідношенням :
x n = x n − 1 − f ( x n − 1 ) x n − 1 − x n − 2 f ( x n − 1 ) − f ( x n − 2 ) {\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})}}} Як видно з цього відношення, метод хорд вимагає двох початкових точок, x 0 {\displaystyle x_{0}} і x 1 {\displaystyle x_{1}} , які в ідеалі мають бути вибрані в околі розв'язку.
Скажімо, x n = x ∗ + e n , x n + 1 = x ∗ + e n + 1 {\displaystyle x_{n}=x^{*}+e_{n},x_{n+1}=x^{*}+e_{n+1}} де x ∗ {\displaystyle x^{*}} є коренем f ( x ) = 0 , {\displaystyle f(x)=0,} а e n , e n + 1 {\displaystyle e_{n},e_{n+1}} це похибки на n та n+1 ітераціях і x n , x n + 1 {\displaystyle x_{n},x_{n+1}} це наближення x ∗ {\displaystyle x^{*}} на n та n+1 ітераціях. Якщо e n + 1 = K e n p , {\displaystyle e_{n+1}=Ke_{n}^{p},} де K {\displaystyle K} це деяка стала , тоді швидкість збіжності метода який генерує { x n } {\displaystyle \{x_{n}\}} становить p . {\displaystyle p.}
Ми покажемо, що метод хорд має надлінійну збіжність.
Доведення: Ітераційна схема для метода хорд така:
x n + 1 = f ( x n ) x n − 1 − f ( x n − 1 ) x n f ( x n ) − f ( x n − 1 ) {\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 )
x n + 1 = x n − f ( x n ) ( x n − x n − 1 ) f ( x n ) − f ( x n − 1 ) . {\displaystyle 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 {\displaystyle f(x^{*})=0} і e n = ( x ∗ − x n ) {\displaystyle e_{n}=(x^{*}-x_{n})} тоді помилка на n ітерації в оцінюванні x ∗ {\displaystyle x^{*}} становить:
x n + 1 = e n + 1 + x ∗ x n = e n + x ∗ x n − 1 = e n − 1 + 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 ) ми маємо
e n + 1 = e n − 1 f ( x n ) − f ( x n − 1 ) e n f ( x n ) − f ( x n − 1 ) {\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 )
По теоремі Лагранжа , ∃ ξ n ∈ i n t ( x n , x ∗ ) {\displaystyle \exists \xi _{n}\in int(x_{n},x^{*})} таке, що
f ′ ( ξ n ) = f ( x n ) − f ( x ∗ ) x n − x ∗ {\displaystyle f'(\xi _{n})={\frac {f(x_{n})-f(x^{*})}{x_{n}-x^{*}}}} ∵ f ( x ∗ ) = 0 , x n − x ∗ = e n {\displaystyle \because f(x^{*})=0,x_{n}-x^{*}=e_{n}} Ми маємо
f ′ ( ξ n ) = f ( x n ) e n {\displaystyle f'(\xi _{n})={\frac {f(x_{n})}{e_{n}}}} тоді f ( x n ) = e n f ′ ( ξ n ) {\displaystyle f(x_{n})=e_{n}f'(\xi _{n})}
(5 )
Аналогічно
f ( x n − 1 ) = e n − 1 f ′ ( ξ n − 1 ) {\displaystyle f(x_{n-1})=e_{n-1}f'(\xi _{n-1})}
(6 )
Підставляючи (5 ) і (6 ) у (4 ) ми отримуємо
e n + 1 = e n e n − 1 f ′ ( ξ n ) − f ′ ( ξ n − 1 ) f ( x n ) − f ( x n − 1 ) , {\displaystyle e_{n+1}=e_{n}e_{n-1}{\frac {f'(\xi _{n})-f'(\xi _{n-1})}{f(x_{n})-f(x_{n-1})}},} тобто e n + 1 ∝ e n e n − 1 {\displaystyle e_{n+1}\propto e_{n}e_{n-1}}
(7 )
За визначенням швидкості збіжності порядку p {\displaystyle p}
e n ∝ e n − 1 p e n + 1 ∝ e n p {\displaystyle {\begin{matrix}e_{n}\propto e_{n-1}^{p}\\e_{n+1}\propto e_{n}^{p}\end{matrix}}}
(8 )
З (7 ) і (8 ) випливає
e n p ∝ e n − 1 p e n − 1 {\displaystyle e_{n}^{p}\propto e_{n-1}^{p}e_{n-1}} e n ∝ e n − 1 ( p + 1 ) / p {\displaystyle e_{n}\propto e_{n-1}^{(p+1)/p}}
(9 )
З (8 ) і (9 ) маємо
p = ( p + 1 ) / p {\displaystyle p=(p+1)/p} тоді p 2 − p − 1 = 0 , {\displaystyle p^{2}-p-1=0,} отже p = 1 ± 5 2 . {\displaystyle p={\frac {1\pm {\sqrt {5}}}{2}}.}
Тобто p > 0 , p = 1.618 {\displaystyle p>0,p=1.618} і значить e n + 1 ∝ e n 1.618 . {\displaystyle e_{n+1}\propto e_{n}^{1.618}.} Отже збіжність надлінійна.
Weisstein, Eric W. Метод хорд (англ.) на сайті Wolfram MathWorld .