区間ニュートン法のソースを表示

'''区間ニュートン法''' ({{lang-en-short|Interval Newton method}}, {{lang-de-short|Intervall Newton Verfahren}}) は[[ニュートン法]]の[[区間演算]]バージョンであり、非線形方程式系に対する[[精度保証付き数値計算]]法、[[反復法]]である<ref name="oishi">『精度保証付き数値計算の基礎』[[大石進一]] 編著、[[コロナ社 (出版社)|コロナ社]]、2018年。</ref><ref name="sm"> [[杉原正顯]], & 室田一雄. (1994). 数値計算法の数理. [[岩波書店]].</ref><ref name="rump">Rump, S. M. (2010). Verification methods: Rigorous results using floating-point arithmetic. [[:en:Acta Numerica]], 19, 287-449.</ref><ref name="moore">Moore, R. E. (1966). Interval analysis (Vol. 4). Englewood Cliffs, NJ: Prentice-Hall.</ref>。[[ニュートン＝カントロビッチの定理]]と違って[[バナッハ空間]]では適用できない ([[ユークリッド空間]]にしか適用できない) という弱点はあるものの<ref name="oishi"/><ref name="sm"/><ref name="rump"/><ref name="moore"/>、非線形方程式系に対する[[精度保証付き数値計算]]法として標準的な手法となっている<ref name="oishi"/><ref name="sm"/><ref name="rump"/><ref name="moore"/>。
==定義と主な性質==
方程式<math>f(x)=0</math>に対する区間ニュートン法は次の反復で定義される<ref name="oishi"/><ref name="sm"/><ref name="rump"/><ref name="moore"/>：
:<math>x_{i+1}:=N(x_i)\cap x_i,\quad N(x_i):=\mathrm{mid}(x_i)-\frac{f\left(\mathrm{mid}(x_i)\right)}{f^\prime(x_i)},\quad 0\notin f^\prime(x_i).</math>
* ([[ニュートン法]]と同様の<ref name="sm"/>) 2次収束性 ({{lang-en-short|Quadratic convergence}})<ref name="moore"/>
* 半局所収束性 ({{lang-en-short|Semi-local convergence}}, 初期値に何らかの条件を課すだけで[[零点]]の一意存在を示せるという性質)<ref name="oishi"/><ref name="rump"/><ref>[[ゲッツ・アールフェルト|G. Alefeld]]: Inclusion methods for systems of nonlinear equations in: J. Herzberger (Ed.), Topics in Validated Computations (1994), Studies in Computational Mathematics, Elsevier, Amsterdam, 7–26.</ref>
* ある条件の下で[[零点]]の非存在が示される<ref name="oishi"/>
==変種==
導関数の計算が困難なときには[[ニュートン法]]の代わりに[[割線法]]を使うように<ref name="intro">皆本晃弥. (2005). UNIX & Information Science-5 C 言語による数値計算入門. [[サイエンス社]].</ref>、導関数の計算が困難なときには区間ニュートン法の代わりに[[割線法]]の[[区間演算]]バージョンを使うのは代替策として有力である<ref name="secant">Neumaier, A. (1984). An interval version of the secant method. BIT Numerical Mathematics, 24(3), 366-372.</ref>。[[区間演算]]バージョンでも収束速度は同じである<ref name="intro"/><ref name="secant"/>。
:<math>x_{i+1}:=r(x_i)\cap x_i,\quad r(x_i):=\mathrm{mid}(x_i)-\frac{f\left(\mathrm{mid}(x_i)\right)(x_i-x_{i-1})}{f(x_i)-f(x_{i-1})}.</math>
==関連項目==
*[[ニュートン法]]
*[[区間演算]]
*[[精度保証付き数値計算]]
==外部リンク==
*{{PDFlink|[http://www.sr3.t.u-tokyo.ac.jp/jsiam/slides/2016/takayasu_web.pdf 非線形方程式に対する解の精度保証付き数値計算]}}
*[https://www.slideshare.net/JohannesKananen/interval-newton-method Interval Newton Method], from [[SlideShare]]
==関連論文==
===和文===
*相馬隆郎, [[大石進一]], & 堀内和夫. (1998). 区間 Newton 写像を用いた非線形常微分方程式の解の数値的存在検証法. [[電子情報通信学会]]技術研究報告. NLP, 非線形問題, 97(592), 119-124.
===英文===
* Nickel, K. (1971). On the Newton method in interval analysis (No. MRC-TSR-1136). WISCONSIN UNIV-MADISON MATHEMATICS RESEARCH CENTER.
* Hansen, E. R., & Greenberg, R. I. (1983). An interval Newton method. Applied Mathematics and Computation, 12(2-3), 89-98.
* Hua, J. Z., Brennecke, J. F., & Stadtherr, M. A. (1996). Reliable prediction of phase stability using an interval Newton method. Fluid Phase Equilibria, 116(1-2), 52-59.
* Van Voorhis, T. (2002). A global optimization algorithm using Lagrangian underestimates and the interval Newton method. Journal of Global Optimization, 24(3), 349-370.
* Lin, Y., & Stadtherr, M. A. (2004). LP strategy for the interval-Newton method in deterministic global optimization. Industrial & engineering chemistry research, 43(14), 3741-3749.
* Gecegormez, H., & Demirel, Y. (2005). Phase stability analysis using interval Newton method with NRTL model. Fluid phase equilibria, 237(1-2), 48-58.
* Beck, P. D., & Nehmeier, M. (2012, June). Parallel interval newton method on [[CUDA]]. In International Workshop on Applied Parallel Computing (pp. 454-464). Springer, Berlin, Heidelberg.

==参考文献==
* Tucker, W. (2011). Validated Numerics: A Short Introduction to Rigorous Computations. [[:en:Princeton University Press]].
* Moore, R. E., Kearfott, R. B., & Cloud, M. J. (2009). Introduction to Interval Analysis. [[:en:Society for industrial and applied mathematics|SIAM]].
==出典==
{{reflist}}

{{applied-math-stub}}


{{DEFAULTSORT:くかんにゆうとんほう}}
[[Category:数値解析]]
[[Category:計算科学]]
[[Category:応用数学]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]