Экстраполяция Ричардсона: бесплатно повысить порядок

Урок про экстраполяцию Ричардсона — универсальный приём, превращающий метод низкого порядка в метод высокого почти бесплатно.

Экстраполяция Ричардсона комбинирует приближения на двух сетках (с шагами h и h/2) так, чтобы главный член ошибки сократился, повышая порядок результата.

Идея: знать, как устроена ошибка

Допустим, метод имеет известный порядок p: его ошибка ведёт себя как A(h) = A + C·h^p + ..., где A — точный ответ. Тогда у нас два уравнения — для шага h и для h/2:

A(h)   = A + C·h^p
A(h/2) = A + C·(h/2)^p = A + C·h^p / 2^p

Это система из двух уравнений с двумя неизвестными (A и C·h^p). Решив её относительно A, исключаем главный член ошибки: A ≈ (2^p·A(h/2) − A(h)) / (2^p − 1). Полученная комбинация точнее обоих исходных приближений — её порядок на две единицы выше (для чётных схем). Мы не делали лишней работы — лишь умно скомбинировали то, что уже посчитали.

import math

# Центральная разность — порядок p=2. Применим Ричардсона.
def разность(f, x, h):
    return (f(x + h) - f(x - h)) / (2 * h)

def ричардсон(f, x, h, p=2):
    A_h  = разность(f, x, h)
    A_h2 = разность(f, x, h / 2)
    return (2**p * A_h2 - A_h) / (2**p - 1)

f = math.sin
x = 1.0
истина = math.cos(1.0)            # производная sin = cos
print(f"{'h':>6} | {'центральная':>14} | {'Ричардсон':>14}")
print("-" * 40)
for h in [0.1, 0.05]:
    ц = abs(разность(f, x, h) - истина)
    р = abs(ричардсон(f, x, h) - истина)
    print(f"{h:6} | {ц:14.2e} | {р:14.2e}")

Вывод:

     h |    центральная |      Ричардсон
----------------------------------------
   0.1 |       9.00e-04 |       1.13e-07
  0.05 |       2.25e-04 |       7.03e-09

Сравните столбцы: центральная разность при h=0.1 ошибается на 9e-4, а после экстраполяции Ричардсона — на 1.1e-7, в восемь тысяч раз точнее, из тех же двух вычислений. Порядок подскочил со второго до четвёртого: при делении h вдвое ошибка Ричардсона падает в 16 раз (1.1e-7 → 7e-9), а не в 4.

Где это применяется

Ричардсон — не трюк для одной задачи, а общий принцип, работающий везде, где известен порядок ошибки:

Особенно красив метод Ромберга: берём трапеции на сетках h, h/2, h/4, ... и многократно экстраполируем — каждый столбец таблицы поднимает порядок на 2. Несколько трапециевидных приближений превращаются в результат точности Гаусса.

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

Экстраполяция Ричардсона — частный случай идеи «знать асимптотику ошибки и вычесть её». Тот же приём мы уже видели в адаптивном Симпсоне: слагаемое (L+R−целое)/15 — это ричардсоновская поправка (15 = 2⁴ − 1 для порядка 4). Условие применимости: ошибка должна действительно раскладываться по степеням h с известным p — это верно для гладких функций и регулярных методов, но ломается у функций с особенностями (там Ричардсон может даже ухудшить результат). Поэтому экстраполяцию применяют осознанно, проверяя, что приближения ведут себя «по теории».

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

• Применять с неверным p. Формула опирается на точный порядок метода; ошибка в p испортит комбинацию.
• Экстраполировать у особенностей. Если ошибка не раскладывается по h^p (разрыв, корневая особенность), Ричардсон может ухудшить, а не улучшить.
• Брать слишком малый h для базы. На крошечных шагах вмешивается округление, и асимптотика метода нарушается — экстраполяция «поплывёт».

Итоги

• Экстраполяция Ричардсона комбинирует приближения на сетках h и h/2, сокращая главный член ошибки.
• Порядок результата поднимается (для чётных схем — на 2) почти бесплатно: лишь умное сочетание готовых вычислений.
• Основа метода Ромберга (интегрирование) и поправок в адаптивных схемах.
• Требует, чтобы ошибка раскладывалась по h^p с известным p; у особенностей не применима.