Русская Википедия:Скорость сходимости
Скорость сходимости является основной характеристикой численных методов решения уравнений и оптимизации.
Понятие скорости сходимости
Пусть <math>\left\{x_n\right\}</math> — сходящаяся последовательность приближений некоторого алгоритма нахождения корня уравнения или экстремума функции <math>x^*</math>, тогда:
Говорят, что метод обладает линейной сходимостью, если <math>\exist \alpha \in (0,\;1):\quad \exist N\in \mathbb{N},\;\forall n\geq N \quad ||x_n-x^*||<\alpha||x_{n-1}-x^*||</math>.
Говорят, что метод обладает сходимостью степени <math>\beta</math>, если <math>\exist \alpha \in (0,\;1]:\quad \exist N\in \mathbb{N},\;\forall n\geq N \quad ||x_n-x^*||<\alpha||x_{n-1}-x^*||^\beta</math>.
Отметим, что обычно скорость сходимости методов не превышает квадратичной. В редких случаях метод может обладать кубической скоростью сходимости (метод Чебышёва).
Практическое определение
Пусть <math>\left\{x_n\right\}</math> — последовательность приближений рассматриваемого алгоритма нахождения корня <math>x^*</math> некоторого уравнения, тогда скорость сходимости <math>\beta</math> определяют из уравнения:
<math>||x_n-x^*||<\alpha||x_{n-1}-x^*||^\beta</math>
Для упрощения его переписывают в виде:
<math>\log||x_n-x^*||<\log\alpha+\beta\log||x_{n-1}-x^*||</math>
Непосредственно скорость сходимости оценивают по тангенсу угла наклона логарифмического графика зависимости <math>||x_n-x^*||</math> от <math>||x_{n-1}-x^*||</math>.
Литература по теме
