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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Понятие скорости сходимости[править | править вики-текст]

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