収束証明手法

収束の解析的定義${\displaystyle f}$限界まで${\displaystyle f_{\infty }}$^{[ 1 ]}はすべての${\displaystyle \epsilon }$存在する${\displaystyle k_{0}\in \mathbb {N} }$全ての人にとって${\displaystyle k>k_{0}}$、${\displaystyle \|f(k)-f_{\infty }\|<\epsilon }$この定義から最も直接的な証明手法は、${\displaystyle k_{0}}$そして、必要な不等式を証明します。${\displaystyle f_{\infty }}$事前に分からない場合は、以下の手法が役立つかもしれません。

多くの場合、収束に関心のある関数は次の形式をとる。${\displaystyle f(k+1)=T(f(k))}$何らかの変革のために${\displaystyle T}$。 例えば、${\displaystyle T}$マッピング可能${\displaystyle f(k)}$に${\displaystyle f(k+1)=Af(k)}$ある適合行列に対して${\displaystyle A}$、 となることによって${\displaystyle f(k)=A^{k}f(0)}$等比数列の行列一般化。あるいは、${\displaystyle T}$要素ごとの操作である可能性があり、たとえば、${\displaystyle f(k)}$その大きさの平方根によって。

このような場合、問題がバナッハの不動点定理の条件（定義域が空でない完備距離空間である）を満たすならば、収束を証明するだけで十分である。${\displaystyle T}$これは、不動点を持つことを証明するための縮小写像です。これには、${\displaystyle \|T(x)-T(y)\|<\|\lambda (xy)\|}$ある定数に対して${\displaystyle |\lambda |<1}$これはすべての人にとって固定されています${\displaystyle x}$そして${\displaystyle y}$2 つの縮約写像の合成は縮約写像なので、${\displaystyle T=T_{1}\circ T_{2}}$ならば、以下を示すだけで十分である。${\displaystyle T_{1}}$そして${\displaystyle T_{2}}$どちらも縮約写像です。

全ての有界列$\displaystyle \mathbb {R} ^{n}}$ボルツァーノ・ワイエルシュトラスの定理により、 は収束する部分列を持つ。これらの部分列がすべて同じ極限値を持つ場合、元の数列もその極限値に収束する。 のすべての部分列が同じ極限値を持つことが示されれば、${\displaystyle f}$同じ極限を持つ必要がある。例えば、変換の唯一の不動点が存在することを示すことによって証明する。${\displaystyle T}$不変集合は存在しない${\displaystyle T}$固定点を含まない${\displaystyle T}$そうすれば、初期数列もその極限値に収束しなければならない。

有界な単調列$\displaystyle \mathbb {R} ^{n}}$極限値に収束する。

この事実は直接利用できるだけでなく、アレクサンドル・リャプノフにちなんで名付けられた手法や定理を用いて、単調でない数列の収束を証明するためにも利用できる。これらの場合、関数を定義する。${\displaystyle V:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$そのため${\displaystyle V(f(k))}$単調である${\displaystyle k}$そしてこうして${\displaystyle V(f(k))}$収束する。${\displaystyle V}$がリアプノフ関数の条件を満たすならば、リアプノフの定理は、${\displaystyle f}$も収束する。リアプノフの定理は通常、常微分方程式に対して述べられるが、導関数を離散差分に置き換えることで、反復列にも適用できる。

基本的な要件${\displaystyle V}$リアプノフ関数であるということは、

1. ${\displaystyle V(x)>0}$すべての人々のために${\displaystyle x\neq 0}$そして${\displaystyle V(0)=0}$
2. ${\displaystyle V(f(k+1))-V(f(k))<0}$のために${\displaystyle f(k)\neq 0}$（個別のケース）または${\displaystyle {\dot {V}}(x)<0}$のために${\displaystyle x\neq 0}$（進行形）
3. ${\displaystyle V}$「放射状に無限」である、つまり${\textstyle \lim _{k\rightarrow \infty }V(f(k))=\infty }$任意のシーケンスに対して${\textstyle \lim _{k\rightarrow \infty }||f(k)||=\infty }$。

多くの場合、次の形式の二次リアプノフ関数${\displaystyle V(x)=x^{T}Ax}$より複雑な形式も一般的ですが、例えば確率分布の収束の研究におけるエントロピーなど、そのような形式も見られます。

遅延微分方程式の場合も同様のアプローチが適用されますが、リアプノフ関数はリアプノフ汎関数（リアプノフ・クラソフスキー汎関数とも呼ばれる）に置き換えられます。

条件2の不等式が弱い場合、ラサールの不変性原理を用いることができる。