Экстраполяция Ричардсона: как ускорить сходимость метода

Экстраполяция Ричардсона - приём, который позволяет из двух не очень точных численных приближений получить одно намного более точное, не меняя ни формулу метода, ни объём вычислений на каждом шаге. Идея работает для производных, интегралов, решений дифференциальных уравнений - везде, где приближение зависит от шага $h$ и известно, с каким порядком убывает его ошибка. Ниже разберём, откуда берётся формула экстраполяции, почему она гасит именно главный член ошибки и как её применять на конкретных числах. Чтобы сразу увидеть эффект, покрутите калькулятор ниже: он считает производную $\sin x$ центральной разностью с двумя шагами и показывает, насколько экстраполированное значение ближе к истине, чем каждое из исходных.

Идея метода: убрать главный член ошибки

Пусть численный метод даёт приближение $F(h)$ к истинному значению $F$, и известно, что ошибка ведёт себя как

$F(h) = F + C\,h^{p} + O(h^{p+1}),$

где $C$ - некоторая константа, не зависящая от $h$, а $p$ - порядок точности метода. Если посчитать это же приближение с вдвое меньшим шагом, $F(h/2) = F + C\,(h/2)^p + O(h^{p+1})$, то у нас появляются два уравнения с двумя неизвестными: сама величина $F$ и мешающий член $C h^p$. Комбинируя их так, чтобы член с $C$ сократился, получаем формулу экстраполяции Ричардсона:

$R = \frac{2^{p}\,F(h/2) - F(h)}{2^{p} - 1}.$

Эта комбинация всё ещё содержит ошибку, но уже не порядка $h^p$, а порядка $h^{p+1}$ (или выше, если в разложении отсутствуют промежуточные степени). Иными словами, из двух приближений сравнительно низкого порядка получается одно приближение существенно более высокого порядка - и всё это без единого нового вычисления значения функции сверх тех, что уже понадобились для $F(h)$ и $F(h/2)$.

Пример: ускорение производной центральной разностью

Самый наглядный пример - численное дифференцирование. Возьмём функцию $f(x) = \sin x$ и приближение производной центральной разностью:

$D(h) = \frac{f(x_0+h) - f(x_0-h)}{2h}.$

Разложив числитель в ряд Тейлора вокруг $x_0$, получаем

$D(h) = f'(x_0) + \frac{h^{2}}{6}\,f'''(x_0) + O(h^{4}),$

то есть погрешность центральной разности имеет порядок $p=2$: при уменьшении шага вдвое ошибка падает примерно в четыре раза. Здесь работает важная особенность симметричных формул - в разложении присутствуют только чётные степени $h$, поэтому следующий член после $h^2$ идёт сразу с $h^4$, а не с $h^3$.

Рассчитать для своей задачи

Как вывести формулу для конкретного порядка

Для центральной разности $p = 2$, поэтому общая формула $R = (2^p F(h/2) - F(h)) / (2^p - 1)$ превращается в

$R(h) = \frac{4\,D(h/2) - D(h)}{3}.$

Подставив сюда разложения $D(h)$ и $D(h/2)$, легко убедиться, что член с $h^2$ действительно сокращается: $4\big(f' + \tfrac{h^2}{24}f'''\big) - \big(f' + \tfrac{h^2}{6}f'''\big) = 3f' + 0\cdot h^2 + \dots$, а после деления на 3 остаётся $f'(x_0)$ плюс член порядка $h^4$. Именно поэтому важно знать порядок метода заранее - без него нельзя подобрать правильный множитель $2^p$, и сокращения не произойдёт.

Расчёт для конкретных чисел

Возьмём $x_0 = 1$ (радиан) и начальный шаг $h = 0{,}5$. Тогда

$D(0{,}5) = \frac{\sin 1{,}5 - \sin 0{,}5}{1} \approx 0{,}5181, \qquad D(0{,}25) = \frac{\sin 1{,}25 - \sin 0{,}75}{0{,}5} \approx 0{,}5347.$

Истинное значение производной - $f'(1) = \cos 1 \approx 0{,}5403$. Ошибка при шаге $0{,}5$ составляет примерно $-0{,}0222$, при шаге $0{,}25$ - около $-0{,}0056$: уменьшение шага вдвое дало уменьшение ошибки почти в четыре раза, как и предсказывает порядок $p=2$. Теперь соберём экстраполяцию:

$R = \frac{4 \cdot 0{,}5347 - 0{,}5181}{3} \approx 0{,}540232.$

Ошибка результата - примерно $-0{,}00007$, то есть почти в 320 раз меньше ошибки при шаге $0{,}5$ и на два порядка меньше ошибки при шаге $0{,}25$. Это и есть эффект перехода с порядка $h^2$ на порядок $h^4$: при следующем уполовинивании шага сырая разность ускорится в 4 раза, а экстраполяция Ричардсона - примерно в 16 раз.

Как быстро растёт точность с уменьшением шага

Чтобы увидеть разницу порядков глазами, удобно построить график ошибки от шага в логарифмических координатах по обеим осям. На таком графике степенная зависимость $\text{ошибка} \sim h^p$ превращается в прямую линию с наклоном $p$: у сырой центральной разности наклон около 2, у экстраполяции Ричардсона - около 4. Чем круче линия, тем быстрее метод набирает точность при уменьшении шага.

Продолжив уполовинивание шага дальше - до $h=0{,}125$, $h=0{,}0625$ и так далее, - легко проверить закономерность численно: отношение соседних ошибок сырой разности стабильно приближается к 4, а отношение соседних ошибок экстраполяции Ричардсона - к 16. Это прямое следствие показателя степени: при $p=2$ уменьшение шага вдвое уменьшает $h^2$ ровно в 4 раза, а при эффективном порядке 4 - в $2^4=16$ раз. Такая проверка на практике служит хорошим тестом правильности реализации: если отношение ошибок экстраполированных значений не приближается к ожидаемой степени двойки, значит, в вычислениях или в порядке $p$ есть ошибка.

Рассчитать для своей задачи

Метод Ромберга: экстраполяция для интегралов

Экстраполяция Ричардсона не привязана к производным - она применяется к любому методу с известным порядком ошибки. Классический пример - метод Ромберга: сначала интеграл считается методом трапеций с шагами $h$ и $h/2$ (порядок ошибки трапеций $p=2$), затем к двум результатам применяется та же формула $R = (4T(h/2) - T(h))/3$, что даёт точность уровня правила Симпсона без явного вычисления по формуле Симпсона. Если продолжить процесс, комбинируя уже экстраполированные значения между собой с новым порядком $p=4$, получится ещё более точное приближение - это и есть таблица Ромберга, где каждый столбец повышает порядок точности на единицу по сравнению с предыдущим.

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

• Неверно определён порядок метода. Если взять множитель $2^p$ не для того $p$, экстраполяция не устранит главный член ошибки, а исказит результат ещё сильнее.
• Шаги берутся не в отношении 2. Формула $R = (2^p F(h/2) - F(h))/(2^p-1)$ выведена именно для уполовинивания шага; при произвольном отношении шагов $r$ вместо $2^p$ нужно подставлять $r^p$.
• Путаница между сырым приближением и экстраполированным. После расчёта $R$ дальнейшие оценки точности нужно вести относительно $R$, а не продолжать сравнивать между собой исходные $F(h)$ и $F(h/2)$.
• Забыт следующий член разложения. Экстраполяция убирает только главный член ошибки; остаточный член $O(h^{p+1})$ никуда не девается, просто становится меньше на порядок.
• Применение к методу без гладкого разложения ошибки. Если функция имеет разрыв или особенность на отрезке, разложение $F(h) = F + Ch^p + \dots$ может не выполняться, и экстраполяция не даст ожидаемого ускорения.

FAQ

Зачем нужна экстраполяция Ричардсона, если можно просто уменьшить шаг? Уменьшение шага даёт линейный (по порядку метода) прирост точности и требует пропорционально больше вычислений в сложных задачах. Экстраполяция получает прирост на целый порядок практически бесплатно - используя уже посчитанные значения при двух шагах.

Можно ли применить экстраполяцию несколько раз подряд? Да, это и есть идея метода Ромберга: экстраполированные значения одного уровня комбинируются между собой по той же формуле, но с новым, увеличенным на единицу порядком $p$, и точность растёт дальше.

Какой порядок $p$ нужно знать заранее? Порядок ошибки самого базового метода: для центральной разности это $p=2$, для метода трапеций тоже $p=2$, для одностороннего разностного приближения производной - $p=1$. Порядок обычно известен из теоремы о разложении ошибки конкретного метода.

Что делать, если порядок метода неизвестен заранее? Его можно оценить экспериментально: посчитать приближение при трёх шагах $h$, $h/2$, $h/4$ и по отношению последовательных разностей $(F(h)-F(h/2))/(F(h/2)-F(h/4))$ найти степень двойки, которой равно это отношение - это и будет порядок $p$. Такой приём часто применяют, когда аналитический вывод разложения ошибки слишком громоздкий.

Коротко

Экстраполяция Ричардсона комбинирует два приближения одного и того же метода, посчитанные с шагами $h$ и $h/2$, по формуле $R = (2^p F(h/2) - F(h)) / (2^p - 1)$, где $p$ - известный порядок ошибки метода. Комбинация устраняет главный член ошибки и повышает точность результата на один порядок, а при повторном применении к уже экстраполированным значениям превращается в метод Ромберга. Приём работает для любых численных методов с гладким разложением ошибки по степеням шага - от производных до интегралов и разностных схем.