収束速度

等比数列${\textstyle (a_{k})=1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},{\frac {1}{32}},\ldots ,{\bigl (}{\tfrac {1}{2}}{\bigr )}^{k},\dots }$ 収束して${\displaystyle L=0}$数列をQ線形収束の定義（すなわち収束次数1）に代入すると、次のことがわかる。

$${\displaystyle \lim _{k\to \infty }{\frac {\left|1/2^{k+1}-0\right|}{\left|1/2^{k}-0\right|}}=\lim _{k\to \infty }{\frac {2^{k}}{2^{k+1}}}={\frac {1}{2}}.}$$

したがって${\displaystyle (a_{k})}$Q線形に収束し、収束率は${\displaystyle \mu =1/2}$下の図の最初のグラフを参照してください。

より一般的には、任意の初期値に対して${\displaystyle a}$実数と実数の公比において${\displaystyle r}$-1から1の間の等比数列${\displaystyle (ar^{k})}$速度とともに線形に収束する${\displaystyle |r|}$そして等比級数の部分和の数列${\textstyle {\bigl (}\sum _{n=0}^{k}ar^{n}{\bigr )}}$また、速度とともに線形に収束する${\displaystyle |r|}$同様のことは、任意の複素数でパラメータ化された等比数列や等比級数にも当てはまります。${\displaystyle a\in \mathbb {C} ,r\in \mathbb {C} ,|r|<1.}$

段階的な幾何級数${\textstyle (b_{k})=1,1,{\frac {1}{4}},{\frac {1}{4}},{\frac {1}{16}},{\frac {1}{16}},\ldots ,{\bigl (}{\tfrac {1}{4}}{\bigr )}^{\left\lfloor k/2\right\rfloor },\ldots ,}$床関数を使用する${\textstyle \lfloor x\rfloor }$これは以下の最大の整数を与えます${\displaystyle x,}$は 1/2 の収束率で R-線形に 0 に収束しますが、Q-線形には収束しません。下の図の 2 番目のグラフを参照してください。この数列には、定義となる Q-線形収束限界が存在しません。これは、奇数ステップから始まる誤差商の 1 つの部分列が 1 に収束し、偶数ステップから始まる別の部分列が 1/4 に収束するためです。数列の 2 つの部分列が異なる限界に収束する場合、数列自体は限界に収束しません。一般に、任意の段階的等比数列に対して、${\displaystyle (ar^{\lfloor k/m\rfloor })}$数列は Q 線形に収束しないが、収束率 R 線形に収束する。${\textstyle {\sqrt[{m}]{|r|}};}$これらの例は、R線形収束における「R」が「root」の略である理由を示しています。

シーケンス $${\displaystyle (c_{k})={\frac {1}{2}},{\frac {1}{4}},{\frac {1}{16}},{\frac {1}{256}},{\frac {1}{65,\!536}},\ldots ,{\frac {1}{2^{2^{k}}}},\ldots }$$ Q超線形的にゼロに収束する。実際には、収束率が1の2次収束を示す2次収束である。これは、下の図の3番目のグラフに示されている。

最後に、シーケンス $${\displaystyle (d_{k})=1,{\frac {1}{2}},{\frac {1}{3}},{\frac {1}{4}},{\frac {1}{5}},{\frac {1}{6}},\ldots ,{\frac {1}{k+1}},\ldots }$$ Qは0に劣線形かつ対数的に収束し、その収束は下図の4番目のグラフに示されています。

反復シーケンス${\textstyle x_{k+1}:=f(x_{k})}$固定点反復と呼ばれるものは、離散時間自律力学系を定義し、その収束挙動に関するさまざまな固定点定理を通じて数学において重要な一般応用があります。fが連続的に微分可能で、固定点pが与えられた場合、${\textstyle f(p)=p,}$そのため${\textstyle |f'(p)|<1}$固定点は魅力的な固定点であり、任意の初期値に対して漸化式は少なくとも線形的にpに収束する。${\displaystyle x_{0}}$pに十分近い場合。${\displaystyle |f'(p)|=0}$そして${\textstyle |f''(p)|<1}$ならば、漸化式は少なくとも二次的に収束し、以下同様である。${\displaystyle |f'(p)|>1}$この場合、固定点は反発固定点であり、数列はpのすぐ近傍からpに収束することはできませんが、局所的な近傍の外側から直接pにジャンプすることは可能です。

不動点反復によって生成された数列の収束次数を計算する実用的な方法は、次の数列を計算することです。この数列は、次の次数に収束します。${\displaystyle q}$: ^{[ 8 ]}$${\displaystyle q\approx {\frac {\log \left|\displaystyle {\frac {x_{k+1}-x_{k}}{x_{k}-x_{k-1}}}\right|}{\log \left|\displaystyle {\frac {x_{k}-x_{k-1}}{x_{k-1}-x_{k-2}}}\right|}}.}$$

次数 の数値法による正確な値の数値近似${\displaystyle q}$参照。^{[ 9 ]}

与えられた数列の収束を加速する、つまり、ある数列を同じ極限に速く収束する別の数列に変換する方法は数多く存在する。このような手法は一般に「級数加速」法として知られている。これらは、元の数列の極限を近似する際の計算コストを削減できる可能性がある。数列変換による級数加速の一例として、エイトケンのデルタ二乗法がある。これらの方法は一般に、特にエイトケン法は、収束次数を増加させるものではないため、初期収束が線形よりも速くない場合にのみ有効である。${\displaystyle (x_{k})}$線形収束するが、エイトケン法はそれを数列に変換する。${\displaystyle (a_{k})}$（病的に設計された特殊なケースを除いて）依然として線形収束するが、より速いという意味で、${\textstyle \lim _{k\rightarrow \infty }(a_{k}-L)/(x_{k}-L)=0}$一方、収束がすでに2次以上の場合、エイトケン法は改善をもたらさない。

離散化された近似のシーケンス${\displaystyle (y_{k})}$ある連続領域関数${\displaystyle S}$この目標値に収束する値と、それに対応する離散化スケールパラメータのシーケンス${\displaystyle (h_{k})}$0に収束するものは、漸近収束次数を持つと言われます。${\displaystyle q}$および漸近収束率${\displaystyle \mu }$もし

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|y_{k}-S\right|}{h_{k}^{q}}}=\mu ,}$$

いくつかの正の定数に対して${\displaystyle \mu }$そして${\displaystyle q}$そして使用する${\displaystyle |x|}$解空間上の適切な距離尺度を表すもので、多くの場合、一様ノルム、絶対差、またはユークリッド距離のいずれかです。離散化スケールパラメータは、空間または時間における規則的なグリッドの間隔、1次元のグリッドの点数の逆数、多角形メッシュ内の点間の平均または最大距離、不規則な疎グリッドの1次元間隔、または量子力学的基底セットにおける特性エネルギーまたは運動量量子である場合があります。

すべての離散化が単一の共通手法を用いて生成される場合、離散化された解の特定の離散系列ではなく、手法自体の漸近収束率と収束次数を議論するのが一般的である。このような場合、単一の抽象的な離散化解を考える。${\displaystyle y_{h}}$スケールパラメータを用いた方法で生成${\displaystyle h}$そして、この方法は漸近収束次数を持つと言われている。${\displaystyle q}$および漸近収束率${\displaystyle \mu }$もし

$${\displaystyle \lim _{h\rightarrow 0}{\frac {\left|y_{h}-S\right|}{h^{q}}}=\mu ,}$$

また、いくつかの正の定数について${\displaystyle \mu }$そして${\displaystyle q}$そして適切な指標${\displaystyle |x|.}$これは、離散化の誤差が漸近的に離散化のスケールパラメータに比例して変化することを意味する。${\displaystyle q}$電力、または${\textstyle \left|y_{h}-S\right|=O(h^{q})}$漸近的なビッグオー記法を用いると、より正確には、主要項の誤差は${\displaystyle \mu h^{q},}$これは漸近小数点表記を用いて次のように表すことができる。${\textstyle \left|y_{h}-S\right|=\mu h^{q}+o(h^{q}).}$

場合によっては、同じ手法でもスケールパラメータの選択が異なることで、複数の収束率と収束次数が重要になることがあります。例えば、異なる次元でグリッド間隔が異なる多次元グリッドに基づく有限差分法や、メッシュ点間の平均距離または最大距離をスケールパラメータとして選択することで収束次数が異なる多角形メッシュに基づく有限要素法などが挙げられます。特に技術的な文脈では、離散化手法の漸近収束率と収束次数は、複数のスケールパラメータによって同時に特徴付けられ、各スケールパラメータの値は、他のスケールパラメータに対する手法の漸近収束率と収束次数に影響を与える可能性があります。

常微分方程式を考える

${\displaystyle {\frac {dy}{dx}}=-\kappa y}$

初期条件付き${\displaystyle y(0)=y_{0}}$この一次元方程式の解は、数列を用いて近似することができます。${\displaystyle (y_{n})}$任意の規則的な格子間隔を用いた数値離散化のための前進オイラー法の適用${\displaystyle h}$およびグリッドポイントは、${\displaystyle n}$次のように：

${\displaystyle {\frac {y_{n+1}-y_{n}}{h}}=-\kappa y_{n},}$

これは定数係数を持つ一次線形漸化式を意味する。

${\displaystyle y_{n+1}=y_{n}(1-h\kappa ).}$

与えられた${\displaystyle y(0)=y_{0}}$、その漸化式を満たす数列は等比数列である。

$${\displaystyle y_{n}=y_{0}(1-h\kappa )^{n}=y_{0}\left(1-nh\kappa +{\frac {n(n-1)}{2}}h^{2}\kappa ^{2}+....\right).}$$

微分方程式の厳密な解析解は${\displaystyle y=f(x)=y_{0}\exp(-\kappa x)}$、次のテイラー展開に対応します。${\displaystyle nh\kappa }$: $${\displaystyle f(x_{n})=f(nh)=y_{0}\exp(-\kappa nh)=y_{0}\left(1-nh\kappa +{\frac {n^{2}h^{2}\kappa ^{2}}{2}}+...\right).}$$

したがって、各離散点における離散近似の誤差は

$${\displaystyle |y_{n}-f(x_{n})|={\frac {nh^{2}\kappa ^{2}}{2}}+\ldots }$$

特定の${\displaystyle x=p}$一連の前方オイラー近似が与えられた場合${\displaystyle ((y_{n})_{k})}$それぞれグリッド間隔を使用${\displaystyle h_{k}}$その分断${\displaystyle p}$となることによって${\displaystyle n_{p,k}=p/h_{k}}$1つは

$${\displaystyle \lim _{h_{k}\rightarrow 0}{\frac {|y_{k}(p)-f(p)|}{h_{k}}}=\lim _{h_{k}\rightarrow 0}{\frac {|y_{k,n_{p,k}}-f(h_{k}n_{p,k})|}{h_{k}}}={\frac {h_{k}n_{p,k}\kappa ^{2}}{2}}={\frac {p\kappa ^{2}}{2}}}$$

グリッド間隔が徐々に小さくなる任意のグリッドのシーケンスに対して${\displaystyle h_{k}}$。 したがって${\displaystyle ((y_{n})_{k})}$収束して${\displaystyle f(x)}$収束次数で点ごとに${\displaystyle q=1}$漸近誤差定数${\displaystyle p\kappa ^{2}/2}$各ポイントで${\displaystyle p>0.}$同様に、数列は同じ次数と収束率で一様に収束する。${\displaystyle L\kappa ^{2}/2}$任意の有界区間において${\displaystyle p\leq L}$しかし、それはすべての正の実数値の無限集合上で一様に収束するわけではない。${\displaystyle [0,\infty ).}$

一般的に漸近解析では、1つのシーケンス${\displaystyle (a_{k})_{k\in \mathbb {N} }}$極限に収束する${\displaystyle L}$漸近的に収束すると言われている${\displaystyle L}$他の数列よりも収束の速さが速い${\displaystyle (b_{k})_{k\in \mathbb {N} }}$収束して${\displaystyle L}$距離指標を持つ共有メトリック空間において${\displaystyle |\cdot |,}$通常の絶対差メトリックを持つ実数や複素数など、

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=0,}$$

2つは漸近的に収束すると言われている${\displaystyle L}$収束の次数が同じ場合

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=\mu }$$

ある正の有限定数に対して${\displaystyle \mu ,}$そして、この2つは漸近的に収束すると言われている。${\displaystyle L}$同じ収束率と収束次数で

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=1.}$$

漸近収束の速度と次数に関するこれらの比較定義は、漸近解析において基本的である。^{[ 10 ] [ 11 ]}これらのうち最初の2つについては、漸近O記法で関連する式がある。1つ目は次の通りである。${\displaystyle a_{k}-L=o(b_{k}-L)}$小文字のo表記^{[ 12 ]}で、2つ目は${\displaystyle a_{k}-L=\Theta (b_{k}-L)}$Knuth記法では^{[ 13 ]} 3番目は漸近等価とも呼ばれ、次のように表される。${\displaystyle a_{k}-L\sim b_{k}-L.}$^{[ 14 ] [ 15 ]}

任意の2つの等比数列について${\displaystyle (ar^{k})_{k\in \mathbb {N} }}$そして${\displaystyle (bs^{k})_{k\in \mathbb {N} },}$共通の極限ゼロを持つ2つの数列は、両方とも${\displaystyle a=b}$そして${\displaystyle r=s.}$同じ次数で収束するのは、${\displaystyle r=s.}$${\displaystyle (ar^{k})}$より速いオーダーで収束する${\displaystyle (bs^{k})}$かつその場合に限り${\displaystyle r<s.}$幾何級数が極限に収束する際の誤差項は幾何級数に等しくなるため、幾何級数間でも同様の関係が成り立ちます。漸近的に収束する幾何級数と等価な数列は、極限からの絶対差に関して「幾何級数的に収束する」または「指数関数的に収束する」と表現できます。あるいは、絶対差の対数、例えば「精度の小数点以下の桁数」に関して「線形的に収束する」と表現することもできます。後者は数値解析において標準的な表現です。

逆べき乗に比例する任意の 2 つの要素のシーケンスについて${\displaystyle k,}$${\displaystyle (ak^{-n})_{k\in \mathbb {N} }}$そして${\displaystyle (bk^{-m})_{k\in \mathbb {N} },}$共通の極限ゼロを持つ2つの数列は、両方とも${\displaystyle a=b}$そして${\displaystyle n=m.}$同じ次数で収束するのは、${\displaystyle n=m.}$${\displaystyle (ak^{-n})}$より速いオーダーで収束する${\displaystyle (bk^{-m})}$かつその場合に限り${\displaystyle n>m.}$

任意のシーケンス${\displaystyle (a_{k})_{k\in \mathbb {N} }}$ゼロを極限とした場合、その収束はシフトされた数列の収束と比較することができる。${\displaystyle (a_{k-1})_{k\in \mathbb {N} },}$シフトされたシーケンスを定数倍にリスケールする${\displaystyle \mu ,}$${\displaystyle (\mu a_{k-1})_{k\in \mathbb {N} },}$そしてスケール${\displaystyle q}$-シフトされたシーケンスのパワー、${\displaystyle (\mu a_{k-1}^{q})_{k\in \mathbb {N} }.}$これらの比較は、上述の反復数値法のQ収束分類の基礎となるものです。数値法からの反復誤差のシーケンスが${\displaystyle (|x_{k}-L|)_{k\in \mathbb {N} }}$これは、反復誤差のシフト、指数化、および再スケーリングされたシーケンスと漸近的に等価である。${\displaystyle (\mu |x_{k-1}-L|^{q})_{k\in \mathbb {N} },}$次数とともに収束すると言われている${\displaystyle q}$そして評価する${\displaystyle \mu .}$