区間演算のソースを表示

{{Expand English|Interval arithmetic|date=2024年5月}}
'''区間演算'''（くかんえんざん、{{lang-en-short|Interval arithmetic}}、{{lang-de-short|Intervall arithmetik}}）（あるいはそれを用いた区間解析(interval analysis)）は数学者たちによって1950年代から1960年代にかけて作られた手法であり、数学的計算における丸め誤差と測定誤差に対して評価を行い信頼できる結果をもたらす数値的な手法を開発するものである<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref>。簡単に言うと、すべての値をとりうる数値の範囲で表現するのである。例えば、人の身長を通常の計算で2メートルと表わす代わりに、1.97メートルから2.03メートルの範囲であると表すのである。

この概念は様々な用途がある。主な使用方法は計算途中の丸め誤差を把握することである。区間演算は[[最適化問題]]や[[微分方程式]]の信頼できる求解を助けるという役割もある<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref>。

数学的に表現すると、不確かな[[実数]]xについて扱う代わりに、xを含む区間[a, b]を扱う。xを代入した関数fの値も不明である。区間演算において関数fは区間[c, d]を生成する。[c, d]は[a, b]内にある全てのxについてf(x)が取りうる値を表す<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref>。

==導入==
区間演算の主な目的は与えられた関数の値域の上界と下界を簡単に計算することである<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref>。端点は上限、下限とは限らない。なぜならば端点の具体的計算は困難もしくは不可能な場合があるからだ。伝統的な[[実数]]の計算と同様に、四則演算と区間値の関数が定義されなければならない<ref name="Kulisch">{{cite book |author-last=Kulisch |author-first=Ulrich |author-link=:de:Ulrich Kulisch |title=Wissenschaftliches Rechnen mit Ergebnisverifikation. Eine Einführung |year=1989 |publisher=Vieweg-Verlag |location=Wiesbaden |language=German |isbn=3-528-08943-1}}</ref>。より複雑な関数もこれに基づいて計算される<ref name="Kulisch"/>。
===演算の定義===
区間演算では四則演算を以下のようにして行う<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref>：
* [[加法]]: <math>[x_1, x_2] + [y_1, y_2] = [x_1+y_1, x_2+y_2]</math>
* [[減法]]: <math>[x_1, x_2] - [y_1, y_2] = [x_1-y_2, x_2-y_1]</math>
* [[乗法]]: <math>[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)]</math>
* [[除法]]:

::<math>\frac{[x_1, x_2]}{[y_1, y_2]} = [x_1, x_2] \cdot \frac{1}{[y_1, y_2]},</math>

:ただし、
::<math>\begin{align}
\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{align}</math>
である。
===表記===
数式中における区間の表記を簡明にするため、カギ括弧が使われる<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref>。
よって<math>[x] \equiv [x_1, x_2]</math>を区間の表記のために使うことができる。有限区間全体の集合を表す記号として
:<math>[\R] := \left \{\, [x_1, x_2] \,|\, x_1 \leq x_2 \text{ and } x_1, x_2 \in \R \cup \{-\infty, \infty\} \right \}</math>
も使われる。区間を成分に持つベクトルについては<math>\left([x]_1, \ldots , [x]_n \right) \in  [\R]^n </math>または<math>[\mathbf{x}]</math>を用いる。

==複素区間演算==
区間は中心から一定の距離を持った点の軌跡として定義することができて、この定義は[[実数]]から[[複素数]]に拡張することもできる<ref>[https://books.google.com/books?id=Vtqk6WgttzcC Complex interval arithmetic and its applications], Miodrag Petkovi?, Ljiljana Petkovi?, Wiley-VCH, 1998, {{ISBN2|978-3-527-40134-5}}</ref>。
[[実数]]の場合と同様に、[[複素数]]の計算も不確かなデータを含む。区間が実の閉区間で[[複素数]]が[[実数]]のペアであることから、区間演算の応用を[[実数]]計算の不確かさを測るのに限定する理由はない<ref name="Dawood">Hend Dawood (2011). ''Theories of Interval Arithmetic: Mathematical Foundations and Applications''. Saarbrücken: LAP LAMBERT Academic Publishing. {{ISBN2|978-3-8465-0154-2}}.</ref>。よって区間演算は複素数計算での不確かさの領域を特定するために複素区間へ拡張できる<ref name="Dawood"/>。
実の閉区間に対する基本的な代数的操作は[[複素数]]に拡張できる。ゆえに複素区間演算が「通常の複素計算と全く同じではないが類似している」のは驚くことではない<ref name="Dawood"/> 。複素区間演算は[[実数]]区間演算と同様に（特別な場合を除いて）[[加法]]と[[乗法]]に分配側がないことと、逆元が常に存在するわけではないことが知られている<ref name="Dawood"/>。また、複素共役の[[加法]]的、[[乗法]]的性質は複素区間の共役については成り立たない<ref name="Dawood"/>。
区間演算は複素の場合と同様に、[[四元数]]や[[八元数]]などの多次元の[[数]]に拡張できるが、通常の計算における便利な性質が犠牲になるという特徴がある。<ref name="Dawood"/>

==応用==
区間演算は確かな数値を持たない推定量を扱うために様々な分野で使われる。例えば{{ill2|集合反転|en|set inversion}}、ロボットの{{ill2|行動計画|en|motion planning|fr|Planification de mouvement|es|Planificación de movimiento|zh|运动规划}}、{{ill2|集合推定|en|set estimation}}、安定性解析などに使われる<ref>Jaulin, L. Kieffer, M., Didrit, O. Walter, E. (2001). Applied Interval Analysis. Berlin: Springer.</ref>。

===丸め誤差解析===
区間演算は計算ごとに生じる[[:en:rounding error|丸め誤差]]を制御するために誤差解析で用いられる。区間演算の利点は計算が終わるごとに必ず真値を含む区間が得られることである。区間の端点間の距離は計算の誤差量を表している<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref>。[[:en:rounding error|丸め誤差]]解析の研究では[[ジェームズ・H・ウィルキンソン]]が著名である<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref>。

===区間ニュートン法===
{{main|区間ニュートン法}}
[[区間ニュートン法]] ({{lang-en-short|Interval Newton method}}) は[[ニュートン法]]の一部を区間演算に置き換えた手法であり、非線形方程式の[[精度保証付き数値計算]]に用いられる<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref><ref>[http://www.sr3.t.u-tokyo.ac.jp/jsiam/slides/2016/takayasu_web.pdf 非線形方程式に対する解の精度保証付き数値計算]</ref><ref name="Hansen">{{cite book |author-last1=Walster |author-first1=G. William |author-last2=Hansen |author-first2=Eldon Robert |author-link2=Eldon R. Hansen |title=Global Optimization using Interval Analysis |edition=2nd |year=2004 |publisher=Marcel Dekker |location=New York, USA |isbn=0-8247-4059-9}}</ref>。[[ゲッツ・アールフェルト]]によって提案された<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref><ref>G. Alefeld: [https://www.semanticscholar.org/paper/lnclusion-methods-for-systems-of-nonlinear-interval-Alefeld/0be1a6662e897aa3200ccbe618b30ac587874df9 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="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref><ref>S. M. Rump: Verification Methods: Rigorous Results using Floating-Point Arithmetic,
Acta Numerica 19 (2010), 287–449.
</ref>。

===計算機援用証明===
{{see also|計算機援用証明}}
====力学系====
[[ウォリック・タッカー]]は区間演算を活用して、14番目の[[スメイルの問題]]を解決した<ref> Tucker, W. (1999). The Lorenz attractor exists. Comptes Rendus de l'Académie des Sciences-Series I-Mathematics, 328(12), 1197-1202.</ref>。
====幾何学====
3次元[[多様体]]の双曲性を判定するために区間演算が活用されている<ref name="大石他2018">{{harvnb|大石、他 (2018)|ref="大石他2018"}}</ref><ref>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.
</ref>。

==歴史==
区間演算は数学において全く新しいものではない。数学の歴史において、異なる名前で複数回現れている。例えば[[アルキメデス]]は紀元前3世紀に223/71 < [[円周率#歴史|π]] < 22/7を計算した。区間を用いた具体的計算は他の数値的手法のように人気になることはなかったが、完璧に忘れられることもなかった。
区間などの演算規則は1931年に[[ケンブリッジ大学]]の博士課程学生であったRosalind Cicely Youngによって出版された<ref>Young, R. C. (1931). The algebra of many-valued quantities. Mathematische Annalen, 104(1), 260-290.</ref>。その後、デジタル系の信頼性を高めるために区間の数的研究がミシガン大学のPaul Dwyerによって出版された<ref>Dwyer, P. S. (1951). Linear computations. Oxford, England: Wiley.</ref>。区間は浮動小数点数に伴う丸め誤差を把握するために使われた。[[数値解析]]における区間代数の体系的研究は須永照夫によって発表された<ref>{{cite book |author-first=Teruo |author-last=Sunaga |title=Theory of interval algebra and its application to numerical analysis |journal=RAAG Memoirs |issue<!-- ? -->=2 |date=1958 |pages=29–46}}</ref>。
現代の区間演算はRamon E. Mooreが1966年に出版した''Interval Analysis''に端を発する<ref>{{cite book |author-last=Moore |author-first=R. E. |title=Interval Analysis |year=1966 |publisher=Prentice-Hall|location=Englewood Cliff, New Jersey, USA |isbn=0-13-476853-1}}</ref><ref name="siam">{{cite book |author-last1=Cloud |author-first1=Michael J. |author-last2=Moore |author-first2=Ramon E. |author-last3=Kearfott |author-first3=R. Baker |title=Introduction to Interval Analysis |year=2009 |publisher=Society for Industrial and Applied Mathematics (SIAM) |location=Philadelphia |isbn=0-89871-669-1}}</ref>。彼は1958年の春にはアイデアを持っており、数年後に[[コンピュータ]]による区間演算についての記事を出版する<ref>{{cite web |url=http://interval.louisiana.edu/Moores_early_papers/bibliography.html |title=Publications Related to Early Interval Work of R. E. Moore |author-last=Hansen |author-first=E. R. |author-link=Eldon R. Hansen |date=2001-08-13 |publisher=University of Louisiana at Lafayette Press |access-date=2015-06-29}}</ref>。その利点は単純な原理から出発して自動的な（丸め誤差以外の誤差を含む）誤差解析のための一般的方法を提供することであった。
上記とは独立に1956年、Mieczyslaw Warmusが区間を用いた計算の公式を提案した<ref>[http://www.ippt.gov.pl/~zkulpa/quaphys/warmus.html Precursory papers on interval analysis by M. Warmus] {{webarchive |url=https://web.archive.org/web/20080418041803/http://www.ippt.gov.pl/~zkulpa/quaphys/warmus.html |date=April 18, 2008 }}</ref>。だが最初に非自明な応用を発見したのはMooreであった。
その後20年にわたって[[カールスルーエ工科大学]]の[[ゲッツ・アールフェルト]]<ref>{{cite book |author-last1=Alefeld |author-first1=Götz |author-link=:de:Götz Alefeld |author-last2=Herzberger |author-first2=Jürgen |title=Einführung in die Intervallrechnung |series=Reihe Informatik |volume=12 |publisher=B.I.-Wissenschaftsverlag |location=Mannheim, Wien, Zürich |isbn=3-411-01466-0 |language=German}}</ref> と[[ウルリヒ・クリッシュ]]<ref name="Kulisch">{{cite book |author-last=Kulisch |author-first=Ulrich |author-link=:de:Ulrich Kulisch |title=Wissenschaftliches Rechnen mit Ergebnisverifikation. Eine Einführung |year=1989 |publisher=Vieweg-Verlag |location=Wiesbaden |language=German |isbn=3-528-08943-1}}</ref><ref name="Kulisch_1969">{{cite book |chapter=Grundzüge der Intervallrechnung |language=German |author-first=Ulrich |author-last=Kulisch |author-link=:de:Ulrich Kulisch |date=1969 |title=Jahrbuch Überblicke Mathematik |editor-first=Detlef |editor-last=Laugwitz |volume=2 |publisher=Bibliographisches Institut |location=Mannheim, Germany |pages=51–98}}</ref>を中心にしたドイツのグループが研究を推進した。
例えば、{{仮リンク|Karl Nickel|de|Karl Nickel}}がより効果的な実装を探求すると同時に、Arnold Neumaierなどが方程式系の解集合を包含する手順を改良した。1960年代には{{仮リンク|Eldon R. Hansen|en|Eldon R. Hansen}}が線型方程式系の区間拡張を扱い、大域最適化に重要な貢献を果たした。この研究は今日でいうHansen法を含んでおり、もしかしたらこれが最も広く使われる区間アルゴリズムかもしれない<ref name="Hansen"/>。
このような古典的手法はしばしば最大（もしくは最小）の大域値を決定するのに問題が起きるが、局所最適解を見つけてより良い値が見つけられなかった。Helmut RatschekとJon George Rokneは[[分枝限定法]]を開発し、それまでは整数値にしか適用できなかったが、区間を使うことで連続値に対しても応用を与えることが可能になった。
1988年にはRudolf LohnerがODEの初期値問題に対して信頼できる解を得るために[[FORTRAN]]に基づいたソフトウェアを開発した<ref>[http://fam-pape.de/raw/ralph/studium/dgl/dglsem.html Bounds for ordinary differential equations of Rudolf Lohner] ([[ドイツ語]])</ref>。
論文誌''Reliable Computing'' (元々は ''Interval Computations'')は1990年代以降に刊行され、[[コンピュータ]]による数値計算の信頼性に貢献した。この論文誌の編集者を務め、大域最適化の研究でも知られるR. Baker Kearfottは区間演算で用いられる表記と用語の統一に大きく貢献した。
なお近年の研究は[[フランス]]のINRIA傘下の[http://www-sop.inria.fr/coprin/index_english.html COPRIN]に集中している。

==IEEE Std 1788-2015 – 区間演算のためのIEEE規格==
2015年6月に区間演算のための規格が改正された<ref>[http://standards.ieee.org/findstds/standard/1788-2015.html IEEE Standard for Interval Arithmetic]</ref>。2つの実装が無料で使える<ref>Revol, N. (2015). The (near-)future IEEE 1788 standard for interval arithmetic. 8th small workshop on interval methods. [http://kam.mff.cuni.cz/conferences/swim2015/slides/revol.pdf Slides (PDF)]</ref>。これらは規格のワーキンググループの構成員たちによって作成された<ref>[https://github.com/nehmeier/libieeep1788 C++ implementation of the preliminary IEEE P1788 standard for interval arithmetic]</ref><ref>[http://octave.sourceforge.net/interval/ GNU Octave interval package]</ref>。この企画の一部は[[IEEE]] Std 1788.1-2017として2017年12月に改正され、2018年2月に公開された。これは実装の簡略化、高速化を助けるであろう<ref>{{cite web 
  |url= https://standards.ieee.org/findstds/standard/1788.1-2017.html
  |title= IEEE Std 1788.1-2017 - IEEE Standard for Interval Arithmetic (Simplified)
  |author=<!--Staff writer(s); no by-line.--> 
  |date= 
  |website= IEEE Standard
  |publisher=IEEE Standards Association 
  |accessdate=2018-02-06
}}</ref>
。

==関連する研究集会==
区間演算に関連する研究集会は世界中でいくつか行われている。代表的なのは[[SCAN (国際研究集会)|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）がある。

==外部リンク==
===区間演算ライブラリ===
*[http://www.ti3.tu-harburg.de/rump/intlab/ INTLAB] [[MATLAB]]/[[GNU Octave]]による区間演算ライブラリ<ref>S.M. Rump: INTLAB - INTerval LABoratory. In Tibor Csendes, editor, Developments in Reliable Computing, pages 77-104. Kluwer Academic Publishers, Dordrecht, 1999.</ref>
*{{GitHub|fredrik-johansson/arb}}<ref>Johansson, F. (2017). Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers, 66(8), 1281-1292.</ref>
*{{GitHub|JuliaIntervals}} ([[Julia (プログラミング言語)|Julia]]による区間演算ライブラリ)<ref>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 (国際研究集会)|SCAN]] 2016, 124.</ref><ref>ValidatedNumerics.jl: a new framework in Julia, David P. Sanders and Luis Benet, [[SCAN (国際研究集会)|SCAN]] 2018.</ref>
*{{GitHub|mskashi/kv}} ([[C++]]による区間演算ライブラリ)<ref>Overview of kv – a C++ library for verified numerical computation, Masahide Kashiwagi, [[SCAN (国際研究集会)|SCAN]] 2018.</ref>
**[http://verifiedby.me/kv/ kv-日本語ページ]
*[https://osdn.net/projects/lilib/ LILIB] ([[C++]]による多倍長区間演算ライブラリ)<ref>松田望. (2016). 中心値・半径方式による精度保証付き多倍長区間演算ライブラリの開発. [[電気通信大学]]博士論文.</ref>
*[http://www.cs.utep.edu/interval-comp/intsoft.html Interval and related software] (区間演算ライブラリの一覧サイト)

===関連する研究集会===
*[https://www.ensta-bretagne.fr/jaulin/swim.html SWIM (Summer Workshop on Interval Methods)]
*[https://link.springer.com/conference/ppam International Conference on Parallel Processing and Applied Mathematics]

==脚注==
{{脚注ヘルプ}}
{{reflist|2}}

==参考文献==
===和書===
* {{Cite book|和書|others=[[大石進一]] 編著|title=精度保証付き数値計算の基礎|publisher=[[コロナ社 (出版社)|コロナ社]]|year=2018|url=http://www.coronasha.co.jp/np/download/6965501695.pdf|accessdate=2019-04-19|ref="大石他2018"}}
* {{Cite book|和書|author=大石進一|authorlink=大石進一|title=精度保証付き数値計算|publisher=[[コロナ社 (出版社)|コロナ社]]|year=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", [[SIAM (学会)|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 [[:en:De Gruyter|de Gruyter]] GmbH & Co KG.

==関連項目==
*[[精度保証付き数値計算]]
*[[計算機援用証明]]
*[[アフィン演算]]
*[[INTLAB]]
*[[SCAN (国際研究集会)]]
{{データ型}}
{{デフォルトソート:くかんえんさん}}
[[Category:アルゴリズム]]
[[Category:応用数学]]
[[Category:計算科学]]
[[Category:数値解析]]
[[Category:数学に関する記事]]