理查德森外推法

數值分析中，理查德森外推法(Richardson extrapolation)用以改善級數序列收斂效率，它是在20世紀前期由英國數學家，物理學家，氣象學家Lewis Fry Richardson提出的。在數值分析領域，Richardson外推法有很多實際應用，如Romberg's method，是在梯形公式的基礎上應用Richardson外推法導出的；還有用於求解常微分方程的Bulirsch–Stoer算法。

推導

假定某一函數$D$可數值近似（離散化）為$D\left(h\right)$，其中$h$為步長，

$D=D\left(h\right)+ah^{p}+bh^{q}+\ldots$ （1）

其中$p$為首項階數，$q$下一項階數, 滿足$q>p$。

考慮該函數又可以使用同樣的數值近似方法，以步長為$h_{2}$做離散近似

$D=D\left(h_{2}\right)+ah_{2}^{p}+bh_{2}^{q}+\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)+ah^{p}+bh^{q}-rD\left(h_{2}\right)-rah_{2}^{p}-rbh_{2}^{q}+\ldots =D\left(h\right)-rD\left(h_{2}\right)+a\underbrace {\left(h^{p}-rh_{2}^{p}\right)} _{0}+b\left(h^{q}-rh_{2}^{q}\right)$

$\left(1-r\right)D=D\left(h\right)-rD\left(h_{2}\right)+b\left(h^{q}-rh_{2}^{q}\right)$

$D={\frac {D\left(h\right)-rD\left(h_{2}\right)}{1-r}}+{\frac {b\left(h^{q}-rh_{2}^{q}\right)}{1-r}}={\frac {D\left(h\right)-rD\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)-rD\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)-rD\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)}{2h}} }}-{\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}=2h,r=\left({\frac {1}{2}}\right)^{p}={\frac {1}{4}}$ 代入公式：

$D^{\ast }={\frac {D\left(h\right)-rD\left(h_{2}\right)}{1-r}}={\frac {{\frac {f\left(x_{n}+h\right)-f\left(x_{n}-h\right)}{2h}}-{\frac {1}{4}}{\frac {f\left(x_{n}+2h\right)-f\left(x_{n}-2h\right)}{4h}}}{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}+2h\right)+f\left(x_{n}-2h\right)}{12h}}$

由此，中心差分公式精度由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) （頁面存檔備份，存於互聯網檔案館）