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

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

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

Пусть $\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. Шаблон:Книга