固定小数点反復

数値解析において、固定小数点反復法は関数の 固定小数点を計算する方法です。

より具体的には、実数値を持つ実数上で定義された関数との領域内の点が与えられた場合、固定点反復は となり、 反復関数適用のシーケンス が生成され、点 に収束することが期待されます。 が連続している場合、得られた がの固定点であることが証明できます。つまり、 ${\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の平方根を計算するバビロニア法です。これは、 （開始点 から） 、つまりxとa / xの平均値を取って、限界に近づくというものです。これは、以下に引用するニュートン法の特殊なケースです。${\displaystyle f(x)={\frac {1}{2}}\left({\frac {a}{x}}+x\right)}$${\displaystyle x={\sqrt {a}}}$${\displaystyle x_{0}\gg 0}$
• 固定小数点反復は、任意の開始点に対して関数の唯一の固定小数点に収束します。この例は、（遅くとも最初の反復ステップの後に）バナッハの固定小数点定理の仮定を満たしています。したがって、n ステップ後の誤差は（から開始する場合はを取ることができます）を満たします。誤差が何らかの定数qに対しての倍数より小さい場合、線形収束があるといいます。バナッハの固定小数点定理により、線形収束を伴う固定小数点反復を得ることができます。${\displaystyle x_{n+1}=\cos x_{n}\,}$${\displaystyle f(x)=\cos x\,}$${\displaystyle x_{0}.}$${\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}}$
• 次の例が示すように、 fが連続であるという要件は重要です。のすべての値に対して、反復は0 に収束します。ただし、この関数は で連続しておらず、実際には固定点がないため、 0 は関数の固定点ではありません。$${\displaystyle x_{n+1}={\begin{cases}{\frac {x_{n}}{2}},&x_{n}\neq 0\\1,&x_{n}=0\end{cases}}}$$${\displaystyle x_{0}}$$${\displaystyle f(x)={\begin{cases}{\frac {x}{2}},&x\neq 0\\1,&x=0\end{cases}}}$$${\displaystyle x=0}$

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

自然余弦関数（「自然」とはラジアン を意味し、度や他の単位ではない）には、正確に 1 つの固定点があり、その固定点は を引き付けます。この場合、「十分に近い」というのはまったく厳密な基準ではありません。これを証明するには、任意の実数から始めて、電卓のcosキーを繰り返し押します（最初に電卓が「ラジアン」モードになっていることを確認します）。最終的に、固定点であるDottie 数（約 0.739085133）に収束します。それは、余弦関数のグラフが線 と交差する場所です。^[2]${\displaystyle y=x}$

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

吸引固定点は、それがリャプノフ安定でもある場合、安定固定点であると言われます。

固定点は、リャプノフ安定だが吸引しない場合は、中立的に安定な固定点と呼ばれます。2 次線形同次微分方程式の中心は、中立的に安定な固定点の例です。

複数の吸引ポイントを吸引固定セットに収集できます。

バナッハの不動点定理は、引き寄せる不動点が存在するための十分な条件を与える。完全な計量空間上で定義された収縮写像関数は正確に 1 つの不動点を持ち、不動点反復は関数のドメイン内の任意の初期推定値に対してその不動点に向かって引き寄せられる。一般的な特殊なケースは、(1) が実数値を持つ実数直線上で定義され、リプシッツ定数 でリプシッツ連続であること、および (2) 関数f が不動点x _fixの開近傍で連続的に微分可能であり、 である。 ${\displaystyle f}$${\displaystyle x_{0}}$${\displaystyle f}$${\displaystyle L<1}$${\displaystyle |f'(x_{\text{fix}})|<1}$

他にも不動点定理はありますが、すべての不動点が魅力的であるとは限らないため、この定理は特に有用です。不動点反復を構築する場合、不動点に収束することを確認することが非常に重要です。通常、バナッハの不動点定理を使用して、不動点が魅力的であることを示すことができます。

固定点の引き付けは、アトラクターというより広い数学的概念の特殊なケースです。固定点反復は、1 つの変数上の離散的な動的システムです。分岐理論は、動的システムを研究し、固定点の引き付け、周期軌道、またはストレンジ アトラクターなどのさまざまな動作を分類します。例となるシステムは、ロジスティック マップです。

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

反復シーケンスの収束速度は、アンダーソン加速やエイトケンのデルタ二乗過程などの収束加速法を使用することで向上できます。エイトケン法を固定小数点反復に適用したものはステフェンセン法と呼ばれ、ステフェンセン法では少なくとも 2 次収束率が得られることが示されています。

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

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

• 固定小数点アルゴリズムオンライン
• 固定小数点反復オンライン計算機 (Web 上の数学アシスタント)