Ztráta významu - Loss of significance

Ztráta významnosti je nežádoucím účinkem ve výpočtech pomocí aritmetiky s konečnou přesností, jako je aritmetika s plovoucí desetinnou čárkou . Dochází k němu, když operace na dvou číslech zvyšuje relativní chybu podstatně více, než zvyšuje absolutní chybu , například při odečtení dvou téměř stejných čísel (známé jako katastrofické zrušení ). Důsledkem je , že počet platných číslic ve výsledku je nepřijatelně snížen. Způsoby, jak se tomuto efektu vyhnout, jsou studovány v numerické analýze .

Demonstrace problému

Odčítání

Efekt lze prokázat desetinnými čísly. Následující příklad ukazuje katastrofické zrušení 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 považovat za prováděné na antilogaritmech , u nichž pravidla pro významné číslice naznačují, že počet platných čísel zůstává stejný jako nejmenší počet platných čísel v mantisách . Způsob, jak to naznačit a představovat odpověď na 10 platných čísel, je

   1.000000000×10−10

Ztráta významných bitů

Nechť x a y jsou kladná normalizovaná čísla s plovoucí desetinnou čárkou.

V odčítání x - y , kde jsou ztraceny r 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 .

Ř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 (xy \ right) \ left (x + y \ right) = x ^ {2} -y ^ {2}}$

S výrazem tedy vynásobte čitatele a jmenovatele dáváním ${\ displaystyle xy}$${\ displaystyle x + y}$

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

Lze nyní výraz snížit tak, aby se vyloučilo odčítání? Někdy může. ${\ displaystyle x ^ {2} -y ^ {2}}$

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

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

Nestabilita kvadratické rovnice

Zvažte například kvadratickou rovnici

${\ 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ž 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 c}$${\ displaystyle b}$

Případ , , bude sloužit pro ilustraci problému: ${\ displaystyle a = 1}$${\ displaystyle b = 200}$${\ displaystyle c = -0,000015}$

${\ 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ší velikosti 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

Pečlivá počítačová implementace s plovoucí desetinnou čárkou kombinuje několik strategií k dosažení robustního výsledku. Za předpokladu, že diskriminační b ² - 4 ac je kladné a b je nenulové, výpočet by byl následující:

${\ 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 funkci znaménka , kde je 1, pokud je kladné, a -1, pokud je záporné. Tím se zabrání problémům se zrušením mezi a druhou odmocninou diskriminujícího zajištěním přidání pouze čísel stejného znaménka. ${\ displaystyle \ operatorname {sgn} (b)}$${\ displaystyle b}$${\ displaystyle b}$${\ displaystyle b}$

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

${\ 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í vedlo k tomu, že bylo počítáno pouze s 8 platnými číslicemi přesnosti. ${\ displaystyle x_ {2}}$

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.149782767465722\krát 10 ^ {- 8}.}$

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

Všimněte si, že i když se výše uvedená formulace vyhne katastrofickému zrušení mezi a , zůstává forma zrušení mezi podmínkami a diskriminační, což může stále vést ke ztrátě až poloviny správných platných číslic. Aby se tomu zabránilo, je třeba diskriminátor vypočítat aritmeticky s dvojnásobnou přesností výsledku (např. Čtyřnásobná přesnost, pokud má být konečný výsledek přesný na plnou dvojnásobnou přesnost). Může to být ve formě operace kondenzovaného vícenásobného přidání . ${\ displaystyle b}$${\ displaystyle {\ sqrt {b ^ {2} -4ac}}}$${\ displaystyle b ^ {2}}$${\ displaystyle -4ac}$${\ displaystyle b ^ {2} -4ac}$

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

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

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

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

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

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

${\ 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í.

Další příklady

• Funkce expm1 vypočítá exponenciální mínus 1 . Pro malé x , exp ( x ) - 1 způsobí ztrátu významu v odčítání; použití speciálně navržené funkce pomáhá vyřešit problém.

Viz také

• Chyba zaokrouhlování
• Kahanův součtový algoritmus
• Karlsruhe přesná aritmetika
• Exsecant
• Příklad ve wikibookech: Zrušení platných číslic v numerických výpočtech

Reference