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

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

Понятие скорости сходимости

Пусть $\left\{x_n\right\}\!$ — последовательность приближений рассматриваемого алгоритма нахождения корня $x^*\!$ некоторого уравнения, тогда:

Говорят, что метод обладает линейной сходимостью, если $\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\!$, если $\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\!$.

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

Практическое определение

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

$||x_i-x_n||<\alpha||x_{i-1}-x_n||^\beta\!$

Для упрощения его переписывают в виде:

$\log||x_i-x_n||<\log\alpha+\beta\log||x_{i-1}-x_n||\!$

Непосредственно скорость сходимости оценивают по тангенсу угла наклона логарифмического графика зависимости $||x_i-x_n||\!$ от $||x_{i-1}-x_n||\!$.

Литература по теме

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