区間演算
区間演算（くかんえんざん、英: Interval arithmetic、独: Intervall arithmetik）（あるいはそれを用いた区間解析(interval analysis)）は数学者たちによって1950年代から1960年代にかけて作られた手法であり、数学的計算における丸め誤差と測定誤差に対して評価を行い信頼できる結果をもたらす数値的な手法を開発するものである[1]。簡単に言うと、すべての値をとりうる数値の範囲で表現するのである。例えば、人の身長を通常の計算で2メートルと表わす代わりに、1.97メートルから2.03メートルの範囲であると表すのである。
この概念は様々な用途がある。主な使用方法は計算途中の丸め誤差を把握することである。区間演算は最適化問題や微分方程式の信頼できる求解を助けるという役割もある[1]。
数学的に表現すると、不確かな実数xについて扱う代わりに、xを含む区間[a, b]を扱う。xを代入した関数fの値も不明である。区間演算において関数fは区間[c, d]を生成する。[c, d]は[a, b]内にある全てのxについてf(x)が取りうる値を表す[1]。
導入 編集
区間演算の主な目的は与えられた関数の値域の上界と下界を簡単に計算することである[1]。端点は上限、下限とは限らない。なぜならば端点の具体的計算は困難もしくは不可能な場合があるからだ。伝統的な実数の計算と同様に、四則演算と区間値の関数が定義されなければならない[2]。より複雑な関数もこれに基づいて計算される[2]。
演算の定義 編集
区間演算では四則演算を以下のようにして行う[1]：
![{\displaystyle [x_{1},x_{2}]+[y_{1},y_{2}]=[x_{1}+y_{1},x_{2}+y_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b542d7b116e1934f6f7cba9ef63333cc26a77e3)
![{\displaystyle [x_{1},x_{2}]-[y_{1},y_{2}]=[x_{1}-y_{2},x_{2}-y_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/85c4d944e4f5856cca9f868e7f42649a5ef8d30f)
![{\displaystyle [x_{1},x_{2}]\cdot [y_{1},y_{2}]=[\min(x_{1}y_{1},x_{1}y_{2},x_{2}y_{1},x_{2}y_{2}),\max(x_{1}y_{1},x_{1}y_{2},x_{2}y_{1},x_{2}y_{2})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/873a6844ded4d23bd1a4dd067105b62ea9d149b3)
![{\displaystyle {\frac {[x_{1},x_{2}]}{[y_{1},y_{2}]}}=[x_{1},x_{2}]\cdot {\frac {1}{[y_{1},y_{2}]}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1587a3bd99c9a574533aa4de686aec4ee5c7daa4)
- ただし、
![{\displaystyle {\begin{aligned}{\frac {1}{[y_{1},y_{2}]}}&=\left[{\tfrac {1}{y_{2}}},{\tfrac {1}{y_{1}}}\right]&&0\notin [y_{1},y_{2}]\\{\frac {1}{[y_{1},0]}}&=\left[-\infty ,{\tfrac {1}{y_{1}}}\right]\\{\frac {1}{[0,y_{2}]}}&=\left[{\tfrac {1}{y_{2}}},\infty \right]\\{\frac {1}{[y_{1},y_{2}]}}&=\left[-\infty ,{\tfrac {1}{y_{1}}}\right]\cup \left[{\tfrac {1}{y_{2}}},\infty \right]=[-\infty ,\infty ]&&0\in (y_{1},y_{2})\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7af098b91d736602987dcd64d61be9848222b138)
である。
表記 編集
数式中における区間の表記を簡明にするため、カギ括弧が使われる[1]。 よって を区間の表記のために使うことができる。有限区間全体の集合を表す記号として
![{\displaystyle [x]\equiv [x_{1},x_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d322dcd67b7a0ab33a04094ffef417552119ad2)
![{\displaystyle [\mathbb {R} ]:=\left\{\,[x_{1},x_{2}]\,|\,x_{1}\leq x_{2}{\text{ and }}x_{1},x_{2}\in \mathbb {R} \cup \{-\infty ,\infty \}\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c246d6579baaaa59be83c8d31e670ea1a334646)
も使われる。区間を成分に持つベクトルについては または を用いる。
![{\displaystyle \left([x]_{1},\ldots ,[x]_{n}\right)\in [\mathbb {R} ]^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fb4b1fbe11a16a257ea7f976b25b3e95c65a56b)
![{\displaystyle [\mathbf {x} ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4290e7f30dee955efaed120787cce1b1b5ec6134)
複素区間演算 編集
区間は中心から一定の距離を持った点の軌跡として定義することができて、この定義は実数から複素数に拡張することもできる[3]。 実数の場合と同様に、複素数の計算も不確かなデータを含む。区間が実の閉区間で複素数が実数のペアであることから、区間演算の応用を実数計算の不確かさを測るのに限定する理由はない[4]。よって区間演算は複素数計算での不確かさの領域を特定するために複素区間へ拡張できる[4]。 実の閉区間に対する基本的な代数的操作は複素数に拡張できる。ゆえに複素区間演算が「通常の複素計算と全く同じではないが類似している」のは驚くことではない[4] 。複素区間演算は実数区間演算と同様に（特別な場合を除いて）加法と乗法に分配側がないことと、逆元が常に存在するわけではないことが知られている[4]。また、複素共役の加法的、乗法的性質は複素区間の共役については成り立たない[4]。 区間演算は複素の場合と同様に、四元数や八元数などの多次元の数に拡張できるが、通常の計算における便利な性質が犠牲になるという特徴がある。[4]
応用 編集
区間演算は確かな数値を持たない推定量を扱うために様々な分野で使われる。例えば集合反転、ロボットの行動計画、集合推定、安定性解析などに使われる[5]。
丸め誤差解析 編集
区間演算は計算ごとに生じる丸め誤差を制御するために誤差解析で用いられる。区間演算の利点は計算が終わるごとに必ず真値を含む区間が得られることである。区間の端点間の距離は計算の誤差量を表している[1]。丸め誤差解析の研究ではジェームズ・H・ウィルキンソンが著名である[1]。
区間ニュートン法 編集
区間ニュートン法 (英: Interval Newton method) はニュートン法の一部を区間演算に置き換えた手法であり、非線形方程式の精度保証付き数値計算に用いられる[1][6][7]。ゲッツ・アールフェルトによって提案された[1][8]。区間ニュートン法については解の存在定理があり、その証明にはブラウワーの不動点定理が使われる[1][9]。
計算機援用証明 編集
力学系 編集
ウォリック・タッカーは区間演算を活用して、14番目のスメイルの問題を解決した[10]。
幾何学 編集
歴史 編集
区間演算は数学において全く新しいものではない。数学の歴史において、異なる名前で複数回現れている。例えばアルキメデスは紀元前3世紀に223/71 < π < 22/7を計算した。区間を用いた具体的計算は他の数値的手法のように人気になることはなかったが、完璧に忘れられることもなかった。 区間などの演算規則は1931年にケンブリッジ大学の博士課程学生であったRosalind Cicely Youngによって出版された[12]。その後、デジタル系の信頼性を高めるために区間の数的研究がミシガン大学のPaul Dwyerによって出版された[13]。区間は浮動小数点数に伴う丸め誤差を把握するために使われた。数値解析における区間代数の体系的研究は須永照夫によって発表された[14]。 現代の区間演算はRamon E. Mooreが1966年に出版したInterval Analysisに端を発する[15][16]。彼は1958年の春にはアイデアを持っており、数年後にコンピュータによる区間演算についての記事を出版する[17]。その利点は単純な原理から出発して自動的な（丸め誤差以外の誤差を含む）誤差解析のための一般的方法を提供することであった。 上記とは独立に1956年、Mieczyslaw Warmusが区間を用いた計算の公式を提案した[18]。だが最初に非自明な応用を発見したのはMooreであった。 その後20年にわたってカールスルーエ工科大学のゲッツ・アールフェルト[19] とウルリヒ・クリッシュ[2][20]を中心にしたドイツのグループが研究を推進した。 例えば、Karl Nickelがより効果的な実装を探求すると同時に、Arnold Neumaierなどが方程式系の解集合を包含する手順を改良した。1960年代にはEldon R. Hansenが線型方程式系の区間拡張を扱い、大域最適化に重要な貢献を果たした。この研究は今日でいうHansen法を含んでおり、もしかしたらこれが最も広く使われる区間アルゴリズムかもしれない[7]。 このような古典的手法はしばしば最大（もしくは最小）の大域値を決定するのに問題が起きるが、局所最適解を見つけてより良い値が見つけられなかった。Helmut RatschekとJon George Rokneは分枝限定法を開発し、それまでは整数値にしか適用できなかったが、区間を使うことで連続値に対しても応用を与えることが可能になった。 1988年にはRudolf LohnerがODEの初期値問題に対して信頼できる解を得るためにFORTRANに基づいたソフトウェアを開発した[21]。 論文誌Reliable Computing (元々は Interval Computations)は1990年代以降に刊行され、コンピュータによる数値計算の信頼性に貢献した。この論文誌の編集者を務め、大域最適化の研究でも知られるR. Baker Kearfottは区間演算で用いられる表記と用語の統一に大きく貢献した。 なお近年の研究はフランスのINRIA傘下のCOPRINに集中している。
IEEE Std 1788-2015 – 区間演算のためのIEEE規格 編集
2015年6月に区間演算のための規格が改正された[22]。2つの実装が無料で使える[23]。これらは規格のワーキンググループの構成員たちによって作成された[24][25]。この企画の一部はIEEE Std 1788.1-2017として2017年12月に改正され、2018年2月に公開された。これは実装の簡略化、高速化を助けるであろう[26] 。
関連する研究集会 編集
区間演算に関連する研究集会は世界中でいくつか行われている。代表的なのはSCAN（International Symposium on Scientific Computing, Computer Arithmetic, and Verified Numerical Computation）であり、他にはSWIM（Small Workshop on Interval Methods）、PPAM（International Conference on Parallel Processing and Applied Mathematics）、 REC（International Workshop on Reliable Engineering Computing）がある。
外部リンク 編集
区間演算ライブラリ 編集
- INTLAB MATLAB/GNU Octaveによる区間演算ライブラリ[27]
- arb - GitHub[28]
- JuliaIntervals - GitHub (Juliaによる区間演算ライブラリ)[29][30]
- kv - GitHub (C++による区間演算ライブラリ)[31]
- LILIB (C++による多倍長区間演算ライブラリ)[32]
- Interval and related software (区間演算ライブラリの一覧サイト)
関連する研究集会 編集
脚注 編集
- ^ a b c d e f g h i j k l 大石、他 (2018)
- ^ a b c (German) Wissenschaftliches Rechnen mit Ergebnisverifikation. Eine Einführung. Wiesbaden: Vieweg-Verlag. (1989). ISBN 3-528-08943-1
- ^ Complex interval arithmetic and its applications, Miodrag Petkovi?, Ljiljana Petkovi?, Wiley-VCH, 1998, ISBN 978-3-527-40134-5
- ^ a b c d e f Hend Dawood (2011). Theories of Interval Arithmetic: Mathematical Foundations and Applications. Saarbrücken: LAP LAMBERT Academic Publishing. ISBN 978-3-8465-0154-2.
- ^ Jaulin, L. Kieffer, M., Didrit, O. Walter, E. (2001). Applied Interval Analysis. Berlin: Springer.
- ^ 非線形方程式に対する解の精度保証付き数値計算
- ^ a b Global Optimization using Interval Analysis (2nd ed.). New York, USA: Marcel Dekker. (2004). ISBN 0-8247-4059-9
- ^ 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.
- ^ S. M. Rump: Verification Methods: Rigorous Results using Floating-Point Arithmetic, Acta Numerica 19 (2010), 287–449.
- ^ Tucker, W. (1999). The Lorenz attractor exists. Comptes Rendus de l'Académie des Sciences-Series I-Mathematics, 328(12), 1197-1202.
- ^ N. Hoffman, K. Ichihara, M. Kashiwagi, H. Masai, S. Oishi, and A. Takayasu, Verified computations for hyperbolic 3‐manifolds, Exper. Math., 25 (2016), Issue 1, 66‐78.
- ^ Young, R. C. (1931). The algebra of many-valued quantities. Mathematische Annalen, 104(1), 260-290.
- ^ Dwyer, P. S. (1951). Linear computations. Oxford, England: Wiley.
- ^ Theory of interval algebra and its application to numerical analysis. (1958). 29–46
- ^ Interval Analysis. Englewood Cliff, New Jersey, USA: Prentice-Hall. (1966). ISBN 0-13-476853-1
- ^ Introduction to Interval Analysis. Philadelphia: Society for Industrial and Applied Mathematics (SIAM). (2009). ISBN 0-89871-669-1
- ^ “Publications Related to Early Interval Work of R. E. Moore”. University of Louisiana at Lafayette Press (2001年8月13日). 2015年6月29日閲覧。
- ^ Precursory papers on interval analysis by M. Warmus Archived April 18, 2008, at the Wayback Machine.
- ^ (German) Einführung in die Intervallrechnung. Reihe Informatik. 12. Mannheim, Wien, Zürich: B.I.-Wissenschaftsverlag. ISBN 3-411-01466-0
- ^ Laugwitz, Detlef, ed (1969). “Grundzüge der Intervallrechnung” (German). Jahrbuch Überblicke Mathematik. 2. Mannheim, Germany: Bibliographisches Institut. pp. 51–98
- ^ Bounds for ordinary differential equations of Rudolf Lohner (ドイツ語)
- ^ IEEE Standard for Interval Arithmetic
- ^ Revol, N. (2015). The (near-)future IEEE 1788 standard for interval arithmetic. 8th small workshop on interval methods. Slides (PDF)
- ^ C++ implementation of the preliminary IEEE P1788 standard for interval arithmetic
- ^ GNU Octave interval package
- ^ “IEEE Std 1788.1-2017 - IEEE Standard for Interval Arithmetic (Simplified)”. IEEE Standard. IEEE Standards Association. 2018年2月6日閲覧。
- ^ S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.
- ^ Johansson, F. (2017). Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers, 66(8), 1281-1292.
- ^ 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.
- ^ Overview of kv – a C++ library for verified numerical computation, Masahide Kashiwagi, SCAN 2018.
- ^ 松田望. (2016). 中心値・半径方式による精度保証付き多倍長区間演算ライブラリの開発. 電気通信大学博士論文.
参考文献 編集
和書 編集
- 『精度保証付き数値計算の基礎』大石進一 編著、コロナ社、2018年。2019年4月19日閲覧。
- 大石進一『精度保証付き数値計算』コロナ社、2000年。
- 大石進一(編著）、他：「精度保証付き数値計算の基礎」、コロナ社、ISBN 978-4-339-02887-4（2018年7月26日）。
洋書 編集
- Ramon E. Moore: "Methods and Applications of Interval Analysis", SIAM, ISBN 978-0-898711-61-5 (1979年).
- Gotz Alefeld, Jurgen Herzberger: "Introduction to Interval Computation", Academic Press, ISBN 978-0120498208 (1983年12月12日)．
- Alefeld, G., & Mayer, G. (2000). Interval analysis: theory and applications. en:Journal of Computational and Applied Mathematics, 121(1-2), 421-464.
- Ramon E. Moore, R. Baker Kearfott, and Michael J. Cloud: "Introduction to Interval Analysis", Society for Industrial and Applied Mathematics, ISBN 978-0-898716-69-6 (2009年4月16日）．
- Tucker, W. (2011). Validated Numerics: A Short Introduction to Rigorous Computations. en:Princeton University Press.
- Mayer, G. (2017). Interval analysis: and automatic result verification. Walter de Gruyter GmbH & Co KG.