カントロヴィッチの定理

カントロヴィッチの定理（またはニュートン・カントロヴィッチの定理）は、ニュートン法の半局所収束に関する数学的な定理である。 1948年にレオニード・カントロヴィッチによって初めて提唱された。[ 1 ] [ 2 ]バナッハの不動点定理と形式は似ているが、不動点ではなく零点の存在と一意性を述べている。[ 3 ]

ニュートン法は、ある条件下で方程式の解、または連立方程式のベクトル解に収束する点列を構築する。カントロヴィッチの定理は、この列の初期点に関する条件を与える。これらの条件が満たされる場合、初期点の近くに解が存在し、列はその点に収束する。[ 1 ] [ 2 ]×{\displaystyle x}f（×）＝0{\displaystyle f(x)=0}F（×）＝0{\displaystyle F(x)=0}

仮定

を開集合とし、ヤコビアンが局所リプシッツ連続である微分可能関数とする（例えば、が2回微分可能である場合）。つまり、任意のに対して、となる開集合が存在し、任意のに対してとなる定数が存在すると仮定する。X⊂Rn{\displaystyle X\subset \mathbb {R} ^{n}}F:X⊂Rn→Rn{\displaystyle F:X\subset \mathbb {R} ^{n}\to \mathbb {R} ^{n}}F′（×）{\displaystyle F^{\prime }(\mathbf {x} )}F{\displaystyle F}×∈X{\displaystyle x\in X}あなた⊂X{\displaystyle U\subset X}×∈あなた{\displaystyle x\in U}L>0{\displaystyle L>0}×、y∈あなた{\displaystyle \mathbf {x} ,\mathbf {y} \in U}

‖F′（×）−F′（y）‖≤L‖×−y‖{\displaystyle \|F'(\mathbf {x} )-F'(\mathbf {y} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|}

が成り立つ。左辺のノルムは作用素ノルムである。言い換えれば、任意のベクトルに対して不等式 v∈Rn{\displaystyle \mathbf {v} \in \mathbb {R} ^{n}}

‖F′（×）（v）−F′（y）（v）‖≤L‖×−y‖‖v‖{\displaystyle \|F'(\mathbf {x} )(\mathbf {v} )-F'(\mathbf {y} )(\mathbf {v} )\|\leq L\;\|\mathbf {x} -\mathbf {y} \|\,\|\mathbf {v} \|}

保持する必要があります。

任意の初期点を選ぶ。が可逆であると仮定し、ニュートンステップを構築する。×0∈X{\displaystyle \mathbf {x} _{0}\in X}F′（×0）{\displaystyle F'(\mathbf {x} _{0})}h0＝−F′（×0）−1F（×0）。{\displaystyle \mathbf {h} _{0}=-F'(\mathbf {x} _{0})^{-1}F(\mathbf {x} _{0}).}

次の仮定は、次の点だけでなく球体全体が集合 内に含まれるというものです。 をこの球体上のヤコビアン（存在すると仮定）のリプシッツ定数とします。 ×1＝×0+h0{\displaystyle \mathbf {x} _{1}=\mathbf {x} _{0}+\mathbf {h} _{0}}B（×1、‖h0‖）{\displaystyle B(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}X{\displaystyle X}M{\displaystyle M}

最後の準備として、可能な限り、シーケンス、、を次のように 再帰的に構築します。（×け）け{\displaystyle (\mathbf {x} _{k})_{k}}（hけ）け{\displaystyle (\mathbf {h} _{k})_{k}}（αけ）け{\displaystyle (\alpha _{k})_{k}}

hけ＝−F′（×け）−1F（×け）αけ＝M‖F′（×け）−1‖‖hけ‖×け+1＝×け+hけ。{\displaystyle {\begin{alignedat}{2}\mathbf {h} _{k}&=-F'(\mathbf {x} _{k})^{-1}F(\mathbf {x} _{k})\\[0.4em]\alpha _{k}&=M\,\|F'(\mathbf {x} _{k})^{-1}\|\,\|\mathbf {h} _{k}\|\\[0.4em]\mathbf {x} _{k+1}&=\mathbf {x} _{k}+\mathbf {h} _{k}.\end{alignedat}}}

声明

さて、もしそうなら α0≤12{\displaystyle \alpha _{0}\leq {\tfrac {1}{2}}}

  1. の解は閉じた球体の中に存在し、×∗{\displaystyle \mathbf {x} ^{*}}F（×∗）＝0{\displaystyle F(\mathbf {x} ^{*})=0}B¯（×1、‖h0‖）{\displaystyle {\bar {B}}(\mathbf {x} _{1},\|\mathbf {h} _{0}\|)}
  2. から始まるニュートン反復法は、少なくとも線形収束の順序でに収束します。×0{\displaystyle \mathbf {x} _{0}}×∗{\displaystyle \mathbf {x} ^{*}}

より正確だが証明が少し難しい記述は、二次多項式の 根を使うものである。t∗≤t∗∗{\displaystyle t^{\ast }\leq t^{**}}

p（t）＝（12L‖F′（×0）−1‖−1）t2−t+‖h0‖{\displaystyle p(t)=\left({\tfrac {1}{2}}L\|F'(\mathbf {x} _{0})^{-1}\|^{-1}\right)t^{2}-t+\|\mathbf {h} _{0}\|}、
t∗/∗∗＝2‖h0‖1±1−2α0{\displaystyle t^{\ast /**}={\frac {2\|\mathbf {h} _{0}\|}{1\pm {\sqrt {1-2\alpha _{0}}}}}}

とその比率

θ＝t∗t∗∗＝1−1−2α01+1−2α0。{\displaystyle \theta ={\frac {t^{*}}{t^{**}}}={\frac {1-{\sqrt {1-2\alpha _{0}}}}{1+{\sqrt {1-2\alpha _{0}}}}}.}}

それから

  1. 閉じた球の中に解が存在する×∗{\displaystyle \mathbf {x} ^{*}}B¯（×1、θ‖h0‖）⊂B¯（×0、t∗）{\displaystyle {\bar {B}}(\mathbf {x} _{1},\theta \|\mathbf {h} _{0}\|)\subset {\bar {B}}(\mathbf {x} _{0},t^{*})}
  2. 大きなボールの中にあるユニークなものB（×0、t∗∗）{\displaystyle B(\mathbf {x} _{0},t^{*\ast })}
  3. そして 、の解への収束は、2次多項式のニュートン反復法がその最小根に収束することによって支配される。[ 4 ]F{\displaystyle F}p（t）{\displaystyle p(t)}t∗{\displaystyle t^{\ast}}t0＝0、tけ+1＝tけ−p（tけ）p′（tけ）{\displaystyle t_{0}=0,\,t_{k+1}=t_{k}-{\tfrac {p(t_{k})}{p'(t_{k})}}}
    ‖xk+p−xk‖≤tk+p−tk.{\displaystyle \|\mathbf {x} _{k+p}-\mathbf {x} _{k}\|\leq t_{k+p}-t_{k}.}
  4. 二次収束は誤差推定から得られる[ 5 ]
    ‖xn+1−x∗‖≤θ2n‖xn+1−xn‖≤θ2n2n‖h0‖.{\displaystyle \|\mathbf {x} _{n+1}-\mathbf {x} ^{*}\|\leq \theta ^{2^{n}}\|\mathbf {x} _{n+1}-\mathbf {x} _{n}\|\leq {\frac {\theta ^{2^{n}}}{2^{n}}}\|\mathbf {h} _{0}\|.}

推論

1986年に山本は、ドーリング（1969）、オストロフスキー（1971、1973）[ 6 ] [ 7 ]グラッグ・タピア（1974）、ポトラ・プタク（1980）、[8] ミエル（1981）、[ 9 ]ポトラ（ 1984）、[ 10 ] などのニュートン法の誤差評価がカントロヴィッチの定理から導かれることを証明した。[ 11 ]

一般化

カントロヴィッチの定理にはq類似のものが存在する。[ 12 ] [ 13 ]その他の一般化/変形については、Ortega & Rheinboldt (1970)を参照のこと。[ 14 ]

アプリケーション

大石と田辺は、カントロヴィッチの定理を適用すれば線形計画法の信頼できる解が得られると主張した。[ 15 ]

参考文献

  1. ^ a b Deuflhard, P. (2004).非線形問題に対するニュートン法. アフィン不変性と適応アルゴリズム. Springer Series in Computational Mathematics. 第35巻. ベルリン: Springer. ISBN 3-540-21099-7。
  2. ^ a b Zeidler, E. (1985).非線形関数解析とその応用：第1部：不動点定理. ニューヨーク：Springer. ISBN 0-387-96499-1。
  3. ^デニス, ジョン・E. ;シュナーベル, ロバート・B. (1983). 「カントロヴィッチ定理と縮約写像定理」 .制約なし最適化と非線形方程式の数値解析法. エングルウッド・クリフス: プレンティス・ホール. pp.  92– 94. ISBN 0-13-627216-9。
  4. ^ Ortega, JM (1968). 「ニュートン・カントロヴィッチの定理」.アメリカ数学月刊誌. 75 (6): 658– 660. doi : 10.2307/2313800 . JSTOR 2313800 . 
  5. ^ Gragg, WB; Tapia, RA (1974). 「ニュートン-カントロビッチ定理の最適誤差境界」. SIAM Journal on Numerical Analysis . 11 (1): 10– 13. Bibcode : 1974SJNA...11...10G . doi : 10.1137/0711002 . JSTOR 2156425 . 
  6. ^オストロフスキー、AM (1971)。 「ニュートンとバナッハの空間の方法」。CRアカデミー。科学。パリ。27 (A): 1251–1253。
  7. ^ Ostrowski, AM (1973). 『ユークリッド空間とバナッハ空間における方程式の解』ニューヨーク: アカデミック・プレス. ISBN 0-12-530260-6。
  8. ^ Potra, FA; Ptak, V. (1980). 「ニュートン過程の鋭い誤差境界」. Numer. Math . 34 : 63–72 . doi : 10.1007/BF01463998 .
  9. ^ Miel, GJ (1981). 「ニュートン法におけるカントロヴィッチの定理の最新版」. Computing . 27 (3): 237– 244. doi : 10.1007/BF02237981 .
  10. ^ポトラ、FA (1984)。 「ニュートン法の事後誤差推定について」。Beiträge zur Numericsche Mathematik。12：125～ 138。
  11. ^山本 孝文 (1986). 「カントロヴィッチの仮定の下でニュートン法の鋭い誤差境界を求める方法」.数値数学. 49 ( 2–3 ): 203– 220. doi : 10.1007/BF01389624 .
  12. ^ Rajkovic, PM; Stankovic, MS; Marinkovic, SD (2003). 「方程式とシステムの解法におけるq反復法について」Novi Sad J. Math . 33 (2): 127– 137.
  13. ^ Rajković, PM; Marinković, SD; Stanković, MS (2005). 「連立方程式の解法におけるq-ニュートン–カントロビッチ法について」.応用数学と計算. 168 (2): 1432– 1448. doi : 10.1016/j.amc.2004.10.035 .
  14. ^ Ortega, JM; Rheinboldt, WC (1970).多変数非線形方程式の反復解法. SIAM. OCLC 95021 . 
  15. ^大石 誠; 田辺 健一 (2009). 「線形計画法における最適点の数値的包含」 .応用数理学会論文集. 1 : 5–8 . doi : 10.14495/jsiaml.1.5 .

さらに読む

「 https://en.wikipedia.org/w/index.php?title=Kantorovich_theorem&oldid=1286472521」より取得