🔢 Численные методы

Экстраполяция Ричардсона

англ. Richardson extrapolation

Комбинация двух расчётов с шагами h и h/2 убивает главный член ошибки: (2^p·A(h/2) − A(h))/(2^p − 1) даёт следующий порядок точности почти бесплатно.

Два смазанных кадра одного события способны дать резкий: если известен закон смазывания, его можно вычесть. Экстраполяция Ричардсона делает это с численными методами. Пусть расчёт с шагом $h$ даёт ответ $A (h) = A^{*} + C h^{p} + \dots$ , где $A^{*}$ — точное значение, а $p$ — порядок метода. Тогда комбинация двух расчётов $(2^{p} A (h /2) - A (h)) / (2^{p} - 1)$ уничтожает главный член ошибки и выдаёт ответ порядка $p + 1$ — почти бесплатно: второй расчёт всё равно часто нужен ради контроля. Степень $p$ берётся из теории метода, не с потолка.

Классика жанра — трапеции в интеграле $\int_{- 1}^{1} x^{2} d x = 2/3$ . Грубая сетка с узлами $- 1, 0, 1$ даёт $T (1) = 1$ , сетка вдвое мельче — $T (1/2) = 0.75$ ; ошибки $1/3$ и $1/12$ относятся ровно как $4 : 1$ , что выдаёт порядок $p = 2$ . Комбинация $(4 \cdot 0.75 - 1) /3 = 2/3$ попадает в точный ответ: у квадратичной функции члены $h^{4}$ , $h^{6}$ пусты. Из таких слоёв экстраполяции собирается таблица Ромберга. Бонус: разность двух расчётов — готовая апостериорная оценка ошибки. Интегральный контекст — в уроке численное интегрирование, источник разложений — в терминах ряд Тейлора, управление шагом в ОДУ — в численном решении ОДУ.

A^{*} \approx \frac{2 ^{p} A ( h /2 ) - A ( h )}{2 ^{p} - 1}, если A (h) = A^{*} + C h^{p} + \dots

трапеции для

\int_{- 1}^{1} x^{2} d x

T (1) = 1

T (1/2) = 0.75

, комбинация

(4 \cdot 0.75 - 1) /3 = 2/3

— точный ответ; главный член ошибки

h^{2}

уничтожен

Частые вопросы

Откуда берётся степень p?

Из теории метода, а не из догадки. Для трапеций разложение Эйлера–Маклорена даёт $p = 2$ , для центральной разности производной тоже $2$ , для Рунге–Кутты четвёртого порядка — $4$ . Если порядок неизвестен, его оценивают по трём расчётам через логарифм отношения разностей соседних приближений. Ошибка в $p$ фатальна: комбинация перестаёт убивать главный член и может даже усилить погрешность, поэтому на практике порядок проверяют по фактической сходимости.

Чем это лучше простого уменьшения шага?

Скоростью и бесплатностью. Уменьшение шага вдвое снижает ошибку в $2^{p}$ раз, но требует повторять весь расчёт на мелкой сетке. Экстраполяция комбинирует уже готовые расчёты и поднимает порядок точности почти без новых затрат — за пару арифметических действий. Дополнительный подарок: расхождение двух расчётов служит оценкой достигнутой точности, нужной для автоматического контроля шага. Ограничение одно, но жёсткое: разложение по степеням $h$ должно существовать — грубые особенности его отменяют.