Lemat Sterbenza

W arytmetyce zmiennoprzecinkowej lemat Sterbenza lub lemat Sterbenza jest twierdzeniem podającym warunki, w których dokładnie obliczane są różnice zmiennoprzecinkowe. Został nazwany na cześć Pata H. Sterbenza, który opublikował jego wariant w 1974 roku.

Lemat Sterbenza - W systemie liczb zmiennoprzecinkowych z liczbami podnormalnymi , jeśli i $x}$ są liczbami zmiennoprzecinkowymi takimi, że ${\ displaystyle$

$${\ Displaystyle {\ Frac {y} {2}} \ równoważnik x \ równoważnik 2y,}$$

wtedy jest $liczbą$ Zatem poprawnie zaokrąglone odejmowanie zmiennoprzecinkowe

$${\ Displaystyle x \ ominus y = \ operatorname {fl} (xy) = xy}$$

oblicza się dokładnie.

Lemat Sterbenza ma zastosowanie do IEEE 754 , najczęściej używanego systemu liczb zmiennoprzecinkowych w komputerach.

Dowód

Niech $precyzją$ podstawą systemu $i$ .

Najpierw rozważ kilka łatwych przypadków:

• Jeśli ${\ Displaystyle x}$ wynosi zero, to , a jeśli wynosi zero , to $= -y} ,$$\ Displaystyle xy$ więc ${\ Displaystyle xy = -y}$ wynik jest trywialny, ponieważ negacja zmiennoprzecinkowa jest zawsze dokładna.

• Jeśli ${\ displaystyle x = y},$ wynik wynosi zero, a zatem jest dokładny.

• jeśli ${\ displaystyle x <0}$ wtedy musimy również mieć ${\ Displaystyle y/2 \ równoważnik x <0}$ , więc ${\ Displaystyle y <0}$ . $y \geq 0}$ tym przypadku $ograniczonego$ do .

• Jeśli ${\ Displaystyle x \ równoważnik y}$ , możemy napisać ${\ Displaystyle xy = - (yx)}$ z ${\ Displaystyle x/2 \ równoważnik y \leq 2x}$ , więc wynik wynika z twierdzenia ograniczonego do ${\ Displaystyle x \ geq y}$ .

W $_$ dowodu

Napisz ${\ Displaystyle x, y> 0}$ w kategoriach ich dodatnich mantys całkowych ${\ Displaystyle s_ {x}, s_ {y} \ równoważnik \ beta ^ {p } -1}$ i minimalne wykładniki ${\ displaystyle e_ {x}, e_ {y}}$ :

$${\ Displaystyle {\ rozpocząć {wyrównane} x & = s_ {x} \ cdot \ beta ^ {e_ {x} - p+1}\\y&=s_{y}\cdot \beta ^{e_{y}-p+1}\end{wyrównane}}}$$

Zauważ, że i ${\ displaystyle$$y}$ mogą być nienormalne - nie zakładamy, $\ geq \ beta ^ {p-1}}$ .

Odejmowanie daje:

$${\ Displaystyle {\ rozpocząć {wyrównane} 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{wyrównane}}}$$

Niech ${\ Displaystyle s' = s_ {x} \ beta ^ {e_ {x} -e_ {y}} -s_ {y}}$ . Ponieważ mamy: ${\ displaystyle 0 <y <x}$

• ${\ Displaystyle e_ {y} \ równoważnik e_ {x}}$ , więc ${\ Displaystyle e_ {x} -e_ {y} \ geq 0}$ , z którego możemy wywnioskować ${\ Displaystyle \ beta ^ {e_ {x} -e_ {y}}}$ jest liczbą całkowitą, a zatem ${\ Displaystyle s '= s_ {x} \ beta ^ {e_ {x} -e_ {y}} -s_ {y}}$ ; I
• ${\ Displaystyle xy> 0}$ , więc ${\ Displaystyle s'> 0}$ .

Ponadto, ponieważ ${\ Displaystyle x \ równoważnik 2y}$ , mamy tak, że ${\ Displaystyle xy \ równoważnik y}$

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

co implikuje, że

$${\ Displaystyle 0 <s '\ równoważnik s_ {y} \ równoważnik \ beta ^ {p} -1.}$$

Stąd

$${\ Displaystyle xy = s '\ cdot \ beta ^ {e_ {y} -p + 1} \ quad {\text{for}}\quad 0<s'\równoważnik \beta ^{p}-1,}$$

więc $_$ . ◻

Uwaga: Nawet jeśli i ${\ Displaystyle$$y}$ są normalne, tj. , $\ geq \ beta ^ { p-1}}$ , nie możemy udowodnić, że ${\ Displaystyle s'\ geq \ beta ^ {p-1}}$ i dlatego nie możemy udowodnić, że ${\ displaystyle xy}$ jest też normalne. Na przykład różnica dwóch najmniejszych dodatnich normalnych liczb zmiennoprzecinkowych ${\ Displaystyle x = (\ beta ^ {p-1} + 1)\cdot \beta ^{e_{\mathrm {min} }-p+1}}$ i ${\ Displaystyle y = \ beta ^ {p-1} \ cdot \ beta ^ {e _ {\ operatorname {min}} -p + 1}}$ jest ${ \displaystyle xy=1\cdot \beta ^{e_{\mathrm {min}}-p+1}},$ co z konieczności jest poniżej normy. W systemach liczb zmiennoprzecinkowych bez liczb podnormalnych , takich jak procesory w niestandardowym trybie od zera do zera zamiast standardowego stopniowego niedomiaru, lemat Sterbenza nie ma zastosowania.

Związek z katastrofalnym odwołaniem

Lemat Sterbenza można skontrastować ze zjawiskiem katastroficznego anulowania :

• Lemat Sterbenza twierdzi, że jeśli ${\ Displaystyle x \ ominus y = \ operatorname {fl} (xy)}$$to$ wystarczająco $zmiennoprzecinkowej$$liczbami zmiennoprzecinkowymi,$ ich różnica pomocą arytmetyki , bez konieczności zaokrąglania.
• Zjawisko katastrofalnego anulowania polega na tym, że jeśli i $\ Displaystyle {\ tylda$${y}}}$ są przybliżeniami liczb prawdziwych ${\ displaystyle x}$ i ${\ displaystyle y}$ - czy przybliżenia wynikają z wcześniejszego błędu zaokrąglenia, obcięcia serii, niepewności fizycznej czy czegokolwiek innego - błąd różnicy ${\ Displaystyle {\ tylda {x}} - {\ tylda {y }}}$ od żądanej różnicy ${\ displaystyle xy}$ jest odwrotnie proporcjonalne do ${\ displaystyle xy}$ . Zatem im bliżej i ${\ Displaystyle$$y}$ , tym gorzej może $displaystyle x}} - {\ tylda {y$ jako przybliżenie do ${\ displaystyle xy}$ , nawet jeśli samo odejmowanie jest obliczane dokładnie.

Innymi słowy, lemat Sterbenza pokazuje, że odejmowanie pobliskich liczb zmiennoprzecinkowych jest dokładne, ale jeśli liczby, które masz, są przybliżeniami, to nawet ich dokładna różnica może być daleka od różnicy liczb, które chciałeś odjąć.

Zastosowanie w analizie numerycznej

Lemat Sterbenza odgrywa zasadniczą rolę w dowodzeniu twierdzeń o granicach błędów w analizie numerycznej algorytmów zmiennoprzecinkowych. Na przykład wzór Herona

$${\ Displaystyle A = {\ sqrt {s (sa) (sb) (sc)}}}$$

dla obszaru trójkąta o długościach boków , $i$${\ Displaystyle b}$ do $\ Displaystyle c}$ , gdzie $(a + b+c)/2}$ to półobwód, może dawać słabą dokładność w przypadku długich wąskich trójkątów, jeśli jest oceniany bezpośrednio w arytmetyce zmiennoprzecinkowej. Jednak dla za $\ Displaystyle a \ geq b \ geq c}$ , alternatywna formuła

$${\ Displaystyle A = {\ Frac {1 }{4}}{\sqrt {{\bigl (}a+(b+c){\bigr )}{\bigl (}c-(ab){\bigr )}{\bigl (}c+(ab){ \bigr )}{\bigl (}a+(bc){\bigr )}}}}$$

można udowodnić, za pomocą lematu Sterbenza, że ​​ma niski błąd przewodzenia dla wszystkich danych wejściowych.