Speed of convergence of a mathematical sequence
数学的解析 、特に 数値解析 において 、 極限 に収束する 数列 の 収束率 と 収束次数は、 数列が極限に近づく速さを特徴づけるいくつかの指標のいずれかです。これらは大まかに、数列が既に極限に近づいている状態からさらに極限に近づく速さを表す収束率と収束次数（ 漸近収束 率と収束次数）と、必ずしも極限に近いわけではない出発点から数列が極限に近づく速さを表す収束率と収束次数（非漸近収束率と収束次数）に分けられます。
漸近的挙動は、例えば反復 根探索アルゴリズム で目標精度に到達した時など、数値計算のシーケンスをいつ停止するかを決定する際に特に有用である。しかし、漸近前挙動は、一連の計算をそもそも開始するかどうかを判断する上で非常に重要である。なぜなら、不適切なアプローチを選択した場合、目標精度に到達することが不可能または非現実的になる可能性があるからである。本稿では、漸近速度と収束次数に焦点を当てる。
実際の数値計算において、漸近収束率と収束次数は、2種類のシーケンスに対して共通の規則に従います。1つは 反復数値法 の反復シーケンス、もう1つはターゲットの数値 離散化精度 を段階的に向上させるシーケンスです。正式な数学では、収束率と収束次数は、 一般的に「 ビッグオー記法」と呼ばれる 漸近記法 を用いて比較記述されることが多く、この記法は前述の2つの規則の両方を包含することができます。これは 漸近解析 の応用です。
反復法では、収束する 数列は、次の 場合
、 漸近収束順序 と漸近 収束速度 を持つと言われる。 ( x k ) {\displaystyle (x_{k})} L {\displaystyle L} q ≥ 1 {\displaystyle q\geq 1} μ {\displaystyle \mu }
lim k → ∞ | x k + 1 − L | | x k − L | q = μ . {\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|x_{k+1}-L\right|}{\left|x_{k}-L\right|^{q}}}=\mu .} [1] 方法論的な精度が求められる場合、これらの収束速度と収束次数は、問題の極限が誤差項の商であるため、Q収束（商収束の略）の速度と次数として特に知られています。 [1] 収束速度は 漸近誤差定数 と呼ばれることもあり、 この記事で次数を使用しているところを、一部の著者は収束 速度 を使用します 。 [2] 級数加速法は、 級数 の部分和の収束速度を改善し 、場合によっては収束次数も改善する手法です。 μ {\displaystyle \mu }
同様の概念は離散化の列にも用いられます。例えば、理想的には、 規則的なグリッド を用いて離散化された 微分方程式 の解は、グリッド間隔がゼロに近づくにつれて連続方程式の解に収束します。そして、もしそうであれば、その収束の漸近速度と収束の順序は、グリッド化法の重要な特性です。 ある問題の近似グリッド解の列が真の解に収束し、 対応する規則的なグリッド間隔の列 が0に収束する 場合
、漸近 収束順序 と漸近 収束速度を持つとされます。 ( y k ) {\displaystyle (y_{k})} S {\displaystyle S} ( h k ) {\displaystyle (h_{k})} q {\displaystyle q} μ {\displaystyle \mu }
lim k → ∞ | y k − S | h k q = μ , {\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|y_{k}-S\right|}{h_{k}^{q}}}=\mu ,}
ここで、絶対値記号は、 一様ノルム などの解空間の 計量を表します。同様の定義は、 有限要素法 の ポリゴンメッシュ や 計算化学 における 基底関数系 などの非グリッド離散化スキームにも適用されます 。一般に、漸近速度の適切な定義 は、上の近似誤差項と下の離散化スケールパラメータの漸近次位数べきの比の漸近極限を含みます 。 μ {\displaystyle \mu } q {\displaystyle q}
一般的に、 ある極限に収束する数列は、他の 極限に収束する 数列よりも漸近収束が速いと言われる 。 ( a k ) {\displaystyle (a_{k})} L a {\displaystyle L_{a}} ( b k ) {\displaystyle (b_{k})} L b {\displaystyle L_{b}}
lim k → ∞ | a k − L a | | b k − L b | = 0 , {\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L_{a}\right|}{|b_{k}-L_{b}|}}=0,}
そして、極限が任意の正の有限値である場合、両者は同じ収束次数で漸近収束すると言われます。極限が1に等しい場合、両者は漸近的に同値であると言われます。漸近収束速度と収束次数に関するこれらの比較定義は、漸近解析における基本的なものであり、数値解析、 実解析、複素解析 、 関数 解析 など、数学解析全般に広く応用されています 。
反復法の漸近収束率
定義
Q収束 反復法 の反復処理の 列 がの 極限 数 に収束する と仮定する。反復処理の連続する 各反復処理の 絶対値 の差の商の極限が を満たす とき、反復処理の 列はの位数 で 収束 し、 収束率 で収束すると言わ れる。 ( x k ) {\displaystyle (x_{k})} L {\displaystyle L} k → ∞ {\displaystyle k\rightarrow \infty } q {\displaystyle q} L {\displaystyle L} μ {\displaystyle \mu } k → ∞ {\displaystyle k\rightarrow \infty } x k , x k + 1 {\displaystyle x_{k},x_{k+1}} L {\displaystyle L}
lim k → ∞ | x k + 1 − L | | x k − L | q = μ {\displaystyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|^{q}}}=\mu }
何らかの正の定数に対して、 かつ の 場合に成り立ちます 。 [1] [3] [4] シーケンスが収束するが [5] または極限が存在しない場合は、より専門的なレートの定義が必要になります。 [1] この定義は専門的には商収束の略である Q 収束と呼ばれ、レートと次数は技術的な詳細が必要なときに Q 収束のレートと次数と呼ばれます。§ 以下の R 収束は、この極限が存在しない場合の適切な代替手段です。 μ ∈ ( 0 , 1 ) {\displaystyle \mu \in (0,1)} q = 1 {\displaystyle q=1} μ ∈ ( 0 , ∞ ) {\displaystyle \mu \in (0,\infty )} q > 1 {\displaystyle q>1} lim k → ∞ | x k + 1 − L | | x k − L | = 1 {\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=1}
大きな次数を持つシーケンスは、 小さな次数を持つシーケンスよりも速く収束し、また、 ある次数において、収束率が小さなシーケンスは、収束率が大きなシーケンスよりも速く収束します。同じ次数を持つシーケンス間では、この「小さな収束率がより速く収束する」という挙動は一般的ですが、直感に反する場合があります。そのため、 収束率を と定義することも一般的です。これは、次数1で収束するシーケンスの「反復ごとに精度が余分に何桁増えるか」を表します。 [1] q {\displaystyle q} μ {\displaystyle \mu } − log 10 μ {\displaystyle -\log _{10}\mu }
の整数乗は 一般的であり、共通の名前が付けられています。 と の位数での収束 は 線型収束 と呼ば れ、数列は に 線型収束すると言われています 。 と任意のでの収束は 二次 収束と呼ばれ、数列は に二次収束する と言われています。 と任意の での収束は 三次収束 と呼ばれます 。ただし、 は整数である必要はありません 。例えば、 正割法 は、規則的な 単純な根 に収束する場合、 黄金比 φ ≈ 1.618の位数を持ちます 。 [6] q {\displaystyle q} q = 1 {\displaystyle q=1} μ ∈ ( 0 , 1 ) {\displaystyle \mu \in (0,1)} L {\displaystyle L} q = 2 {\displaystyle q=2} μ {\displaystyle \mu } q = 3 {\displaystyle q=3} μ {\displaystyle \mu } q {\displaystyle q}
整数収束の一般的な名称は、 漸近的大O記法 に結びついており、商の収束は次式を意味する。 これらは、それぞれ が1、2、3 のときの線形、二次、三次の多項式である 。より正確には、これらの極限は、主次誤差がちょうど であることを意味し、これは 漸近的小O記法 を用いて次のように 表すことができる。 | x k + 1 − L | = O ( | x k − L | q ) . {\textstyle |x_{k+1}-L|=O(|x_{k}-L|^{q}).} q {\displaystyle q} μ | x k − L | q , {\textstyle \mu |x_{k}-L|^{q},} | x k + 1 − L | = μ | x k − L | q + o ( | x k − L | q ) . {\textstyle |x_{k+1}-L|=\mu |x_{k}-L|^{q}+o(|x_{k}-L|^{q}).}
一般に、 数列が となる場合、または となる任意の数列が となる場合 、これらの数列は 超線形収束 （ つまり線形収束より速い）すると言われる。 [1] 数列 が となり収束する場合、その数列は となり、 となる。 重要な点として、これらの となる数列が漸近収束率1で線形収束すると言うのは誤りである。数列が となり対数収束する場合、数列は となり 、また となる 。[5] q > 1 {\displaystyle q>1} lim k → ∞ | x k + 1 − L | | x k − L | = 0 , {\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=0,} lim k → ∞ | x k + 1 − L | | x k − L | = 1. {\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=1.} ( x k ) {\displaystyle (x_{k})} L {\displaystyle L} lim k → ∞ | x k + 1 − x k | | x k − x k − 1 | = 1. {\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-x_{k}|}{|x_{k}-x_{k-1}|}}=1.}
R収束 Q 収束率の定義には、収束はするがステップごとに漸近的に一定の率で収束しないシーケンスの収束挙動を自然に捉えていないという欠点があり、そのため Q 収束極限は存在しません。1 つの例として、1 ステップおきまたは数ステップおきにのみ極限に近づく、ずらした等比数列があります。 以下に詳述する例 ( は 床関数 に適用されています ) がその例です。このシーケンスには定義的な Q 線形収束極限は存在しません。これは、奇数ステップから始まる誤差商の 1 つの部分シーケンスが 1 に収束し、偶数ステップから始まる別の誤差商の部分シーケンスが 1/4 に収束するためです。シーケンスの 2 つの部分シーケンスが異なる極限に収束する場合、シーケンス自体は極限に収束しません。 ( b k ) = 1 , 1 , 1 / 4 , 1 / 4 , 1 / 16 , 1 / 16 , … , 1 / 4 ⌊ k 2 ⌋ , … {\textstyle (b_{k})=1,1,1/4,1/4,1/16,1/16,\ldots ,1/4^{\left\lfloor {\frac {k}{2}}\right\rfloor },\ldots } ⌊ x ⌋ {\textstyle \lfloor x\rfloor } x {\displaystyle x}
このような場合、収束速度のより専門的な定義であるR収束がより適切です。接頭辞「R」は「根」を意味します。 [1] [7] : 620 に収束する 数列が 少なくともR線型収束する とは、誤差制限数列が存在し 、 かつQ線型収束でゼロに収束する場合を 指します 。R超線型収束、R劣線型収束、R二次収束などにも同様の定義が当てはまります。 [1] ( x k ) {\displaystyle (x_{k})} L {\displaystyle L} ( ε k ) {\displaystyle (\varepsilon _{k})} | x k − L | ≤ ε k for all k {\textstyle |x_{k}-L|\leq \varepsilon _{k}\quad {\text{for all }}k} ( ε k ) {\displaystyle (\varepsilon _{k})}
任意の誤差境界シーケンスは、 R収束の速度と次数の下限値を与え、最大の下限値はR収束の正確な速度と次数を与えます。Q収束に関しては、与えられた次数に対して、次数が大きいシーケンスは より速く収束し、速度が小さいシーケンスは より速く収束します。したがって、これらの最大速度下限値誤差上限シーケンスは、 を条件として、 が可能な限り最大かつ が可能 な限り最小となるシーケンス です 。 ( ε k ) {\displaystyle (\varepsilon _{k})} q {\displaystyle q} μ {\displaystyle \mu } q {\displaystyle q} μ {\displaystyle \mu } q {\displaystyle q}
上記の 例では、タイトバウンディングシーケンスは Q線形収束速度1/2で収束するため、 R線形収束速度1/2で収束します。一般的に、任意のスタッガード等比数列では 、シーケンスはQ線形収束ではなく、R線形収束速度で収束します。 これらの例は、R線形収束の「R」が「ルート」の略語である理由を示しています。 ( b k ) {\textstyle (b_{k})} ( ε k ) = 2 , 1 , 1 / 2 , 1 / 4 , 1 / 8 , 1 / 16 , … , 1 / 2 k − 1 , … {\textstyle (\varepsilon _{k})=2,1,1/2,1/4,1/8,1/16,\ldots ,1/2^{k-1},\ldots } ( b k ) {\textstyle (b_{k})} ( a r ⌊ k / m ⌋ ) {\displaystyle (ar^{\lfloor k/m\rfloor })} | r | m . {\textstyle {\sqrt[{m}]{|r|}}.}
例 等比 数列 は に収束する 。この数列をQ線型収束の定義（収束次数1）に当てはめると、次のようになる。 ( a k ) = 1 , 1 2 , 1 4 , 1 8 , 1 16 , 1 32 , … , ( 1 2 ) k , … {\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 } L = 0 {\displaystyle L=0}
lim k → ∞ | 1 / 2 k + 1 − 0 | | 1 / 2 k − 0 | = lim k → ∞ 2 k 2 k + 1 = 1 2 . {\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}}.}
したがって、 は収束率 で Q 線形収束します 。下の図の最初のプロットを参照してください。 ( a k ) {\displaystyle (a_{k})} μ = 1 / 2 {\displaystyle \mu =1/2}
より一般的には、実数の任意の 初期値と -1と1の間の実数公比に対して、等比数列は 速度とともに線形収束し、 等比数列 の部分和の列 もまた速度とともに線形収束する。任意の 複素数 によってパラメータ化された等比数列と等比数列についても同様である。 a {\displaystyle a} r {\displaystyle r} ( a r k ) {\displaystyle (ar^{k})} | r | {\displaystyle |r|} ( ∑ n = 0 k a r n ) {\textstyle {\bigl (}\sum _{n=0}^{k}ar^{n}{\bigr )}} | r | {\displaystyle |r|} a ∈ C , r ∈ C , | r | < 1. {\displaystyle a\in \mathbb {C} ,r\in \mathbb {C} ,|r|<1.}
最小の整数を与える 床関数 を用いた スタッガード等比数列は 、1/2の速度でR線形収束しますが、Q線形収束はしません（下図の2番目のプロットを参照）。この数列にはQ線形収束の定義極限は存在しません。これは、奇数ステップから始まる誤差商の部分列の1つが1に収束し、偶数ステップから始まる別の誤差商の部分列が1/4に収束するためです。数列の2つの部分列が異なる極限に収束する場合、数列自体は極限に収束しません。一般に、任意のスタッガード等比数列では 、数列はQ線形収束しませんが、収束速度でR線形収束します。 これらの例は、R線形収束の「R」が「ルート」の略語である理由を示しています。 ( b k ) = 1 , 1 , 1 4 , 1 4 , 1 16 , 1 16 , … , ( 1 4 ) ⌊ k / 2 ⌋ , … , {\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 ,} ⌊ x ⌋ {\textstyle \lfloor x\rfloor } x , {\displaystyle x,} ( a r ⌊ k / m ⌋ ) {\displaystyle (ar^{\lfloor k/m\rfloor })} | r | m ; {\textstyle {\sqrt[{m}]{|r|}};}
この数列は Q超線形的にゼロに収束します。実際、これは2次収束を示し、収束率は1です。これは下の図の3番目のプロットに示されています。 ( c k ) = 1 2 , 1 4 , 1 16 , 1 256 , 1 65 , 536 , … , 1 2 2 k , … {\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 サブ線形かつ対数的にゼロに収束し、その収束は下の図の 4 番目のプロットとして表示されます。 ( d k ) = 1 , 1 2 , 1 3 , 1 4 , 1 5 , 1 6 , … , 1 k + 1 , … {\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 }
それぞれ線形、線形、超線形 (2 次)、および線形以下の収束率を示す サンプル シーケンス a k 、 b k 、 c k 、および d kの対数線形プロット。
再帰列の固定点への収束率 再帰シーケンスは 、 固定点反復 と呼ばれ、離散時間自律 動的システム を定義し、収束挙動に関する さまざまな 固定点定理を通じて数学の重要な一般アプリケーションを持っています。 f が 連続的に微分可能 で 、 となる 固定点 p が与えられている場合、 固定点は 吸引固定点 であり、再帰シーケンスは、 p に十分近い 任意の開始値に対して、少なくとも線形に p に収束します。 および の場合 、再帰シーケンスは少なくとも二次収束し、以下同様に収束します。 の場合 、固定点は 反発固定点 であり、シーケンスは、そのすぐ近くの から p に 収束することはできませんが、 その局所的近傍の外側から直接 p にジャンプすることはできます。 x k + 1 := f ( x k ) {\textstyle x_{k+1}:=f(x_{k})} f ( p ) = p , {\textstyle f(p)=p,} | f ′ ( p ) | < 1 {\textstyle |f'(p)|<1} x 0 {\displaystyle x_{0}} | f ′ ( p ) | = 0 {\displaystyle |f'(p)|=0} | f ″ ( p ) | < 1 {\textstyle |f''(p)|<1} | f ′ ( p ) | > 1 {\displaystyle |f'(p)|>1}
注文見積 固定小数点反復法によって生成されたシーケンスの収束次数を計算する実用的な方法は、次のシーケンスを計算することである。これは次の順序に収束する ： [8] q {\displaystyle q} q ≈ log | x k + 1 − x k x k − x k − 1 | log | x k − x k − 1 x k − 1 − x k − 2 | . {\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|}}.}
数値近似法による正確な値の近似値については [9]を 参照。 q {\displaystyle q}
収束速度の加速 与えられたシーケンスの収束を加速する方法、すなわち、 あるシーケンスを 、より速く同じ極限に収束する別のシーケンスに変換する方法は数多く存在します。このような技術は一般に「 級数加速 」法と呼ばれています。これらは、元のシーケンスの極限を近似するための 計算コスト を削減できます。シーケンス変換による級数加速の 1 つの例は 、Aitken のデルタ 2 乗プロセス です。これらの方法、特に Aitken 法は一般に収束の次数を上げないため、収束が最初は線形よりも速くない場合にのみ有用です。つまり 、 が線形に収束する場合、Aitken 法はそれを (病的に設計された特殊なケースを除く) 依然として線形収束するシーケンスに変換しますが、 という意味でより高速になります 。一方、収束の次数がすでに ≥ 2 である場合、Aitken 法では改善はもたらされません。 ( x k ) {\displaystyle (x_{k})} ( a k ) {\displaystyle (a_{k})} lim k → ∞ ( a k − L ) / ( x k − L ) = 0 {\textstyle \lim _{k\rightarrow \infty }(a_{k}-L)/(x_{k}-L)=0}
離散化法の漸近収束率
定義 この目標に収束する連続領域関数の 離散化近似値の列 と、それに対応する0に収束する離散化スケールパラメータの列は、次の式が成り立つとき、 漸近収束順序 と漸近 収束速度 を持つと言われる 。 ( y k ) {\displaystyle (y_{k})} S {\displaystyle S} ( h k ) {\displaystyle (h_{k})} q {\displaystyle q} μ {\displaystyle \mu }
lim k → ∞ | y k − S | h k q = μ , {\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|y_{k}-S\right|}{h_{k}^{q}}}=\mu ,}
いくつかの正の定数とに対して 、 解の空間 における適切な 距離計量 を表すために、 が用いられます 。距離計量は通常、 一様ノルム 、 絶対差 、または ユークリッド距離 のいずれかです。離散化スケールパラメータは、空間または時間における規則的な グリッドの間隔、1次元のグリッドの点数の逆数、 ポリゴンメッシュ 内の点間の平均距離または最大距離、不規則な スパースグリッド の1次元間隔、または 量子力学 基底関数 におけるエネルギーまたは運動量の特性量子などです 。 μ {\displaystyle \mu } q {\displaystyle q} | x | {\displaystyle |x|}
すべての離散化が単一の共通手法を用いて生成される場合、特定の離散解の離散列ではなく、その手法自体の漸近収束速度と収束次数を議論するのが一般的です。このような場合、スケールパラメータを用いて生成された単一の抽象的な離散化解を考え、 その 手法が漸近 収束次数 と漸近 収束速度 を持つと仮定します。 y h {\displaystyle y_{h}} h {\displaystyle h} q {\displaystyle q} μ {\displaystyle \mu }
lim h → 0 | y h − S | h q = μ , {\displaystyle \lim _{h\rightarrow 0}{\frac {\left|y_{h}-S\right|}{h^{q}}}=\mu ,}
再び、いくつかの正の定数と適切な計量について、 離散 化 の誤差は、離散化のスケールパラメータのべき乗のように漸近的にスケールする 、あるいは 漸近的な大O記法 のように スケールすることを意味する。より正確には、これは主要次誤差が であることを意味し、 漸近的な小O記法 を用いて次のように 表すことができる。 μ {\displaystyle \mu } q {\displaystyle q} | x | . {\displaystyle |x|.} q {\displaystyle q} | y h − S | = O ( h q ) {\textstyle \left|y_{h}-S\right|=O(h^{q})} μ h q , {\displaystyle \mu h^{q},} | y h − S | = μ h q + o ( h q ) . {\textstyle \left|y_{h}-S\right|=\mu h^{q}+o(h^{q}).}
場合によっては、同じ手法であってもスケールパラメータの選択が異なる複数の収束速度と収束次数が重要になることがあります。例えば、 異なる次元に異なるグリッド間隔を持つ多次元グリッドに基づく 有限差分法や、スケールパラメータとしてメッシュポイント間の平均距離または最大距離のいずれかを選択することで異なる収束次数を意味する可能性があるポリゴンメッシュに基づく 有限要素法 などです。特に技術的な状況では、離散化手法の漸近速度と収束次数は、複数のスケールパラメータによって一度に特徴付けられ、各スケールパラメータの値が、他のスケールパラメータに対する手法の漸近速度と収束次数に影響を与える可能性があります。
例 常微分方程式を考えてみましょう
d y d x = − κ y {\displaystyle {\frac {dy}{dx}}=-\kappa y} 初期条件は です 。この1次元方程式の解は、任意の規則的なグリッド間隔 と でインデックス付けされたグリッドポイント を用いた数値離散化のための順 方向オイラー法 を適用したシーケンスを使用して 近似できます。 y ( 0 ) = y 0 {\displaystyle y(0)=y_{0}} ( y n ) {\displaystyle (y_{n})} h {\displaystyle h} n {\displaystyle n}
y n + 1 − y n h = − κ y n , {\displaystyle {\frac {y_{n+1}-y_{n}}{h}}=-\kappa y_{n},} これは定数係数の 一次線形回帰を意味する。
y n + 1 = y n ( 1 − h κ ) . {\displaystyle y_{n+1}=y_{n}(1-h\kappa ).} が与えられたとき 、その再帰性を満たす数列は 等比数列である。 y ( 0 ) = y 0 {\displaystyle y(0)=y_{0}}
y n = y 0 ( 1 − h κ ) n = y 0 ( 1 − n h κ + n ( n − 1 ) 2 h 2 κ 2 + . . . . ) . {\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).}
微分方程式の正確な解析解は であり、 における 次の テイラー展開 に対応します。 y = f ( x ) = y 0 exp ( − κ x ) {\displaystyle y=f(x)=y_{0}\exp(-\kappa x)} n h κ {\displaystyle nh\kappa } f ( x n ) = f ( n h ) = y 0 exp ( − κ n h ) = y 0 ( 1 − n h κ + n 2 h 2 κ 2 2 + . . . ) . {\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).}
したがって、各離散点における離散近似の誤差は
| y n − f ( x n ) | = n h 2 κ 2 2 + … {\displaystyle |y_{n}-f(x_{n})|={\frac {nh^{2}\kappa ^{2}}{2}}+\ldots } 任意の特定の に対して、 を 割り切れる グリッド間隔をそれぞれ用いた 順方向オイラー近似の列が与えられれば 、 x = p {\displaystyle x=p} ( ( y n ) k ) {\displaystyle ((y_{n})_{k})} h k {\displaystyle h_{k}} p {\displaystyle p} n p , k = p / h k {\displaystyle n_{p,k}=p/h_{k}}
lim h k → 0 | y k ( p ) − f ( p ) | h k = lim h k → 0 | y k , n p , k − f ( h k n p , k ) | h k = h k n p , k κ 2 2 = p κ 2 2 {\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}}}
グリッド間隔が徐々に小さくなる任意のグリッド列に対して、は 各点で 収束順序 と漸近誤差定数で 点ごと に収束します 。同様に、 の任意の有界区間では 、 列は 同じ順序と速度で 一様 収束しますが、すべての正の実数値の非有界集合では一様収束しません。 h k {\displaystyle h_{k}} ( ( y n ) k ) {\displaystyle ((y_{n})_{k})} f ( x ) {\displaystyle f(x)} q = 1 {\displaystyle q=1} p κ 2 / 2 {\displaystyle p\kappa ^{2}/2} p > 0. {\displaystyle p>0.} L κ 2 / 2 {\displaystyle L\kappa ^{2}/2} p ≤ L {\displaystyle p\leq L} [ 0 , ∞ ) . {\displaystyle [0,\infty ).}
漸近収束速度の比較
定義 漸近解析 において、ある 極限 に収束する 列は、 実数 や 複素数 などの 距離計量 を持つ 共有 計量空間 において、通常の 絶対差 計量を 持つ 列よりも、より速い収束の順序で漸近 収束すると言われる。 ( a k ) k ∈ N {\displaystyle (a_{k})_{k\in \mathbb {N} }} L {\displaystyle L} L {\displaystyle L} ( b k ) k ∈ N {\displaystyle (b_{k})_{k\in \mathbb {N} }} L {\displaystyle L} | ⋅ | , {\displaystyle |\cdot |,}
lim k → ∞ | a k − L | | b k − L | = 0 , {\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=0,}
両者は 同じ収束次数で漸近収束するとは、 L {\displaystyle L}
lim k → ∞ | a k − L | | b k − L | = μ {\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=\mu }
何らかの正の有限定数に対して 、両者は 同じ収束速度と収束次数で漸近収束すると言われる。 μ , {\displaystyle \mu ,} L {\displaystyle L}
lim k → ∞ | a k − L | | b k − L | = 1. {\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=1.}
漸近収束の速度と順序に関するこれらの比較定義は、 漸近解析 において基本的なものである。 [10] [11] これらの最初の2つについては、 漸近O表記法 による関連表現がある。1つ目は 小文字のO表記法 [12] 、2つ目はクヌース表記法 [13] である。3 つ目は漸近同値とも呼ばれ、次のように表現される [14] [15]。 a k − L = o ( b k − L ) {\displaystyle a_{k}-L=o(b_{k}-L)} a k − L = Θ ( b k − L ) {\displaystyle a_{k}-L=\Theta (b_{k}-L)} a k − L ∼ b k − L . {\displaystyle a_{k}-L\sim b_{k}-L.}
例 極限ゼロを共有する任意の2 つの 等比数列 とに対して 、2 つの数列が漸近的に同値である場合、かつその場合 に 限ります。が よりも速い位数で収束する場合 、かつその場合に限ります。 任意の等比 数列 がその極限に収束すると、等比数列に等しい誤差項が生じるため、等比数列間でも同様の関係が成り立ちます。 収束する等比数列と漸近的に同値な数列は、その極限からの絶対差に関して「等比的に収束する」または「指数的に収束する」と言うことも、あるいは「精度の小数点以下桁数」などの絶対差の対数に関して「線形収束する」と言うこともできます。後者は数値解析では標準です。 ( a r k ) k ∈ N {\displaystyle (ar^{k})_{k\in \mathbb {N} }} ( b s k ) k ∈ N , {\displaystyle (bs^{k})_{k\in \mathbb {N} },} a = b {\displaystyle a=b} r = s . {\displaystyle r=s.} r = s . {\displaystyle r=s.} ( a r k ) {\displaystyle (ar^{k})} ( b s k ) {\displaystyle (bs^{k})} r < s . {\displaystyle r<s.}
の逆べき乗に比例し、 かつ 共有の極限がゼロである2つの要素の列について、2つの列が漸近的に同値であるのは、両方がであり、であるときのみである。それら が 同じ位数で収束するのは、 がよりも速い位数で収束する場合のみであり、が速い位数で収束する 場合のみである。 k , {\displaystyle k,} ( a k − n ) k ∈ N {\displaystyle (ak^{-n})_{k\in \mathbb {N} }} ( b k − m ) k ∈ N , {\displaystyle (bk^{-m})_{k\in \mathbb {N} },} a = b {\displaystyle a=b} n = m . {\displaystyle n=m.} n = m . {\displaystyle n=m.} ( a k − n ) {\displaystyle (ak^{-n})} ( b k − m ) {\displaystyle (bk^{-m})} n > m . {\displaystyle n>m.}
ゼロの極限を持つ任意の シーケンスの収束は、シフトされたシーケンス の定数による再スケーリングと、シフトされたシーケンスのスケーリングされた -べき乗 によるシフトされたシーケンスの収束と比較できます。 これらの比較は、上記の反復数値法のQ収束分類の基礎です。数値法からの反復エラーのシーケンスが、反復エラーの シフト、指数化、および再スケーリングされたシーケンスと漸近的に等しい場合、順序 と速度 で収束すると言われています。 ( a k ) k ∈ N {\displaystyle (a_{k})_{k\in \mathbb {N} }} ( a k − 1 ) k ∈ N , {\displaystyle (a_{k-1})_{k\in \mathbb {N} },} μ , {\displaystyle \mu ,} ( μ a k − 1 ) k ∈ N , {\displaystyle (\mu a_{k-1})_{k\in \mathbb {N} },} q {\displaystyle q} ( μ a k − 1 q ) k ∈ N . {\displaystyle (\mu a_{k-1}^{q})_{k\in \mathbb {N} }.} ( | x k − L | ) k ∈ N {\displaystyle (|x_{k}-L|)_{k\in \mathbb {N} }} ( μ | x k − 1 − L | q ) k ∈ N , {\displaystyle (\mu |x_{k-1}-L|^{q})_{k\in \mathbb {N} },} q {\displaystyle q} μ . {\displaystyle \mu .}
非漸近収束速度 非漸近収束速度には、漸近収束速度のような共通の標準的な定義はありません。形式的手法の中でも、 リアプノフ理論 は、非漸近収束挙動を特徴づけ、解析するための最も強力で広く応用されている枠組みの一つです。
反復法 において、これらの収束速度を、限界から遠い開始点から限界の 近傍 に到達するまでに要した反復回数または 計算時間 で議論するのが、一般的な実用的なアプローチの一つです 。非漸近収束速度は、その反復回数または計算時間の逆数です。実際の応用においては、目標精度に到達するまでに要したステップ数または計算時間が他の反復法よりも少ない場合、たとえ漸近収束が遅い場合でも、他の反復法よりも収束が速いと言えます。これらの収束速度は、通常、開始点や近傍を定義するための誤差閾値によって異なります。最も一般的なのは、ある手法を ある問題に適用し、ある固定誤差閾値を適用した場合の「平均非漸近収束速度」、「中央値非漸近収束速度」、「最悪ケースの非漸近収束速度」など、考えられる開始点の分布に対応する、これらの単一点収束速度の統計分布の要約を議論することです 。 これらの開始点の集合は、最終的な限界からの初期距離などのパラメータに従って選択することができ、「特定の距離からの平均非漸近収束率」などの量を定義できます。
離散化近似 法においても、 グリッド点 や メッシュ 点 の数の逆数、あるいは逆反復回数の役割を果たす フーリエ級数カットオフ 周波数 などの離散化スケールパラメータを用いて同様のアプローチを用いることができるが、これは特に一般的ではない。いかなる問題にも、所望の近似精度と両立する最大の離散化スケールパラメータが存在するが、その値は、漸近速度と収束次数が誤差の正確な推定値を提供するために必要なほど小さくない可能性がある。実際の応用においては、ある離散化法が他の方法よりも大きな離散化スケールパラメータで所望の精度を与える場合、最終的な漸近収束が遅い場合でも、その離散化法は他の方法よりも収束が速いと言われることが多い。
参考文献 ^ abcdefgh Nocedal, Jorge; Wright, Stephen J. (1999). 数値最適化 （第1版）. ニューヨーク：Springer. pp. 28– 29. ISBN 978-0-387-98793-4 。 ^ Senning, Jonathan R. 「収束速度の計算と推定」 （PDF） . gordon.edu . 2020年8月7日 閲覧 。 ^ ハンドリー、ダグラス. 「収束速度」 (PDF) . ホイットマン大学. 2020年12月13日 閲覧 。 ^ Porta, FA (1989). 「Q次収束とR次収束について」 (PDF) . Journal of Optimization Theory and Applications . 63 (3): 415– 431. doi :10.1007/BF00939805. S2CID 116192710. 2020年7月31日 閲覧 。 ^ ab Van Tuyl, Andrew H. (1994). 「対数収束する系列の族の収束の加速」 (PDF) . 計算数学 . 63 (207): 229– 246. doi :10.2307/2153571. JSTOR 2153571. 2020年8月2日 閲覧 。 ^ Chanson, Jeffrey R. (2024年10月3日). 「収束の順序」. LibreTexts Mathematics . 2024年 10月3日 閲覧 。 ^ Nocedal, Jorge; Wright, Stephen J. (2006). 数値最適化 （第2版）. ベルリン、ニューヨーク: Springer-Verlag . ISBN 978-0-387-30303-1 。 ^ Senning, Jonathan R. 「収束速度の計算と推定」 （PDF） . gordon.edu . 2020年8月7日 閲覧 。 ^ Senning, Jonathan R. 「数値収束率の検証」 （PDF） . 2024年2月9日 閲覧 。 ^ バルカサル、ホセ L.;ガバロ、ホアキン。 「下限と上限によって指定される不均一な複雑さのクラス」 (PDF) 。 RAIRO – 理論情報学とアプリケーション – Informatique Théorique et Applications 。 23 (2): 180。ISSN 0988-3754 。 2017 年 3 月 14 日のオリジナルから アーカイブ (PDF) 。 2017 年 3 月 14 日 に取得 – Numdam 経由。 ^ Cucker, Felipe; Bürgisser, Peter (2013). 「A.1 Big Oh, Little Oh, and Other Comparisons」. Condition: The Geometry of Numerical Algorithms . Berlin, Heidelberg: Springer. pp. 467– 468. doi :10.1007/978-3-642-38896-5. ISBN 978-3-642-38896-5 。 ^ アポストル, トム・M. (1967). 微積分学 第1巻 (第2版). 米国: John Wiley & Sons. p. 286. ISBN 0-471-00005-1 。 ^ クヌース、ドナルド（1976年4月～6月）「ビッグ・オミクロン、ビッグ・オメガ、ビッグ・シータ」 SIGACTニュース 8 ( 2): 18– 24. doi : 10.1145/1008328.1008329 . S2CID 5230246 . ^ アポストル, トム・M. (1967). 微積分学 第1巻 (第2版). 米国: John Wiley & Sons. p. 396. ISBN 0-471-00005-1 。 ^ 「漸近的等式」、 数学百科事典 、 EMSプレス 、2001 [1994]
![{\textstyle {\sqrt[{m}]{|r|}}。}](https://wikimedia.org/api/rest_v1/media/math/render/svg/31020b77516ba8bab63bd9ea590caa8c630fbd43)
![{\textstyle {\sqrt[{m}]{|r|}};}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06abd59852f8c47697c7c4a123a10b497a9c027a)
