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

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

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

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

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

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

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

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

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

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

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

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

Література

1. Шаблон:Книга
2. Шаблон:Книга
3. Шаблон:Книга