区間演算
数学的計算における丸め誤差と測定誤差に対して評価を行い信頼できる結果をもたらす数値的手法を開発する技術
From Wikipedia, the free encyclopedia
区間演算（くかんえんざん、英: 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}]}](http://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}]}](http://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})]}](http://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}]}},}](http://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}}}](http://wikimedia.org/api/rest_v1/media/math/render/svg/7af098b91d736602987dcd64d61be9848222b138)
である。
表記
数式中における区間の表記を簡明にするため、カギ括弧が使われる[1]。 よってを区間の表記のために使うことができる。有限区間全体の集合を表す記号として
![{\displaystyle [x]\equiv [x_{1},x_{2}]}](http://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\}}](http://wikimedia.org/api/rest_v1/media/math/render/svg/9c246d6579baaaa59be83c8d31e670ea1a334646)
も使われる。区間を成分に持つベクトルについてはまたはを用いる。
![{\displaystyle \left([x]_{1},\ldots ,[x]_{n}\right)\in [\mathbb {R} ]^{n}}](http://wikimedia.org/api/rest_v1/media/math/render/svg/5fb4b1fbe11a16a257ea7f976b25b3e95c65a56b)
![{\displaystyle [\mathbf {x} ]}](http://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規格
関連する研究集会
区間演算に関連する研究集会は世界中でいくつか行われている。代表的なのは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）がある。