区間演算

人の体格指数(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 、身長1.80mの男性の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 ]と報告できます。これは、この区間が計算された区間のスーパーセットであるためです。しかし、この範囲は[ 24.6, 24.8 ]と報告することはできません。なぜなら、この区間には可能な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].}$

この場合、男性は標準体重である可能性もあれば、過体重である可能性もある。体重と身長の測定値は、明確な結論を出すには精度が不十分だった。

区間の表記を簡略化するために、括弧を使用することができます。

[ 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 ₂ )となります( f_が減少する場合は_、 f ( y 1 ) ≥ f ( _y 2 )となり_ます)。

したがって、区間[ 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 ] ^{n を}[ −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 ] : [ ℝ ]  n ^→ [ℝ]は、次の条件を満たす場合に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のテイラー区間拡張の特殊なケースは、平均値形式とも呼ばれます。

実際の実装で効果的に機能するには、区間は浮動小数点演算と互換性がある必要があります。以前の演算は正確な算術に基づいていましたが、一般的に高速な数値解法が利用できない場合があります。この例では、 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）の計算におけるプロセッサの丸め設定を変更することで実現できます。あるいは、適切な小さな区間[ ε1 , ε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}}}$

除算⁠ 1 / [ a _ii ] ⁠が許されるならば、変数x _iによって決定できる。したがって、同時に

${\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区間のカバーが得られるが、計算コストは​​大幅に増加する。

区間幅が非常に広い場合、すべての区間を一定の（より狭い）幅を持つ複数の部分区間に分割する方法が有効です。この方法は「分割法」と呼ばれています。これにより、中間的な二分法の計算を回避できます。ただし、どちらの方法も低次元の問題にのみ適しています。

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

誤差 = abs( a − b )は、与えられた区間[ 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の変動範囲に正確に対応します。

不明確な値x ₁ , …, x _nおよび対応する数列に関する関数f ( 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 ]}トーマス・ヘイルズは、ケプラー予想を解決するために区間演算を使用した。

Fast Library for Number Theoryのウェブサイトには、FLINT/Arbボール算術ライブラリが発表論文やプレプリントで使用されている例がいくつか掲載されています。^{[ 11 ]}