Метод хорд (іноді метод лінійного інтерполювання або метод пропорційних частин ) — ітераційний числовий метод знаходження наближених коренів нелінійного алгебраїчного рівняння .
В цьому методі нелінійна функція на виділеному інтервалі
[
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}.}
Див. також
ред.
Посилання
ред.
![{\displaystyle [a;b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68e776d74130a8890a814c1f4e74372a9110d2f9)
