Utrata znaczenia - Loss of significance

Utrata znaczenia jest niepożądanym efektem w obliczeniach przy użyciu arytmetyki o skończonej precyzji, takiej jak arytmetyka zmiennoprzecinkowa . Występuje, gdy operacja na dwóch liczbach zwiększa błąd względny znacznie bardziej niż zwiększa błąd bezwzględny , na przykład przy odejmowaniu dwóch prawie równych liczb (znane jako anulowanie katastroficzne ). W efekcie liczba cyfr znaczących w wyniku jest niedopuszczalnie zmniejszona. Sposoby uniknięcia tego efektu są badane w analizie numerycznej .

Demonstracja problemu

Odejmowanie

Efekt można zademonstrować za pomocą liczb dziesiętnych. Poniższy przykład ilustruje katastroficzne anulowanie dla dziesiętnego typu danych zmiennoprzecinkowych z 10 cyframi znaczącymi:

Rozważ liczbę dziesiętną

x = 0.1234567891234567890

Reprezentacja zmiennoprzecinkowa tej liczby na maszynie, która przechowuje 10 cyfr zmiennoprzecinkowych, byłaby

y = 0.1234567891

co jest dość bliskie, gdy mierzy się błąd jako procent wartości. Jest bardzo różny, gdy mierzy się go w kolejności dokładności. Wartość „x” jest dokładna 10 × 10 ⁻¹⁹ , podczas gdy wartość „y” jest dokładna tylko do 10 × 10 ⁻¹⁰ .

Teraz wykonaj obliczenia

x - y = 0.1234567891234567890 − 0.1234567890000000000

Odpowiedź, z dokładnością do 20 cyfr znaczących, brzmi

0.0000000001234567890

Jednak na 10-cyfrowej maszynie zmiennoprzecinkowej obliczenia dają wynik

0.1234567891 − 0.1234567890 = 0.0000000001

W obu przypadkach wynik jest dokładny do tego samego rzędu wielkości co dane wejściowe (odpowiednio −20 i −10). W drugim przypadku odpowiedź wydaje się mieć jedną cyfrę znaczącą, co oznaczałoby utratę znaczenia. Jednak w komputerowej arytmetyce zmiennoprzecinkowej wszystkie operacje można postrzegać jako wykonywane na antylogarytmach , dla których reguły dotyczące cyfr znaczących wskazują, że liczba cyfr znaczących pozostaje taka sama, jak najmniejsza liczba cyfr znaczących w mantysach . Sposobem na wskazanie tego i przedstawienie odpowiedzi na 10 cyfr znaczących jest

   1.000000000×10−10

Utrata znaczących bitów

Niech x i y będą dodatnimi znormalizowanymi liczbami zmiennoprzecinkowymi.

Podczas odejmowania x - y , r znaczące bity są tracone, gdzie

${\ Displaystyle q \ równoważnik r \ równoważnik p,}$

${\ Displaystyle 2 ^ {- p} \ równoważnik 1 - {\ Frac {y} {x}} \ równoważnik 2 ^ {- q}}$

dla niektórych dodatnich liczb całkowitych p i q .

Obejścia

Możliwe jest wykonywanie obliczeń przy użyciu dokładnej ułamkowej reprezentacji liczb wymiernych i zachowanie wszystkich cyfr znaczących, ale jest to często zbyt wolniejsze niż arytmetyka zmiennoprzecinkowa.

Jedną z najważniejszych części analizy numerycznej jest uniknięcie lub zminimalizowanie utraty znaczenia w obliczeniach. Jeśli podstawowy problem jest dobrze postawiony, powinien istnieć stabilny algorytm jego rozwiązania.

Czasami sprytne sztuczki algebry mogą zmienić wyrażenie w formę, która omija problem. Jedną z takich sztuczek jest użycie dobrze znanego równania

${\ Displaystyle \ lewo (xy \ prawej) \ lewo (x + y \ prawej) = x ^ {2} -y ^ {2}}$

Więc za pomocą wyrażenia pomnóż licznik i mianownik, dając ${\ displaystyle xy}$${\ displaystyle x + y}$

${\ Displaystyle {\ Frac {x ^ {2} -y ^ {2}} {x + y}}}$

Czy można teraz zredukować wyrażenie, aby wyeliminować odejmowanie? Czasami tak. ${\ Displaystyle x ^ {2} -y ^ {2}}$

Na przykład, wyrażenie może utracić znaczące bity, jeśli jest znacznie mniejsze niż 1. Więc przepisz wyrażenie jako ${\ displaystyle 1 - {\ sqrt {1- \ delta}}}$${\ displaystyle | \ delta |}$

${\ Displaystyle {\ Frac {1- \ lewo (1- \ delta \ prawej)} {1 + {\ sqrt {1- \ delta}}}}}$ lub ${\ Displaystyle {\ Frac {\ delta} {1 + {\ sqrt {1- \ delta}}}}}$

Niestabilność równania kwadratowego

Na przykład rozważmy równanie kwadratowe

${\ displaystyle ax ^ {2} + bx + c = 0,}$

z dwoma dokładnymi rozwiązaniami:

${\ Displaystyle x = {\ Frac {-b \ pm {\ sqrt {b ^ {2} -4ac}}}} {2a}}.}$

Ta formuła może nie zawsze dawać dokładny wynik. Na przykład, gdy jest bardzo mały, utrata znaczenia może wystąpić w każdym z obliczeń pierwiastka, w zależności od znaku . ${\ displaystyle c}$${\ displaystyle b}$

Sprawa , , posłużą do zilustrowania problemu: ${\ displaystyle a = 1}$${\ displaystyle b = 200}$${\ displaystyle c = -0,000015}$

${\ Displaystyle x ^ {2} + 200x-0,000015 = 0.}$

Mamy

${\ Displaystyle {\ sqrt {b ^ {2} -4ac}} = {\ sqrt {200 ^ {2} +4 \ times 1 \ times 0,000015}} = 200,00000015 \ dotso}$

W prawdziwej arytmetyce pierwiastki to

${\ displaystyle (-200-200.00000015) /2=-200.000000075,}$

${\ Displaystyle (-200 + 200,00000015) /2=0,000000075.}$

W 10-cyfrowej arytmetyce zmiennoprzecinkowej:

${\ displaystyle (-200-200.0000001) /2=-200.00000005,}$

${\ Displaystyle (-200 + 200,0000001) /2=0,00000005.}$

Zauważ, że rozwiązanie o większej wielkości jest dokładne do dziesięciu cyfr, ale pierwsza niezerowa cyfra rozwiązania o mniejszej wielkości jest błędna.

Z powodu odejmowania, które występuje w równaniu kwadratowym, nie stanowi stabilnego algorytmu obliczania dwóch pierwiastków.

Lepszy algorytm

Staranna implementacja komputera zmiennoprzecinkowego łączy kilka strategii w celu uzyskania solidnego wyniku. Zakładając, że dyskryminator b ² - 4 ac jest dodatni i b jest różny od zera, obliczenia wyglądałyby następująco:

${\ Displaystyle {\ rozpocząć {wyrównane} x_ {1} & = {\ Frac {-b- \ operatorname {sgn} (b) \, {\ sqrt {b ^ {2} -4ac}}} {2a}} , \\ x_ {2} & = {\ frac {2c} {- b- \ operatorname {sgn} (b) \, {\ sqrt {b ^ {2} -4ac}}}} = {\ frac {c } {ax_ {1}}}. \ end {aligned}}}$

Tutaj sgn oznacza funkcję znaku , gdzie wynosi 1, jeśli jest dodatnia, a −1, jeśli jest ujemna. Pozwala to uniknąć problemów z anulowaniem między i pierwiastkiem kwadratowym dyskryminatora, zapewniając, że dodawane są tylko liczby o tym samym znaku. ${\ displaystyle \ operatorname {sgn} (b)}$${\ displaystyle b}$${\ displaystyle b}$${\ displaystyle b}$

Aby zilustrować niestabilność standardowego wzoru kwadratowego w porównaniu z tym wzorem, rozważ równanie kwadratowe z pierwiastkami i . Do 16 cyfr znaczących, które w przybliżeniu odpowiadają dokładności podwójnej precyzji na komputerze, moniczne równanie kwadratowe z tymi pierwiastkami można zapisać jako ${\ Displaystyle 1.786737589984535}$${\ Displaystyle 1.149782767465722 \ times 10 ^ {- 8}}$

${\ Displaystyle x ^ {2} -1,786737601482363x + 2,054360090947453 \ times 10 ^ {- 8} = 0.}$

Używając standardowego wzoru kwadratowego i zachowując 16 cyfr znaczących na każdym kroku, uzyskuje się standardowy wzór kwadratowy

${\ displaystyle {\ sqrt {\ Delta}} = 1,786737578486707,}$

${\ Displaystyle x_ {1} = (1,786737601482363 + 1,786737578486707) /2 = 1,786737589984535,}$

${\ Displaystyle x_ {2} = (1,786737601482363-1,786737578486707) /2 = 0,000000011497828.}$

Zwróć uwagę, jak anulowanie spowodowało, że zostało obliczone tylko do 8 znaczących cyfr dokładności. ${\ displaystyle x_ {2}}$

Przedstawiona tutaj formuła wariantowa daje jednak następujące wyniki:

${\ Displaystyle x_ {1} = (1,786737601482363 + 1,786737578486707) /2 = 1,786737589984535,}$

${\ Displaystyle x_ {2} = 2,054360090947453 \ times 10 ^ {- 8} /1,786737589984535=1,149782767465722\ razy 10 ^ {- 8}.}$

Zwróć uwagę na zachowanie wszystkich znaczących cyfr dla . ${\ displaystyle x_ {2}}$

Należy zauważyć, że chociaż powyższe sformułowanie pozwala uniknąć katastrofalnego anulowania między terminami i , pozostaje forma anulowania między wyrazami a elementem wyróżniającym , co nadal może prowadzić do utraty nawet połowy prawidłowych cyfr znaczących. Aby tego uniknąć, dyskryminator musi być obliczony arytmetycznie z dwukrotnie większą dokładnością wyniku (np. Precyzja poczwórna, jeśli wynik końcowy ma być dokładny do pełnej podwójnej precyzji). Może to mieć postać połączonej operacji mnożenia i dodawania . ${\ displaystyle b}$${\ displaystyle {\ sqrt {b ^ {2} -4ac}}}$${\ displaystyle b ^ {2}}$${\ displaystyle -4ac}$${\ displaystyle b ^ {2} -4ac}$

Aby to zilustrować, rozważ następujące równanie kwadratowe, zaadaptowane z Kahana (2004):

${\ Displaystyle 94906265.625x ^ {2} -189812534x + 94906268,375.}$

To równanie ma i korzenie ${\ displaystyle \ Delta = 7,5625}$

${\ displaystyle x_ {1} = 1,000000028975958,}$

${\ Displaystyle x_ {2} = 1,000000000000000.}$

Jednak po obliczeniu za pomocą arytmetyki podwójnej precyzji IEEE 754 odpowiadającej 15 do 17 cyfr znaczących dokładności, jest zaokrąglany do 0,0, a obliczone pierwiastki są ${\ displaystyle \ Delta}$

${\ displaystyle x_ {1} = 1,000000014487979,}$

${\ displaystyle x_ {2} = 1,000000014487979,}$

które są fałszywe po ósmej cyfrze znaczącej. Dzieje się tak pomimo faktu, że na pozór wydaje się, że do rozwiązania problemu potrzeba tylko 11 znaczących cyfr dokładności.

Inne przykłady

• Funkcja expm1 oblicza wykładniczy minus 1 . Dla małej X , exp ( x ) - 1 spowoduje utratę wagi podczas odejmowania; użycie specjalnie zaprojektowanej funkcji pomaga rozwiązać problem.

Zobacz też

• Błąd zaokrąglenia
• Algorytm sumowania Kahana
• Dokładna arytmetyka Karlsruhe
• Exsecant
• Przykład w wikibookach: Anulowanie cyfr znaczących w obliczeniach numerycznych

Bibliografia