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

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

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

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

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

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

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

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

$| | x_{n} - x^{*} | | < α | | x_{n - 1} - x^{*} | |^{β}$

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

$\log | | x_{n} - x^{*} | | < \log α + β \log | | x_{n - 1} - x^{*} | |$

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

Література

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

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

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

Література

Навігаційне меню

Пошук