Русская Википедия:Скорость сходимости

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

Пусть <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>.

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

1. Шаблон:Книга
2. Шаблон:Книга
3. Шаблон:Книга