スターベンツの補題

浮動小数点演算において、ステルベンツの補題またはステルベンツの補題^[1]は、浮動小数点の差が正確に計算される条件を与える定理である。これは、1974年にその変種を発表したパット・H・ステルベンツにちなんで名付けられた。^[2]

シュテルベンツの補題は、コンピュータで最も広く使用されている浮動小数点数システムである IEEE 754に適用されます。

を浮動小数点システムの基数、を精度 とします。${\displaystyle \beta}$${\displaystyle p}$

まず、いくつかの簡単なケースを考えてみましょう。

• がゼロの場合は となり、 がゼロの場合は となり、浮動小数点数の否定は常に正確であるため、結果は自明です。${\displaystyle x}$${\displaystyle xy=-y}$${\displaystyle y}$${\displaystyle xy=x}$

• 結果がゼロで正確である場合。${\displaystyle x=y}$

• ならば も成り立つはずなので。この場合 なので、に制限された定理から結果が導かれます。${\displaystyle x<0}$${\displaystyle y/2\leq x<0}$${\displaystyle y<0}$${\displaystyle xy=-(-x--y)}$${\displaystyle x,y\geq 0}$

• の場合、と書くことができるので、 に制限された定理から結果が導かれます。${\displaystyle x\leq y}$${\displaystyle xy=-(yx)}$${\displaystyle x/2\leq y\leq 2x}$${\displaystyle x\geq y}$

残りの証明では、一般性を失うことなく仮定します。 ${\displaystyle 0<y<x\leq 2y}$

正の整数仮数と最小指数を使って書きます。 ${\displaystyle x,y>0}$${\displaystyle s_{x},s_{y}\leq \beta ^{p}-1}$${\displaystyle e_{x},e_{y}}$

$${\displaystyle {\begin{aligned}x&=s_{x}\cdot \beta ^{e_{x}-p+1}\\y&=s_{y}\cdot \beta ^{e_{y}-p+1}\end{aligned}}}$$

および は非正規になる可能性があることに注意してください。 と仮定しているわけではありません。${\displaystyle x}$${\displaystyle y}$${\displaystyle s_{x},s_{y}\geq \beta ^{p-1}}$

減算すると次のようになります。

$${\displaystyle {\begin{aligned}xy&=s_{x}\cdot \beta ^{e_{x}-p+1}-s_{y}\cdot \beta ^{e_{y}-p+1}\\&=s_{x}\beta ^{e_{x}-e_{y}}\cdot \beta ^{e_{y}-p+1}-s_{y}\cdot \beta ^{e_{y}-p+1}\\&=(s_{x}\beta ^{e_{x}-e_{y}}-s_{y})\cdot \beta ^{e_{y}-p+1}.\end{aligned}}}$$

とします。次の式が成り立ちます。 ${\displaystyle s'=s_{x}\beta ^{e_{x}-e_{y}}-s_{y}}$${\displaystyle 0<y<x}$

• ${\displaystyle e_{y}\leq e_{x}}$したがって は整数であり、したがって も整数であると結論付けることができます。${\displaystyle e_{x}-e_{y}\geq 0}$${\displaystyle \beta ^{e_{x}-e_{y}}}$${\displaystyle s'=s_{x}\beta ^{e_{x}-e_{y}}-s_{y}}$
• ${\displaystyle xy>0}$、 それで。${\displaystyle s'>0}$

さらに、 なので、 となり、 ${\displaystyle x\leq 2y}$${\displaystyle xy\leq y}$

$${\displaystyle s'\cdot \beta ^{e_{y}-p+1}=xy\leq y=s_{y}\cdot \beta ^{e_{y}-p+1}}$$

これは、

$${\displaystyle 0<s'\leq s_{y}\leq \beta ^{p}-1.}$$

したがって

$${\displaystyle xy=s'\cdot \beta ^{e_{y}-p+1},\quad {\text{for}}\quad 0<s'\leq \beta ^{p}-1,}$$

浮動小数点数 も同様です。∎${\displaystyle xy}$

注:およびが正規、つまり、であっても、 であることを証明することはできません。したがって も正規であることを証明することはできません。たとえば、2 つの最小の正の正規浮動小数点数 と の差は であり、これは必然的に非正規です。非正規数のない浮動小数点数システム(標準の段階的アンダーフローではなく非標準の flush-to-zero モードの CPU など) では、ステルベンツの補題は適用されません。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle s_{x},s_{y}\geq \beta ^{p-1}}$${\displaystyle s'\geq \beta ^{p-1}}$${\displaystyle xy}$${\displaystyle x=(\beta ^{p-1}+1)\cdot \beta ^{e_{\mathrm {min} }-p+1}}$${\displaystyle y=\beta ^{p-1}\cdot \beta ^{e_{\mathrm {min} }-p+1}}$${\displaystyle xy=1\cdot \beta ^{e_{\mathrm {min} }-p+1}}$

シュテルベンツの補題は、破滅的相殺の現象と対比​​される。

• ステルベンツの補題は、と が十分に近い浮動小数点数である場合、それらの差は浮動小数点演算によって正確に計算され、丸めは必要ないと主張しています。${\displaystyle x}$${\displaystyle y}$${\displaystyle xy}$${\displaystyle x\ominus y=\operatorname {fl} (xy)}$
• 破滅的な相殺現象とは、と が真の数値と の近似値である場合、その近似値が事前の丸め誤差、級数の切り捨て、物理的な不確実性、またはその他の原因から生じたものであるかどうかに関係なく、と の差の誤差がに反比例することです。したがって、とが近いほど、減算自体が正確に計算されたとしても、の近似値としては悪くなる可能性があります。${\displaystyle {\tilde {x}}}$${\displaystyle {\tilde {y}}}$${\displaystyle x}$${\displaystyle y}$${\displaystyle {\チルダ {x}}-{\チルダ {y}}}$${\displaystyle xy}$${\displaystyle xy}$${\displaystyle x}$${\displaystyle y}$${\displaystyle {\チルダ {x}}-{\チルダ {y}}}$${\displaystyle xy}$

言い換えれば、ステルベンツの補題は、近い浮動小数点数の減算は正確であるが、持っている数値が近似値である場合、それらの正確な差であっても、減算したい数値の差から大きく離れる可能性があることを示しています。

ステルベンツの補題は、浮動小数点アルゴリズムの数値解析における誤差の境界に関する定理を証明するのに役立ちます。たとえば、辺の長さが、、（半周長）の三角形の面積に関するヘロンの公式は、浮動小数点演算で直接評価すると、細長い三角形に対して精度が低くなる可能性があります。ただし、 については、 ステルベンツの 補題 の助けを借りて、すべての入力に対して前方誤差が低いことが証明できます。 ^{[3] [4] [5]}$${\displaystyle A={\sqrt {s(sa)(sb)(sc)}}}$$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle s=(a+b+c)/2}$${\displaystyle a\geq b\geq c}$$${\displaystyle A={\frac {1}{4}}{\sqrt {{\bigl (}a+(b+c){\bigr )}{\bigl (}c-(ab){\bigr )}{\bigl (}c+(ab){\bigr )}{\bigl (}a+(bc){\bigr )}}}}$$