利用者:Wetch/リチャードソン外挿

リチャードソン外挿とは、数値解析において数列の収束速度を向上させるために使用される一連の加速方法である。20世紀初頭にルイス・フライ・リチャードソンによって提案された。 In numerical analysis, Richardson extrapolation is a sequence acceleration method, used to improve the rate of convergence of a sequence. It is named after Lewis Fry Richardson, who introduced the technique in the early 20th century.

In the words of Birkhoff and Rota, "... its usefulness for practical computations can hardly be overestimated."

リチャードソン補外法の実用的なアプリケーションとしてはロンバーグ積分がある。これは、常微分方程式を解くため、台形公式にリチャードソン補外法を適用しBulirsch–Stoer algorithmを使ったものである。 Practical applications of Richardson extrapolation include Romberg integration, which applies Richardson extrapolation to the trapezium rule, and the Bulirsch–Stoer algorithm for solving ordinary differential equations.

例

真値A に対して、パラメータh で決まる推定値A (h )を考える。

$A=\lim _{h\to 0}A(h)$

A (h )はn 次精度、すなわち

$A-A(h)=a_{n}h^{n}+O(h^{m}),\quad a_{n}\neq 0,\quad m>n$

であるとする。このとき、次のR を A (h )のリチャードソン外挿という：

$R(h)=A(h/2)+{\frac {A(h/2)-A(h)}{2^{n}-1}}={\frac {2^{n}\,A(h/2)-A(h)}{2^{n}-1}}$

Suppose that $A(h)\;$ is an estimation of order $h^{n}\;$ for $A=\lim _{h\to 0}A(h)$, i.e. $A-A(h)=a_{n}h^{n}+O(h^{m}),~a_{n}\neq 0,~m>n$. Then

$R(h)=A(h/2)+{\frac {A(h/2)-A(h)}{2^{n}-1}}={\frac {2^{n}\,A(h/2)-A(h)}{2^{n}-1}}$

is called the Richardson extrapolation of A(h); it is an estimate of order h^m for A, with m>n.

一般的には、係数2は他の係数に置き換えられる（後述）。 More generally, the factor 2 can be replaced by any other factor, as shown below.

与えられた精度を得るにはA(h)よりR(h)を使うほうが簡単である。 Very often, it is much easier to obtain a given precision by using R(h) rather than A(h') with a much smaller h' , which can cause problems due to limited precision (rounding errors) and/or due to the increasing number of calculations needed (see examples below).

一般式

Let A(h) be an approximation of A that depends on a positive step size h with an error formula of the form

$A-A(h)=a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots$

where the a_i are unknown constants and the k_i are known constants such that h^k_i > h^k_i+1.

The exact value sought can be given by

$A=A(h)+a_{0}h^{k_{0}}+a_{1}h^{k_{1}}+a_{2}h^{k_{2}}+\cdots$

which can be simplified with Big O notation to be

$A=A(h)+a_{0}h^{k_{0}}+O(h^{k_{1}}).\,\!$

Using the step sizes h and h / t for some t, the two formulas for A are:

$A=A(h)+a_{0}h^{k_{0}}+O(h^{k_{1}})\,\!$

$A=A\!\left({\frac {h}{t}}\right)+a_{0}\left({\frac {h}{t}}\right)^{k_{0}}+O(h^{k_{1}}).$

Multiplying the second equation by t^k₀ and subtracting the first equation gives

$(t^{k_{0}}-1)A=t^{k_{0}}A\left({\frac {h}{t}}\right)-A(h)+O(h^{k_{1}})$

which can be solved for A to give

$A={\frac {t^{k_{0}}A\left({\frac {h}{t}}\right)-A(h)}{t^{k_{0}}-1}}+O(h^{k_{1}}).$

By this process, we have achieved a better approximation of A by subtracting the largest term in the error which was O(h^k₀). This process can be repeated to remove more error terms to get even better approximations.

A general recurrence relation can be defined for the approximations by

$A_{i+1}(h)={\frac {t^{k_{i}}A_{i}\left({\frac {h}{t}}\right)-A_{i}(h)}{t^{k_{i}}-1}}$

such that

$A=A_{i+1}(h)+O(h^{k_{i+1}})$

with $A_{0}=A(h)$.

リチャードソン外挿は線型な The Richardson extrapolation can be considered as a linear sequence transformation.

Additionally, the general formula can be used to estimate k₀ when neither its value nor A is known a priori. Such a technique can be useful for quantifying an unknown rate of convergence. Given approximations of A from three distinct step sizes h, h / t, and h / s, the exact relationship

$A={\frac {t^{k_{0}}A\left({\frac {h}{t}}\right)-A(h)}{t^{k_{0}}-1}}+O(h^{k_{1}})={\frac {s^{k_{0}}A\left({\frac {h}{s}}\right)-A(h)}{s^{k_{0}}-1}}+O(h^{k_{1}})$

yields an approximate relationship

$A\left({\frac {h}{t}}\right)+{\frac {A\left({\frac {h}{t}}\right)-A(h)}{t^{k_{0}}-1}}\approx A\left({\frac {h}{s}}\right)+{\frac {A\left({\frac {h}{s}}\right)-A(h)}{s^{k_{0}}-1}}$

which can be solved numerically to estimate k₀.

例

テイラーの定理 Using Taylor's theorem,

$f(x+h)=f(x)+f'(x)h+{\frac {f''(x)}{2}}h^{2}+\cdots$

を用いると、f (x ) の微分は次で与えられる： the derivative of f(x) is given by

$f'(x)={\frac {f(x+h)-f(x)}{h}}-{\frac {f''(x)}{2}}h+\cdots$

この微分の近時の初期値として If the initial approximations of the derivative are chosen to be

$A_{0}(h)={\frac {f(x+h)-f(x)}{h}}$

を選ぶと、k_i = i+1 である。 then k_i = i+1.

t = 2 に対し、最初の式をA について展開すると For t = 2, the first formula extrapolated for A would be

$A=2A_{0}\!\left({\frac {h}{2}}\right)-A_{0}(h)+O(h^{2})$

となる。

新しい近似 For the new approximation

$A_{1}(h)=2A_{0}\!\left({\frac {h}{2}}\right)-A_{0}(h)$

に対し、再度外挿して we can extrapolate again to obtain

$A={\frac {4A_{1}\!\left({\frac {h}{2}}\right)-A_{1}(h)}{3}}+O(h^{3}).$

を得る。

関連項目

• Aitken's delta-squared process

Category:数値解析 Category:Asymptotic analysis

en:Richardson extrapolation