Ztráta významu - Loss of significance

Příklad LOS v případě výpočtu 2 forem stejné funkce

Ztráta významu je nežádoucí účinek ve výpočtech využívajících aritmetiku s konečnou přesností, jako je aritmetika s plovoucí desetinnou čárkou. Nastane, když se zvýší operace na dvou číslech relativní chyba podstatně více, než se zvyšuje absolutní chyba, například při odečtení dvou téměř stejných čísel (označovaných jako katastrofické zrušení). Výsledkem je, že počet významné číslice ve výsledku je nepřijatelně snížen. Způsoby, jak se tomuto efektu vyhnout, jsou studovány v numerická analýza.

Demonstrace problému

Efekt lze demonstrovat pomocí desetinných čísel. Následující příklad ukazuje ztrátu významnosti pro datový typ s desetinnou plovoucí desetinnou čárkou s 10 platnými číslicemi:

Zvažte desetinné číslo

   x = 0,1234567891234567890

Reprezentace tohoto čísla s plovoucí desetinnou čárkou na stroji, který uchovává 10 číslic s plovoucí desetinnou čárkou, by byla

   y = 0,1234567891

což je docela blízko při měření chyby jako procenta hodnoty. Při měření v pořadí přesnosti je to velmi odlišné. Hodnota 'x' je přesná 10×10⁻¹⁹, zatímco hodnota „y“ je pouze přesná 10×10⁻¹⁰.

Nyní proveďte výpočet

   x - y = 0,1234567891234567890 - 0,1234567890000000000

Odpověď s přesností na 20 platných číslic je

   0.0000000001234567890

Na 10místném stroji s plovoucí desetinnou čárkou však výpočet přináší

   0.1234567891 − 0.1234567890 = 0.0000000001

V obou případech je výsledek přesný se stejným řádem jako vstupy (−20 a −10). V druhém případě se zdá, že odpověď má jednu významnou číslici, což by znamenalo ztrátu významnosti. Avšak v počítačové aritmetice s plovoucí desetinnou čárkou lze všechny operace zobrazit jako prováděné na antilogaritmy, pro které platí pravidla pro významné postavy uveďte, že počet platných čísel zůstává stejný jako nejmenší počet platných čísel v EU kudlanky. Způsob, jak to naznačit a představovat odpověď na 10 platných čísel, je

   1.000000000×10⁻¹⁰

Řešení

Je možné provádět výpočty pomocí přesné zlomkové reprezentace racionálních čísel a zachovat všechny významné číslice, ale toto je často neúměrně pomalejší než aritmetika s plovoucí desetinnou čárkou.

Jednou z nejdůležitějších částí numerické analýzy je vyhnout se nebo minimalizovat ztrátu významnosti ve výpočtech. Pokud je základní problém dobře položený, měl by existovat stabilní algoritmus pro jeho řešení.

Někdy chytré triky algebry mohou změnit výraz do podoby, která obchází problém. Jedním z takových triků je použití známé rovnice

{ displaystyle left (x-y right) left (x + y right) = x ^ {2} -y ^ {2}}

Takže s výrazem ${ displaystyle x-y}$ , vynásobte čitatele a jmenovatele číslem ${ displaystyle x + y}$ dávat

{ displaystyle { frac {x ^ {2} -y ^ {2}} {x + y}}}

Nyní může výraz ${ displaystyle x ^ {2} -y ^ {2}}$ být snížena, aby se odstranilo odečtení? Někdy může.

Například výraz ${ displaystyle 1 - { sqrt {1- delta}}}$ může utrpět ztrátu významných bitů, pokud ${ displaystyle | delta |}$ je mnohem menší než 1. Takže přepište výraz jako

{ displaystyle { frac {1- levý (1- delta pravý)} {1 + { sqrt {1- delta}}}}}

nebo

{ displaystyle { frac { delta} {1 + { sqrt {1- delta}}}}}

Ztráta významných bitů

Nechat X a y být kladná normalizovaná čísla s plovoucí desetinnou čárkou.

V odčítání X − y, r kde se ztratí významné bity

{ Displaystyle q leq r leq p,}

{ displaystyle 2 ^ {- p} leq 1 - { frac {y} {x}} leq 2 ^ {- q}}

pro některá kladná celá čísla p a q.

Nestabilita kvadratické rovnice

Zvažte například kvadratická rovnice

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

se dvěma přesnými řešeními:

{ displaystyle x = { frac {-b pm { sqrt {b ^ {2} -4ac}}} {2a}}.}

Tento vzorec nemusí vždy přinést přesný výsledek. Například když ${ displaystyle c}$ je velmi malý, může dojít ke ztrátě významnosti v některém z kořenových výpočtů, v závislosti na znaménku ${ displaystyle b}$ .

Pouzdro ${ displaystyle a = 1}$ , ${ displaystyle b = 200}$ , ${ displaystyle c = -0,000015}$ bude sloužit k ilustraci problému:

{ displaystyle x ^ {2} + 200x-0,000015 = 0.}

My máme

{ displaystyle { sqrt {b ^ {2} -4ac}} = { sqrt {200 ^ {2} +4 krát 1 krát 0,000015}} = 200,00000015 dotso}

Ve skutečné aritmetice jsou kořeny

{ displaystyle (-200-200,0000000015) /2=-200,000000075,}

{ displaystyle (-200 + 200,00000015) /2=0,000000075.}

V 10místné aritmetice s plovoucí desetinnou čárkou:

{ displaystyle (-200-200,000000001) /2=-200,00000005,}

{ displaystyle (-200 + 200,0000001) /2=0,00000005.}

Všimněte si, že řešení větší velikost je přesný na deset číslic, ale první nenulová číslice řešení menší velikosti je nesprávná.

Kvůli odčítání, které se vyskytuje v kvadratické rovnici, nepředstavuje stabilní algoritmus pro výpočet dvou kořenů.

Lepší algoritmus

Opatrně plovoucí bod počítačová implementace kombinuje několik strategií k dosažení robustního výsledku. Za předpokladu, že diskriminující b² − 4ac je pozitivní a b je nenulová, výpočet by byl následující:^[1]

{ displaystyle { begin {aligned} 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 {zarovnáno}}}

Zde sgn označuje znaková funkce, kde ${ displaystyle operatorname {sgn} (b)}$ je 1, pokud ${ displaystyle b}$ je kladné a −1 pokud ${ displaystyle b}$ je negativní. Tím se vyhnete problémům se zrušením mezi ${ displaystyle b}$ a druhá odmocnina diskriminujícího zajištěním přidání pouze čísel stejného znaménka.

Pro ilustraci nestability standardního kvadratického vzorce ve srovnání s tímto vzorcem zvažte kvadratickou rovnici s kořeny ${ displaystyle 1.786737589984535}$ a ${ displaystyle 1.149782767465722 krát 10 ^ {- 8}}$ . Na 16 platných číslic, což zhruba odpovídá dvojnásobná přesnost přesnost na počítači lze monickou kvadratickou rovnici s těmito kořeny zapsat jako

{ displaystyle x ^ {2} -1,786737601482363x + 2,054360090947453 krát 10 ^ {- 8} = 0.}

Při použití standardního kvadratického vzorce a zachování 16 platných číslic v každém kroku se získá standardní kvadratický vzorec

{ 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.}

Všimněte si, jak zrušení vyústilo ${ displaystyle x_ {2}}$ vypočítává se pouze na 8 platných číslic přesnosti.

Zde uvedený variantní vzorec však poskytuje následující:

{ displaystyle x_ {1} = (1,786737601482363 + 1,786737578486707) /2=1.786737589984535,}

{ displaystyle x_ {2} = 2,054360090947453 krát 10 ^ {- 8} /1.786737589984535=1.149782767465722krát 10 ^ {- 8}.}

Všimněte si uchování všech platných číslic pro ${ displaystyle x_ {2}}$ .

Všimněte si, že zatímco výše uvedená formulace se vyhne katastrofickému zrušení mezi ${ displaystyle b}$ a ${ displaystyle { sqrt {b ^ {2} -4ac}}}$ , mezi podmínkami zůstává forma zrušení ${ displaystyle b ^ {2}}$ a ${ displaystyle -4ac}$ diskriminátoru, což může stále vést ke ztrátě až poloviny správných platných číslic.^[2]^[3] Diskriminační ${ displaystyle b ^ {2} -4ac}$ je třeba počítat aritmetikou dvojnásobné přesnosti výsledku, aby se tomu zabránilo (např. čtyřkolka přesnost, pokud má být konečný výsledek přesný dvojnásobek přesnost).^[4] Může to mít formu a fúzovaný násobit-přidat úkon.^[2]

Pro ilustraci zvažte následující kvadratickou rovnici převzatou z Kahana (2004):^[2]

{ displaystyle 94906265.625x ^ {2} -189812534x + 94906268.375.}

Tato rovnice má ${ displaystyle Delta = 7,5625}$ a kořeny

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

{ displaystyle x_ {2} = 1,000000000000000.}

Při výpočtu pomocí aritmetiky s dvojitou přesností IEEE 754, která odpovídá 15 až 17 platným číslicím přesnosti, ${ displaystyle Delta}$ je zaokrouhleno na 0,0 a vypočítané kořeny jsou

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

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

které jsou po 8. významné číslici nepravdivé. A to navzdory skutečnosti, že povrchně se zdá, že problém vyžaduje pouze 11 platných číslic přesnosti pro jeho řešení.

Viz také

Reference

^ Press, William Henry; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (1992). „Oddíl 5.6: Kvadratické a kubické rovnice“. Numerické recepty v jazyce C. (2. vyd.).
^ ^A ^b ^C Kahan, William Morton (2004-11-20). „Na úkor výpočtu s plovoucí desetinnou čárkou bez mimořádně přesné aritmetiky“ (PDF). Citováno 2012-12-25.
^ Higham, Nicholas John (2002). Přesnost a stabilita numerických algoritmů (2. vyd.). SIAM. str. 10. ISBN 978-0-89871-521-7.
^ Hough, David (březen 1981). Msgstr "Aplikace navrhovaného standardu IEEE 754 pro aritmetiku s plovoucí desetinnou čárkou". Počítač. IEEE. 14 (3): 70–74. doi:10.1109 / C-M.1981.220381.

[Press_1992-1] Press, William Henry; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (1992). „Oddíl 5.6: Kvadratické a kubické rovnice“. Numerické recepty v jazyce C. (2. vyd.).

[Kahan_2004-2] A ^b ^C Kahan, William Morton (2004-11-20). „Na úkor výpočtu s plovoucí desetinnou čárkou bez mimořádně přesné aritmetiky“ (PDF). Citováno 2012-12-25.

[Higham_2002-3] Higham, Nicholas John (2002). Přesnost a stabilita numerických algoritmů (2. vyd.). SIAM. str. 10. ISBN 978-0-89871-521-7.

[Hough_1981-4] Hough, David (březen 1981). Msgstr "Aplikace navrhovaného standardu IEEE 754 pro aritmetiku s plovoucí desetinnou čárkou". Počítač. IEEE. 14 (3): 70–74. doi:10.1109 / C-M.1981.220381.

[1]

[2]

[3]

[4]