Введение

Метод ускорения сходимости последовательности в численном анализе

В численном анализе экстраполяция Ричардсона — это метод ускорения сходимости, используемый для повышения скорости сходимости последовательности приближений некоторого значения. По сути, имея значения для нескольких значений , мы можем оценить , экстраполируя эти приближения к . Метод назван в честь Льюиса Фрая Ричардсона, который ввёл эту технику в начале XX века, хотя сама идея была известна Кристиану Гюйгенсу при вычислении . По словам Биркгоффа и Роты, "его полезность для практических вычислений трудно переоценить". Практические применения экстраполяции Ричардсона включают интеграцию Ромберга, которая применяет экстраполяцию Ричардсона к методу трапеций, и алгоритм Булирша — Штёра для решения обыкновенных дифференциальных уравнений.

Цель

Экстраполяция Ричардсона — это процесс, позволяющий получить более точное приближение, изменяя формулу ошибки с ε на ε². Таким образом, заменяя h на h/2, ошибка отсечения уменьшается с ε до ε²/2 при том же шаге. Общая закономерность заключается в том, что φ(h/2) является более точной оценкой, чем φ(h). С помощью этого процесса мы достигли лучшего приближения, вычтя наибольший член в ошибке, который был равен ε. Этот процесс можно повторить для удаления дополнительных членов ошибки и получения еще более точных приближений.

Свойства

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