Błąd zaokrąglenia — Round-off error

Błąd zaokrąglenia , zwany także zaokrąglania błąd , jest różnica między wynikiem wytwarzanego przez dany algorytm za pomocą arytmetyki i dokładny wynik wyprodukowany przez tego samego algorytmu z wykorzystaniem skończonej precyzji zaokrąglony arytmetyki. Błędy zaokrągleń wynikają z niedokładności w reprezentacji liczb rzeczywistych i wykonywanych na nich operacji arytmetycznych. Jest to forma błędu kwantyzacji . Podczas korzystania z równań lub algorytmów aproksymacyjnych , zwłaszcza gdy do reprezentacji liczb rzeczywistych (które teoretycznie mają nieskończenie wiele cyfr), używa się skończenie wielu cyfr, jednym z celów analizy numerycznej jest oszacowanie błędów obliczeniowych. Błędy obliczeniowe, zwane również błędami liczbowymi , obejmują zarówno błędy obcięcia, jak i błędy zaokrąglenia.

Gdy wykonywana jest sekwencja obliczeń z danymi wejściowymi zawierającymi dowolny błąd zaokrąglenia, błędy mogą się kumulować, czasami dominując w obliczeniach. W źle uwarunkowanych problemach może kumulować się znaczny błąd.

W skrócie, istnieją dwa główne aspekty błędów zaokrąglania w obliczeniach numerycznych:

1. Komputery cyfrowe mają ograniczenia dotyczące wielkości i precyzji ich zdolności do reprezentowania liczb.
2. Niektóre manipulacje numeryczne są bardzo wrażliwe na błędy zaokrągleń. Może to wynikać zarówno ze względów matematycznych, jak i ze sposobu, w jaki komputery wykonują operacje arytmetyczne.

Błąd reprezentacji

Błąd wprowadzony przez próbę przedstawienia liczby za pomocą skończonego ciągu cyfr jest formą błędu zaokrąglenia zwanego błędem reprezentacji . Oto kilka przykładów błędu reprezentacji w reprezentacjach dziesiętnych:

Notacja	Reprezentacja	Przybliżenie	Błąd
1/7	0,14 857	0,142 857	0,000000 142 857
w 2	0,693 147 180 559 945 309 41...	0,693 147	0.000 000 180 559 945 309 41...
log 10 2	0,301 029 995 663 981 195 21...	0,3010	0,000 029 995 663 981 195 21...
3 √ 2	1.259 921 049 894 873 164 76...	1,25992	0,000 001 049 894 873 164 76...
√ 2	1.414 213 562 373 095 048 80...	1.41421	0,000 003 562 373 095 048 80...
mi	2.718 281 828 459 045 235 36...	2,718 281 828 459 045	0,000 000 000 000 000 235 36...
π	3.141 592 653 589 793 238 46...	3,141 592 653 589 793	0,000 000 000 000 000 238 46...

Zwiększenie liczby cyfr dozwolonych w reprezentacji zmniejsza wielkość możliwych błędów zaokrągleń, ale każda reprezentacja ograniczona do skończonej liczby cyfr nadal będzie powodować pewien stopień błędu zaokrąglenia dla nieprzeliczalnie wielu liczb rzeczywistych. Dodatkowe cyfry używane w pośrednich krokach obliczeń są znane jako cyfry ochronne .

Wielokrotne zaokrąglanie może spowodować akumulację błędów. Na przykład, jeśli 9,945309 jest zaokrąglane do dwóch miejsc po przecinku (9,95), a następnie ponownie zaokrąglane do jednego miejsca po przecinku (10,0), całkowity błąd wynosi 0,054691. Zaokrąglanie 9,945309 do jednego miejsca po przecinku (9,9) w jednym kroku wprowadza mniej błędów (0,045309). Dzieje się tak często podczas wykonywania operacji arytmetycznych (patrz Utrata znaczenia ).

System liczb zmiennoprzecinkowych

W porównaniu z stałoprzecinkowym systemu liczbowego The zmiennoprzecinkową system liczbowy jest bardziej wydajny w reprezentacji liczb rzeczywistych, więc jest on powszechnie stosowany w nowoczesnych komputerach. Podczas gdy liczby rzeczywiste są nieskończone i ciągłe, system liczb zmiennoprzecinkowych jest skończony i dyskretny. Zatem w systemie liczb zmiennoprzecinkowych występuje błąd reprezentacji, który prowadzi do błędu zaokrąglenia. ${\ Displaystyle \ mathbb {R}}$${\ Displaystyle F}$

Notacja systemu liczb zmiennoprzecinkowych

System liczb zmiennoprzecinkowych charakteryzuje się liczbami całkowitymi: ${\ Displaystyle F}$${\ Displaystyle 4}$

${\ Displaystyle \ beta}$: podstawa lub podstawa

${\displaystyle p}$: precyzja

${\displaystyle [L,U]}$: zakres wykładników, gdzie jest dolną granicą i jest górną granicą${\ Displaystyle L}$${\ Displaystyle U}$

• Każdy ma następującą postać:${\displaystyle x\wf}$

${\ Displaystyle x = \ pm (\ underbrace {d_ {0}.d_ {1} d_ {2} \ ldots d_ {p-1}} _ {\ tekst {mantissa}})_ {\ beta} \ razy \ beta ^{\overbrace {E} ^{\text{wykładnik}}}=\pm d_{0}\times \beta ^{E}+d_{1}\times \beta ^{E-1}+\ldots +d_{p-1}\times \beta ^{E-(p-1)}}$

gdzie jest liczbą całkowitą taką, że dla , i jest liczbą całkowitą taką, że .${\displaystyle d_{i}}$${\ Displaystyle 0 \ leq d_ {i} \ leq \ beta -1}$${\displaystyle i=0,1,\ldots,p-1}$${\ Displaystyle E}$${\displaystyle L\leq E\leq U}$

Znormalizowany system liczb zmiennoprzecinkowych

• System liczb zmiennoprzecinkowych jest normalizowany, jeśli cyfra wiodąca jest zawsze różna od zera, chyba że liczba wynosi zero. Ponieważ mantysa jest , mantysa liczby niezerowej w znormalizowanym systemie spełnia . W związku z tym znormalizowaną formą niezerowej liczby zmiennoprzecinkowej IEEE jest gdzie . W systemie binarnym cyfra wiodąca jest zawsze, więc nie jest zapisywana i nazywana jest bitem niejawnym. Daje to dodatkową odrobinę precyzji, dzięki czemu zmniejsza się błąd zaokrąglenia spowodowany błędem reprezentacji.${\displaystyle d_{0}}$${\displaystyle d_{0}.d_{1}d_{2}\ldots d_{p-1}}$${\displaystyle 1\leq {\tekst{mantysa}}<\beta}$${\ Displaystyle \ pm 1.bb \ ldots b \ razy 2 ^ {E}}$${\displaystyle b\w {0,1}}$${\ Displaystyle 1}$
• Ponieważ system liczb zmiennoprzecinkowych jest skończony i dyskretny, nie może reprezentować wszystkich liczb rzeczywistych, co oznacza, że ​​nieskończone liczby rzeczywiste mogą być aproksymowane tylko przez niektóre liczby skończone za pomocą reguł zaokrąglania . Pływający punkt przybliżenie danej liczby rzeczywistej Przez mogą być oznaczone. ${\ Displaystyle F}$${\displaystyle x}$${\displaystyle fl(x)}$
  • Całkowita liczba znormalizowanych liczb zmiennoprzecinkowych wynosi

${\ Displaystyle 2 (\ beta -1) \ beta ^ {p-1} (U-L + 1) + 1}$, gdzie

${\ Displaystyle 2}$ liczy wybór znaku, bycie dodatnim lub ujemnym

${\displaystyle (\beta-1)}$ liczy wybór cyfry wiodącej

${\ Displaystyle \ beta ^ {p-1}}$ liczy pozostałą mantysę

${\ Displaystyle U-L + 1}$ liczy wybór wykładników

${\ Displaystyle 1}$liczy przypadek, gdy liczba jest .${\ Displaystyle 0}$

Standard IEEE

W standardzie IEEE podstawa jest binarna, tj . stosowana jest normalizacja. Standard IEEE przechowuje znak, wykładnik i mantysę w oddzielnych polach słowa zmiennoprzecinkowego, z których każde ma stałą szerokość (liczbę bitów). Dwa najczęściej używane poziomy dokładności dla liczb zmiennoprzecinkowych to pojedyncza precyzja i podwójna precyzja. ${\ Displaystyle \ beta = 2}$

Precyzja	Znak (bity)	Wykładnik (bity)	Mantysa (kawałki)
Pojedynczy	1	8	23
Podwójnie	1	11	52

Maszyna epsilon

Maszyna epsilon może być wykorzystana do pomiaru poziomu błędu zaokrąglenia w systemie liczb zmiennoprzecinkowych. Oto dwie różne definicje.

• Epsilon maszynowy, oznaczony jako , jest maksymalnym możliwym bezwzględnym błędem względnym w reprezentowaniu niezerowej liczby rzeczywistej w systemie liczb zmiennoprzecinkowych.${\ Displaystyle \ epsilon _ {mach}}$${\displaystyle x}$

${\ Displaystyle \ epsilon _ {mach} = \ max _ {x} {\ Frac {| x-fl (x) |} {| x |}}}$

• Epsilon maszyny, oznaczony jako , jest najmniejszą liczbą taką, że . Tak więc, gdy .${\ Displaystyle \ epsilon _ {mach}}$${\displaystyle \epsilon}$${\displaystyle fl(1+\epsilon)>1}$${\displaystyle fl(1+\delta)=fl(1)=1}$${\displaystyle |\delta |<\epsilon_{mach}}$

Błąd zaokrąglania przy różnych zasadach zaokrąglania

Istnieją dwie wspólne zasady zaokrąglania: runda po kawałku i runda do najbliższego. Standard IEEE wykorzystuje zaokrąglenie do najbliższego.

• Round-by-chop : Rozwinięcie podstawy jest obcinane po cyfrze. ${\ Displaystyle \ beta}$${\displaystyle x}$${\ Displaystyle (p-1) ^ {th}}$
  • Ta zasada zaokrąglania jest stronnicza, ponieważ zawsze przesuwa wynik w kierunku zera.
• Round-to-nearest : jest ustawiana na najbliższą liczbę zmiennoprzecinkową do . W przypadku remisu używana jest liczba zmiennoprzecinkowa, której ostatnia zapisana cyfra jest parzysta. ${\displaystyle fl(x)}$${\displaystyle x}$
  • W przypadku standardu IEEE, w którym znajduje się podstawa , oznacza to, że w przypadku remisu jest on zaokrąglany tak, aby ostatnia cyfra była równa .${\ Displaystyle \ beta}$${\ Displaystyle 2}$${\ Displaystyle 0}$
  • Ta reguła zaokrąglania jest dokładniejsza, ale bardziej kosztowna obliczeniowo.
  • Zaokrąglanie tak, aby ostatnia zapisana cyfra była nawet wtedy, gdy istnieje remis, zapewnia, że ​​nie jest ona systematycznie zaokrąglana w górę lub w dół. Ma to na celu uniknięcie niepożądanego powolnego dryftu w długich obliczeniach z powodu po prostu obciążonego zaokrąglenia.
• Poniższy przykład ilustruje poziom błędu zaokrąglania w ramach dwóch reguł zaokrąglania. Reguła zaokrąglania, od zaokrąglania do najbliższej, prowadzi ogólnie do mniejszego błędu zaokrąglania.

x	Okrąg po posiekaniu	Błąd zaokrąglenia	Okrągły do ​​najbliższego	Błąd zaokrąglenia
1,649	1,6	0,049	1,6	0,049
1.650	1,6	0,050	1,7	0,050
1,651	1,6	0,051	1,7	-0,049
1,699	1,6	0,099	1,7	-0.001
1,749	1,7	0,049	1,7	0,049
1.750	1,7	0,050	1,8	-0,050

Obliczanie błędu zaokrąglenia w standardzie IEEE

Załóżmy, że zastosowano metodę round-to-neast i podwójną precyzję IEEE.

• Przykład: liczbę dziesiętną można zmienić na${\ Displaystyle (9,4) _ {10} = (1001. {\ overline {0110}}) _ {2}}$

${\ Displaystyle +1. \ Underbrace {001011001100100110011001100110011001100110011001100} _ {\ tekst {52 bity}} 110 \ ldots \ razy 2 ^ {3}}$

Ponieważ bit na prawo od punktu binarnego to a, po którym następują inne niezerowe bity, reguła zaokrąglania do najbliższego wymaga zaokrąglania w górę, to znaczy dodawania bitu do bitu. Tak więc znormalizowana reprezentacja zmiennoprzecinkowa w standardzie IEEE to ${\ Displaystyle 53 ^ {rd}}$${\ Displaystyle 1}$${\ Displaystyle 1}$${\ Displaystyle 52 ^ {nd}}$${\ Displaystyle 9,4}$

${\ Displaystyle fl (9.4) = 1.001100110011001100110011001100110011001100110011001101\razy 2 ^ {3}}$.

• Teraz błąd zaokrąglenia można obliczyć podczas reprezentowania za pomocą .${\ Displaystyle 9,4}$${\ Displaystyle fl (9,4)}$

Ta reprezentacja jest uzyskiwana przez odrzucenie nieskończonego ogona

${\ Displaystyle 0. {\ overline {1100}} \ razy 2 ^ {-52} \ razy 2 ^ {3} = 0. {\ overline {0110}} \ razy 2 ^ {-51} \ razy 2 ^ { 3}=0.4\razy 2^{-48}}$

od prawego ogona, a następnie dodawane w kroku zaokrąglania. ${\ Displaystyle 1 \ razy 2 ^ {-52} \ razy 2 ^ {3} = 2 ^ {-49}}$

Następnie .${\ Displaystyle fl (9,4) = 9,4-0,4 \ razy 2 ^ {-48} +2 ^ {-49} = 9,4 + (0,2) _ {10} \ razy 2 ^ {-49}}$

Zatem błąd zaokrąglenia wynosi .${\ Displaystyle (0,2 \ razy 2 ^ {-49}) _ {10}}$

Pomiar błędu zaokrąglenia za pomocą maszyny epsilon

Maszyna epsilon może być wykorzystana do pomiaru poziomu błędu zaokrąglenia przy użyciu dwóch powyższych reguł zaokrąglania. Poniżej znajdują się wzory i odpowiadający im dowód. Używamy tutaj pierwszej definicji maszyny epsilon. ${\ Displaystyle \ epsilon _ {mach}}$

Twierdzenie

1. Runda po kawałku: ${\ Displaystyle \ epsilon _ {mach} = \ beta ^ {1-p}}$
2. Od zaokrąglenia do najbliższego: ${\ Displaystyle \ epsilon _ {mach} = {\ Frac {1} {2}} \ beta ^ {1-p}}$

Dowód

Niech gdzie , i niech będzie zmiennoprzecinkową reprezentacją . Ponieważ stosuje się metodę round-by-chop, * Aby określić maksimum tej wielkości, należy znaleźć maksimum licznika i minimum mianownika. Ponieważ (system znormalizowany), minimalna wartość mianownika to . Licznik jest ograniczony powyżej przez . Tak więc . Dlatego dla rundy po kawałku. Dowód na zaokrąglenie do najbliższego jest podobny. ${\ Displaystyle x = d_ {0}. d_ {1} d_ {2} \ ldots d_ {p-1} d_ {p} \ ldots \ razy \ beta ^ {n} \ w \ mathbb {R}}$${\displaystyle n\w [L,U]}$${\displaystyle fl(x)}$${\displaystyle x}$${\ Displaystyle {\ zacząć {wyrównany} {\ Frac {| x-fl (x) |} {| x |}} i = {\ Frac {| d_ {0}.d_ {1} d_ {2} \ ldots d_{p-1}d_{p}d_{p+1}\ldots \times \beta ^{n}-d_{0}.d_{1}d_{2}\ldots d_{p-1}\times \beta ^{n}|}{|d_{0}.d_{1}d_{2}\ldots \times \beta ^{n}|}}\\&={\frac {|d_{p}. d_{p+1}\ldots \times \beta ^{np}|}{|d_{0}.d_{1}d_{2}\ldots \times \beta ^{n}|}}\\&= {\frac {|d_{p}.d_{p+1}d_{p+2}\ldots |}{|d_{0}.d_{1}d_{2}\ldots |}}\times \beta ^{-p}\end{wyrównany}}}$${\displaystyle d_{0}\neq 0}$${\ Displaystyle 1}$${\ Displaystyle (\ beta -1). (\ beta -1) {\ overline {(\ beta -1)}} = \ beta}$${\ Displaystyle {\ Frac {| x-fl (x) |} {| x |}} \ leq {\ Frac {\ beta} {1}} \ razy \ beta ^ {-p} = \ beta ^ {1 -P}}$${\ Displaystyle \ epsilon = \ beta ^ {1-p}}$

• Zauważ, że pierwsza definicja maszyny epsilon nie jest do końca równoważna z drugą definicją przy użyciu reguły round-to-neaest, ale jest równoważna dla round-by-chop.

Błąd zaokrąglenia spowodowany przez arytmetykę zmiennoprzecinkową

Nawet jeśli niektóre liczby mogą być dokładnie reprezentowane przez liczby zmiennoprzecinkowe i takie liczby są nazywane liczbami maszynowymi , wykonywanie arytmetyki zmiennoprzecinkowej może prowadzić do błędu zaokrąglenia w wyniku końcowym.

Dodatek

Dodawanie maszynowe polega na wyrównaniu miejsc dziesiętnych dwóch dodanych liczb, dodaniu ich, a następnie ponownym zapisaniu wyniku jako liczby zmiennoprzecinkowej. Samo dodawanie można wykonać z większą precyzją, ale wynik należy zaokrąglić z powrotem do określonej precyzji, co może prowadzić do błędu zaokrąglenia.

Na przykład dodanie do w podwójnej precyzji IEEE następująco, ${\ Displaystyle 1}$${\ Displaystyle 2 ^ {-53}}$

${\ Displaystyle {\ zacząć {wyrównany} 1,00 \ ldots 0 \ razy 2 ^ {0} + 1,00 \ ldots 0 \ razy 2 ^ {-53} i = 1. \ underbrace {00 \ ldots 0} _ {\ tekst { 52 bits}}\times 2^{0}+0.\underbrace {00\ldots 0} _{\text{52 bits}}1\times 2^{0}\\&=1.\underbrace {00\ ldots 0} _{\text{52 bity}}1\times 2^{0}\end{wyrównany}}}$

• Jest to zachowane, ponieważ w standardzie IEEE stosuje się zaokrąglanie do najbliższego. Dlatego jest równy podwójnej precyzji IEEE, a błąd zaokrąglenia wynosi .${\ Displaystyle 1. \ underbrace {00 \ ldots 0} _ {\ tekst {52 bity}} \ razy 2 ^ {0}}$${\ Displaystyle 1 + 2 ^ {-53}}$${\ Displaystyle 1}$${\ Displaystyle 2 ^ {-53}}$

Z tego przykładu widać, że błąd zaokrąglenia może zostać wprowadzony podczas dodawania dużej liczby i małej liczby, ponieważ przesunięcie punktów dziesiętnych w mantysach w celu dopasowania wykładników może spowodować utratę niektórych cyfr.

Mnożenie

Ogólnie rzecz biorąc, iloczyn -digit mantys zawiera do cyfr, więc wynik może nie pasować do mantysy. Tak więc błąd zaokrąglenia będzie miał wpływ na wynik. ${\ Displaystyle 2}$ ${\displaystyle p}$${\displaystyle 2p}$

• Rozważmy na przykład znormalizowany system liczb zmiennoprzecinkowych, w którym cyfry podstawy i mantysy to co najwyżej . Następnie i . Zauważ, że ale ponieważ tam co najwyżej cyfry mantysy. Błąd zaokrąglenia to .${\ Displaystyle \ beta = 10}$${\ Displaystyle 2}$${\ Displaystyle fl (77) = 7,7 \ razy 10}$${\ Displaystyle fl (88) = 8,8 \ razy 10}$${\ Displaystyle 77 \ razy 88 = 6776}$${\ Displaystyle fl (6776) = 6,7 \ razy 10 ^ {3}}$${\ Displaystyle 2}$${\ Displaystyle 6776-fl (6776) = 6776-6,7 \ razy 10 ^ {3} = 76}$

Podział

Ogólnie rzecz biorąc, iloraz -cyfr mantys może zawierać więcej niż -cyfr. Tak więc błąd zaokrąglenia będzie miał wpływ na wynik. ${\ Displaystyle 2}$ ${\displaystyle p}$${\displaystyle p}$

• Na przykład, w przypadku znormalizowanego zmiennoprzecinkową układ ilość wyżej nadal używany, to jednak . Więc ogon jest odcięty.${\ Displaystyle 1/3 = 0,333 \ ldots}$${\ Displaystyle fl (1/3) = fl (0,333 \ ldots) = 3,3 \ razy 10 ^ {-1}}$${\ Displaystyle 0,333 \ ldots -3,3 \ razy 10 ^ {-1} = 0,00333 \ ldots}$

Anulowanie subtraktywne

Odejmowanie dwóch prawie równych liczb nazywa się odejmowaniem .

• Gdy wiodące cyfry zostaną anulowane, wynik może być zbyt mały, aby można go było dokładnie przedstawić i będzie po prostu reprezentowany jako . ${\ Displaystyle 0}$
  • Na przykład let i druga definicja maszyny epsilon jest tutaj używana. Jakie jest rozwiązanie ? Wiadomo, że i są to liczby prawie równe i . Natomiast w systemie liczb zmiennoprzecinkowych . Chociaż jest wystarczająco duży, aby można go było przedstawić, oba przypadki zostały zaokrąglone dając .${\displaystyle |\epsilon |<\epsilon_{mach}}$${\displaystyle (1+\epsilon)-(1-\epsilon)}$
    ${\displaystyle 1+\epsilon}$${\ Displaystyle 1-\epsilon}$${\ Displaystyle (1+ \ epsilon ) - (1- \ epsilon ) = 1 + \ epsilon -1 + \ epsilon = 2 \ epsilon }$${\ Displaystyle fl((1+\epsilon)-(1-\epsilon))=fl(1+\epsilon)-fl(1-\epsilon)=1-1=0}$${\displaystyle 2\epsilon}$${\displaystyle \epsilon}$${\ Displaystyle 0}$
• Nawet przy nieco większym , wynik w typowych przypadkach jest nadal znacząco niewiarygodny. Nie ma wielkiej wiary w dokładność wartości, ponieważ największą niepewnością w każdej liczbie zmiennoprzecinkowej są cyfry po prawej stronie. ${\displaystyle \epsilon}$
  • Na przykład . Wynik jest wyraźnie widoczny, ale nie ma w nim zbytniej wiary.${\ Displaystyle 1,99999\razy 10^{2}-1,99998\razy 10^{2}=0.00001\razy 10^{2}=1\razy 10^{-5}\razy 10^{2}=1\razy 10^{-3}}$${\ Displaystyle 1 \ razy 10 ^ {-3}}$

Akumulacja błędu zaokrąglenia

Błędy mogą być powiększane lub kumulowane, gdy sekwencja obliczeń jest stosowana na początkowych danych wejściowych z błędem zaokrąglenia z powodu niedokładnej reprezentacji.

Niestabilne algorytmy

Algorytm lub proces numeryczny nazywa się stabilnym, jeśli małe zmiany na wejściu powodują tylko małe zmiany na wyjściu, i nazywa się go niestabilnym, jeśli powstają duże zmiany na wyjściu.

Sekwencja obliczeń zwykle występuje podczas uruchamiania jakiegoś algorytmu. Wielkość błędu w wyniku zależy od stabilności algorytmu . Błąd zaokrąglenia zostanie powiększony przez niestabilne algorytmy.

Na przykład dla z danym. Łatwo to pokazać . Załóżmy, że jest to nasza wartość początkowa i ma mały błąd reprezentacji , co oznacza, że ​​początkowym wejściem tego algorytmu jest zamiast . Następnie algorytm wykonuje następującą sekwencję obliczeń. ${\ Displaystyle y_ {n} = \ int _ {0} ^ {1} \ {\ Frac {x ^ {n}} {x + 5}} dx}$${\displaystyle n=1,2,\ldots,8}$${\displaystyle y_{0}}$${\ Displaystyle y_ {n} = {\ Frac {1} {n}}-5y_ {n-1}}$${\displaystyle y_{0}}$${\displaystyle \epsilon}$${\displaystyle y_{0}+\epsilon}$${\displaystyle y_{0}}$

${\ Displaystyle {\ zacząć {wyrównany} Y_ {1} i = 1-5 (y_ {0}+ \ epsilon) = 1-5 Y_ {0}-5 \ epsilon \ \ y_ {2} i = {\ Frac { 1}{2}}-5(1-5lat_{0}-5\epsilon )={\frac {1}{2}}-5+25lat_{0}+5^{2}\epsilon \\\vdots \\y_{n}&=\ldots +5^{n}\epsilon \end{aligned}}}$

Błąd zaokrąglenia jest wzmacniany w kolejnych obliczeniach, więc ten algorytm jest niestabilny.

źle uwarunkowane problemy

Nawet jeśli używany jest stabilny algorytm, rozwiązanie problemu może nadal być niedokładne z powodu nagromadzenia błędu zaokrąglenia, gdy sam problem jest źle uwarunkowany .

Liczba stan problemem jest to stosunek względnej zmiany w roztworze względnej zmianie wejścia. Problem jest dobrze uwarunkowany, jeśli niewielkie względne zmiany danych wejściowych powodują niewielkie względne zmiany w rozwiązaniu. W przeciwnym razie problem jest źle uwarunkowany . Innymi słowy, problem jest źle uwarunkowany, jeśli jego numer warunku jest „znacznie większy” niż . ${\ Displaystyle 1}$

Numer warunku jest wprowadzany jako miara błędów zaokrągleń, które mogą wystąpić podczas rozwiązywania źle uwarunkowanych problemów.

Przykład ze świata rzeczywistego: awaria pocisku Patriot z powodu powiększenia błędu zaokrąglenia

25 lutego 1991 r., podczas wojny w Zatoce Perskiej, amerykańska bateria rakiet Patriot w Dharanie w Arabii Saudyjskiej nie zdołała przechwycić nadlatującego irackiego pocisku Scud. Scud uderzył w koszary armii amerykańskiej i zabił 28 żołnierzy. Raport ówczesnego General Accounting Office zatytułowany „Patriot Missile Defense: Software Problem Led to System Failure w Dhahran w Arabii Saudyjskiej” podał przyczynę awarii: niedokładne obliczenie czasu od uruchomienia systemu z powodu błędów arytmetycznych komputera. W szczególności czas w dziesiątych częściach sekundy, mierzony przez wewnętrzny zegar systemu, został pomnożony przez 10, aby otrzymać czas w sekundach. To obliczenie zostało wykonane przy użyciu 24-bitowego rejestru stałoprzecinkowego. W szczególności wartość 1/10, która ma niekończące się rozwinięcie binarne, została pocięta w 24 bity za punktem podstawy. Mały błąd cięcia, pomnożony przez dużą liczbę podającą czas w dziesiątych częściach sekundy, prowadził do znacznego błędu. Rzeczywiście, bateria Patriota działała około 100 godzin, a proste obliczenia pokazują, że wynikowy błąd czasu spowodowany powiększonym błędem cięcia wyniósł około 0,34 sekundy. (Liczba 1/10 równa się . Innymi słowy, rozwinięcie binarne 1/10 to . Teraz 24-bitowy rejestr w Patriocie zapisany zamiast wprowadza błąd binarny lub około dziesiętny. Mnożenie przez liczbę dziesiątych części sekundy w godzinach daje ). Scud podróżuje około${\ Displaystyle 1/2 ^ {4} + 1/2 ^ {5} + 1/2 ^ {8} + 1/2 ^ {9} + 1/2 ^ {12} + 1/2 ^ {13} +\ldots }$${\ Displaystyle 0,0001100110011001100110011001100\ldots}$${\ Displaystyle 0,00011001100110011001100}$${\ Displaystyle 0,000000000000000000000011001100\ldots}$${\ Displaystyle 0.000000095}$${\displaystyle 100}$${\displaystyle 0.000000095\razy 100\razy 60\razy 60\razy 10=0,34}$1676 metrów na sekundę, a więc pokonuje w tym czasie ponad pół kilometra. To było na tyle daleko, że nadlatujący Scud znajdował się poza „bramą zasięgu”, którą śledził Patriot. Jak na ironię, fakt, że złe obliczanie czasu zostało ulepszone w niektórych częściach kodu, ale nie we wszystkich, przyczynił się do problemu, ponieważ oznaczał, że nieścisłości nie zostały anulowane.

Zobacz też

• Precyzja (arytmetyka)
• Obcięcie
• Zaokrąglanie
• Utrata znaczenia
• zmiennoprzecinkowy
• Algorytm sumowania Kahana
• Maszyna epsilon
• Wielomian Wilkinsona

Bibliografia

Dalsza lektura

• Matta Parkera (2021). Humble Pi: Kiedy matematyka się nie udaje w prawdziwym świecie . Książki nadrzeczne. Numer ISBN 978-0593084694.

Linki zewnętrzne

• Błąd zaokrąglenia w MathWorld.
• Goldberg, David (marzec 1991). „Co każdy informatyk powinien wiedzieć o arytmetyce zmiennoprzecinkowej” (PDF) . Ankiety ACM Computing . 23 (1): 5-48. doi : 10.1145/103162.103163 . Źródło 2016-01-20 .( [1] , [2] )
• 20 słynnych katastrof oprogramowania