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

Скорость сходимости — это характеристика того, как быстро последовательность приближений приближается к пределу при увеличении числа итераций, объёма данных или числа выборок. Формально она описывает, насколько быстро убывает ошибка $e_{k} = ∣ x_{k} - x^{*} ∣$ или $e_{n} = ∣ a_{n} - a ∣$ .

Разные задачи и алгоритмы имеют разные скорости сходимости. Ниже — основные типы.

1. Формальные определения

Пусть $e_{k} = ∣ x_{k} - x^{*} ∣$ — ошибка на $k$ -й итерации, $x^{*}$ — предел.

Линейная сходимость

e_{k + 1} \leq q e_{k}, 0 < q < 1.

Ошибка убывает примерно в $q$ раз за итерацию. В логарифмическом масштабе — прямая линия.
Пример: метод простой итерации, градиентный спуск с постоянным шагом.

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

k \to \infty lim \frac{e _{k + 1}}{e _{k}} = 0.

Быстрее линейной, но медленнее квадратичной.
Пример: метод секущих (порядок $\approx 1.618$ ).

Квадратичная сходимость

e_{k + 1} \leq C e_{k}^{2} .

Число верных знаков примерно удваивается на каждой итерации.
Пример: метод Ньютона вблизи корня.

Кубическая и выше

e_{k + 1} \leq C e_{k}^{p}, p > 2.

Очень быстрая, но редкая. Пример: метод Чебышёва для корней.

Сублогарифмическая / сублинейная

Ошибка убывает, но медленнее любой геометрической прогрессии.
Пример: метод Монте-Карло: $e_{N} = O (1/ N)$ , то есть $e \sim N^{- 1/2}$ .

2. Сводная таблица

Тип	Формула	Что происходит	Пример
Сублинейная	$e_{k} \sim k^{- p}$	Медленно, полиномиально	Монте-Карло $p = 1/2$
Линейная	$e_{k + 1} \leq q e_{k}$	Ошибка умножается на $q$	Простая итерация, градиентный спуск
Сверхлинейная	$e_{k + 1} / e_{k} \to 0$	Быстрее линейной	Метод секущих
Квадратичная	$e_{k + 1} \leq C e_{k}^{2}$	Удвоение верных цифр	Метод Ньютона
Кубическая	$e_{k + 1} \leq C e_{k}^{3}$	Утроение верных цифр	Метод Чебышёва
Экспоненциальная	$e_{k} \leq C e^{- c k}$	Очень быстро	Некоторые спектральные методы

3. Скорость сходимости в разных контекстах

Численная оптимизация

Градиентный спуск: линейная (зависит от числа обусловленности).
Метод Ньютона: квадратичная вблизи минимума.
Квазиньютоновские методы (BFGS, L-BFGS): сверхлинейная.
Стохастический градиентный спуск (SGD): сублинейная $O (1/ k)$ или $O (1/ k)$ .

Итерационные методы решения уравнений

Метод простой итерации: линейная.
Метод секущих: сверхлинейная, порядок $φ \approx 1.618$ .
Метод Ньютона: квадратичная.
Метод бисекции: линейная, $q = 1/2$ .

Метод Монте-Карло

Ошибка оценки: $O (1/ N)$ , где $N$ — число выборок.
Чтобы уменьшить ошибку в 10 раз, нужно в 100 раз больше выборок.
Методы снижения дисперсии (importance sampling, antithetic variates) улучшают константу, но не порядок.

MCMC

Скорость сходимости к стационарному распределению зависит от:
- геометрии целевого распределения;
- корреляции между параметрами;
- выбора proposal distribution.
Диагностики: $\hat{R}$ , ESS, autocorrelation time.
Hamiltonian Monte Carlo обычно сходится быстрее, чем Metropolis–Hastings, благодаря использованию градиентов.

EM-алгоритм

Обычно линейная сходимость.
В некоторых задачах — сверхлинейная.
Может быть очень медленным, если данные «неполные» сильно.

Смешанные модели

Оценка ML/REML — итерационная (Newton–Raphson, EM, оптимизация).
Сходимость обычно линейная или сверхлинейная.
При сложной структуре случайных эффектов возможны медленная сходимость или её отсутствие.

Численное интегрирование

Квадратура Гаусса: ошибка $O (n^{- 2 m})$ для гладких функций, где $m$ связано с числом узлов.
Метод трапеций: $O (h^{2})$ .
Метод Симпсона: $O (h^{4})$ .
Монте-Карло: $O (N^{- 1/2})$ , независимо от размерности (но с большой константой).

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

Для последовательности случайных величин:

Закон больших чисел: сходимость по вероятности, $O (1/ N)$ .
Центральная предельная теорема: скорость сходимости к нормальному распределению $O (1/ N)$ (теорема Берри–Эссеена).
Скорость сходимости оценок: $N$ -состоятельность — стандарт в статистике.
Непараметрические оценки: медленнее, например $N^{- 2/5}$ для ядерной регрессии.

5. Как измерить скорость сходимости

Построить график ошибки $e_{k}$ от $k$ :
- в обычном масштабе — линейная сходимость выглядит как экспонента;
- в логарифмическом — линейная сходимость выглядит как прямая.
Оценить порядок $p$ : $lo g e_{k + 1} \approx p lo g e_{k} + const$ .
Оценить константу $q$ : $q \approx e_{k + 1} / e_{k}$ .
Для MCMC: $\hat{R}$ , ESS, autocorrelation function.
Для оптимизации: норма градиента, изменение функции, число итераций до допуска.

6. Что влияет на скорость сходимости

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

Быстрая сходимость — это хорошо, но она не гарантирует корректности: можно быстро сойтись к неправильному решению, если модель или предположения неверны.

LDS