Katastrofické zrušení - Catastrophic cancellation

V numerické analýze je katastrofické zrušení fenomén, který po odečtení dobrých aproximací dvou blízkých čísel může přinést velmi špatnou aproximaci rozdílu původních čísel.

Předpokládejme například, že máte dva dřevěné cvočky, jeden dlouhý a druhý dlouhý. Pokud je změříte pomocí pravítka, které je dobré pouze na centimetr, můžete získat aproximace a . V závislosti na vašich potřebách, mohou být dobré přiblížení, v relativní chyby , ke skutečné délky: aproximace jsou omylem o méně než 2% skutečných délek . ${\ displaystyle L_ {1} = 254,5 \, {\ text {cm}}}$${\ displaystyle L_ {2} = 253,5 \, {\ text {cm}}}$${\ displaystyle {\ tilde {L}} _ {1} = 255 \, {\ text {cm}}}$${\ displaystyle {\ tilde {L}} _ {2} = 253 \, {\ text {cm}}}$${\ displaystyle | L_ {1} - {\ tilde {L}} _ {1} | / | L_ {1} | <2 \%}$

Pokud však odečtete přibližné délky, dostanete , i když skutečný rozdíl mezi délkami je . Rozdíl z aproximací, a již chybou 100% velikosti rozdílu skutečných hodnot . ${\ displaystyle {\ tilde {L}} _ {1} - {\ tilde {L}} _ {2} = 255 \, {\ text {cm}} - 253 \, {\ text {cm}} = 2 \, {\ text {cm}}}$${\ displaystyle L_ {1} -L_ {2} = 254,5 \, {\ text {cm}} - 253,5 \, {\ text {cm}} = 1 \, {\ text {cm}}}$${\ displaystyle 2 \, {\ text {cm}}}$${\ displaystyle 1 \, {\ text {cm}}}$

Katastrofické zrušení může nastat, i když je rozdíl vypočítán přesně, jako v příkladu výše - nejde o vlastnost žádného konkrétního druhu aritmetiky, jako je aritmetika s plovoucí desetinnou čárkou ; spíše je vlastní odčítání, když vstupy jsou samotné aproximace. V aritmetice s plovoucí desetinnou čárkou, když jsou vstupy dostatečně blízko, je rozdíl s plovoucí desetinnou čárkou vypočítán přesně pomocí Sterbenzova lematu - při operaci odčítání s plovoucí desetinnou čárkou není zavedena žádná chyba zaokrouhlování.

Formální analýza

Formálně ke katastrofickému zrušení dochází, protože odčítání je na blízkých vstupech špatně podmíněno : i když jsou aproximace a mají malé relativní chyby a od skutečných hodnot a relativní chyba přibližného rozdílu od skutečného rozdílu je nepřímo úměrná skutečnému rozdílu: ${\ displaystyle {\ tilde {x}} = x (1+ \ delta _ {x})}$${\ displaystyle {\ tilde {y}} = y (1+ \ delta _ {y})}$ ${\ displaystyle | \ delta _ {x} | = | x - {\ tilde {x}} | / | x |}$${\ displaystyle | \ delta _ {y} | = | y - {\ tilde {y}} | / | y |}$${\ displaystyle x}$${\ displaystyle y}$ ${\ displaystyle {\ tilde {x}} - {\ tilde {y}}}$${\ displaystyle xy}$

$${\ displaystyle {\ begin {aligned} {\ tilde {x}} - {\ tilde {y}} & = x (1+ \ delta _ {x}) - y (1+ \ delta _ {y}) = x-y + x \ delta _ {x} -y \ delta _ {y} \\ & = x-y + (xy) {\ frac {x \ delta _ {x} -y \ delta _ {y}} { xy}} \\ & = (xy) {\ biggr (} 1 + {\ frac {x \ delta _ {x} -y \ delta _ {y}} {xy}} {\ biggr)}. \ end { zarovnaný}}}$$

Relativní chyba přesného rozdílu aproximací z rozdílu skutečných čísel tedy je ${\ displaystyle {\ tilde {x}} - {\ tilde {y}}}$${\ displaystyle xy}$

$${\ displaystyle \ left | {\ frac {x \ delta _ {x} -y \ delta _ {y}} {xy}} \ doprava |.}$$

které mohou být libovolně velké, pokud jsou skutečné vstupy a jsou blízké. ${\ displaystyle x}$${\ displaystyle y}$

V numerických algoritmech

Odečtení blízkých čísel aritmetikou s plovoucí desetinnou čárkou nemusí vždy způsobit katastrofické zrušení nebo dokonce jakoukoli chybu - u Sterbenzova lematu , pokud jsou čísla dostatečně blízko, je rozdíl s plovoucí desetinnou čárkou přesný. Ale zrušení může zesílit chyby ve vstupech, které vznikly zaokrouhlováním v jiné aritmetice s plovoucí desetinnou čárkou.

Příklad: Rozdíl čtverců

Vzhledem k daným číslům a naivní pokus o výpočet matematické funkce aritmetikou s plovoucí desetinnou čárkou podléhá katastrofickému zrušení, když jsou a jsou blízko velikosti, protože odčítání zesílí chyby zaokrouhlování ve čtvercích. Alternativní factoring , vyhodnocený aritmetikou s plovoucí desetinnou čárkou , se vyhne katastrofickému zrušení, protože se vyhne zavedení chyby zaokrouhlování vedoucí k odčítání. ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle x ^ {2} -y ^ {2}}$${\ displaystyle \ operatorname {fl} (\ operatorname {fl} (x ^ {2}) - \ operatorname {fl} (y ^ {2}))}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle (x + y) (xy)}$${\ displaystyle \ operatorname {fl} (\ operatorname {fl} (x + y) \ cdot \ operatorname {fl} (xy))}$

Například, jestliže a , pak skutečná hodnota tohoto rozdílu je . V aritmetice IEEE 754 binary64 poskytuje vyhodnocení alternativního factoringu správný výsledek přesně (bez zaokrouhlování), ale vyhodnocení naivního výrazu dává nejbližší číslo s plovoucí desetinnou čárkou , z nichž je správná pouze polovina číslic a druhá polovina (podtrženo) jsou odpadky. ${\ displaystyle x = 1 + 2 ^ {- 29} \ přibližně 1,0000000018626451}$${\ displaystyle y = 1 + 2 ^ {- 30} \ přibližně 1,0000000009313226}$${\ displaystyle x ^ {2} -y ^ {2}}$${\ displaystyle 2 ^ {- 29} \ cdot (1 + 2 ^ {- 30} +2 ^ {- 31}) \ přibližně 1,8626451518330422 \ krát 10 ^ {- 9}}$${\ displaystyle (x + y) (xy)}$${\ displaystyle x ^ {2} -y ^ {2}}$${\ displaystyle 1.8626451 {\ podtržení {49230957}} \ krát 10 ^ {- 9}}$

Příklad: Složitý arcsine

Při výpočtu komplexní funkce arcsine může být v pokušení použít logaritmický vzorec přímo:

$${\ displaystyle \ arcsin (z) = i \ log {\ bigl (} {\ sqrt {1-z ^ {2}}} - iz {\ bigr)}.}$$

Předpokládejme však, že pro . Pak a ; nazvat rozdíl mezi nimi - velmi malý rozdíl, téměř nulový. If se hodnotí v aritmetickém dávání s plovoucí desetinnou čárkou ${\ displaystyle z = iy}$${\ displaystyle y \ ll 0}$${\ displaystyle {\ sqrt {1-z ^ {2}}} \ přibližně -y}$${\ displaystyle iz = -y}$${\ displaystyle \ varepsilon}$${\ displaystyle {\ sqrt {1-z ^ {2}}}}$

$${\ displaystyle \ operatorname {fl} {\ Bigl (} {\ sqrt {\ operatorname {fl} (1- \ operatorname {fl} (z ^ {2}))}}} \ \ Bigr)} = {\ sqrt { 1-z ^ {2}}} (1+ \ delta)}$$

s jakoukoli chybou , kde označuje zaokrouhlování s plovoucí desetinnou čárkou, pak výpočet rozdílu ${\ displaystyle \ delta \ neq 0}$${\ displaystyle \ operatorname {fl} (\ cdots)}$

$${\ displaystyle {\ sqrt {1-z ^ {2}}} (1+ \ delta) -iz}$$

dvou blízkých čísel, obě velmi blízko , může zesílit chybu v jednom vstupu o faktor - velmi velký faktor, protože byl téměř nulový. Například pokud , skutečná hodnota je přibližně , ale použití naivního logaritmického vzorce v aritmetice IEEE 754 binary64 může dát , pouze pět z šestnácti číslic je správné a zbytek (podtrženo) veškerý odpad. ${\ displaystyle -y}$${\ displaystyle \ delta}$${\ displaystyle 1 / \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle z = -1234567i}$${\ displaystyle \ arcsin (z)}$${\ displaystyle -14.71937803983977i}$${\ displaystyle -14,719 {\ podtržení {644263563968}} i}$

V případě for se použití identity vyhne zrušení, protože ale , takže odčítání je fakticky přidání se stejným znaménkem, které se nezruší. ${\ displaystyle z = iy}$${\ displaystyle y <0}$${\ displaystyle \ arcsin (z) = - \ arcsin (-z)}$${\ textstyle {\ sqrt {1 - (- z) ^ {2}}} = {\ sqrt {1-z ^ {2}}} \ přibližně -y}$${\ displaystyle i (-z) = - iz = y}$

Příklad: převod Radix

Numerické konstanty v softwarových programech jsou často psány desítkově, například ve fragmentu C double x = 1.000000000000001;k deklaraci a inicializaci pojmenované proměnné IEEE 754 binary64 x. Není však číslo s plovoucí desetinnou čárkou binary64; nejbližší, na kterou bude inicializován tento fragment, je . Ačkoli převod radixu z desetinné plovoucí desetinné čárky na binární plovoucí desetinnou čárku způsobí pouze malou relativní chybu, může ji katastrofické zrušení zesílit na mnohem větší: ${\ displaystyle 1,000000000000001}$x${\ displaystyle 1,0000000000000011102230246251565404236316680908203125 = 1 + 5 \ cdot 2 ^ {- 52}}$

double x = 1.000000000000001;  // rounded to 1 + 5*2^{-52}
double y = 1.000000000000002;  // rounded to 1 + 9*2^{-52}
double z = y - x;              // difference is exactly 4*2^{-52}

Rozdíl je . Relativní chyby od a od jsou oba níže a odčítání s plovoucí desetinnou čárkou se počítá přesně podle Sterbenzova lematu. ${\ displaystyle 1,000000000000002-1,000000000000001}$${\ displaystyle 0,000000000000001 = 1,0 \ krát 10 ^ {- 15}}$x${\ displaystyle 1,000000000000001}$y${\ displaystyle 1,000000000000002}$${\ displaystyle 10 ^ {- 15} = 0,0000000000001 \%}$y - x

Ale i když jsou vstupy dobré aproximace a přestože je odčítání vypočítáno přesně, rozdíl aproximací má relativní chybu přes od rozdílu původních hodnot, jak je napsáno v desítkové soustavě: katastrofické zrušení zesílilo malou chybu v převodu radixu do velké chyby ve výstupu. ${\ displaystyle {\ tilde {y}} - {\ tilde {x}} = (1 + 9 \ cdot 2 ^ {- 52}) - (1 + 5 \ cdot 2 ^ {- 52}) = 4 \ cdot 2 ^ {- 52} \ přibližně 8,88 \ krát 10 ^ {- 16}}$${\ displaystyle 11 \%}$${\ displaystyle 1,0 \ krát 10 ^ {- 15}}$

Benigní zrušení

V numerických algoritmech je zrušení někdy užitečné a žádoucí. Například algoritmy 2Sum a Fast2Sum se spoléhají na takové zrušení po chybě zaokrouhlování, aby přesně vypočítali, jaká byla chyba v operaci s plovoucí desetinnou čárkou jako samotné číslo s plovoucí desetinnou čárkou.

Pokud bude funkce naivně hodnocena v bodech , ztratí zaokrouhlování většinu číslic . Samotná funkce je však při vstupech blízko dobře stabilizována . Přepis to jako ${\ displaystyle \ log (1 + x)}$${\ displaystyle 0 <x \ lll 1}$${\ displaystyle x}$${\ displaystyle \ operatorname {fl} (1 + x)}$${\ displaystyle \ log (1 + x)}$${\ displaystyle 0}$

$${\ displaystyle \ log (1 + x) = x {\ frac {\ log (1 + x)} {(1 + x) -1}}}$$

${\ displaystyle {\ hat {x}}: = \ operatorname {fl} (1 + x) -1}$

${\ displaystyle \ log (1 + x)}$

${\ displaystyle \ log (\ operatorname {fl} (1 + x)) = {\ hat {x}} + O ({\ hat {x}} ^ {2})}$

${\ displaystyle {\ hat {x}} = \ operatorname {fl} (1 + x) -1}$

${\ displaystyle \ mu (\ xi) = \ log (1+ \ xi) / \ xi}$

${\ displaystyle \ mu ({\ hat {x}})}$

${\ displaystyle \ mu (x)}$

${\ displaystyle x \ cdot \ mu ({\ hat {x}})}$

${\ Displaystyle x \ cdot \ mu (x) = \ log (1 + x)}$

Reference