Скорость сходимости

---

Скорость сходимости является основной характеристикой численных методов решения уравнений и оптимизации.

Пусть ${\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 }}$.

Отметим, что обычно скорость сходимости методов не превышает квадратичной. В редких случаях метод может обладать кубической скоростью сходимости (метод Чебышёва).

---