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

Как получить высокую точность из грубых вычислений?

В вычислительной математике существует изящный и невероятно мощный прием, позволяющий искусственно повысить точность практически любого численного алгоритма без изменения его внутренней логики. Этот метод называется экстраполяцией Ричардсона, в честь британского физика Льюиса Фрая Ричардсона, который активно применял его в начале 20 века при решении задач метеорологии и гидродинамики. Идея Ричардсона настолько красива, что ее часто называют математическим фокусом или «магией» ускорения сходимости.

Допустим, у нас есть простой алгоритм для вычисления какой-либо величины (производной, определенного интеграла или решения ОДУ), который имеет низкий порядок точности. Пусть его ошибка пропорциональна квадрату шага сетки O(h^2). Если мы посчитаем значение с шагом h, мы получим грубый ответ. Если мы посчитаем значение с вдвое меньшим шагом (h/2), мы получим более точный ответ (ошибка уменьшится в 4 раза). Идея Ричардсона заключается в том, чтобы взять эти два приближенных результата и алгебраически скомбинировать их так, чтобы главный член ошибки O(h^2) взаимно уничтожился (вычелся). В результате мы получаем новую оценку, погрешность которой пропорциональна уже O(h^4) — то есть алгоритм второго порядка мгновенно превращается в алгоритм четвертого порядка практически бесплатно!

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

Наиболее известное и триумфальное применение экстраполяции Ричардсона было предложено Вернером Ромбергом в 1955 году для задачи численного интегрирования. Алгоритм получил название метод (или процесс) Ромберга. Базой для этого метода служит самая простая и грубая квадратурная формула — составной метод трапеций.

Формула Эйлера-Маклорена доказывает, что ошибка метода трапеций раскладывается в бесконечный ряд только по четным степеням шага h (h^2, h^4, h^6 и т.д.). Алгоритм Ромберга использует этот факт на полную мощность. Вычисления организуются в виде треугольной таблицы. В первый столбец записываются результаты вычисления интеграла методом трапеций с последовательным делением шага пополам (1 разбиение, 2, 4, 8, 16...). Это самая ресурсоемкая часть алгоритма. Затем начинается магия экстраполяции.

Построение треугольной таблицы и феноменальная сходимость

Второй столбец таблицы формируется путем применения экстраполяции Ричардсона к соседним элементам первого столбца. Удивительно, но элементы второго столбца математически строго совпадают с результатами, которые дал бы метод Симпсона (точность O(h^4)). Но мы на этом не останавливаемся! Мы применяем ту же формулу экстраполяции (с измененными коэффициентами) к элементам второго столбца, формируя третий столбец, ошибка которого имеет порядок O(h^6) (метод Буля). Процесс продолжается до тех пор, пока мы не дойдем до вершины треугольника.

Последнее число в этой таблице представляет собой экстраполированное значение интеграла при шаге h, стремящемся к нулю. Метод Ромберга обладает феноменальной скоростью сходимости для гладких функций. Чтобы получить 10 верных знаков после запятой, методу трапеций могут потребоваться миллионы узлов сетки. Метод Ромберга достигает той же машинной точности, вычислив функцию всего в нескольких десятках точек. Этот алгоритм стал классическим примером того, как глубокое понимание структуры погрешности (ряда Тейлора) позволяет инженерам многократно экономить вычислительные мощности суперкомпьютеров.