Epsilon maszynowy

Maszyna epsilon lub precyzja maszyny to górna granica względnego błędu przybliżenia z powodu zaokrąglania w arytmetyce zmiennoprzecinkowej . Wartość ta charakteryzuje arytmetykę komputerową w dziedzinie analizy numerycznej , a co za tym idzie w dziedzinie informatyki . Ilość jest również nazywana machepami i ma greckie symbole epsilon ${\ displaystyle \ varepsilon}$ .

Dominują dwie definicje. W analizie numerycznej epsilon maszynowy jest zależny od rodzaju zastosowanego zaokrąglenia i jest również nazywany zaokrągleniem jednostkowym , które ma symbol pogrubionego rzymskiego u . Jednak zgodnie z mniej formalną, ale szerzej stosowaną definicją, epsilon maszynowy jest niezależny od metody zaokrąglania i może być równoważny u lub 2 u .

Wartości dla standardowej arytmetyki sprzętowej

W poniższej tabeli wymieniono wartości epsilon maszyny dla standardowych formatów zmiennoprzecinkowych. Każdy format używa zaokrąglenia do najbliższego .

IEEE 754-2008	Nazwa zwyczajowa	Typ danych C++	podstawa ${\ displaystyle b}$	precyzja ${\ displaystyle p}$	Maszyna epsilon ${\ Displaystyle b ^ {- (p-1)}/2}$	Maszyna epsilon ${\ Displaystyle b ^ {- (p-1)}}$
binarny16	pół precyzja	Nie dotyczy	2	11 (jeden bit jest niejawny)	2-11 ≈ 4,88e- ⁰⁴	2-10 ≈ 9,77e- ⁰⁴
binarny32	Pojedyncza precyzja	platforma	2	24 (jeden bit jest niejawny)	2-24 ≈ 5,96e- ⁰⁸	2-23 ≈ 1.19e- ⁰⁷
binarny64	podwójna precyzja	podwójnie	2	53 (jeden bit jest niejawny)	2-53 ≈ 1,11e- ¹⁶	2 ⁻⁵² ≈ 2,22e-16
	rozszerzona precyzja , długie podwójne	_float80	2	64	2-64 ≈ 5,42e- ²⁰	2-63 ≈ 1,08e- ¹⁹
binarny128	poczwórna (podwójna) precyzja	_float128	2	113 (jeden bit jest niejawny)	2-113 ≈ 9,63e- ³⁵	2-112 ≈ 1,93e- ³⁴
dziesiętny32	ułamek dziesiętny o pojedynczej precyzji	_Dziesiętny32	10	7	5 × ^10-7	10-6 ^_
dziesiętny64	dziesiętna podwójnej precyzji	_Dziesiętny64	10	16	5 × ^10-16	10-15 ^_
dziesiętny128	dziesiętna precyzja poczwórna (szeregowa).	_Dziesiętny128	10	34	5 × ^10-34	10-33 ^_

Definicja formalna

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

Aby określić wartość na podstawie tej definicji, potrzebne jest pewne tło. System liczb zmiennoprzecinkowych charakteryzuje się podstawą , $displaystyle$ jest również nazywana podstawą , oraz precyzją, tj $.$ cyfr podstawy $b}$ cyfr mantysy (w tym dowolny wiodący niejawny bit). Wszystkie liczby z tym $wykładnikiem$ mają odstęp ${\ Displaystyle b ^ {e- (p-1)}}$ . Odstępy zmieniają się przy liczbach, które są doskonałymi potęgami ${\ displaystyle b}$ ; odstęp po stronie o większej wielkości jest $odstęp$ po stronie o mniejszej wielkości.

Ponieważ epsilon maszyny jest granicą błędu względnego, wystarczy wziąć pod uwagę liczby z wykładnikiem mi $\ displaystyle e = 0}$ . Wystarczy wziąć pod uwagę liczby dodatnie. W przypadku zwykłego zaokrąglenia od zaokrąglenia do najbliższego bezwzględny błąd zaokrąglenia wynosi co najwyżej połowę odstępu lub ${\ Displaystyle b ^ {- (p-1)}/2}$ . Ta wartość jest największym możliwym licznikiem błędu względnego. Mianownik _ w błędzie względnym zaokrąglana jest liczba, która powinna być jak najmniejsza, aby błąd względny był duży. Najgorszy błąd względny występuje zatem, gdy zaokrąglanie jest stosowane do liczb w postaci ${\ displaystyle 1 + a}$ gdzie ${\ displaystyle a}$ jest między ${\ displaystyle 0}$ i $b ^ {- (p-1)}/2$ . Wszystkie te liczby są zaokrąglane do ${\ displaystyle 1}$ z błędem względnym ${\ Displaystyle a / (1 + a)}$ . Maksimum występuje, gdy $znajduje$ na górnym końcu swojego zakresu. 1 ${\ Displaystyle 1 + a} w mianowniku jest znikomy w porównaniu z$ , więc jest pomijany ze względów praktycznych i po prostu ${\ Displaystyle b ^ {- (p- 1)}/2}$ jest traktowany jako epsilon maszynowy. Jak pokazano tutaj, błąd względny jest najgorszy w przypadku liczb, które zaokrąglają 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”.

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

Model arytmetyczny

Analiza numeryczna wykorzystuje maszynowy 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 stosuje się następujący prosty model. Standard arytmetyczny IEEE mówi, że wszystkie operacje zmiennoprzecinkowe są wykonywane tak, jakby możliwe było wykonanie operacji z nieskończoną precyzją, a następnie wynik jest zaokrąglany do liczby zmiennoprzecinkowej. Załóżmy, że (1) ${\ displaystyle x}$ y $\ displaystyle y}$ są liczbami zmiennoprzecinkowymi, (2) ${\ displaystyle \ punktor}$ jest operacją arytmetyczną na liczbach zmiennoprzecinkowych, taką jak dodawanie lub mnożenie, a (3) $operacją$ nieskończonej precyzji. Zgodnie z normą komputer oblicza:

{\ Displaystyle x \ punktor y = {\ mbox {okrągły}} (x \ circ y)}

W znaczeniu maszyny epsilon względny błąd zaokrąglenia ma co najwyżej wielkość maszyny epsilon, więc:

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

gdzie $bezwzględnej$ $wielkości$ wynosi co lub u . Można zapoznać się z książkami Demmela i Highama w odnośnikach, aby zobaczyć, jak ten model jest używany do analizy błędów, powiedzmy, eliminacji Gaussa.

Definicje wariantów

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

Formalna definicja maszynowego epsilon to ta, której użył prof. James Demmel w scenariuszach wykładów, pakiecie algebry liniowej LAPACK , pracach badawczych z zakresu numeryki i niektórych programach do obliczeń naukowych. Większość analityków numerycznych używa słów maszyna epsilon i zaokrąglenie jednostek zamiennie w tym znaczeniu.

Ta alternatywna definicja jest znacznie bardziej rozpowszechniona poza środowiskiem akademickim: maszyna epsilon to różnica między 1 a kolejną większą liczbą zmiennoprzecinkową .

Zgodnie z tą definicją, równa się wartości jednostki na ostatnim miejscu względem 1, tj. $b$ ${- (p-1)}}$ (gdzie ${\ Displaystyle b}$ jest podstawą systemu zmiennoprzecinkowego i precyzją, a zaokrąglenie jednostek to $,$ = $\ Displaystyle \, = \ varepsilon / 2}$ przy założeniu zaokrąglenia do -najbliższy tryb i u ${\ Displaystyle \, = \ varepsilon}$ , zakładając , że krok po kroku .

Rozpowszechnienie tej definicji jest zakorzenione w jej zastosowaniu w normie ISO C dla stałych związanych z typami zmiennoprzecinkowymi i odpowiadających im stałych w innych językach programowania. Jest również szeroko stosowany w oprogramowaniu do obliczeń naukowych oraz w literaturze liczbowej i komputerowej.

Jak określić epsilon maszynowy

Tam, gdzie biblioteki standardowe nie udostępniają wstępnie obliczonych wartości (tak jak robi to < float.h > z FLT_EPSILON , DBL_EPSILON i LDBL_EPSILON dla C, a < limits > z std::numeric_limits< T >::epsilon() w C++), najlepszym sposobem określenie maszyny epsilon polega na odwołaniu się do powyższej tabeli i zastosowaniu odpowiedniego wzoru na potęgę. Maszyna komputerowa epsilon jest często podawana jako ćwiczenie z podręcznika. Poniższe przykłady obliczają epsilon maszynowy w sensie odstępu między liczbami zmiennoprzecinkowymi przy 1, a nie w sensie zaokrąglenia jednostek.

Należy zauważyć, że wyniki zależą od konkretnego używanego formatu zmiennoprzecinkowego, takiego jak float , double , long double lub podobnego obsługiwanego 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. Biblioteka środowiska uruchomieniowego może emulować inne formaty, w tym arytmetykę o dowolnej precyzji dostępną w niektórych językach i bibliotekach.

W ścisłym sensie termin maszyna epsilon oznacza $dokładność$ procesor (lub koprocesor), a nie jakąś obsługiwaną przez określony $\ Displaystyle 1+ \ varepsilon}$ kompilator dla określonego systemu operacyjnego, chyba że wiadomo, że używa najlepszego formatu.

Formaty zmiennoprzecinkowe IEEE 754 mają tę właściwość, że po ponownej interpretacji jako liczba całkowita z uzupełnieniem do dwóch o tej samej szerokości monotonicznie rosną w stosunku do wartości dodatnich i monotonicznie maleją w stosunku do wartości ujemnych (patrz binarna reprezentacja 32-bitowych liczb zmiennoprzecinkowych ). Mają również właściwość, że ${\ Displaystyle 0 <| f (x) | <\ infty}$ i ${\ Displaystyle | f (x + 1) -f (x) | \ geq | f (x) -f (x-1) |} (gdzie$ fa $\ Displaystyle f (x)}$ jest wspomnianą liczbą całkowitą reinterpretacja ${\ displaystyle x}$ ). W językach, które pozwalają na wykreślanie czcionek i zawsze używają IEEE 754-1985, możemy to wykorzystać do obliczenia maszyny epsilon w stałym czasie. Na przykład w C:

  
    
   
 

   

     
      
    
       
 typedef  związek  {  długi  długi  i64  ;  podwójne  d64  ;  }  dbl_64  ;  double  machine_eps  (  podwójna  wartość  )  {  dbl_64  s  ;  s  .  d64  =  wartość  ;  s  .  i64  ++  ;  zwrot  s  .  d64  -  wartość  ;  }

Przykład w Pythonie:

 
      
       
          
            
      def  machineEpsilon  (  func  =  float  ):  machine_epsilon  =  func  (  1  )  while  func  (  1  )  +  machine_epsilon  !=  func  (  1  ):  machine_epsilon_last  =  machine_epsilon  machine_epsilon  =  func  (  machine_epsilon  )  /  func  (  2  )  return  machine_epsilon_last

Da to wynik tego samego znaku co wartość. Jeśli zawsze pożądany jest pozytywny wynik, instrukcja return maszyny_eps może zostać zastąpiona przez:

       0       return  (  s  .  i64  <  ?  wartość  -  s.d64  :  s.d64  -  wartość  )  ;  _  _  _

64-bitowe dublety dają 2,220446e-16, czyli 2-52 ^zgodnie z oczekiwaniami.

Przybliżenie

Poniższy prosty algorytm może być użyty do przybliżenia ^{[ wymagane wyjaśnienie ]} maszyny epsilon z dokładnością do współczynnika dwóch (jeden rząd wielkości ) jej prawdziwej wartości, przy użyciu wyszukiwania liniowego .

epsilon = 1,0; natomiast (1,0 + 0,5 * epsilon) ≠ 1,0: epsilon = 0,5 * epsilon

Maszyna epsilon, ${\ textstyle \ varepsilon _ {\ text {mach}}}$ może być również po prostu obliczona jako dwa do ujemnej potęgi liczby bitów użytych do mantysy.

{\ Displaystyle \ varepsilon _ {\ tekst {mach}} \ =\ 2 ^ {- {\ tekst {bity użyte do wielkości mantysy}}}}

Związek z bezwzględnym błędem względnym

Jeśli ${\ textstyle y}$ jest maszynową reprezentacją liczby ${\ textstyle x},$ to bezwzględny błąd względny w reprezentacji wynosi ${\textstyle \left|{\dfrac {xy}{x}}\right|\leq \varepsilon _{\text{mach}}.}$

Dowód

Poniższy dowód jest ograniczony do liczb dodatnich i reprezentacji maszynowych przy użyciu round-by-chop .

Jeśli ${$ \ textstyle x} jest liczbą dodatnią, którą chcemy przedstawić, będzie ona między numerem maszyny poniżej $}$ \ $a$ numerem maszyny ${\ textstyle x_ {u}}$ powyżej ${\ textstyle x}$ .

Jeśli ${\ textstyle x_ {b} = \ lewo (1.b_ {1} b_ {2} \ ldots b_ {m} \ prawej) _ {2}\times 2^{k}}$ , gdzie ${\textstyle m}$ jest liczbą bitów użytych do określenia wielkości mantysy , wtedy:

{\ Displaystyle {\ rozpocząć {wyrównane} x_ {u} & = \ lewo [(1.b_ {1} b_ {2} \ ldots b_ {m}) _ {2} + (0,00 \ ldots 1) _ {2 }\right]\times 2^{k}\\&=\left[(1.b_{1}b_{2}\ldots b_{m})_{2}+2^{-m}\right] \times 2^{k}\\&=(1.b_{1}b_{2}\ldots b_{m})_{2}\times 2^{k}+2^{-m}\times 2 ^{k}\\&=(1.b_{1}b_{2}\ldots b_{m})_{2}\razy 2^{k}+2^{-m+k}.\koniec{ wyrównany}}}

Ponieważ reprezentacja ${\ textstyle x}$ będzie albo ${\ textstyle x_ {b}}$ lub ${\ textstyle x_ {u}}$ ,

{\ Displaystyle {\ rozpocząć {wyrównane} \ lewo | xy \ prawo | & \ równoważnik \ lewo | x_ {b} -x_ {u} \ prawo | \\ & = 2 ^ {- m + k}\end{wyrównane}}}

{\ Displaystyle {\ rozpocząć {wyrównane} \ lewo | {\ Frac {xy} {x}} \ prawo | & \ równoważnik {\ Frac {2 ^ {-m + k}}} {x}} \\& \ równoważnik {\frac {2^{-m+k}}{x_{b}}}\\&={\frac {2^{-m+k}}{(1\cdot b_{1}b_{2} \ldots b_{m})_{2}2^{k}}}\\&={\frac {2^{-m}}{(1\cdot b_{1}b_{2}\ldots b_{ m})_{2}}}\\&\leq 2^{-m}=\varepsilon _{\text{mach}}.\end{aligned}}}

Chociaż ten dowód jest ograniczony do liczb dodatnich i okrągłych, ta sama metoda może być użyta do udowodnienia nierówności w odniesieniu do liczb ujemnych i zaokrąglonych do najbliższych reprezentacji maszynowych.

Zobacz też

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

Uwagi i odniesienia

Anderson, E.; Podręcznik użytkownika LAPACK, Towarzystwo Matematyki Przemysłowej i Stosowanej (SIAM), Filadelfia, Pensylwania, wydanie trzecie, 1999.
Cody, William J.; MACHAR: Soubroutine do dynamicznego określania parametrów maszyny, ACM Transactions on Mathematical Software, tom. 14(4), 1988, 303-311.
Besset, Didier H.; Zorientowana obiektowo implementacja metod numerycznych, Morgan & Kaufmann, San Francisco, CA, 2000.
Demmel, James W. , Applied Numerical Linear Algebra, Towarzystwo Matematyki Przemysłowej i Stosowanej (SIAM), Filadelfia, PA, 1997.
Higham, Mikołaj J.; Dokładność i stabilność algorytmów numerycznych, Towarzystwo Matematyki Przemysłowej i Stosowanej (SIAM), Filadelfia, Pensylwania, wydanie drugie, 2002.
Prasa, William H.; Teukolsky, Saul A.; Vetterling, William T.; i Flannery, Brian P.; Przepisy liczbowe w języku Fortran 77 , wyd. 2, rozdz. 20.2, s. 881–886
Forsythe, George E.; Malcolm, Michael A.; Moler, Cleve B.; „Metody komputerowe do obliczeń matematycznych”, Prentice-Hall, ISBN 0-13-165332-6 , 1977

Linki zewnętrzne

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