Швидкість збіжності

Швидкість збіжності є основною характеристикою чисельних методів розв'язування рівнянь і оптимізації.

Поняття швидкості збіжності

Нехай ${\displaystyle \left\{x_{n}\right\}}$ — збіжна послідовність наближень деякого алгоритму знаходження кореня рівняння або екстремуму функції ${\displaystyle x^{*}}$, тоді: Кажуть, що метод має лінійну збіжність, якщо ${\displaystyle \exists \alpha \in (0,\;1):\quad \exists N\in \mathbb {N} ,\;\forall n\geq N\quad ||x_{n}-x^{*}||<\alpha ||x_{n-1}-x^{*}||}$.

Кажуть, що метод має збіжність степеня ${\displaystyle \beta }$, якщо ${\displaystyle \exists \alpha \in (0,\;1]:\quad \exists N\in \mathbb {N} ,\;\forall n\geq N\quad ||x_{n}-x^{*}||<\alpha ||x_{n-1}-x^{*}||^{\beta }}$.

Відзначимо, що зазвичай швидкість збіжності методів не перевищує квадратичної. У рідкісних випадках метод може мати кубічну швидкість збіжності ().

Практичне визначення

Нехай ${\displaystyle \left\{x_{n}\right\}}$ — послідовність наближень розглянутого алгоритму знаходження кореня ${\displaystyle x^{*}}$ деякого рівняння, тоді швидкість збіжності ${\displaystyle \beta }$ визначають з рівняння:

${\displaystyle ||x_{n}-x^{*}||<\alpha ||x_{n-1}-x^{*}||^{\beta }}$

Для спрощення його переписують у вигляді:

${\displaystyle \log ||x_{n}-x^{*}||<\log \alpha +\beta \log ||x_{n-1}-x^{*}||}$

Безпосередньо швидкість збіжності оцінюють за тангенсом кута нахилу логарифмічного графіка залежності ${\displaystyle ||x_{n}-x^{*}||}$ від ${\displaystyle ||x_{n-1}-x^{*}||}$.

Література

1. Амосов А. А., Дубинский Ю. А., Копченова Н. В. Вычислительные методы для инженеров. — М. : Мир, 1998.
2. Бахвалов Н. С., , Кобельков Г. Г. Численные методы. — 8-е изд. — М. : Лаборатория Базовых Знаний, 2000.
3. Волков Е. А. Численные методы. — М. : , 2003.