Maszyna epsilon - Machine epsilon

Maszyna epsilon podaje górną granicę błędu względnego z powodu zaokrąglania w arytmetyce zmiennoprzecinkowej . Wartość ta charakteryzuje arytmetykę komputerową w dziedzinie analizy numerycznej , a co za tym idzie w dziedzinie informatyki . Wielkość ta jest również nazywana macheps lub jednostkowym zaokrągleniem i ma odpowiednio symbole greckiego epsilon lub pogrubionego rzymskiego u . ${\displaystyle \varepsilon}$

Wartości dla standardowej sprzętowej arytmetyki zmiennoprzecinkowej

Następujące wartości maszyny epsilon dotyczą standardowych formatów zmiennoprzecinkowych:

IEEE 754 - 2008	Nazwa zwyczajowa	typ danych C++	Baza ${\displaystyle b}$	Precyzja ${\displaystyle p}$	Maszyna epsilon ${\ Displaystyle b ^ {- (p-1)}/2}$	Maszyna epsilon ${\ Displaystyle b ^ {- (p-1)}}$
binarny16	pół precyzji	Nie dotyczy	2	11 (jeden bit jest niejawny)	2 −11 ≈ 4,88e-04	2 −10 ≈ 9,77e-04
binarny32	Pojedyncza precyzja	pływak	2	24 (jeden bit jest niejawny)	2 −24 5.96e-08	2 −23 ≈ 1.19e-07
binarny64	podwójna precyzja	podwójnie	2	53 (jeden bit jest niejawny)	2 −53 ≈ 1,11e-16	2 −52 ≈ 2,22e-16
	zwiększona precyzja , długa podwójna	_float80	2	64	2 −64 ≈ 5,42e-20	2 −63 ≈ 1,08e-19
binarny128	poczwórna (krotna) precyzja	_float128	2	113 (jeden bit jest niejawny)	2 -113 ≈ 9.63e-35	2 −112 ≈ 1,93e-34
dziesiętny32	dziesiętny o pojedynczej precyzji	_Dziesiętny32	10	7	5 × 10-7	10 -6
dziesiętny64	dziesiętna o podwójnej precyzji	_Dziesiętny64	10	16	5 × 10-16	10 -15
dziesiętny128	poczwórna(rupa) precyzja dziesiętna	_Dziesiętny128	10	34	5 × 10 −34	10 −33

Formalna definicja

Zaokrąglanie to procedura wyboru reprezentacji liczby rzeczywistej w systemie liczb zmiennoprzecinkowych . W przypadku systemu liczbowego i procedury zaokrąglania epsilon maszyny jest maksymalnym błędem względnym wybranej procedury zaokrąglania.

Aby określić wartość z tej definicji, potrzebne jest pewne tło. Pływający system liczbowy punkt charakteryzuje się radix które nazywa się także podstawa, oraz przez precyzją , czyli liczba Radix cyfr mantysy (w tym wiodących niejawny bit). Wszystkie liczby z tym samym wykładnikiem , , mają odstępy , . Odstępy zmieniają się przy liczbach, które są doskonałymi potęgami ; odstęp po stronie większej wielkości jest razy większy niż odstęp po stronie mniejszej wielkości. ${\displaystyle b}$ ${\displaystyle p}$${\displaystyle b}$${\displaystyle e}$${\ Displaystyle b ^ {e-(p-1)}}$${\displaystyle b}$${\displaystyle b}$

Ponieważ epsilon maszynowy jest związany z błędem względnym, wystarczy wziąć pod uwagę liczby z wykładnikiem . Wystarczy również wziąć pod uwagę liczby dodatnie. W przypadku zwykłego zaokrąglania od zaokrąglenia do najbliższego bezwzględny błąd zaokrąglania wynosi co najwyżej połowę odstępu lub . Ta wartość jest największym możliwym licznikiem błędu względnego. Mianownikiem we względnym błędem jest liczba jest zaokrąglona, która powinna być jak najmniejsza, aby błąd względny duża. Najgorszy błąd względny występuje zatem, gdy zaokrąglanie jest stosowane do liczb w postaci, gdzie jest pomiędzy i . Wszystkie te liczby zaokrąglają się do ze względnym błędem . Maksimum występuje, gdy znajduje się na górnym końcu swojego zakresu. W mianowniku jest nieistotny w porównaniu z licznikiem, więc jest pomijany dla celów praktycznych i po prostu traktowany jako epsilon maszyny. Jak pokazano tutaj, względny błąd jest najgorszy dla liczb, które zaokrąglają się do , więc maszyna epsilon jest również nazywana zaokrągleniem jednostek, co oznacza z grubsza „maksymalny błąd, który może wystąpić podczas zaokrąglania do wartości jednostki”. ${\displaystyle e=0}$${\ Displaystyle b ^ {- (p-1)}/2}$${\displaystyle 1+a}$${\displaystyle a}$${\ Displaystyle 0}$${\ Displaystyle b ^ {- (p-1)}/2}$${\ Displaystyle 1}$${\ Displaystyle a/(1+a)}$${\displaystyle a}$${\displaystyle 1+a}$${\ Displaystyle b ^ {- (p-1)}/2}$${\ Displaystyle 1}$

Zatem maksymalny odstęp między znormalizowaną liczbą zmiennoprzecinkową a sąsiednią znormalizowaną liczbą wynosi . ${\displaystyle x}$${\displaystyle 2\varepsilon |x|}$

Model arytmetyczny

Analiza numeryczna wykorzystuje maszynę epsilon do badania skutków błędu zaokrąglenia. Rzeczywiste błędy arytmetyki maszynowej są zbyt skomplikowane, aby można je było badać bezpośrednio, dlatego zamiast tego zastosowano następujący prosty model. Standard arytmetyczny IEEE mówi, że wszystkie operacje zmiennoprzecinkowe są wykonywane tak, jakby można było wykonać operację o nieskończonej precyzji, a następnie wynik jest zaokrąglany do liczby zmiennoprzecinkowej. Załóżmy, że (1) , to liczby zmiennoprzecinkowe, (2) to operacja arytmetyczna na liczbach zmiennoprzecinkowych, taka jak dodawanie lub mnożenie, oraz (3) to operacja o nieskończonej precyzji. Zgodnie z normą komputer oblicza: ${\displaystyle x}$${\displaystyle y}$${\ Displaystyle \ pocisk}$${\displaystyle \circ}$

${\ Displaystyle x \ pocisk y = {\ mbox {okrągły}} (x \ okrąg y)}$

W rozumieniu maszyny epsilon względny błąd zaokrąglenia wynosi co najwyżej epsilon maszyny, więc:

${\ Displaystyle x \ bullet y = (x \ circ y) (1 + z)}$

gdzie w absolutnej wielkości jest co najwyżej lub u . Można zapoznać się z książkami Demmel i Higham w odnośnikach, aby zobaczyć, w jaki sposób ten model jest używany do analizy błędów, powiedzmy, eliminacji Gaussa. ${\displaystyle z}$${\displaystyle \varepsilon}$

Definicje wariantów

Standard IEEE nie definiuje terminów machine epsilon i unit roundoff , dlatego stosowane są różne definicje tych terminów, co może powodować pewne zamieszanie.

Definicja podana tutaj dla epsilon maszynowego jest taka, jaka została użyta przez prof. Jamesa Demmela w skryptach wykładów, pakiecie algebry liniowej LAPACK , pracach z zakresu numeracji i niektórych naukowych programach obliczeniowych. Większość analityków numerycznych używa słów maszyna epsilon i zaokrąglenie jednostek zamiennie z tym znaczeniem.

Następująca inna definicja jest znacznie bardziej rozpowszechniona poza środowiskiem akademickim: epsilon maszynowy jest definiowany jako różnica między 1 a następną większą liczbą zmiennoprzecinkową. Zgodnie z tą definicją, równa się wartości jednostki na ostatnim miejscu względem 1, tj. , a zaokrąglenie jednostki wynosi u , przy założeniu trybu zaokrąglania do najbliższego. Powszechność tej definicji jest zakorzeniona w jej użyciu w standardzie ISO C dla stałych odnoszących się do typów zmiennoprzecinkowych i odpowiadających im stałych w innych językach programowania. Jest również szeroko stosowany w oprogramowaniu do obliczeń naukowych oraz w literaturze numerycznej i komputerowej. ${\displaystyle \varepsilon}$${\ Displaystyle b ^ {- (p-1)}}$${\ Displaystyle \, = \ varepsilon /2}$

Jak określić epsilon maszyny?

Tam, gdzie standardowe biblioteki nie dostarczają wstępnie obliczonych wartości (tak jak < float.h > robi z FLT_EPSILON, DBL_EPSILONa LDBL_EPSILONdla C i < limity > robi z w C++), najlepszym sposobem określenia epsilon maszyny jest odwołanie się do powyższej tabeli i użycie odpowiednia formuła mocy. Komputerowa maszyna epsilon jest często podawana jako ćwiczenie podręcznikowe. Poniższe przykłady obliczają maszynę epsilon w sensie odstępów liczb zmiennoprzecinkowych na poziomie 1, a nie w sensie zaokrąglenia jednostki. std::numeric_limits<T>::epsilon()

Należy zauważyć, że wyniki zależą od konkretnego używanego formatu zmiennoprzecinkowego, takiego jak float, double, long doublelub podobny, który jest obsługiwany przez język programowania, kompilator i bibliotekę środowiska uruchomieniowego dla rzeczywistej platformy.

Niektóre formaty obsługiwane przez procesor mogą nie być obsługiwane przez wybrany kompilator i system operacyjny. Inne formaty mogą być emulowane przez bibliotekę środowiska uruchomieniowego, w tym arytmetykę o dowolnej precyzji dostępną w niektórych językach i bibliotekach.

W ścisłym znaczeniu termin maszyna epsilon oznacza dokładność obsługiwaną bezpośrednio przez procesor (lub koprocesor), a nie pewną dokładność obsługiwaną przez konkretny kompilator dla konkretnego systemu operacyjnego, chyba że wiadomo, że używa najlepszego formatu. ${\displaystyle 1+\varepsilon}$${\displaystyle 1+\varepsilon}$

Formaty zmiennoprzecinkowe IEEE 754 mają tę właściwość, że po reinterpretowaniu jako liczba całkowita uzupełniająca do dwóch o tej samej szerokości, monotonicznie zwiększają się względem wartości dodatnich i monotonicznie zmniejszają się względem wartości ujemnych (patrz binarna reprezentacja 32-bitowych elementów zmiennoprzecinkowych ). Mają również właściwość that , i (gdzie jest wspomniana reinterpretacja liczby całkowitej ). W językach, które pozwalają na określanie typów i zawsze używają IEEE 754-1985, możemy to wykorzystać do obliczenia epsilon maszyny w stałym czasie. Na przykład w C: ${\displaystyle 0<|f(x)|<\infty}$${\ Displaystyle | f (x + 1) - f (x) | \ geq | f (x) - f (x-1) |}$${\displaystyle f(x)}$${\displaystyle x}$

typedef union {
  long long i64;
  double d64;
} dbl_64;
double machine_eps (double value)
{
    dbl_64 s;
    s.d64 = value;
    s.i64++;
    return s.d64 - value;
}

Da to wynik tego samego znaku co wartość. Jeśli zawsze pożądany jest wynik dodatni, instrukcję return z machine_eps można zastąpić:

    return (s.i64 < 0 ? value - s.d64 : s.d64 - value);

64-bitowe podwójna daje 2.220446e-16, który jest 2 ^-52 , jak oczekiwano.

Przybliżenie

Poniższy prosty algorytm może być użyty do przybliżenia epsilon maszyny ze współczynnikiem dwa (jeden rząd wielkości ) jego prawdziwej wartości za pomocą wyszukiwania liniowego .

epsilon = 1.0;

while (1.0 + 0.5 * epsilon) ≠ 1.0:
    epsilon = 0.5 * epsilon

Zobacz też

• Zmiennoprzecinkowa , ogólne omówienie zagadnień dokładności w arytmetyce zmiennoprzecinkowej
• Jednostka na ostatnim miejscu (ULP)

Uwagi i referencje

Zewnętrzne linki

• MACHAR , procedura (w C i Fortran) do „dynamicznego obliczania stałych maszynowych” (algorytm ACM 722)
• Diagnozowanie dokładności obliczeń zmiennoprzecinkowych , Implementacja MACHAR w Component Pascal i Oberon w oparciu o wersję MACHAR Fortran 77 opublikowaną w Numerical Recipes (Press et al., 1992).