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

Экстраполя́ция Ри́чардсона, метод ускорения сходимости решений разностных задач (см. Аппроксимация дифференциальной краевой задачи разностной). Основная идея метода состоит в исследовании решения ${\displaystyle u_{h}(x)}$ сходящейся разностной задачи при фиксированных ${\displaystyle x}$ как функции параметра ${\displaystyle h}$ разностной сетки, стремящегося к нулю, в подборе подходящей интерполяционной функции ${\displaystyle \operatorname {ch} i(h)}$, построенной по нескольким значениям решения ${\displaystyle u_{h}(x)}$ при различных ${\displaystyle h}$, и вычислении величины ${\displaystyle \operatorname {ch} i(0)}$, являющейся приближённым значением искомого решения ${\displaystyle u(x)}$ – предела последовательности ${\displaystyle u_{h}(x)}$ при ${\displaystyle h\to 0}$. Чаще всего функция ${\displaystyle \operatorname {ch} i(h)}$ ищется в виде интерполяционного многочлена от ${\displaystyle h}$.

Метод носит имя Л. Ричардсона (^[1]), который впервые использовал его как средство для улучшения точности решений разностных задач и называл постепенным переходом к пределу.

Теоретической основой применимости метода служит существование разложения вида

${\displaystyle u_{h}(x)=u(x)+\sum _{i=1}^{m-1}h^{\beta _{i}}\nu _{i}(x)+h^{B}\eta _{h}(x)}$,

где ${\displaystyle B>\beta _{m-1}>\dots >\beta _{1}>0}$ и функции ${\displaystyle \nu _{i}}$ не зависят от ${\displaystyle h}$, а ${\displaystyle \eta _{h}(x)}$ – значения сеточной функции, ограниченные при ${\displaystyle h\to 0}$. Имеется несколько теоретических приёмов для выяснения существования таких разложений (^[2]).

Чаще всего используется линейная экстраполяция: с помощью ${\displaystyle m}$ значений ${\displaystyle u_{h}(x)}$ в одной точке ${\displaystyle x}$ для различных параметров ${\displaystyle h=h_{1},\dots ,h_{m}}$ вычисляется экстраполированное значение ${\displaystyle u_{H}(x)}$ по правилу

${\displaystyle u_{H}(x)=\ \sum _{k=1}^{m}\gamma _{k}u_{h_{k}}(x)}$,

где веса ${\displaystyle \gamma _{k}}$ определяются из системы уравнений:

${\displaystyle \sum _{k=1}^{m}\gamma _{k}=1;\quad \sum _{k=1}^{m}\gamma _{k}h_{k}^{\beta _{i}}=0,\quad i=1,\dots ,m-1}$.

Если среди ${\displaystyle h_{k}}$ нет слишком близких значений, то

${\displaystyle \mid u_{H}(x)-u(x)\mid =O({h\!\!\!\!{^{-}}}^{B})}$,

где ${\displaystyle h\!\!\!\!{^{-}}}=\max \limits _{1\leqslant k\leqslant m}h_{k}$, то есть величина ${\displaystyle u_{H}(x)}$ сходится к ${\displaystyle u(x)}$ при ${\displaystyle h\to 0}$ с порядком ${\displaystyle B}$, что больше ${\displaystyle \beta _{1}}$ – порядка сходимости ${\displaystyle u_{h}(x)}$ к ${\displaystyle u(x)}$. В двух частных случаях существуют алгоритмы вычисления величины ${\displaystyle u_{H}(x)}$, минуя определение коэффициентов ${\displaystyle \gamma _{k}}$:

а) в случае ${\displaystyle \beta _{i}=ip}$, ${\displaystyle p>0}$, ${\displaystyle i=1,\dots ,m-1}$, метод приводит к интерполяции многочлена от ${\displaystyle h^{p}}$ и из свойств интерполяционной формулы Лагранжа следует, что

${\displaystyle u_{H}(x)=a_{1}^{(m-1)}}$,

где

${\displaystyle a_{j}^{(0)}=u_{h_{j}}(x),\quad j=1,2,\dots ,m}$;

${\displaystyle {\begin{aligned}a_{j}^{(i)}=a_{j+1}^{(i-1)}+{\frac {a_{j+1}^{(i-1)}-a_{j}^{(i-1)}}{(h_{j}/h_{i+j})^{p-1}}}\;,\quad (*)\\j=1,\dots ,m-i,\quad i=1,\dots ,m-1\end{aligned}}}$

б) в случае ${\displaystyle h_{i}=h_{0}b^{i}}$, ${\displaystyle 0<b<1}$, ${\displaystyle i=1,\dots ,m-1}$, формула ${\displaystyle (*)}$ заменяется следующей:

${\displaystyle a_{j}^{(i)}=a_{j+1}^{(i-1)}+{\frac {a_{j+1}^{(i-1)}-a_{j}^{(i-1)}}{b^{\beta _{i-1}}}}}$.

Этот алгоритм, называемый правилом Ромберга (^[3]), нашёл распространение при конструировании квадратурных формул (см. ^[4]). Для того чтобы при различных ${\displaystyle h_{i}}$ сетки ${\displaystyle D_{h_{i}U}}$ (см. Аппроксимация дифференциального оператора разностным) имели возможно больше общих узлов для осуществления экстраполяции Ричардсона, параметры ${\displaystyle h_{i}}$ выбирают как часть одной из последовательностей: ${\displaystyle h_{i}=h_{0}/i}$, ${\displaystyle i=1,2,\dots }$; ${\displaystyle h_{i}=h_{0}2^{1-i}}$, ${\displaystyle i=1,2,\dots }$; ${\displaystyle h_{0}}$, ${\displaystyle h_{0}/2}$, ${\displaystyle h_{0}/3}$, ${\displaystyle h_{0}/4}$, ${\displaystyle h_{0}/6}$, ${\displaystyle h_{0}/8}$, ${\displaystyle h_{0}/12,\dots }$.

Линейная экстраполяция не является единственно возможной. Например, в случае ${\displaystyle \beta _{i}=ip}$, ${\displaystyle p>0}$, в качестве интерполяционной функции ${\displaystyle \operatorname {ch} i(h)}$ используют рациональные функции вида ${\displaystyle \varphi (h^{p})/\psi (h^{p})}$, где ${\displaystyle \varphi (t)}$, ${\displaystyle \psi (t)}$ – многочлены от ${\displaystyle t}$ степени ${\displaystyle [(m-1)/2]}$ и ${\displaystyle [m/2]}$ соответственно. Тогда результат рациональной экстраполяции ${\displaystyle u_{H}(x)=\operatorname {ch} i(0)}$ может быть вычислен с помощью рекуррентной процедуры:

${\displaystyle d_{j}^{(-1)}=0,\quad j=2,\dots ,m}$;

${\displaystyle d_{j}^{(0)}=u_{h_{j}}(x),\quad j=1,2,\dots ,m}$;

${\displaystyle {\begin{aligned}d_{j}^{(i)}=d_{j+1}^{(i-1)}+\left(d_{j+1}^{(i-1)}-d_{j}^{(i-1)}\right)\times \left\{\left({\frac {h_{j}}{h_{i+j}}}\;\right)^{p}\left[1-{\frac {d_{j+1}^{(i-1)}-d_{j}^{(i-1)}}{d_{j+1}^{(i-1)}-d_{j+1}^{(i-1)}}}\;\right]-1\right\}^{-1},\\j=1,\dots ,m-i,\quad i=1,\dots ,m-1;\\\quad u_{H}(x)=d_{1}^{(m-1)}\end{aligned}}}$

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