固定小数点計算

固定小数点計算とは、与えられた関数の正確な固定小数点または近似固定小数点を計算する処理を指します。 [ 1 ]最も一般的な形式では、与えられた関数はブラウワーの固定小数点定理の条件を満たします。つまり、関数は連続であり、単位d立方体を自身に写像します。ブラウワーの固定小数点定理は、関数が固定小数点を持つことを保証しますが、その証明は構成的ではありません。近似固定小数点を計算するための様々なアルゴリズムが考案されています。このようなアルゴリズムは、次のような様々なタスクで使用されます。 f{\displaystyle f}f{\displaystyle f}f{\displaystyle f}

定義

3つの固定点を持つ関数の例
3つの固定点を持つ例の関数のグラフ

単位区間は で表され、単位d次元立方体は で表されます。連続関数は（ から自身へ）上で定義されます。は連続であるだけでなく、リプシッツ連続でもある、つまりの任意の に対して、 ある定数に対して となると仮定されることがよくあります。 E:=[0、1]{\displaystyle E:=[0,1]}Ed{\displaystyle E^{d}}f{\displaystyle f}Ed{\displaystyle E^{d}}Ed{\displaystyle E^{d}}f{\displaystyle f}L{\displaystyle L}|f（×）−f（y）|≤L⋅|×−y|{\displaystyle |f(x)-f(y)|\leq L\cdot |xy|}×、y{\displaystyle x,y}Ed{\displaystyle E^{d}}

の不動点とは、となる点である。ブラウワーの不動点定理によれば、 から への任意の連続関数は、 それ自体が不動点を持つ。しかし、一般の関数では、不動点は任意の実数となる可能性があるため、不動点を正確に計算することは不可能である。不動点計算アルゴリズムは、近似的な不動点を求める。近似的な不動点にはいくつかの基準がある。一般的な基準としては、以下のものがある：[ 2 ]f{\displaystyle f}×{\displaystyle x}Ed{\displaystyle E^{d}}f（×）＝×{\displaystyle f(x)=x}Ed{\displaystyle E^{d}}

  • 残差基準：近似パラメータ が与えられたとき、 のε残差固定点とは、 '内の点であって、 となる点である。ここで は最大ノルムを表す。つまり、差のすべての座標は最大でもεでなければならない。[ 3 ]：4 ε>0{\displaystyle \varepsilon >0}f{\displaystyle f}×{\displaystyle x}Ed{\displaystyle E^{d}}|f（×）−×|≤ε{\displaystyle |f(x)-x|\leq \epsilon }|⋅|{\displaystyle |\cdot |}d{\displaystyle d}f（×）−×{\displaystyle f(x)-x}
  • 絶対基準: 近似パラメータ が与えられた場合、の δ 絶対不動点はとなる 内の点であり、は の任意の不動点です。δ>0{\displaystyle \delta >0}f{\displaystyle f}×{\displaystyle x}Ed{\displaystyle E^{d}}|×−×0|≤δ{\displaystyle |x-x_{0}|\leq \delta }×0{\displaystyle x_{0}}f{\displaystyle f}
  • 相対的基準: 近似パラメータ が与えられた場合、の δ 相対的固定点は となるの点xであり、は の任意の固定点です。δ>0{\displaystyle \delta >0}f{\displaystyle f}Ed{\displaystyle E^{d}}|×−×0|/|×0|≤δ{\displaystyle |x-x_{0}|/|x_{0}|\leq \delta }×0{\displaystyle x_{0}}f{\displaystyle f}

リプシッツ連続関数の場合、絶対基準は残差基準よりも強力です。 が定数 でリプシッツ連続である場合、 が成り立ちます。は の不動点であるため、 が成り立ち、 となります。したがって、 δ 絶対不動点はを持つε残差不動点でもあります。 f{\displaystyle f}L{\displaystyle L}|×−×0|≤δ{\displaystyle |x-x_{0}|\leq \delta }|f（×）−f（×0）|≤L⋅δ{\displaystyle |f(x)-f(x_{0})|\leq L\cdot \delta }×0{\displaystyle x_{0}}f{\displaystyle f}|f（×）−×0|≤L⋅δ{\displaystyle |f(x)-x_{0}|\leq L\cdot \delta }|f（×）−×|≤（1+L）⋅δ{\displaystyle |f(x)-x|\leq (1+L)\cdot \delta }ε＝（1+L）⋅δ{\displaystyle \varepsilon =(1+L)\cdot \delta }

固定小数点計算アルゴリズムの最も基本的なステップは、値の問い合わせです。内の任意の値が与えられた場合、アルゴリズムには値 を返すオラクルが提供されます。近似固定小数点の精度は、オラクルの誤差に依存します。 ×{\displaystyle x}Ed{\displaystyle E^{d}}f〜{\displaystyle {\tilde {f}}}f{\displaystyle f}f（×）{\displaystyle f(x)}f〜（×）{\displaystyle {\tilde {f}}(x)}

関数は評価クエリを介してアクセス可能です。任意の に対して、アルゴリズムは を評価できます。アルゴリズムの実行時の複雑さは通常、必要な評価回数によって決まります。 f{\displaystyle f}×{\displaystyle x}f（×）{\displaystyle f(x)}

収縮関数

定数 を持つリプシッツ連続関数は、 のとき縮約的関数と呼ばれ、 のとき弱縮約的関数と呼ばれる。ブラウワーの条件を満たすすべての縮約関数は、唯一の不動点を持つ。さらに、縮約関数の不動点計算は、一般の関数よりも容易である。 L{\displaystyle L}L<1{\displaystyle L<1}L≤1{\displaystyle L\leq 1}

関数の反復を使用して固定小数点を計算する
関数の反復処理を使用して固定小数点を計算する

固定小数点計算の最初のアルゴリズムは、バナッハの固定小数点反復アルゴリズムでした。バナッハの固定小数点定理によれば、固定小数点反復を縮約写像に適用した場合、反復後の誤差は 単位となります。したがって、 -相対固定小数点に必要な評価回数は、およそ 単位となります。Sikorski と Wozniakowski [ 4 ]は、次元が大きい場合にバナッハのアルゴリズムが最適であることを示しました。具体的には、 のとき、 -相対固定小数点に対する任意のアルゴリズムに必要な評価回数は、反復アルゴリズムに必要な評価回数の 50% よりも大きくなります。 が 1 に近づくと、評価回数は無限大に近づくことに注意してください。のすべての関数に対して -絶対固定小数点を計算できる有限アルゴリズムはありません。[ 5 ]t{\displaystyle t}お（Lt）{\displaystyle O(L^{t})}δ{\displaystyle \delta}ログL⁡（δ）＝ログ⁡（δ）/ログ⁡（L）＝ログ⁡（1/δ）/ログ⁡（1/L）{\displaystyle \log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)}d≥ログ⁡（1/δ）/ログ⁡（1/L）{\displaystyle d\geq \log(1/\delta )/\log(1/L)}δ{\displaystyle \delta}L{\displaystyle L}δ{\displaystyle \delta}L＝1{\displaystyle L=1}

< 1かつd = 1の場合、最適なアルゴリズムはシコルスキーとウォズニアコフスキーによる固定点エンベロープ（FPE）アルゴリズムである。[ 4 ]このアルゴリズムは、クエリを用いてδ相対固定点を求め、またクエリを用いてδ絶対固定点を求める。これは固定点反復アルゴリズムよりも高速である。[ 6 ]L{\displaystyle L}お（ログ⁡（1/δ）+ログ⁡ログ⁡（1/（1−L）））{\displaystyle O(\log(1/\delta )+\log \log(1/(1-L)))}お（ログ⁡（1/δ））{\displaystyle O(\log(1/\delta ))}

が大きすぎず、かつ の場合、最適なアルゴリズムは内部楕円体アルゴリズム（楕円体法に基づく）です。[ 7 ]このアルゴリズムは、評価を使用してε残差固定点を求めます。 の場合、評価を使用して -絶対固定点を求めます。 d>1{\displaystyle d>1}L≤1{\displaystyle L\leq 1}お（d⋅ログ⁡（1/ε））{\displaystyle O(d\cdot \log(1/\epsilon ))}L<1{\displaystyle L<1}δ{\displaystyle \delta}お（d⋅[ログ⁡（1/δ）+ログ⁡（1/（1−L））]）{\displaystyle O(d\cdot [\log(1/\delta )+\log(1/(1-L))])}

ShellmanとSikorski [ 8 ]は、クエリのみを使用して、' を持つ2次元関数のε -残差固定小数点を計算するBEFix （Bisection Envelope Fixed-point）と呼ばれるアルゴリズムを発表しました。彼らは後に[ 9 ] 、同じ最悪ケースの保証を持ちながら、より優れた実験的性能を持つBEDFix（Bisection Envelope Deep-cut Fixed-point）と呼ばれる改良を発表しました。のとき、BEDFixはクエリ を使用して-絶対固定小数点を計算することもできます。L≤1{\displaystyle L\leq 1}2⌈ログ2⁡（1/ε）⌉+1{\displaystyle 2\lceil \log _{2}(1/\varepsilon )\rceil +1}L<1{\displaystyle L<1}δ{\displaystyle \delta}お（ログ⁡（1/ε）+ログ⁡（1/（1−L）））{\displaystyle O(\log(1/\varepsilon )+\log(1/(1-L)))}

ShellmanとSikorski [ 2 ]は、クエリを用いてL ≤ 1のd次元関数 のε残差固定小数点を計算するPFixと呼ばれるアルゴリズムを提示した。 < 1の場合、PFixは で実行でき、その場合、クエリを用いてδ絶対固定小数点を計算する。PFixは、 が1に近い場合、反復アルゴリズムよりも効率的である。このアルゴリズムは再帰的であり、d次元関数を( d -1)次元関数の再帰呼び出しによって処理する。 お（ログd⁡（1/ε））{\displaystyle O(\log ^{d}(1/\varepsilon ))}L{\displaystyle L}ε＝（1−L）⋅δ{\displaystyle \varepsilon =(1-L)\cdot \delta }お（ログd⁡（1/[（1−L）δ]））{\displaystyle O(\log ^{d}(1/[(1-L)\delta ]))}L{\displaystyle L}

微分可能関数のアルゴリズム

関数が微分可能で、アルゴリズムがその導関数（それ自身だけでなく）を評価できる場合、ニュートン法を使用することができ、はるかに高速になります。[ 10 ] [ 11 ]f{\displaystyle f}f{\displaystyle f}

一般関数: 1次元

リプシッツ定数> 1 を持つ関数の場合、固定小数点の計算は非常に難しくなります。 L{\displaystyle L}

1次元関数（d = 1）の場合、二分法を用いたクエリを用いて -絶対固定点を求めることができます。まず区間 から始め、各反復において を現在の区間の中心として を計算し、であれば の右側の部分区間を再帰し、そうでなければ の左側の区間を再帰します。現在の区間には常に固定点が含まれているため、クエリの後、残りの区間の任意の点は の-絶対固定点になることに注意してください。 （ はリプシッツ定数）を設定すると、クエリを用いてε -残差固定点が得られます。[ 3 ]δ{\displaystyle \delta}お（ログ⁡（1/δ））{\displaystyle O(\log(1/\delta ))}E:=[0、1]{\displaystyle E:=[0,1]}×{\displaystyle x}f（×）{\displaystyle f(x)}f（×）>×{\displaystyle f(x)>x}×{\displaystyle x}×{\displaystyle x}お（ログ⁡（1/δ））{\displaystyle O(\log(1/\delta ))}δ{\displaystyle \delta}f{\displaystyle f}δ:=ε/（L+1）{\displaystyle \delta :=\varepsilon /(L+1)}L{\displaystyle L}お（ログ⁡（L/ε）＝ログ⁡（L）+ログ⁡（1/ε））{\displaystyle O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))}

一般関数: 2次元以上

2次元以上の関数の場合、問題ははるかに困難になります。ShellmanとSikorski [ 2 ]は、任意の整数d ≥ 2および> 1に対して、 d次元の-Lipschitz関数の δ 絶対固定点を見つけるには、無限回の評価が必要になる可能性があることを証明しました。証明の考え方は次のとおりです。任意の整数T > 1と評価クエリの任意のシーケンスTに対して、定数 でLipschitz連続である2つの関数を構築し、これらすべてのクエリに同じ答えを生成できますが、そのうちの1つは( x 、0)に一意の固定点を持ち、もう一方は( x 、1)に一意の固定点を持ちます。T評価を使用するアルゴリズムはどれもこれらの関数を区別できないため、δ 絶対固定点を見つけることができません。これは任意の有限整数Tに当てはまります。 L{\displaystyle L}L{\displaystyle L}L{\displaystyle L}

ε残差固定点 を見つけるために、関数評価に基づくいくつかのアルゴリズムが開発されています。

単純法

一般関数の固定点を近似する最初のアルゴリズムは、1967年にハーバート・スカーフによって開発されました。 [ 12 ] [ 13 ]スカーフのアルゴリズムは、スペルナーの補題に似た構成で、完全にラベル付けされた「原始集合」を見つけることによってε残差固定点を見つけます。

ハロルド・クーン[ 14 ]による後のアルゴリズムでは、原始集合の代わりに単体と単体分割が使用されました。

単純化アプローチをさらに発展させて、オリン・ハリソン・メリル[ 15 ]は再開アルゴリズムを提示した。

ホモトピー法

B.カーティス・イーブス[ 16 ]はホモトピーの概念に基づいたホモトピー法を提示した。

関数fが与えられ、その固定点を見つけたい場合、アルゴリズムはf を近似するアフィン関数から始めて、固定点をたどりながらfに向かって変形することによって機能します。

ホモトピー法は市場均衡の計算に使われてきた。[ 17 ]

この方法は、1976年までに開発された様々なアルゴリズムを調査したマイケル・トッドの著書[ 18 ]でさらに詳しく説明されています。

その他のアルゴリズム

  • デイヴィッド・ゲイル[ 19 ]は、 n次元関数（単位d次元立方体上）の不動点を計算することは、d次元ゲームHex（d人のプレイヤーがd立方体の2つの反対面を繋げるゲーム）の勝者を決めることと同等であることを示した。望ましい精度ε
    • 大きさがkdの六角形のボードを構築します。各頂点zは単位n立方体の点z / kに対応します。け>1/ε{\displaystyle k>1/\バレプシロン }
    • 差( z / k ) - z / kを計算します。差はnベクトルであることに注意してください。f{\displaystyle f}
    • 頂点zに、差分ベクトルの最大座標を表す1, ..., dのラベルを付けます。
    • 得られたラベル付けは、 d人のプレイヤーによるd次元ヘックスゲームのプレイの可能性に対応する。このゲームには必ず勝者がおり、ゲイルは勝者パスを構築するためのアルゴリズムを提示している。
    • 勝利経路には、f i ( z / k ) - z / kが正となる点と、それに隣接するf i ( z / k ) - z / kが負となる点が必ず存在する。これは、これら2点の間に不動点が存在することを意味する。f{\displaystyle f}

最悪の場合、これらすべてのアルゴリズムに必要な関数評価の回数は、精度のバイナリ表現で指数関数的になります。つまり、 となります。 Ω（1/ε）{\displaystyle \Omega (1/\varepsilon )}

クエリの複雑さ

ヒルシュ、パパディミトリウ、ヴァヴァシスは、 [ 3 ] 関数評価に基づくfのε残差固定点を求めるアルゴリズムは関数評価を必要とすることを証明した。ここで、は関数のリプシッツ定数である（ であることに注意）。より正確には、 Ω（L′/ε）{\displaystyle \Omega (L'/\varepsilon )}L′{\displaystyle L'}f（×）−×{\displaystyle f(x)-x}L−1≤L′≤L+1{\displaystyle L-1\leq L'\leq L+1}

  • 2次元関数（d =2）の場合、厳密な境界が証明されています。Θ（L′/ε）{\displaystyle \Theta (L'/\varepsilon )}
  • 任意の d ≥ 3 について、d次元関数のε残差固定点を見つけるには、クエリと クエリが必要です。Ω（（L′/ε）d−2）{\displaystyle \Omega ((L'/\varepsilon )^{d-2})}お（（L′/ε）d）{\displaystyle O((L'/\バレプシロン )^{d})}

後者の結果は指数にギャップを残している。ChenとDeng [ 20 ]はこのギャップを埋めた。彼らは、任意のd ≥ 2およびに対して、 ε残差固定小数点を計算するために必要なクエリの数はであることを証明した。 1/ε>4d{\displaystyle 1/\varepsilon >4d}L′/ε>192d3{\displaystyle L'/\varepsilon >192d^{3}}Θ（（L′/ε）d−1）{\displaystyle \Theta ((L'/\varepsilon )^{d-1})}

離散固定小数点計算

離散関数とは、 （d次元整数格子）の部分集合上で定義される関数である。離散不動点定理はいくつか存在し、離散関数が不動点を持つ条件を述べている。例えば、飯村・室田・田村定理は、（特に）が の矩形部分集合からそれ自身への関数であり、かつ が超三次方向保存関数である場合、不動点を持つことを述べている。 Zd{\displaystyle \mathbb {Z} ^{d}}f{\displaystyle f}Zd{\displaystyle \mathbb {Z} ^{d}}f{\displaystyle f}f{\displaystyle f}

を整数立方体からそれ自身への方向保存関数とする。ChenとDeng [ 20 ]は、任意のd≥2およびn > 48dに対して、そのような固定点を計算するに は関数評価が必要であることを証明している。 f{\displaystyle f}{1、…、n}d{\displaystyle \{1,\dots ,n\}^{d}}Θ（nd−1）{\displaystyle \Theta (n^{d-1})}

Chen と Deng [ 21 ]は、異なる離散不動点問題を定義し、これを2D-BROUWERと呼んでいます。この問題では、グリッド上のすべてのxについて、 ( x ) - xが (0, 1)、(1, 0)、(-1, -1) のいずれかとなるような上の離散関数を考慮します。目的は、3 つのラベルがすべて出現するグリッド内の正方形を見つけることです。この関数は正方形をそれ自身にマッピングする必要があるため、直線x = 0 とy = 0 を (0, 1) または (1, 0) のいずれかに、直線x = nを (-1, -1) または (0, 1) のいずれかに、直線y = nを (-1, -1) または (1, 0) のいずれかにマッピングする必要があります。この問題は、2D-SPERNER (スペルナーの補題の条件を満たす三角形分割で完全にラベル付けされた三角形を計算する)に簡約できるため、PPAD 完全です。これは、非常に単純な関数であっても、近似固定小数点の計算が PPAD 完全であることを意味します。 f{\displaystyle f}{0,…,n}2{\displaystyle \{0,\dots ,n\}^{2}}f{\displaystyle f}f{\displaystyle f}{0,…,n}2{\displaystyle \{0,\dots ,n\}^{2}}

固定小数点計算と根探索アルゴリズムの関係

からRへの関数が与えられたとき、の根はにおける点xであって( x )=0 となるものである。 g のε根はにおける点xであって となるものである。 g{\displaystyle g}Ed{\displaystyle E^{d}}g{\displaystyle g}Ed{\displaystyle E^{d}}g{\displaystyle g}Ed{\displaystyle E^{d}}g(x)≤ε{\displaystyle g(x)\leq \varepsilon }

固定小数点計算は根を求める計算の特殊なケースです。上の関数が与えられたとき、 を定義します。Xがの固定小数点となるのは、 x がの根である場合に限ります。また、 xが のε残差固定小数点となるのは、 x がのε根である場合に限ります。したがって、任意の根を求めるアルゴリズム（関数の近似根を計算するアルゴリズム）を使用して、近似固定小数点を求めることができます。 f{\displaystyle f}Ed{\displaystyle E^{d}}g(x):=|f(x)−x|{\displaystyle g(x):=|f(x)-x|}f{\displaystyle f}g{\displaystyle g}f{\displaystyle f}g{\displaystyle g}

逆は真ではありません。一般関数の近似根を見つけることは、近似不動点を見つけることより難しい場合があります。特に、シコルスキー[ 22 ] は、 ε根を見つけるには関数評価が必要であることを証明しました。これにより、1 次元関数の場合でも指数下限が得られます (対照的に、1 次元関数のε残差不動点は、二分法を使用したクエリを使用して見つけることができます)。次に証明の概略を示します。[ 3 ]：35 の ある点x 0の周りの小さな立方体を除いて、 のどこでもεよりわずかに大きい関数を構築します。ここで、 x 0は の唯一の根です。が定数 でリプシッツ連続である場合、 x 0の周りの立方体の辺の長さは になります。 のε根を見つけるアルゴリズムはどれも、 全体をカバーする立方体の集合をチェックする必要があります。そのような立方体の数は少なくとも です。 Ω(1/εd){\displaystyle \Omega (1/\varepsilon ^{d})}O(log⁡(1/ε)){\displaystyle O(\log(1/\varepsilon ))}g{\displaystyle g}Ed{\displaystyle E^{d}}g{\displaystyle g}g{\displaystyle g}L{\displaystyle L}ε/L{\displaystyle \varepsilon /L}g{\displaystyle g}Ed{\displaystyle E^{d}}(L/ε)d{\displaystyle (L/\varepsilon )^{d}}

しかし、近似根を見つけることが近似不動点を見つけることと等価である関数のクラスがあります。 1 つの例[ 20 ]は、 が自分自身にマッピングされるような関数のクラスです （つまり、内のすべての x に対して がに存在します）。 これは、そのような関数すべてについて、関数がBrouwer の不動点定理の条件を満たすためです。Xがの不動点である場合、かつその場合x がの根であり、x がのε根である場合、かつその場合のみ、が のε残差不動点です。 Chen と Deng [ 20 ]は、これらの問題の離散的な変種が計算上等価であることを示しています。どちらの問題も 関数評価が必要です。 g{\displaystyle g}g(x)+x{\displaystyle g(x)+x}Ed{\displaystyle E^{d}}g(x)+x{\displaystyle g(x)+x}Ed{\displaystyle E^{d}}Ed{\displaystyle E^{d}}f(x):=g(x)+x{\displaystyle f(x):=g(x)+x}f{\displaystyle f}g{\displaystyle g}f{\displaystyle f}g{\displaystyle g}Θ(nd−1){\displaystyle \Theta (n^{d-1})}

コミュニケーションの複雑さ

RoughgardenとWeinstein [ 23 ]は、近似不動点を計算する際の通信複雑度を研究した。彼らのモデルでは、2つのエージェントが存在し、1つは関数 を知っており、もう1つは関数 を知っている。どちらの関数もリプシッツ連続であり、Brouwerの条件を満たす。目標は、合成関数の近似不動点を計算することである。彼らは、決定論的通信複雑度が であることを示している。 f{\displaystyle f}g{\displaystyle g}g∘f{\displaystyle g\circ f}Ω(2d){\displaystyle \Omega (2^{d})}

参考文献

  1. ^不動点の計算とその応用. 経済学と数学システム講義ノート. 第124巻. 1976年. doi : 10.1007/978-3-642-50327-6 . ISBN 978-3-540-07685-8。
  2. ^ a b cシェルマン、スペンサー；シコルスキー、K.（2003年12月）「無限ノルム固定点問題に対する再帰アルゴリズム」 Journal of Complexity 19 ( 6): 799– 834. doi : 10.1016/j.jco.2003.06.001 .
  3. ^ a b c d Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (1989年12月). 「Brouwer不動点を見つけるための指数的下限値」. Journal of Complexity . 5 (4): 379– 416. doi : 10.1016/0885-064X(89)90017-4 . S2CID 1727254 . 
  4. ^ a b Sikorski, K; Woźniakowski, H (1987年12月). 「不動点の複雑性、I」 . Journal of Complexity . 3 (4): 388– 405. doi : 10.1016/0885-064X(87)90008-2 .
  5. ^シコルスキー、クリストフ・A. (2001). 『非線形方程式の最適解』オックスフォード大学出版局. ISBN 978-0-19-510690-9。
  6. ^ Sikorski, K. (1989). 「固定点計算のための高速アルゴリズム」.同定と制御におけるロバスト性. pp.  49– 58. doi : 10.1007/978-1-4615-9552-6_4 . ISBN 978-1-4615-9554-0。
  7. ^ Huang, Z; Khachiyan, L; Sikorski, K (1999年6月). 「弱収縮写像の固定点の近似」 . Journal of Complexity . 15 (2): 200– 213. doi : 10.1006/jcom.1999.0504 .
  8. ^ Shellman, Spencer; Sikorski, K. (2002年6月). 「固定点のための2次元二分包絡線アルゴリズム」 . Journal of Complexity . 18 (2): 641– 659. doi : 10.1006/jcom.2001.0625 .
  9. ^ Shellman, Spencer; Sikorski, K. (2003年9月). 「アルゴリズム825：固定点に対する深層二分包絡線アルゴリズム」. ACM Transactions on Mathematical Software . 29 (3): 309– 325. doi : 10.1145/838250.838255 . S2CID 7786886 . 
  10. ^ Kellogg, RB; Li, TY; Yorke, J. (1976年9月). 「Brouwer不動点定理の構成的証明と計算結果」. SIAM Journal on Numerical Analysis . 13 (4): 473– 483. doi : 10.1137/0713041 .
  11. ^スメール、スティーブ（1976年7月）「価格調整の収束過程とグローバルニュートン法」『Journal of Mathematical Economics』3 (2): 107–120 . doi : 10.1016/0304-4068(76)90019-7 .
  12. ^スカーフ、ハーバート（1967年9月）「連続写像の固定点の近似」SIAM応用数学ジャーナル. 15 (5): 1328– 1343. doi : 10.1137/0115116 .
  13. ^ H. Scarfが最初のアルゴリズム的証明を発見した： Voitsekhovskii, MI (2001) [1994]. 「Brouwerの定理」 .数学百科事典. EMS Press . ISBN 1-4020-0609-8。。
  14. ^ Kuhn, Harold W. (1968). 「固定点の単純近似」 .米国科学アカデミー紀要. 61 (4 ) : 1238–1242 . doi : 10.1073 / pnas.61.4.1238 . JSTOR 58762. PMC 225246. PMID 16591723 .   
  15. ^メリル、オリン・ハリソン (1972).特定の上半連続点から集合への写像の固定点を計算するアルゴリズムの応用と拡張(論文). OCLC 570461463 . NAID 10006142329 .  
  16. ^ Eaves, B. Curtis (1972年12月). 「不動点計算のためのホモトピー」.数理計画. 3–3 (1): 1–22 . doi : 10.1007 /BF01584975 . S2CID 39504380 . 
  17. ^コデノッティ、ブルーノ;ペマラジュ、スリラム。バラダラジャン、カストゥリ (2004-12-01)。「市場均衡の計算」。SIGACT ニュース。35 (4): 23–37 .土井: 10.1145/1054916.1054927。ISSN 0163-5700。 
  18. ^不動点の計算とその応用. 経済学と数学システム講義ノート. 第124巻. 1976年. doi : 10.1007/978-3-642-50327-6 . ISBN 978-3-540-07685-8。
  19. ^ゲイル、デイヴィッド (1979). 「ヘックスゲームとブラウワーの不動点定理」.アメリカ数学月刊誌. 86 (10): 818– 827. doi : 10.2307/2320146 . JSTOR 2320146 . 
  20. ^ a b c d Chen, Xi; Deng, Xiaotie (2005). 「離散的および近似ブラウワー不動点のためのアルゴリズムについて」.第37回ACM計算理論シンポジウム論文集. pp.  323– 330. doi : 10.1145/1060590.1060638 . ISBN 1581139608. S2CID  16942881 .
  21. ^ Chen, Xi ; Deng, Xiaotie (2009年10月). 「2次元離散不動点問題の計算量について」.理論計算機科学. 410 (44): 4448– 4456. doi : 10.1016/j.tcs.2009.07.052 . S2CID 2831759 . 
  22. ^シコルスキー、K. (1984 年 6 月)。 「リプシッツ条件を満たす非線形方程式の最適解」。数学数学。43 (2): 225–240。土井: 10.1007/BF01390124。S2CID 120937024。 
  23. ^ Roughgarden, Tim; Weinstein, Omri (2016). 「近似固定点の通信複雑性について」. 2016 IEEE 第57回コンピュータサイエンス基礎シンポジウム (FOCS) . pp.  229– 238. doi : 10.1109/FOCS.2016.32 . ISBN 978-1-5090-3933-3. S2CID  87553 .

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Fixed-point_computation&oldid=1329677418」より取得