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

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

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

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

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

$$\begin{aligned} A(h) &= A + C \cdot h^p \\ A(h/2) &= A + C \cdot (h/2)^p = A + \frac{C \cdot h^p}{2^p} \end{aligned}$$

Это система из двух уравнений с двумя неизвестными ($A$ и $C \cdot h^p$). Решив её относительно $A$, исключаем главный член ошибки: $A \approx \frac{2^p \cdot 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$ ошибается на $9 \cdot 10^{-4}$, а после экстраполяции Ричардсона — на $1.1 \cdot 10^{-7}$, в восемь тысяч раз точнее, из тех же двух вычислений. Порядок подскочил со второго до четвёртого: при делении $h$ вдвое ошибка Ричардсона падает в $16$ раз ($1.1 \cdot 10^{-7} \to 7 \cdot 10^{-9}$), а не в 4.

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

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

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

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

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

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

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

Итоги

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