Порядок сходимости: как его измерить

Урок про то, как количественно сравнивать методы: что такое порядок сходимости и как извлечь его прямо из чисел эксперимента.

Порядок сходимости $p$ — число, для которого $e_{n+1} \approx C \cdot e_n^p$, где $e_n$ — ошибка на шаге $n$. При $p=1$ сходимость линейная, при $p=2$ — квадратичная.

Зачем нужен порядок

«Этот метод быстрее» — расплывчато. Порядок сходимости делает сравнение точным. Он отвечает на вопрос: если ошибка на шаге равна $e$, какой она станет на следующем? Линейный метод ($p=1$) умножает ошибку на постоянный множитель $C \lt 1$ — число верных цифр растёт равномерно. Квадратичный ($p=2$) возводит ошибку в квадрат — число верных цифр удваивается. Кубический утраивает. Разница колоссальна: чтобы добраться до 15 цифр, линейному методу нужны десятки шагов, квадратичному — единицы.

Как измерить p из эксперимента

Если знаем точный корень $r$, считаем ошибки $e_n = |x_n - r|$ и логарифмируем соотношение $e_{n+1} \approx C \cdot e_n^p$. Логарифм превращает степень в множитель: $\ln e_{n+1} \approx \ln C + p \cdot \ln e_n$. Беря две соседние пары, исключаем $C$ и выражаем $p$:

$$p \approx \frac{\ln(e_{n+1}/e_n)}{\ln(e_n/e_{n-1})}$$

import math

# Ньютон для x^2 - 3 = 0, измеряем порядок по последовательности ошибок
r = math.sqrt(3)
xs = [2.0]
for _ in range(6):
    x = xs[-1]
    xs.append(x - (x*x - 3) / (2*x))

errs = [abs(x - r) for x in xs]
print("шаг |   ошибка    | оценка p")
print("-" * 34)
for i in range(1, len(errs) - 1):
    if errs[i-1] > 0 and errs[i] > 0 and errs[i+1] > 0:
        p = math.log(errs[i+1] / errs[i]) / math.log(errs[i] / errs[i-1])
        print(f" {i}  | {errs[i]:.3e} |  p ≈ {p:.3f}")

Вывод:

шаг |   ошибка    | оценка p
----------------------------------
 1  | 1.795e-02 |  p ≈ 1.951
 2  | 9.205e-05 |  p ≈ 1.998

Оценка $p$ уверенно стремится к 2 — численный эксперимент подтверждает теоретическую квадратичную сходимость Ньютона. Так же можно «поймать» порядок 1.618 у секущих или 1 у бисекции. Это мощный приём отладки: если метод, который должен быть квадратичным, на практике даёт $p \approx 1$ — что-то не так (например, корень кратный или ошибка в производной).

Как работает под капотом

Почему именно логарифмы? Соотношение $e_{n+1} = C \cdot e_n^p$ — степенное, а график степенной зависимости в двойных логарифмических осях — прямая с наклоном $p$. Мы фактически измеряем наклон этой прямой по двум точкам. Тонкость: оценка надёжна только в «асимптотическом режиме» — когда приближения уже близки к корню, но ошибки ещё не упёрлись в машинный эпсилон (на последних шагах $e_n$ становится порядка $10^{-16}$, и логарифм шумит). Поэтому смотрят на средние шаги последовательности, отбрасывая и слишком ранние, и слишком поздние.

Частые ошибки

• Мерить p на «дальних» или «слишком близких» шагах. Вдали от корня асимптотика ещё не наступила, у машинного эпсилона ошибки — шум. Берите середину.
• Забывать про кратные корни. У кратного корня Ньютон даёт $p=1$, а не 2 — это не баг, а математика; лечится модифицированным Ньютоном.
• Путать порядок и скорость на шаг. Метод более высокого порядка может на старте отставать; порядок описывает асимптотику, поведение вблизи корня.

Итоги

• Порядок сходимости $p$: $e_{n+1} \approx C \cdot e_n^p$; $p=1$ линейный, $p=2$ квадратичный, $\approx 1.618$ у секущих.
• Измеряют его по формуле $p \approx \frac{\ln(e_{n+1}/e_n)}{\ln(e_n/e_{n-1})}$ на средних шагах.
• Численная оценка $p$ — инструмент проверки: расхождение с теорией сигналит о проблеме (кратный корень, ошибка в коде).
• Порядок — асимптотическое свойство: важно поведение вблизи корня, а не на старте.