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

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

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

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

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

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

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

p ≈ 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 ≈ 1 — что-то не так (например, корень кратный или ошибка в производной).

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

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

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

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

Итоги

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