不動点反復法

数値解析において、不動点反復法は関数の不動点を計算する方法の一つである。

より具体的には、関数が与えられた場合${\displaystyle f}$実数値で定義され、点が与えられる${\displaystyle x_{0}}$の領域において${\displaystyle f}$固定点反復は $${\displaystyle x_{n+1}=f(x_{n}),\,n=0,1,2,\dots }$$これにより、次のシーケンス が生成される。${\displaystyle x_{0},x_{1},x_{2},\dots }$反復関数の適用${\displaystyle x_{0},f(x_{0}),f(f(x_{0})),\dots }$これは一点に収束することが期待される${\displaystyle x_{\text{fix}}}$。 もし${\displaystyle f}$が連続であれば、得られた${\displaystyle x_{\text{fix}}}$は固定点である${\displaystyle f}$つまり、 $${\displaystyle f(x_{\text{fix}})=x_{\text{fix}}.}$$

より一般的には、関数${\displaystyle f}$は、同じ空間内の値を持つ任意の距離空間上で定義できる。

• 最初のシンプルで便利な例は、a > 0の平方根を計算するバビロニアの方法であり、これは、${\displaystyle f(x)={\frac {1}{2}}\left({\frac {a}{x}}+x\right)}$つまり、 xとa / xの平均値に近づき、極限値に近づく${\displaystyle x={\sqrt {a}}}$（出発点が何であれ）${\displaystyle x_{0}\gg 0}$これは、以下に引用するニュートン法の特殊なケースです。
• 不動点反復${\displaystyle x_{n+1}=\cos x_{n}\,}$関数の唯一の不動点に収束する${\displaystyle f(x)=\cos x\,}$どの出発点でも${\displaystyle x_{0}.}$この例は、（遅くとも最初の反復ステップ後には）バナッハの不動点定理の仮定を満たします。したがって、n ステップ後の誤差は以下を満たします。${\displaystyle |x_{n}-x|\leq {q^{n} \over 1-q}|x_{1}-x_{0}|=Cq^{n}}$（私たちが連れて行ける場所）${\displaystyle q=0.85}$から始めると${\displaystyle x_{0}=1}$.) 誤差が倍数より小さい場合$\displaystyle q^{n}}$ある定数qに対して、線形収束が成り立つと言います。バナッハの不動点定理を用いると、線形収束する不動点反復を得ることができます。
• fが連続であるという要件は、次の例が示すように重要です。反復$${\displaystyle x_{n+1}={\begin{cases}{\frac {x_{n}}{2}},&x_{n}\neq 0\\1,&x_{n}=0\end{cases}}}$$すべての値に対して 0 に収束する${\displaystyle x_{0}}$しかし、0は関数の固定点ではない。$${\displaystyle f(x)={\begin{cases}{\frac {x}{2}},&x\neq 0\\1,&x=0\end{cases}}}$$この関数は連続ではないため${\displaystyle x=0}$実際には固定点は存在しない。

関数fの吸引不動点とは、fの不動点x _fixの近傍Uがx _fixの周囲に「十分近い」点の集合であり、 U内の任意のxの値に対して、不動点反復シーケンスが $${\displaystyle x,\ f(x),\ f(f(x)),\ f(f(f(x))),\dots }$$はU に含まれ、x _fixに収束する。x _fixの吸引領域は、そのような最大の近傍Uである。^{[ 1 ]}

自然余弦関数（「自然」とはラジアン単位であり、度数やその他の単位ではない）には、ちょうど1つの不動点があり、その不動点は吸引的です。この場合、「十分近い」というのは厳密な基準ではありません。これを実証するには、任意の実数から始めて、電卓のcosキーを繰り返し押してください（電卓が「ラジアン」モードになっていることを最初に確認してください）。最終的に、ドッティ数（約0.739085133）に収束します。これは不動点です。これは、余弦関数のグラフが直線と交わる点です。${\displaystyle y=x}$[ ^{2 ]​}

すべての固定点が吸引点であるとは限りません。たとえば、0 は関数f ( x ) = 2 xの固定点ですが、0 以外の値でこの関数を反復すると、急速に発散します。${\displaystyle f(x)=2x}$拒絶感がある。

吸引固定点は、リアプノフ安定である場合に安定固定点であると言われる。

不動点がリアプノフ安定であるが吸引的でない場合、その不動点は中立安定不動点と呼ばれる。2階線形同次微分方程式の中心は、中立安定不動点の一例である。

複数の吸引点を吸引固定セットにまとめることができる。

計算数学において、反復法とは、初期値を用いて一連の近似解を生成し、ある問題群に対する近似解を改善していく数学的手法であり、n番目の近似解はそれ以前の近似解から導出される。収束固定点反復法は、反復法を数学的に厳密に定式化したものである。

カオスゲームという用語は、任意の反復関数系(IFS)の不動点を生成する方法を指します。任意の点x _{0から始めて、連続する反復は}x _{k +1} = f _r ( x _k )として形成されます。ここで、f _rは、各反復でランダムに選択される、与えられた IFS の要素です。したがって、カオスゲームはランダム化された不動点反復です。カオスゲームでは、反復プロセスを多数回繰り返すことにより、シェルピンスキー三角形などのフラクタルの一般的な形状をプロットできます。より数学的に言えば、反復は IFS の不動点に収束します。x _{0 が}IFSのアトラクターに属する場合、すべての反復x _kはアトラクター内に留まり、確率 1 でアトラクター内に密な集合を形成します。

• バーデン、リチャード・L. 、フェアーズ、J・ダグラス（1985）。「不動点反復法」。数値解析（第3 版）。PWS Publishers。ISBN 0-87150-857-5。
• ホフマン、ジョー・D.、フランケル、スティーブン（2001）。「固定点反復法」。エンジニアと科学者のための数値計算法（第2 版）。ニューヨーク：CRC Press。pp. 141–145。ISBN  0-8247-0443-6。
• ジャッド、ケネス・L. (1998). 「固定点反復法」 .経済学における数値計算法. ケンブリッジ：MIT Press. pp. 165–167 . ISBN  0-262-10071-1。
• シュテルンベルク、シュロモ（2010）。「反復と不動点」。力学系（初版 ）。ドーバー出版。ISBN 978-0486477053。
• シャシキン、ユーリ A. (1991). 「9. 反復法」.不動点(初版 ). アメリカ数学会. ISBN 0-8218-9000-X。
• ローザ、アレッサンドロ（2021）。「階段状反復図のエピソード的歴史」。Antiquitates Mathematicae。15 : 3– 90.土井: 10.14708/am.v15i1.7056。S2CID 247259939。 

• 固定小数点アルゴリズムのオンライン
• 固定小数点反復計算オンライン計算機（ウェブ上の数学アシスタント）