理查德森外推法

数值分析中，理查德森外推法用以改善序列收敛效率，它是在20世纪前期由英国数学家，物理学家，气象学家Lewis Fry Richardson提出的。在数值分析领域，Richardson外推法有很多实际应用，如隆贝格积分方法，是在梯形公式的基础上应用Richardson外推法导出的；还有用于求解常微分方程的Bulirsch–Stoer算法。

推导

假定某一函数$D$可数值近似（离散化）为$D\left( h \right)$，其中$h$为步长，

$D = D \left( h \right) + a h^p + b h^q + \ldots$ （1）

其中$p$为首项阶数，$q$下一项阶数, 满足$q > p$。

考虑该函数又可以使用同样的数值近似方法，以步长为$h_2$做离散近似

$D = D \left( h_2 \right) + a h_2^p + b h^q_2 + \ldots$ （2）

如果希望消掉式(1)中的$h^p$项，我们可以对以上两式相减，即(1)$- r$(2)，其中$r = \left( \frac{h}{h_2} \right)^p$：

$\left( 1 - r \right) D = D \left( h \right) + a h^p + b h^q - r D \left(h_2 \right) - r a h^p_2 - r b h^q_2 + \ldots = D \left( h \right) - r D \left( h_2 \right) + a \underbrace{\left( h^p - r h_2^p \right)}_0 + b \left( h^q - r h_2^q \right)$

$\left( 1 - r \right) D = D \left( h \right) - r D \left( h_2 \right) + b \left( h^q - r h_2^q \right)$

$D = \frac{D \left( h \right) - r D \left( h_2 \right)}{1 - r} + \frac{b\left( h^q - r h_2^q \right)}{1 - r} = \frac{D \left( h \right) - r D\left( h_2 \right)}{1 - r} + \frac{b \left( 1 - r \frac{h_2^q}{h^q}\right) h^q}{1 - r}$

$D = \frac{D \left( h \right) - r D \left( h_2 \right)}{1 - r} + \frac{b\left( 1 - \left( \frac{h}{h_2} \right)^p \left( \frac{h_2}{h} \right)^q \right) h^q}{1 - r} = \underbrace{\frac{D \left( h \right) - r D \left(h_2 \right)}{1 - r}}_{D^{\ast} \left( h \right)} + \underbrace{\frac{b\left( 1 - \left( \frac{h_2}{h} \right)^{q - p} \right)}{1 - r}}_{b^{\ast}} h^q$

或简记作：

$\therefore D = D^{\ast} \left( h \right) + b^{\ast} h^q$

$D^{\ast}(h)$代替了$D(h)$，为$D$的新的数值近似。新近似相比最初形式具有更高阶的误差项，数值精度由此提高，此方法即为理查德森外推法。

示例

应用理查德森方法，改善用于近似微分的中心差分公式

$f' \left( x_n \right) = \underset{D \left( h \right)}{\underbrace{\frac{f\left( x_n + h \right) - f \left( x_n - h \right)}{2 h}}} -\underset{a}{\underbrace{\frac{f''' \left( x_n \right)}{6}}} h^2 -\underset{b}{\underbrace{\frac{f^{\left( 5 \right)} \left( x_n\right)}{120}}} h^4$

则由式(1)可知$p = 2, q = 4$, $h_2 = 2 h, r = \left( \frac{1}{2} \right)^p = \frac{1}{4}$ 代入公式：

$D^{\ast} = \frac{D \left( h \right) - r D \left( h_2 \right)}{1 - r} = \frac{\frac{f \left( x_n + h \right) - f \left( x_n - h \right)}{2 h} - \frac{1}{4} \frac{f \left( x_n + 2 h \right) - f \left( x_n - 2 h \right)}{4 h}}{1 - \frac{1}{4}}$

$D^{\ast} = \frac{8 \left[ f \left( x_n + h \right) - f \left( x_n - h\right) \right] - f \left( x_n + 2 h \right) + f \left( x_n - 2 h\right)}{12 h}$

由此，中心差分公式精度由2阶变为4阶。

参考文献

• Extrapolation Methods. Theory and Practice by C. Brezinski and M. Redivo Zaglia, North-Holland, 1991.

外部链接

• Module for Richardson's Extrapolation, fullerton.edu
• Fundamental Methods of Numerical Extrapolation With Applications, mit.edu
• Richardson-Extrapolation
• Richardson extrapolation on a website of Robert Israel (University of British Columbia)