Сверхлинейная сходимость¶

Сверхлинейная сходимость — это свойство последовательности приближений (например, в итерационных численных методах), при котором скорость уменьшения ошибки на каждом шаге опережает линейную, то есть отношение ошибки на текущем шаге к ошибке на предыдущем стремится к нулю. В математическом анализе и вычислительной математике сверхлинейная сходимость является одним из наиболее желательных типов сходимости, так как она обеспечивает быстрое достижение заданной точности при относительно небольшом числе итераций.

¶Определение и формализация

Пусть \(\{x_k\}\) — последовательность, сходящаяся к пределу \(x^*\). Говорят, что последовательность сходится сверхлинейно, если существует такая последовательность положительных чисел \(\{\alpha_k\}\), что \(\alpha_k \to 0\) и для всех достаточно больших \(k\) выполняется неравенство:

\[ \|x_{k+1} - x^\| \leq \alpha_k \|x_k - x^\|. \]

Более распространённое эквивалентное определение: последовательность сходится сверхлинейно, если

\[ \lim_{k \to \infty} \frac{\|x_{k+1} - x^\|}{\|x_k - x^\|} = 0. \]

Это означает, что на каждом шаге ошибка уменьшается в прогрессии, которая сама по себе ускоряется. В отличие от линейной сходимости, где отношение ошибок стремится к некоторой константе \(q \in (0,1)\), при сверхлинейной сходимости это отношение стремится к нулю.

¶Классификация по порядку сходимости

Сверхлинейная сходимость является частным случаем более общего понятия порядка сходимости. Если существует такое число \(p > 1\) и константа \(C > 0\), что

\[ \|x_{k+1} - x^\| \leq C \|x_k - x^\|^p, \]

то говорят о сходимости порядка \(p\). При \(p = 2\) сходимость называется квадратичной, при \(p = 3\) — кубической и т. д. Квадратичная сходимость — наиболее часто встречающийся на практике случай сверхлинейной сходимости. Например, метод Ньютона для решения нелинейных уравнений при определённых условиях обеспечивает квадратичную сходимость.

¶Примеры методов со сверхлинейной сходимостью

¶Метод Ньютона (касательных)

Для решения уравнения \(f(x) = 0\) метод Ньютона задаётся итерацией: \[ x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}. \] Если начальное приближение достаточно близко к корню и производная \(f'\) не обращается в нуль, то сходимость квадратичная, то есть сверхлинейная.

¶Метод секущих

В методе секущих производная заменяется конечной разностью: \[ x_{k+1} = x_k - f(x_k) \frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}. \] Порядок сходимости этого метода равен золотому сечению \(\varphi \approx 1.618\), что также является сверхлинейным.

¶Метод парабол (Мюллера)

Используется для нахождения корней многочленов. Сходимость сверхлинейная с порядком около 1.84.

¶Методы сопряжённых градиентов

В задачах оптимизации (например, метод Флетчера — Ривза) для квадратичных функций с положительно определённой матрицей Гессе сходимость является сверхлинейной (на практике — за конечное число шагов, равное размерности пространства). Для неквадратичных функций — сверхлинейная вблизи минимума.

¶Метод Левенберга — Марквардта

Комбинация метода Ньютона и градиентного спуска. В окрестности решения ведёт себя как метод Ньютона и демонстрирует сверхлинейную сходимость.

¶Связь с другими типами сходимости

• Линейная сходимость: \(\|x_{k+1} - x^\| \leq q \|x_k - x^\|\) с \(0 < q < 1\). Скорость постоянна (геометрическая прогрессия).
• Сверхлинейная сходимость: отношение ошибок стремится к нулю.
• Сублинейная сходимость: скорость меньше линейной, например, \( \|x_k - x^*\| \sim 1/k \).

Сверхлинейная сходимость занимает промежуточное положение между линейной и квадратичной, но формально включает в себя квадратичную и более высокие порядки.

¶Условия достижения сверхлинейной сходимости

Для большинства итерационных методов сверхлинейная сходимость не гарантируется глобально. Как правило, она достигается лишь в некоторой окрестности решения (локальная сходимость). Основные условия:

• Гладкость функции: функция должна быть достаточно гладкой (например, дважды непрерывно дифференцируемой для метода Ньютона).
• Невырожденность: в точке решения матрица первых производных (якобиан) или вторая производная (гессиан) не должны быть вырожденными.
• Хорошее начальное приближение: начальная точка должна быть достаточно близка к решению.

При нарушении этих условий сходимость может стать линейной, сублинейной или вовсе отсутствовать.

¶Применение в численных методах

Сверхлинейная сходимость особенно важна в задачах, где каждая итерация требует значительных вычислительных затрат (например, решение больших систем нелинейных уравнений, оптимизация с большим числом переменных). Быстрое уменьшение ошибки позволяет сократить общее число итераций, что критично для задач реального времени или при работе с дорогостоящими вычислениями (например, в методе конечных элементов, в задачах гидродинамики, в машинном обучении при обучении нейронных сетей).

В некоторых методах (например, в методе Ньютона) сверхлинейная сходимость достигается за счёт вычисления производных, что может быть дорого. Альтернативные методы (секущих, Бройдена) жертвуют порядком сходимости (сверхлинейный, но не квадратичный) ради снижения затрат на итерацию.

¶Ограничения и критика

• Локальность: сверхлинейная сходимость часто гарантируется только в малой окрестности решения. Для глобальной сходимости требуются дополнительные техники (линейный поиск, доверительные области).
• Чувствительность к начальному приближению: при плохом начальном приближении метод может расходиться или сходиться медленно (линейно).
• Вычислительная сложность: методы с квадратичной сходимостью (например, Ньютона) требуют вычисления производных, что может быть затруднительно или невозможно для сложных функций (например, «чёрных ящиков»).
• Численная устойчивость: при близости к решению возможна потеря значащих цифр из-за деления на малые числа (в методе Ньютона — на малую производную).

¶Источники

• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином. Лаборатория знаний, 2008.
• Дэннис Дж., Шнабель Р. Численные методы безусловной оптимизации и решения нелинейных уравнений. — М.: Мир, 1988.
• Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. — М.: Мир, 1975.
• Сухарев А. Г., Тимохов А. В., Фёдоров В. В. Курс методов оптимизации. — М.: Наука, 1986.