精度保証付き数値計算

テンプレート:Differential equations 精度保証付き数値計算^[1]（せいどほしょうつきすうちけいさん、Validated Numerics, Rigorous Computation, Reliable Computation, Verified Computation, Numerical Verification, テンプレート:Lang-de-short）とは数学的に厳密な誤差（前進誤差、後退誤差、丸め誤差、打切り誤差、離散化誤差）の評価を伴う数値計算のことであり、数値解析の一分野である^[2]。演算では区間演算を使用し、結果はすべて区間で出力する。精度保証付き数値計算はウォリック・タッカーによって14番目のスメイルの問題を解くのにも活用されており（テンプレート:Harvnbを参照）、力学系の研究では重要なツールとして位置づけられている^[3]^[4]^[5]^[6]。テンプレート:Seealso

精度保証付き数値計算の必要性

精度保証付き数値計算ではない通常の数値計算だと誤差によって不都合な事象が生じてしまう。いくつかのその例を挙げる。

Rumpの例題

1980年代にRumpは次のような例を提示した（テンプレート:Harvnbを参照）。

f (a, b) = 333.75 b^{6} + a^{2} (11 a^{2} b^{2} - b^{6} - 121 b^{4} - 2) + 5.5 b^{8} + \frac{a}{2 b}

という関数を考え、この関数に $a = 77617.0, b = 33096.0$ という値を与えて数値計算をしたときにどういう結果が得られるか実験した。計算機はIBMのメインフレームS/370を使用して、単精度、倍精度、拡張精度で実験を行い、それぞれ

単精度（10進約8桁）: $f (a, b) \sim 1.172603 . . .$
倍精度（10進約17桁）: $f (a, b) \sim 1.1726039400531 . . .$
拡張精度（10進約34桁）: $f (a, b) \sim 1.172603940053178 . . .$

の結果を得た。この結果を見ると、それぞれの精度に応じて途中の桁まで正しい値が得られているように思えたが、実は真の値は $f (a, b) = - 0.82739605 . . .$ であり、真の値とは符号さえ合わないような結果が得られていた。これは、「ある演算精度で計算してそれよりも高い演算精度で計算したときに双方の結果が近ければある程度は結果の正しさを確認できる」とは限らないことを示す例である^[2]^[7]。

幻影解

Breuer-Plum-McKennaはEmden方程式の境界値問題をスペクトル法によって離散化して解き、非対称な近似解が得られると報告した。しかしGidas-Ni-Nirenbergの理論的な解析手法によって非対称な解が存在しないことが証明されていた。つまりBreuer-Plum-McKennaが得た近似解は離散化誤差による幻影解だったのだ。これは珍しい例だが、微分方程式の解の存在を厳密に検討するには数値解法によって得られた近似解を検証しなければいけないことが分かる。

商用ソフトウェアの限界

ローレンツ方程式を精度保証付き数値計算とMATLABのode45（ODEソルバ）において最高精度を指定した場合で比較を行うと、ある程度時刻が進むと得られる解が違ってくるという実験例がある^[8]。

数値計算の誤差による事故

数値計算の誤差によって生じた事故として次の3つが挙げられる。

湾岸戦争でのミサイル迎撃失敗（1991年）^[9]
アリアン5ロケットの発射失敗（1996年）^[10]
選挙結果の間違い^[11]

主な研究分野

精度保証付き数値計算は主に以下の分野に分かれて研究がなされている^[2]^[12]。

数値線形代数 (en) における精度保証（行列積、連立一次方程式、固有値問題を扱う^[13]）
初等関数、特殊関数の精度保証
数値積分の精度保証^[22]^[23]^[24]

（ガウス求積、二重指数関数型数値積分公式などの数値積分公式の誤差評価を行う）

非線形方程式の精度保証付き数値解法（Newton-Kantorovichの定理^[13]^[25]^[26]^[27]、Krawczyk法^[27]、区間ニュートン法^[26]^[27]、Durand-Kerner-Aberth法^[13]^[26]に関する研究が含まれる）
ODE・PDEの精度保証付き数値解法（PDEでは有限要素法、関数解析の知識を駆使する^[25]^[28]）
積分方程式の精度保証付き数値解法
線形計画法の精度保証^[29]
計算幾何学における精度保証^[30]
HPC環境における精度保証

テンプレート:Seealso

主な精度保証付き数値計算ライブラリ

INTLAB: MATLAB/GNU Octaveを使用するライブラリである^[31]。
- VERSOFT (MATLAB/INTLABで開発されたライブラリ)^[32]
- INTSOLVER (大域最適化問題を解くためのライブラリ、INTLABを使用して開発された)^[33]
kv (C++によるライブラリである)^[34]
- テンプレート:GitHub
Arb C言語によるライブラリであり、様々な特殊関数の精度保証に対応している^[35]。
- テンプレート:GitHub
テンプレート:GitHub (Juliaによるライブラリ)^[36]^[37]

その他、様々なライブラリが開発されている^[38]^[39]。

テンプレート:Reflist

参考文献

洋書

テンプレート:Cite journal
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. SIAM. （区間演算に詳しい）
テンプレート:Citation
Rump, S. M. (2010). Verification methods: Rigorous results using floating-point arithmetic. en:Acta Numerica, 19, 287-449.

和書

大石進一：「非線形解析入門」、コロナ社（1997年4月）、ISBN 978-4-339-02600-9。（PDEの精度保証付き数値解法で用いる関数解析の知識を詳述している）
中尾充宏、山本野人：「精度保証付き数値計算：コンピュータによる無限への挑戦」、技術評論社 (1998年6月15日)、ISBN 4-535-78258-X。
大石進一：「数値計算」、裳華房 (1999年3月25日)、ISBN 4-7853-1514-8。
大石進一：「精度保証付き数値計算」、コロナ社 (2000年1月5日)、ISBN 4-339-02605-0。
中尾充宏、渡部善隆：「実例で学ぶ精度保証付き数値計算」、サイエンス社（SGCライブラリ 85）(2011年10月25日)。
テンプレート:Cite book

外部リンク

テンプレート:ウィキプロジェクトリンクテンプレート:ウィキポータルリンク

解説記事

テンプレート:偏微分方程式の数値解法テンプレート:数学テンプレート:Functional analysis

↑ 山本哲朗によって発案された用語である
↑ ^2.0 ^2.1 ^2.2 テンプレート:Harvnb
↑ テンプレート:Cite journal
↑ テンプレート:Cite journal
↑ D. Michelucci (2000), "Reliable computations for dynamic systems". Proc. SCAN 2000 / Interval 2000 — 9th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics
↑ テンプレート:Cite journal
↑ Loh, E., & Walster, G. W. (2002). Rump's example revisited. Reliable Computing, 8(3), 245-248.
↑ 精度保証付き数値計算の必要性
↑ テンプレート:Cite web
↑ テンプレート:Cite web
↑ Rounding error changes Parliament makeup
↑ 大石進一：「精度保証付き数値計算」、コロナ社、（1999年）
↑ ^13.0 ^13.1 ^13.2 テンプレート:Cite book
↑ テンプレート:PDFlink
↑ Yamanaka, N., Okayama, T., & Oishi, S. I. (2015, November). Verified Error Bounds for the Real Gamma Function Using Double Exponential Formula over Semi-infinite Interval. In International Conference on Mathematical Aspects of Computer and Information Sciences (pp. 224-228). Springer, Cham.
↑ Rump, S. M. (2014). Verified sharp bounds for the real gamma function over the entire floating-point range. Nonlinear Theory and Its Applications, IEICE, 5(3), 339-348.
↑ 大石進一(2008): 電子情報通信学会技術研究報告. NLP, 非線形問題, 108, 55-57.
↑ N. Yamamoto and N. Matsuda (2005): Trans. Jap. Soc. Indust. Appl. Math., 15, 347-359.
↑ Johansson, F. (2019). Numerical Evaluation of Elliptic Functions, Elliptic Integrals and Modular Forms. In Elliptic Integrals, Elliptic Functions and Modular Forms in Quantum Field Theory (pp. 269-293). Springer, Cham.
↑ Johansson, F. (2019). Computing Hypergeometric Functions Rigorously. ACM Transactions on Mathematical Software (TOMS), 45(3), 30.
↑ Johansson, F. (2015). Rigorous high-precision computation of the Hurwitz zeta function and its derivatives. Numerical Algorithms, 69(2), 253-270.
↑ Johansson, F. (2017). Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers, 66(8), 1281-1292.
↑ Johansson, F. (2018, July). Numerical integration in arbitrary-precision ball arithmetic. In International Congress on Mathematical Software (pp. 255-263). Springer, Cham.
↑ Johansson, F., & Mezzarobba, M. (2018). Fast and Rigorous Arbitrary-Precision Computation of Gauss--Legendre Quadrature Nodes and Weights. en:SIAM Journal on Scientific Computing, 40(6), C726-C747.
↑ ^25.0 ^25.1 Zeidler, E., Nonlinear Functional Analysis and Its Applications I-V. en:Springer Science & Business Media.
↑ ^26.0 ^26.1 ^26.2 杉原正顯, & 室田一雄. (1994). 数値計算法の数理. 岩波書店.
↑ ^27.0 ^27.1 ^27.2 テンプレート:PDFlink
↑ 中尾充宏, & 山本野人. (1998). 精度保証付き数値計算チュートリアル: 応用数理最前線.
中尾充宏, & 渡部善隆. (2011). 実例で学ぶ精度保証付き数値計算, サイエンス社.
テンプレート:Cite book
↑ Oishi, S., & Tanabe, K. (2009). Numerical Inclusion of Optimum Point for Linear Programming. JSIAM Letters, 1, 5-8.
↑ テンプレート:Cite journal
↑ S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.
↑ Rohn, J. (2009). VERSOFT: verification software in MATLAB/INTLAB.
↑ Montanher, T. M. (2009). Intsolver: An interval based toolbox for global optimization. Version 1.0.
↑ Overview of kv – a C++ library for verified numerical computation, Masahide Kashiwagi, SCAN 2018.
↑ Johansson, F. (2013). Arb: a C library for ball arithmetic. ACM Comm. Computer Algebra, 47(3/4), 166-169.
↑ Sanders, D. P., Benet, L., & Kryukov, N. (2016). The julia package ValidatedNumerics. jl and its application to the rigorous characterization of open billiard models. SCAN 2016, 124.
↑ ValidatedNumerics.jl: a new framework in Julia, David P. Sanders and Luis Benet, SCAN 2018.
↑ Interval and Verified Software
↑ テンプレート:Cite thesis

[1] 山本哲朗によって発案された用語である

[大石他2018-2] 2.0 ^2.1 ^2.2 テンプレート:Harvnb

[3] テンプレート:Cite journal

[4] テンプレート:Cite journal

[5] D. Michelucci (2000), "Reliable computations for dynamic systems". Proc. SCAN 2000 / Interval 2000 — 9th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics

[6] テンプレート:Cite journal

[7] Loh, E., & Walster, G. W. (2002). Rump's example revisited. Reliable Computing, 8(3), 245-248.

[8] 精度保証付き数値計算の必要性

[9] テンプレート:Cite web

[10] テンプレート:Cite web

[11] Rounding error changes Parliament makeup

[12] 大石進一：「精度保証付き数値計算」、コロナ社、（1999年）

[Yamamoto1-13] 13.0 ^13.1 ^13.2 テンプレート:Cite book

[14] テンプレート:PDFlink

[15] Yamanaka, N., Okayama, T., & Oishi, S. I. (2015, November). Verified Error Bounds for the Real Gamma Function Using Double Exponential Formula over Semi-infinite Interval. In International Conference on Mathematical Aspects of Computer and Information Sciences (pp. 224-228). Springer, Cham.

[16] Rump, S. M. (2014). Verified sharp bounds for the real gamma function over the entire floating-point range. Nonlinear Theory and Its Applications, IEICE, 5(3), 339-348.

[17] 大石進一(2008): 電子情報通信学会技術研究報告. NLP, 非線形問題, 108, 55-57.

[18] N. Yamamoto and N. Matsuda (2005): Trans. Jap. Soc. Indust. Appl. Math., 15, 347-359.

[19] Johansson, F. (2019). Numerical Evaluation of Elliptic Functions, Elliptic Integrals and Modular Forms. In Elliptic Integrals, Elliptic Functions and Modular Forms in Quantum Field Theory (pp. 269-293). Springer, Cham.

[20] Johansson, F. (2019). Computing Hypergeometric Functions Rigorously. ACM Transactions on Mathematical Software (TOMS), 45(3), 30.

[21] Johansson, F. (2015). Rigorous high-precision computation of the Hurwitz zeta function and its derivatives. Numerical Algorithms, 69(2), 253-270.

[22] Johansson, F. (2017). Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers, 66(8), 1281-1292.

[23] Johansson, F. (2018, July). Numerical integration in arbitrary-precision ball arithmetic. In International Congress on Mathematical Software (pp. 255-263). Springer, Cham.

[24] Johansson, F., & Mezzarobba, M. (2018). Fast and Rigorous Arbitrary-Precision Computation of Gauss--Legendre Quadrature Nodes and Weights. en:SIAM Journal on Scientific Computing, 40(6), C726-C747.

[zeidler-25] 25.0 ^25.1 Zeidler, E., Nonlinear Functional Analysis and Its Applications I-V. en:Springer Science & Business Media.

[sm-26] 26.0 ^26.1 ^26.2 杉原正顯, & 室田一雄. (1994). 数値計算法の数理. 岩波書店.

[takayasu-27] 27.0 ^27.1 ^27.2 テンプレート:PDFlink

[28] 中尾充宏, & 山本野人. (1998). 精度保証付き数値計算チュートリアル: 応用数理最前線.
中尾充宏, & 渡部善隆. (2011). 実例で学ぶ精度保証付き数値計算, サイエンス社.
テンプレート:Cite book

[29] Oishi, S., & Tanabe, K. (2009). Numerical Inclusion of Optimum Point for Linear Programming. JSIAM Letters, 1, 5-8.

[30] テンプレート:Cite journal

[31] S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.

[32] Rohn, J. (2009). VERSOFT: verification software in MATLAB/INTLAB.

[33] Montanher, T. M. (2009). Intsolver: An interval based toolbox for global optimization. Version 1.0.

[34] Overview of kv – a C++ library for verified numerical computation, Masahide Kashiwagi, SCAN 2018.

[35] Johansson, F. (2013). Arb: a C library for ball arithmetic. ACM Comm. Computer Algebra, 47(3/4), 166-169.

[36] Sanders, D. P., Benet, L., & Kryukov, N. (2016). The julia package ValidatedNumerics. jl and its application to the rigorous characterization of open billiard models. SCAN 2016, 124.

[37] ValidatedNumerics.jl: a new framework in Julia, David P. Sanders and Luis Benet, SCAN 2018.

[38] Interval and Verified Software

[39] テンプレート:Cite thesis

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

精度保証付き数値計算

目次