区間演算

許容関数（青緑）と区間値近似（赤）

区間演算（区間数学、区間分析、区間計算とも呼ばれる）は、関数の境界を計算することで、数学計算における丸め誤差や測定誤差を軽減するために使用される数学的手法です。区間演算を含む数値解析法は、比較的信頼性が高く、数学的に正しい結果を保証できます。区間演算または区間数学では、値を単一の数値として表すのではなく、各値を複数の可能性の範囲として表します。

数学的には、不確実な実数値変数xを扱う代わりに、区間演算はxが取り得る値の範囲を定義する区間[ a , b ]を扱います。言い換えれば、変数xの任意の値はaとbの間の閉区間内にあります。関数f をxに適用すると、すべてのx ∈ [ a , b ]に対してf ( x )が取り得るすべての値を含む区間[ c , d ]が生成されます。

区間演算は様々な用途に適していますが、最も一般的な用途は科学研究、特にソフトウェアによる計算において、計算における丸め誤差や、物理的・技術的パラメータの正確な値に関する知識の不確実性を追跡するために使用されます。後者は、測定誤差や部品の許容誤差、あるいは計算精度の限界によって生じることがよくあります。区間演算は、方程式（微分方程式など）や最適化問題に対する確実な解を求めるのにも役立ちます。

導入

区間演算の主な目的は、 1つ以上の変数における関数の値域の上限と下限を簡便に計算する方法を提供することです。これらの端点は、必ずしも真の値域の上限または下限ではありません。なぜなら、これらの値を正確に計算することは困難または不可能な場合があるからです。境界は、関数の値域を部分集合として含んでいれば十分です。

この処理は、通常、実区間に限定されるので、

${\displaystyle [a,b]=\{x\in \mathbb {R} \mid a\leq x\leq b\},}$

ここで、 a = −∞およびb = ∞が許容される。 a、bのいずれかが無限大の場合、区間は無限区間となる。両方が無限大の場合、区間は拡張実数直線となる。実数rは区間[ r , r ]として解釈できるため、区間と実数は自由に組み合わせることができる。

例

身長1.80mの人の体重m（キログラム）に対するBMI（ボディマス指数）

人の体格指数（BMI）の計算について考えてみましょう。BMIは、体重（キログラム）を身長（メートル）の2乗で割ることで算出されます。1キログラム単位の精度を持つ体重計を使用するとします。この体重計では中間値は判別できず、実際の体重は最も近い整数に切り上げられます。例えば、体重計は最も近いキログラム単位の値しか表示できないため、79.6 kgと80.3 kgは区別できません。体重計が80 kgを示しているときに、その人の体重がちょうど80.0 kgである可能性は低いです。したがって、80 kgと表示されている体重計は、79.5 kgと80.5 kgの間、つまり[79.5, 80.5)の範囲にあることを示しています。

体重80kg、身長180cmの男性のBMIは約24.7です。体重79.5kgで身長が同じ場合のBMIは24.537、体重80.5kgの場合は24.846となります。体重は指定された体重範囲内では常に増加し続けるため、真のBMIは[24.537, 24.846]の範囲内に収まるはずです。この範囲全体が正常体重と過剰体重の境界値である25未満であるため、この男性は正常体重であると確実に結論付けることができます。

この例の誤差は結論（標準体重）には影響しませんが、一般的にはそうではありません。男性の体重がもう少し多ければ、BMIの範囲にカットオフ値25が含まれる可能性があります。そのような場合、体重計の精度では明確な結論を出すには不十分です。

BMIの例の範囲は、計算された区間のスーパーセットであるため、[24.5, 24.9]と報告できます。ただし、この区間にはBMIの可能性のある値が含まれないため、 [24.6, 24.8]と報告することはできません。

複数の間隔

身長L（メートル）と体重別のBMI（ボディマス指数）の関係

身長と体重はどちらもBMIの値に影響します。上記の例では体重の変化のみを考慮しましたが、身長にも不確実性があります。メートル単位での身長測定は通常、最も近いセンチメートルに丸められます。例えば、1.79メートルという記録された測定値は、1.785～1.795の範囲の身長を表します。BMIは体重の増加に対して均一に増加し、身長の増加に対して均一に減少するため、各範囲の最小値と最大値を代入し、最小値と最大値を境界として選択することで、誤差範囲を計算できます。したがって、BMIは次の範囲に存在する必要があります。

${\displaystyle {\frac {[79.5,80.5)}{[1.785,1.795)^{2}}}\subseteq [24.673,25.266].}$

この場合、男性は標準体重であるか太りすぎである可能性があります。体重と身長の測定値は、確定的な結論を出すには正確性が不十分でした。

区間演算子

加算や乗算などの2つの区間に対する2 項演算∗は次のように定義される。

${\displaystyle [x_{1},x_{2}]{\,\star \,}[y_{1},y_{2}]=\{x\star y\,|\,x\in [x_{1},x_{2}]\,\land \,y\in [y_{1},y_{2}]\}.}$

言い換えれば、x ∗ yの全ての可能な値の集合であり、xとy は対応する区間内にある。もし∗ が区間上の各被演算子に対して単調であるならば（これは四則演算（分母がゼロを含む除算を除く）の場合に当てはまる）、極値は被演算子区間の端点に現れる。全ての組み合わせを書き出すと、これを表現する方法の一つは次のようになる。

${\displaystyle [x_{1},x_{2}]\star [y_{1},y_{2}]=\left[\min\{x_{1}\star y_{1},x_{1}\star y_{2},x_{2}\star y_{1},x_{2}\star y_{2}\},\max\{x_{1}\star y_{1},x_{1}\star y_{2},x_{2}\star y_{1},x_{2}\star y_{2}\}\right],}$

ただし、x ∗ yはすべてのx ∈ [ x ₁ , x ₂ ]およびy ∈ [ y ₁ , y ₂ ]に対して定義される。

実際のアプリケーションでは、これをさらに簡略化できます。

• 追加：$${\displaystyle [x_{1},x_{2}]+[y_{1},y_{2}]=[x_{1}+y_{1},x_{2}+y_{2}]}$$
• 減算：$${\displaystyle [x_{1},x_{2}]-[y_{1},y_{2}]=[x_{1}-y_{2},x_{2}-y_{1}]}$$
• 掛け算：$${\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}\}]}$$
• 部門：どこで$${\displaystyle {\frac {[x_{1},x_{2}]}{[y_{1},y_{2}]}}=[x_{1},x_{2}]\cdot {\frac {1}{[y_{1},y_{2}]}},}$$ $${\displaystyle {\begin{aligned}{\frac {1}{[y_{1},y_{2}]}}&=\left[{\frac {1}{y_{2}}},{\frac {1}{y_{1}}}\right]&&{\textrm {if}}\;0\notin [y_{1},y_{2}]\\{\frac {1}{[y_{1},0]}}&=\left[-\infty ,{\frac {1}{y_{1}}}\right]\\{\frac {1}{[0,y_{2}]}}&=\left[{\frac {1}{y_{2}}},\infty \right]\\{\frac {1}{[y_{1},y_{2}]}}&=\left[-\infty ,{\frac {1}{y_{1}}}\right]\cup \left[{\frac {1}{y_{2}}},\infty \right]\subseteq [-\infty ,\infty ]&&{\textrm {if}}\;0\in (y_{1},y_{2})\end{aligned}}}$$

最後のケースでは、（⁠1/y ₁⁠、⁠1/y ₂⁠ )。したがって、 [-∞, ⁠1/y ₁⁠ ]と[ ⁠1/y ₂⁠ , ∞] を別々の区間として扱う。より一般的には、不連続関数を扱う場合、 ⋃ _i [ a _i , b _i ]という形式のいわゆる多重区間を用いて計算を行うことが有用な場合がある。対応する多重区間演算は、（通常は互いに素な）区間の集合を維持し、重なり合う区間を結合することも提供する。 ^{[ 1 ]}

正の区間の乗算

区間乗算は多くの場合2回の乗算のみで済みます。x 1 _、 y 1_が非負の場合、

${\displaystyle [x_{1},x_{2}]\cdot [y_{1},y_{2}]=[x_{1}\cdot y_{1},x_{2}\cdot y_{2}],\qquad {\text{ if }}x_{1},y_{1}\geq 0.}$

この乗算は、辺の長さが変化する長方形の面積として解釈できます。結果の区間は、最小から最大まで、あらゆる面積の範囲をカバーします。

これらの定義を用いることで、f ( a , b , x ) = ax + bのような単純な関数の値域を計算することが可能です。例えば、a = [1, 2]、b = [5, 7]、x = [2, 3]の場合、

${\displaystyle f(a,b,x)=[1,2]\cdot [2,3]+[5,7]=[1\cdot 2,2\cdot 3]+[5,7]=[7,13].}$

表記

間隔の表記を短縮するには、括弧を使用できます。

[ x ] ≡ [ x ₁ , x ₂ ]は区間を表すのに使えます。このような簡潔な表記では、[ x ] を一点区間[ x ₁ , x ₁ ]と一般区間と混同しないように注意が必要です。すべての区間の集合に対して、

${\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\}}$

略語として。区間のベクトルには太字フォントを使用できます。

${\displaystyle [\mathbf {x} ]=\left([x]_{1},\ldots ,[x]_{n}\right)\in [\mathbb {R} ]^{n}.}$

基本関数

単調関数の値

4 つの基本演算子以外の区間関数も定義できます。

単調関数が1変数の場合、値の範囲は簡単に計算できます。f :  ℝ → ℝが区間[ x ₁ , x ₂ ]で単調増加である場合、 y ₁ < y 2 となるすべての y 1 , y ₂ ∈ [ _x 1 _, x 2 ]_に対して、f ₍ y 1 ) ≤ f ( _y 2 )が成立_します（ fが減少する場合は、 f ( y ₁ ) ≥ f ( y ₂ )）。

したがって、区間[ y ₁ , y ₂ ] ⊆ [ x ₁ , x ₂ ]に対応する範囲は、関数をその端点に適用することによって計算できます。

${\displaystyle f([y_{1},y_{2}])=\left[\min \left\{f(y_{1}),f(y_{2})\right\},\max \left\{f(y_{1}),f(y_{2})\right\}\right].}$

このことから、区間関数の次の基本機能を簡単に定義できます。

• 指数関数：$${\displaystyle a^{[x_{1},x_{2}]}=[a^{x_{1}},a^{x_{2}}]\qquad {\text{for }}a>1,}$$
• 対数:$${\displaystyle \log _{a}[x_{1},x_{2}]=[\log _{a}{x_{1}},\log _{a}{x_{2}}]\quad {\text{for positive intervals }}[x_{1},x_{2}]{\text{ and }}a>1,}$$
• 奇妙な力:$${\displaystyle [x_{1},x_{2}]^{n}=[x_{1}^{n},x_{2}^{n}]\qquad {\text{for odd }}n\in \mathbb {N} .}$$

偶数乗の場合、考慮する値の範囲は重要であり、乗算を行う前に処理する必要があります。例えば、x ∈ [−1, 1]に対してx ^{n を}求めると、偶数n ∈ ℕに対して区間[0, 1] が生成されるはずです。しかし、[−1, 1] ⁿを[−1, 1] · [−1, 1] · ⋯ ​​· [−1, 1]という形式の区間乗算を繰り返して求めると 、結果は[−1, 1]となり、必要以上に広くなってしまいます。

より一般的には、区分的単調関数の場合、区間の端点x ₁、x ₂と、区間内のいわゆる臨界点（関数の単調性が変化する点）を併せて考えれば十分であると言える。正弦関数と余弦関数の場合、臨界点はそれぞれ( n + ⁠1/2⁠ ) πとnπ（ n ∈ ℤ ） 。したがって、区間内に少なくとも2つの極値が含まれる場合、結果として得られる区間は[−1, 1]となるため、区間内の最大5点のみを考慮する必要があります。正弦と余弦については、臨界点は簡単に事前に計算できる値、すなわち -1、0、1 につながるため、端点のみを完全に評価する必要があります。

一般関数の区間拡張

一般的に、多くの関数の出力区間について、このような単純な記述を見つけることは容易ではないかもしれません。しかし、関数を区間演算に拡張することは依然として可能です。f : ℝ n → ℝ が実ベクトルから実数への関数である場合、  [ ^f ] : [ ℝ ] ⁿ → [ℝ] は、次の式が成り立つとき、 fの区間拡張と呼ばれます。

${\displaystyle [f]([\mathbf {x} ])\supseteq \{f(\mathbf {y} )\mid \mathbf {y} \in [\mathbf {x} ]\}.}$

この区間拡張の定義は正確な結果を与えません。例えば、 [ f ]( [ x ₁ , x ₂ ] ) = [ e ^{x ₁} , e ^{x ₂} ]と[ g ]( [ x ₁ , x ₂ ] ) = [−∞, ∞]はどちらも指数関数の許容される拡張です。より厳密な拡張が望ましいですが、計算コストと不正確さの相対的なバランスを考慮する必要があります。この場合、最も厳密な結果を与える [ f ] を選択する必要があります。

実数式が与えられた場合、その部分式、関数、演算子のそれぞれの区間拡張を使用して 、その自然な区間拡張が実現されます。

テイラー区間拡張（ k次）は、k + 1回微分可能な関数fで、次のように定義されます 。

${\displaystyle [f]([\mathbf {x} ]):=f(\mathbf {y} )+\sum _{i=1}^{k}{\frac {1}{i!}}\mathrm {D} ^{i}f(\mathbf {y} )\cdot ([\mathbf {x} ]-\mathbf {y} )^{i}+[r]([\mathbf {x} ],[\mathbf {x} ],\mathbf {y} ),}$

あるy∈ [ x ]に対して、D ⁱ f ( y )は点yにおけるfのi階微分、[ r ]はテイラー剰余の区間拡張である。

${\displaystyle r(\mathbf {x} ,{\boldsymbol {\xi }},\mathbf {y} )={\frac {1}{(k+1)!}}\mathrm {D} ^{k+1}f({\boldsymbol {\xi }})\cdot (\mathbf {x} -\mathbf {y} )^{k+1}.}$

平均値形式

ベクトルξはxとyの間にあり、 x , y ∈ [ x ]である。ξは[ x ]によって保護されている。通常、yは区間の中点として選択され、剰余は自然区間拡張によって評価される。

k = 0次テイラー区間拡張の特殊なケースは平均値形式とも呼ばれます。

複素区間演算

区間は中心から指定された距離内にある点の集合として定義することができ、この定義は実数から複素数に拡張することができる。^{[ 2 ]}もう 1 つの拡張では、区間を複素平面内の長方形として定義する。実数の計算の場合と同様に、複素数の計算には不確実なデータが含まれる。したがって、区間数は実数の閉区間であり、複素数は実数の順序付きペアであるという事実を考慮すると、区間演算の適用を実数の計算における不確実性の尺度に限定する理由はない。^{[ 3 ]}このように、区間演算は複素区間数を介して拡張され、複素数の計算における不確実性領域を判定することができる。複素区間演算は長方形または円板を使用して定義することができ、それぞれに長所と短所がある。^{[ 3 ]}

実区間数（実閉区間）の基本的な代数演算は複素数にも拡張できます。したがって、複素区間演算が通常の複素演算と類似しているものの、同一ではないことは驚くべきことではありません。^{[ 3 ]}実区間演算の場合と同様に、特定の特殊な場合を除いて、複素区間数の加法と乗法の間には分配法則はなく、複素区間数には逆元が常に存在するとは限らないことが示されます。^{[ 3 ]}通常の複素演算の他の2つの有用な性質は、複素区間演算では成り立ちません。通常の複素共役の加法性と乗法性は、複素区間共役には成り立ちません。^{[ 3 ]}

区間演算は、同様の方法で、四元数や八元数などの他の多次元数体系に拡張することができますが、通常の演算の他の有用な特性を犠牲にする必要があります。^{[ 3 ]}

間隔法

古典的な数値解析の方法は、数値間の依存関係が通常考慮されないため、区間値アルゴリズムに 1 対 1 で転送することはできません。

丸め区間演算

異なる丸めレベルでの外界

実際の実装で効果的に動作させるには、区間演算は浮動小数点演算と互換性がなければなりません。以前の演算は正確な演算に基づいていましたが、一般的には高速な数値解法は利用できない可能性があります。x ∈ [0.1, 0.8]およびy ∈ [0.06, 0.08]の場合の関数f ( x , y ) = x + yの値の範囲は、この例では[0.16, 0.88]です。同じ計算を1桁の精度で行うと、結果は通常[0.2, 0.9]になります。しかし、[0.2, 0.9] ⊉ [0.16, 0.88]であるため、このアプローチは区間演算の基本原理に反します。 f ( [0.1, 0.8] , [0.06, 0.08] )の定義域の一部が失われるからです。代わりに、外側に丸められた解[0.1, 0.9]が使用されます。

二進浮動小数点演算の標準規格IEEE 754では、丸めの実装手順も規定されています。IEEE 754準拠のシステムでは、プログラマーは最も近い浮動小数点数に丸めることができます。選択肢としては、ゼロ方向への丸め（切り捨て）、正の無限大方向への丸め（切り上げ）、負の無限大方向への丸め（切り捨て）があります。

区間演算に必要な外部丸めは、上限（up）と下限（down）の計算におけるプロセッサの丸め設定を変更することで実現できます。あるいは、適切な小さな区間[ ε ₁ , ε ₂ ]を追加することもできます。

区間演算は任意精度浮動小数点演算を用いて実装されており、精度ははるかに高い（ただし有限であるため、依然として丸め処理が必要となる）。大きな任意精度数は計算に時間がかかり、格納にかなりのスペースを必要とする。区間演算の変種であるボール演算では、従来の（下限-上限）区間演算のような2つの高精度の下限と上限の代わりに、高精度の中点と低精度の半径を格納し、 ^{[ 4 ]}計算コストを削減します。 ^{[ 5 ]}

依存の問題

値の範囲のおおよその見積もり

いわゆる依存性問題は、区間演算の適用における大きな障害です。区間法は基本的な算術演算や関数の範囲を非常に正確に決定できますが、より複雑な関数では必ずしもそうではありません。パラメータを用いた計算において、ある区間が複数回出現し、それぞれの出現を独立に扱う場合、結果として得られる区間が望ましくないほど拡大してしまう可能性があります。

変数の各出現を独立して扱う

例として、f ( x ) = x ² + xで定義される関数fを考えます。この関数の区間[−1, 1]における値は[− ⁠1/4⁠ , 2]。自然な区間拡張として、次のように計算される。

${\displaystyle [-1,1]^{2}+[-1,1]=[0,1]+[-1,1]=[-1,2],}$

これは少し大きいですが、代わりに関数h ( x , y ) = x ² + yのx , y ∈ [−1, 1]における最小値と最大値を計算しました。変数xが一度だけ現れるfのより良い表現があります。それは、二次方程式f ( x ) = x ² + xを平方完成で書き直すことです。

${\displaystyle f(x)=\left(x+{\tfrac {1}{2}}\right)^{2}-{\tfrac {1}{4}}.}$

したがって、適切な間隔計算は

${\displaystyle \left([-1,1]+{\tfrac {1}{2}}\right)^{2}-{\tfrac {1}{4}}=\left[-{\tfrac {1}{2}},{\tfrac {3}{2}}\right]^{2}-{\tfrac {1}{4}}=\left[0,{\tfrac {9}{4}}\right]-{\tfrac {1}{4}}=\left[-{\tfrac {1}{4}},2\right]}$

正しい値を返します。

一般に、各変数が一度だけ出現し、 f がボックス内で連続であれば、正確な値の範囲を実現できることが示されます。ただし、すべての関数がこのように書き直せるわけではありません。

ラッピング効果

値の範囲を過大評価する問題の依存性は、大きな範囲をカバーすることになり、より有意義な結論を導き出すことを妨げる可能性があります。

範囲のさらなる増加は、区間ベクトルの形をとらない領域の解から生じる。線形システムの解集合は

${\displaystyle {\begin{cases}x=p\\y=p\end{cases}}\qquad p\in [-1,1]}$

は点(−1, −1)と点(1, 1)を結ぶ直線です。区間法を用いると単位正方形[−1, 1] × [−1, 1]が得られます。これはラッピング効果として知られています。

線形間隔システム

線形区間システムは、行列区間拡張[ A ] ∈ [ℝ] ^{n × m}と区間ベクトル[ b ] ∈ [ℝ] ⁿから構成される。我々は、すべてのベクトルx ∈ ℝ ^mに対して、A ∈ [ A ]かつb ∈ [ b ]となる( A , b )のペアが存在し、次式を満たす最小の直方体[ x ] ∈ [ ℝ ] ^mを求める 。

${\displaystyle \mathbf {A} \cdot \mathbf {x} =\mathbf {b} }$ 。

二次方程式系（つまりn = m）では、すべての可能な解をカバーする区間ベクトル[ x ]が存在する可能性があり、これは区間ガウス法で簡単に見つけることができます。この方法は数値演算に代わるものであり、ガウス消去法と呼ばれる線型代数法がその区間版となります。しかし、この方法は計算において区間実体[ A ]と[ b ]を繰り返し使用するため、問題によっては結果が不完全になる可能性があります。したがって、区間値ガウスの結果は解集合全体を含みますが、その外側にも大きな領域が存在するため、最初の概算値しか得られません。

大まかな解[ x ]は、ガウス・ザイデル法の区間版によって改善されることが多い。これは、線形方程式の区間拡張の i行目が

${\displaystyle {\begin{pmatrix}{[a_{11}]}&\cdots &{[a_{1n}]}\\\vdots &\ddots &\vdots \\{[a_{n1}]}&\cdots &{[a_{nn}]}\end{pmatrix}}\cdot {\begin{pmatrix}{x_{1}}\\\vdots \\{x_{n}}\end{pmatrix}}={\begin{pmatrix}{[b_{1}]}\\\vdots \\{[b_{n}]}\end{pmatrix}}}$

除算が変数x _iによって決定される場合、⁠1/[ a _ii ]⁠は許可されています。したがって、同時に

${\displaystyle x_{j}\in [x_{j}]\quad {\text{and}}\quad x_{j}\in {\frac {[b_{i}]-\sum \limits _{k\neq j}[a_{ik}]\cdot [x_{k}]}{[a_{ii}]}}.}$

そこで[ x _j ]を次のように 置き換えることができる。

${\displaystyle [x_{j}]\cap {\frac {[b_{i}]-\sum \limits _{k\neq j}[a_{ik}]\cdot [x_{k}]}{[a_{ii}]}},}$

そしてベクトル[ x ]を各要素で割ったものになります。

この手順は対角優勢行列に対してより効率的であるため、システム[ A ] · x = [ b ]の代わりに、適切な有理行列Mを掛けて、結果として得られる行列方程式 を試すことができます。

${\displaystyle (\mathbf {M} \cdot [\mathbf {A} ])\cdot \mathbf {x} =\mathbf {M} \cdot [\mathbf {b} ]}$

解くべき問題は残っている。例えば、中心行列A∈ [ A ]に対してM = A ⁻¹とすると、M · [ A ]は単位行列の外側への拡張となる。

これらの方法は、発生する区間の幅が十分に小さい場合にのみ有効です。より広い区間の場合、有限（ただし大きい）実数同値線形システムに対して区間線形システムを用いると有効です。すべての行列A ∈ [ A ]が逆行列である場合、区間内に発生する端点のすべての可能な組み合わせ（上限と下限）を考慮するだけで十分です。結果として得られる問題は、従来の数値計算法を用いて解くことができます。丸め誤差の決定には、区間演算が依然として用いられています。

この方法は、 n × n行列が完全に占有されている場合、2 ^{n 2個}の実行列を逆行列化し、右辺に2 ^{nベクトルを配置する必要があるため、より小さな次元のシステムにのみ適しています。このアプローチはJiri Rohnによって開発され、現在も開発が進められています。 [ 6 ]}

区間ニュートン法

「厚い」関数の区間ニュートンステップにおける検索領域の縮小。

区間ベクトル[ x ]の零点を求めるニュートン法の区間変形は平均値拡張から導出できる。^{[ 7 ]}未知のベクトルz ∈ [ x ]をy ∈ [ x ]に適用すると、

${\displaystyle f(\mathbf {z} )\in f(\mathbf {y} )+[J_{f}](\mathbf {[x]} )\cdot (\mathbf {z} -\mathbf {y} ).}$

zがゼロの場合、つまりf ( z ) = 0は次式を満たす必要がある。

${\displaystyle f(\mathbf {y} )+[J_{f}](\mathbf {[x]} )\cdot (\mathbf {z} -\mathbf {y} )=0.}$

これは次の式と同等である。

${\displaystyle \mathbf {z} \in \mathbf {y} -[J_{f}](\mathbf {[x]} )^{-1}\cdot f(\mathbf {y} ).}$

[ J _f ]([ x ]) ⁻¹ · f ( y )の外部推定値は線形手法を使用して決定できます。

区間ニュートン法の各ステップでは、近似的な初期値[ x ] ∈ [ℝ] ⁿが次のように置き換えられる。

${\displaystyle [\mathbf {x} ]\cap \left(\mathbf {y} -[J_{f}](\mathbf {[x]} )^{-1}\cdot f(\mathbf {y} )\right)}$

そのため、結果を改善できます。従来の方法とは対照的に、区間法は零点を含むことで結果に近づきます。これにより、結果が初期範囲内のすべての零点を生成することが保証されます。逆に、ニュートンステップで空集合が生成される場合、 初期範囲[ x ]にfの零点が存在しないことが証明されます。

この方法は、開始領域内のすべての零点に収束します。零除算は、異なる零点の分離につながる可能性がありますが、分離は完全ではない可能性があります。これは二分法によって補完できます。

例として、関数f ( x ) = x ² − 2、開始範囲[ x ] = [−2, 2]、点y = 0を考えます。すると、J _f ( x ) = 2 xとなり、最初のニュートンステップは次のようになります。

${\displaystyle [-2,2]\cap \left(0-{\frac {1}{2\cdot [-2,2]}}(0-2)\right)=[-2,2]\cap \left(\left[-\infty ,-{\tfrac {1}{2}}\right]\cup \left[{\tfrac {1}{2}},\infty \right]\right)=\left[-2,-{\tfrac {1}{2}}\right]\cup \left[{\tfrac {1}{2}},2\right].}$

さらにニュートンステップがx ∈ [−2, − ⁠1/2⁠ ]およびx ∈ [ ⁠1/2⁠ , 2] 。これらはそれぞれ−√2と+ √2の周りの任意の小さな区間に収束します。

区間ニュートン法は、 g ( x ) = x ² − [2, 3]のような 厚い関数にも適用できます。これらの関数はいずれにせよ区間結果を持ちます。その結果、[− √ 3 , − √ 2 ] ∪ [ √ 2 , √ 3 ]を含む区間が生成されます。

二分法と被覆

大まかな見積もり（ターコイズ）と「細かく分ける」ことで改善された見積もり（赤）

各種区間法は、異なる区間拡張のサイズ間の依存関係を考慮しないため、保守的な結果をもたらします。ただし、区間が狭い場合、依存関係の問題はそれほど重要ではなくなります。

区間ベクトル[ x ]を小さなボックス[ x ₁ ], …, [ x _k ]で覆うと、

${\displaystyle [\mathbf {x} ]=\bigcup _{i=1}^{k}[\mathbf {x} _{i}],}$

値の範囲に対して有効になります。

${\displaystyle f([\mathbf {x} ])=\bigcup _{i=1}^{k}f([\mathbf {x} _{i}]).}$

したがって、上記の間隔拡張については、次のことが当てはまります。

${\displaystyle [f]([\mathbf {x} ])\supseteq \bigcup _{i=1}^{k}[f]([\mathbf {x} _{i}]).}$

[ f ]([ x ])は多くの場合、右辺の 真のスーパーセットであるため、これにより推定値が改善されることが多いです。

このような被覆は、区間ベクトルの 太い要素[ x _{i 1} , x _{i 2} ]のような二分法によって生成することができる。

${\displaystyle [\mathbf {x} ]=([x_{11},x_{12}],\ldots ,[x_{n1},x_{n2}])}$

中央で2つの区間に分割することで

${\displaystyle \left[x_{i1},{\frac {x_{i1}+x_{i2}}{2}}\right]\quad {\text{and}}\quad \left[{\frac {x_{i1}+x_{i2}}{2}},x_{i2}\right].}$

それでも結果が適切でない場合は、さらに段階的に細分化することが可能です。ベクトル要素をr回分割すると2r^個の区間が被覆されるため、計算コストが大幅に増加します。

区間が非常に広い場合、すべての区間を一定の（より狭い）幅を持つ複数の部分区間に分割すると便利です。この方法はミンシングと呼ばれます。これにより、中間の二分ステップの計算を回避できます。どちらの方法も、低次元の問題にのみ適しています。

応用

区間演算は、正確な数値のない推定値を扱うために、様々な分野（集合反転、動作計画、集合推定、安定性解析など）で使用することができます。 ^{[ 8 ]}

丸め誤差分析

区間演算は誤差解析において、各計算から生じる丸め誤差を制御するために使用されます。区間演算の利点は、各演算の後に真の結果を確実に含む区間が存在することです。区間境界間の距離は、現在の丸め誤差の計算値を直接示します。

与えられた区間[ a、b ]に対して誤差 = abs( a − b )。

区間分析は、ピボットなどの従来の誤差低減手法を置き換えるのではなく、従来の手法に追加されます。

許容差分析

技術的および物理的プロセスのシミュレーションでは、正確な数値を割り当てることができないパラメータがしばしば発生します。技術部品の製造プロセスでは一定の許容範囲が許容されるため、一部のパラメータは一定の範囲内で変動します。さらに、多くの基本定数は正確には分かっていません。^{[ 1 ]}

許容誤差の影響を受けるこのようなシステムの動作が、たとえば、p ∈ [ p ]と未知のxに対してf ( x、p ) = 0 を満たす場合、可能な解の集合は次のようになります。

${\displaystyle \{\mathbf {x} \,|\,\exists \mathbf {p} \in [\mathbf {p} ],f(\mathbf {x} ,\mathbf {p} )=0\}}$ 、

区間法によって求めることができます。これは、従来の誤差伝播解析に代わる手法です。モンテカルロシミュレーションなどの点法とは異なり、区間演算法では解領域のどの部分も見落とされることはありません。ただし、他の確率分布は考慮されていないため、結果は常に誤差分布の最悪ケースの解析となります。

ファジィ区間演算

区間列による正規分布の近似

区間演算は、ファジィ論理で使用されるファジィ量の所属関数にも適用できます。厳密なステートメントx ∈ [ x ]およびx ∉ [ x ]に加えて、実数μ ∈ [0, 1]が割り当てられる中間値も考えられます。μ = 1は明確な所属に対応し、μ = 0 は非所属に対応します。分布関数は不確実性を割り当てますが、これはさらなる区間として理解できます。

ファジィ算術^{[ 9 ]}では、有限個の離散的な所属段階μ _i ∈ [0, 1]のみが考慮される。このような不明確値の分布の形は、区間の列で表すことができる。

${\displaystyle \left[x^{(1)}\right]\supset \left[x^{(2)}\right]\supset \cdots \supset \left[x^{(k)}\right].}$

区間[ x ^{( i )} ]はステージμi_の変動範囲と正確に一致します。

関数f ( x ₁ , …, x _n )の、区別できない値x ₁ , …, x _nとそれに対応するシーケンス に関する適切な分布

${\displaystyle \left[x_{1}^{(1)}\right]\supset \cdots \supset \left[x_{1}^{(k)}\right],\ldots ,\left[x_{n}^{(1)}\right]\supset \cdots \supset \left[x_{n}^{(k)}\right]}$

は、次の数列で近似できる。

${\displaystyle \left[y^{(1)}\right]\supset \cdots \supset \left[y^{(k)}\right],}$

どこ

${\displaystyle \left[y^{(i)}\right]=f\left(\left[x_{1}^{(i)}\right],\ldots \left[x_{n}^{(i)}\right]\right)}$

区間法によって計算することができる。値[ y ⁽¹⁾ ]は区間計算の結果に対応する。

コンピュータ支援証明

ワーウィック・タッカーは区間演算を用いてスメール問題の14番目の問題を解き、ローレンツ・アトラクターがストレンジ・アトラクターであることを証明した。^{[ 10 ]}トーマス・ヘイルズは区間演算を用いてケプラー予想を解決した。

高速数論ライブラリのウェブサイトには、出版された論文やプレプリントにおけるFLINT/Arbボール演算ライブラリの使用例がいくつか掲載されています。^{[ 11 ]}

歴史

区間演算は数学において全く新しい現象ではなく、歴史の中で様々な名前で何度か登場してきました。例えば、アルキメデスは下限と上限を計算しました。223/71⁠ < π < ⁠22/7⁠紀元前3世紀。区間を使った実際の計算は、他の数値計算手法ほど普及しておらず、完全に忘れ去られたわけでもありません。

区間や実数の他の部分集合を用いた計算規則は、1931年にロザリンド・シセリー・ヤングによって発表された。^{[ 12 ]}デジタルシステムの信頼性を向上させるための値域数に関する算術的研究は、1951年にポール・S・ドワイヤーによって線形代数の教科書に掲載された。^{[ 13 ]}区間は、浮動小数点数に関連する丸め誤差を測定するために使用された。数値解析における区間代数に関する包括的な論文は、須永輝雄（1958年）によって発表された。^{[ 14 ]}

現代の区間演算の誕生は、1966年にラモン・E・ムーアが『区間解析』という本を出版したことで始まりました。 ^{[ 15 ] [ 16 ]}彼は1958年の春にこのアイデアを思いつき、1年後にコンピュータ区間演算に関する論文を発表しました。^{[ 17 ]}その利点は、単純な原理から始めて、丸めから生じる誤差だけでなく、自動誤差解析の一般的な方法を提供したことです。

1956年にミェチスワフ・ヴァルムスは独立して区間を使った計算の公式を提案したが^{[ 18 ]}、ムーアが初めて非自明な応用を発見した。

その後の20年間、カールスルーエ大学で、そして後にはベルギッシェ・ヴッパータール大学でも、ドイツの研究者グループがウルリッヒ・W・クーリッシュ^{[ 19 ] [ 20 ]}とゲッツ・アレフェルト^{[ 21 ]}を中心に先駆的な研究を行った。例えば、カール・ニッケルはより効果的な実装を研究し、連立方程式の解集合の包含手順の改善はアーノルド・ノイマイヤーらによるものであった。1960年代には、エルドン・R・ハンセンが線形方程式の区間拡張を扱い、その後、おそらく最も広く使用されている区間アルゴリズムである、現在ハンセン法として知られるものを含む、大域最適化に重要な貢献をした。^{[ 7 ]}この古典的な方法では、最大（または最小）の大域値を決定する問題がしばしばあるが、局所最適値しか見つけることができず、より良い値を見つけることができなかった。ヘルムート・ラチェクとジョン・ジョージ・ロクネは、それまで整数値にのみ適用されていた分岐限定法を、区間を使用して連続値に適用できるように開発しました。

1988年、ルドルフ・ローナーは常微分方程式を用いた初期値問題の信頼性の高い解を求めるFortranベースのソフトウェアを開発した。^{[ 22 ]}

1990年代から発行されている学術誌『Reliable Computing 』 （当初はInterval Computations）は、コンピュータ支援計算の信頼性に特化した雑誌です。主任編集者であるR. Baker Kearfottは、大域最適化に関する研究に加え、区間演算における表記法と用語の統一に大きく貢献しました。^{[ 23 ]}

近年、フランスのソフィア・アンティポリスにあるINRIAのCOPRINワーキンググループでは、特にパラメータ化された関数のプリイメージの推定とロバスト制御理論に研究が集中している。 ^{[ 24 ]}

実装

区間演算を用いた数値アプリケーションの開発を可能にするソフトウェアパッケージは数多く存在します。^{[ 25 ]}これらは通常、プログラムライブラリの形で提供されます。また、C++およびFortranコンパイラの中には、区間データ型と適切な演算を言語拡張として扱うものもあり、区間演算を直接サポートしています。

1967 年以来、カールスルーエ大学でC++、Fortran、Pascalなどさまざまなプログラミング言語向けの科学的計算用拡張機能(XSC) が開発されてきました。^{[ 26 ]}最初のプラットフォームはZuse Z23で、適切な基本演算子を備えた新しい区間データ型が利用可能になりました。 1976 年には、Zilog Z80上の Pascal バリアントであるPascal-SC が登場し、これにより、結果の自動検証用の高速で複雑なルーチンの作成が可能になりました。 次に、System/370アーキテクチャ用のFortran 77ベースの ACRITH-XSC (FORTRAN-SC) が登場し、後に IBM によって提供されました。 1991 年からは、Pascal-XSCでCコンパイラ用のコードを作成できるようになりました。 1 年後には、 C++ クラス ライブラリがさまざまなコンピュータシステムで C-XSC をサポートするようになりました。 1997 2000 年の初めに、改良された C++ 標準に対応するために、 ベルギッシェ・ヴッパータール大学の科学計算ワーキング グループの主導の下、C-XSC 2.0 がリリースされました。

1993年、ハンブルク工科大学でProfil/BIAS （Programmer's Runtime Optimized Fast Interval Library, Basic Interval Arithmetic）と呼ばれるC++クラスのライブラリが開発されました。このライブラリは、一般的な区間演算をよりユーザーフレンドリーなものにしました。ハードウェアの効率的な利用、移植性、そして区間の特定の表現の独立性を重視していました。

Boost C++ライブラリコレクションには、区間演算用のテンプレートクラスが含まれています。このクラスの作成者は、区間演算を標準C++言語で実現することを目指しています。^{[ 27 ]}

Frinkプログラミング言語には、任意精度の数値を扱う区間演算の実装があります。Frinkで書かれたプログラムは、書き換えや再コンパイルなしで区間演算を使用できます。

GAOL ^{[ 28 ]}は、区間制約プログラミングで使用される関係区間演算子を提供するという点でユニークな、もう1つのC++区間演算ライブラリです。

Mooreライブラリ^{[ 29 ]}は、C++における区間演算の効率的な実装です。任意の精度の端点を持つ区間を提供し、C++のconcepts機能に基づいています。

Juliaプログラミング言語[ ^{30 ]に}は、区間演算の実装に加えて、ルート探索（実数値関数と複素数値関数の両方）や区間制約プログラミングなどの高レベル機能がパッケージを介して実装されていますValidatedNumerics.jl。^{[ 31 ]}

さらに、Euler Mathematical Toolbox、FriCAS、Maple、Mathematica、Maxima ^{[ 32 ]}、MuPADなどのコンピュータ代数システムは区間を扱うことができます。Matlabの拡張機能であるIntlab ^{[ 33 ]}はBLASルーチンに基づいており、このツールボックスはb4mProfil/BIASインターフェースを提供します。^{[ 33 ] [ 34 ]}

関数型言語OCamlのライブラリはアセンブリ言語とCで書かれました。^{[ 35 ]}

MPFIは任意精度区間演算用のライブラリであり、C言語で書かれており、MPFRをベースにしている。^{[ 36 ]}

IEEE 1788規格

区間演算の標準規格IEEE Std 1788-2015は、2015年6月に承認されました。^{[ 37 ]} 2つの参照実装が無料で利用可能です。^{[ 38 ]}これらは、標準のワーキンググループのメンバーによって開発されました。C++用のlibieeep1788 ^{[ 39 ]}ライブラリと、 GNU Octave用の区間パッケージ^{[ 40 ]}です。

標準規格の最小限のサブセットであるIEEE Std 1788.1-2017は、2017年12月に承認され、2018年2月に公開されました。これにより実装が容易になり、実装のスピードが速まる可能性があります。^{[ 41 ]}

会議とワークショップ

毎年、世界中で数多くの国際会議やワークショップが開催されています。主要な会議はおそらく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（インターバルラボ）
• 自動微分
• マルチグリッド法
• モンテカルロシミュレーション
• 区間有限要素
• ファジー数
• 有効数字
• カールスルーエ精密算術（KAA）
• ウナム

参考文献

1. Dreyer, Alexander (2003).部品公差を考慮したアナログ回路の区間解析. アーヘン, ドイツ: Shaker Verlag . p. 15. ISBN 3-8322-4555-3。
2. 複素区間演算とその応用、ミオドラグ・S・ペトコビッチ、リリヤナ・D・ペトコビッチ、 Wiley-VCH、1998年、 ISBN 978-3-527-40134-5
3. Hend Dawood (2011).区間演算の理論：数学的基礎と応用. ザールブリュッケン: LAP LAMBERT Academic Publishing. ISBN 978-3-8465-0154-2。
4. van der Hoeven, Joris. 「ボール算術」 . www.texmacs.org .私たちは主に、区間算術の一種（いわゆる「ボール算術」）に基づいて、高品質の誤差境界を自動的かつ効率的に計算することに注力しています。
5. 「機能概要 — FLINT 3.5.0-dev ドキュメント」 . flintlib.org .従来の（inf–sup）区間演算では、区間[ a , b ]の両端は完全精度数であるため、区間演算は浮動小数点演算の2倍のコストがかかります。球面演算では、区間[ m ± r ]の中点mのみが完全精度数であり、半径rには数ビットで十分です。したがって、高精度では、球面演算は通常の浮動小数点演算よりもコストが高くなることはありません。
6. 「Jiri Rohn, 出版物一覧」。2008年11月23日時点のオリジナルよりアーカイブ。2008年5月26日閲覧。
7. ウォルスター、G. ウィリアム;ハンセン、エルドン・ロバート(2004)。間隔分析を使用した全体的な最適化(第 2 版)。米国ニューヨーク州：マーセル・デッカー。ISBN 0-8247-4059-9。
8. リュック・ジョリン;キーファー、ミシェル。ディドリット、オリヴィエ。ウォルター、エリック (2001)。適用された間隔分析。ベルリン：シュプリンガー。ISBN 1-85233-219-0。
9. 不確実なモデルパラメータの影響を定量化するためのファジィ演算の応用、マイケル・ハンス、シュトゥットガルト大学
10. タッカー、ワーウィック(1999).ローレンツアトラクターは存在します。 Comptes Rendus de l'Académie des Sciences-Series I-Mathematics、328(12)、1197-1202。
11. 「アプリケーションとベンチマーク：数値計算」 . FLINT：数論のための高速ライブラリ（flintlib.org） .
12. Young, Rosalind Cicely (1931). The algebra of many-valued volumes. Mathematische Annalen, 104(1), 260-290. (注:ケンブリッジ大学博士課程在学中)
13. Dwyer, Paul Sumner (1951). 線形計算. オックスフォード, イギリス: Wiley. (ミシガン大学)
14. 須永輝雄 (1958). 「区間代数の理論と数値解析への応用」RAAG 回想録(2): 29–46。
15. ムーア、ラモン・エドガー(1966).区間分析. アメリカ合衆国ニュージャージー州エングルウッド・クリフ:プレンティス・ホール. ISBN 0-13-476853-1。
16. Cloud, Michael J.; Moore, Ramon Edgar ; Kearfott, R. Baker (2009).区間解析入門. フィラデルフィア: Society for Industrial and Applied Mathematics (SIAM). ISBN 978-0-89871-669-6。
17. ハンセン、エルドン・ロバート(2001年8月13日). 「R.E.ムーアの初期インターバル研究に関連する出版物」 . ルイジアナ大学ラファイエット校出版. 2015年6月29日閲覧。
18. ミェチスワフ・ヴァルムスによる区間解析に関する先駆的論文2008年4月18日アーカイブ、 Wayback Machine
19. クーリッシュ、ウルリッヒ W. (1989)。Wissenschaftliches Rechnen mit Ergebnisverifikation。 Eine Einführung (ドイツ語)。ヴィースバーデン: Vieweg-Verlag。ISBN 3-528-08943-1。
20. クーリッシュ、ウルリッヒ W. (1969)。 「Grundzüge der Intervalrechnung」。 Laugwitz、Detlef (編)。Jahrbuch Überblicke Mathematik (ドイツ語)。 Vol. 2. ドイツ、マンハイム: Bibliographisches Institut。51–98ページ 。
21. アレフェルト、ゲッツ[ドイツ語] ;ヘルツバーガー、ユルゲン (1974)。Einführung in die Intervalrechnung。 Reihe Informatik (ドイツ語)。 Vol. 12. マンハイム、ウィーン、チューリッヒ: BI-Wissenschaftsverlag。ISBN 3-411-01466-0。
22. ルドルフ・ローナーの常微分方程式の境界値 2018年5月11日アーカイブ、 Wayback Machine（ドイツ語）
23. R. ベイカー・キアフォート著、ルイジアナ大学ラファイエット校の書誌
24. INRIA、 Sophia AntipolisのCOPRINチームの紹介フィルム (mpeg)
25. 区間計算用ソフトウェア、Wayback Machineに 2006-03-02 にアーカイブ、Vladik Kreinovich、テキサス大学エルパソ校が収集。
26. XSC言語の歴史 2007年9月29日アーカイブWayback Machine
27. C++標準ライブラリに区間演算を追加する提案
28. Gaol は単なる区間演算ライブラリではない
29. ムーア: 現代の C++ における区間演算
30. Juliaプログラミング言語
31. ValidatedNumerics.jl
32. [1] Maximaの区間演算：Richard J. Fatemanによる概要。
33. “Intlab INTerval LABoratory” . 2020年1月30日時点のオリジナルよりアーカイブ。2012年11月7日閲覧。
34. b4m
35. Alliot, Jean-Marc; Gotteland, Jean-Baptiste; Vanaret, Charlie; Durand, Nicolas; Gianazza, David (2012). x86/amd64アーキテクチャにおけるOCaml用区間計算ライブラリの実装. 第17回ACM SIGPLAN国際関数型プログラミング会議.
36. MPFI、MPFRに基づく多重精度区間演算ライブラリ
37. IEEE 区間演算標準
38. Nathalie Revol (2015). 区間演算における（近）将来のIEEE 1788標準、スライド// SWIM 2015: 第8回区間法小規模ワークショップ。プラハ、2015年6月9～11日
39. 区間演算のための予備的なIEEE P1788標準のC++実装
40. GNU Octave 間隔パッケージ
41. 「IEEE Std 1788.1-2017 - IEEE Standard for Interval Arithmetic (Simplified)」 . IEEE Standard . IEEE Standards Association. 2017. 2018年2月7日時点のオリジナルよりアーカイブ。 2018年2月6日閲覧。

さらに読む

• ヘイズ、ブライアン（2003年11～12月）「明晰な間隔」（PDF） . American Scientist . 91 (6). Sigma Xi: 484– 488. doi : 10.1511/2003.6.484 .オリジナル（PDF）から2021年8月27日にアーカイブ。 2008年5月24日閲覧。
• タッカー、ワーウィック（2011年）『検証済み数値計算：厳密な計算への短い入門』プリンストン大学出版局、ISBN 978-1400838974。
• ヴィッパーマン、ハンス=ヴィルム (1968) [1967-06-15、1966]。 「Triplex-ALGOL におけるシュランケンツァーレンの定義」。コンピューティング(ドイツ語)。３（２）。カールスルーエ、ドイツ: Springer: 99–109 . doi : 10.1007/BF02277452。ISSN  0010-485X。S2CID  36685400。(11 ページ) (注: Triplex-ALGOL Karlsruheについて。これは、三重数値をサポートする ALGOL 60 (1963) 実装です。)

外部リンク

• 区間演算（Wolfram Mathworld）
• 歩行者向けの検証済み数値
• インターバル法（Arnold Neumaier著）2020年12月2日アーカイブWayback Machine、ウィーン大学
• SWIM（インターバル法夏季ワークショップ）
• 並列処理と応用数学に関する国際会議
• INTLAB、信頼性コンピューティング研究所、Wayback Machineで2020年1月30日にアーカイブ、ハンブルク工科大学
• Joris van der Hoeven によるボール算術
• kv - 検証済み数値計算用の C++ ライブラリ
  • GitHubのkv
• Arb - 任意精度のボール演算用のCライブラリ
  • GitHubのarb
• GitHubのJuliaIntervals