Mašinski Epsilon

Mašinski Epsilon daje gornju granicu relativne greške zbog zaokruživanja aritmetike plutajućih tačaka.Ova vrednost karakteriše računarsku aritmetiku u polju brojčane analize,a produžava se u predmetu računarske nauke.Količina se takođe naziva i "macheps" ili jedinica zaokruživanja,a označava se Grčkim simbolom Epsilon ε ili Romanskim slovom u.

Vrednosti za standardnu hardversku aritmetiku sa plutajućim tačkama

Date vrednosti mašinskog epsilona važe za standarde formata plutajućih tačaka:

IEEE 754 - 2008	Uobičajno ime	C++ tip podatka	Baza $b$	Preciznost $p$	Mašinski epsilon $b^{-(p-1)}/2$	Mašinski epsilon $b^{-(p-1)}$
binary16	polu precizan	short	2	11 (jedan bit je implicitan)	2−11 ≈ 4.88e-04	2−10 ≈ 9.77e-04
binary32	precizan	float	2	24 (jedan bit je implicitan)	2−24 ≈ 5.96e-08	2−23 ≈ 1.19e-07
binary64	duplo precizan	double	2	53 (jedan bit je implicitan)	2−53 ≈ 1.11e-16	2−52 ≈ 2.22e-16
	produženo precizan	_float80	2	64	2−64 ≈ 5.42e-20	2−63 ≈ 1.08e-19
binary128	četvorostruko precizan	_float128	2	113 (jedan bit je implicitan)	2−113 ≈ 9.63e-35	2−112 ≈ 1.93e-34
decimal32	precizna decimala	_Decimal32	10	7	5 × 10−7	10−6
decimal64	duplo precizna decimala	_Decimal64	10	16	5 × 10−16	10−15
decimal128	četvorostruko precizna decimala	_Decimal128	10	34	5 × 10−34	10−33

Formalna definicija

Zaokruživanje je postupak odabira predstavljajućeg realnog broja u sistemu sa plutajućim tačkama.Za brojni sistem i proceduru zaokruživanja , mašina epsilon predstavlja maksimalnu relativnu grešku od izabrane procedure zaokruživanja.

Određeno prethodno izračunavanje je potrebno da bi se odredila vrednost iz ove definicije.Sistem plutajućih brojeva je karakterizovan radiksom koji se drugačije naziva i baza ,$b$ ,i preciznošću $p$, tj. broj radiks $b$ cifara significanda (uključujući bilo koji vodeći implicitni broj).Svi brojevi sa istim stepenom, $e$,imaju razmak ${\displaystyle b^{e-(p-1)}}$.Razmak se menja na brojevima koji su savršenog stepena od $b$; razmak sa strane veće veličine je za $b$ puta veći od razmaka sa strane manje veličine.

Pošto je mašinski epsilon vezan za relativnu grešku , dovoljno je uzeti u obzir brojeve sa eksponentom ${\displaystyle e=0}$.Takođe je dovoljno razmotriti i pozitivne brojeve.Za uobičajenu vrstu zaokruživanja na najbliži broj , apsolutna greška zaokruživanja je veća polovina razmaka ili ${\displaystyle b^{-(p-1)}/2}$.Ova vrednost je najveći mogući brojilac relativne greške.Imenilac u relativnoj grešci je broj koji se zaokružuje , koji bi trebao da je što moguće manji da bi relativna greška bila veća.Stoga , najgora relativna greška se dešava kada se zaokruživanje primenjuje na brojeve obrasca ${\displaystyle 1+a}$ gde je ${\displaystyle a}$ između ${\displaystyle 0}$ i ${\displaystyle b^{-(p-1)}/2}$.Svi ovi brojevi se zaokrugljuju na ${\displaystyle 1}$ sa relativnom greškom ${\displaystyle a/(1+a)}$.Maksimum se javlja kada je ${\displaystyle a}$ na gornjem kraju svog opsega.${\displaystyle 1+a}$ je u imeniocu zanemarljiv sa brojiocem , tako da se ne koristi za probitačnost i samo se ${\displaystyle b^{-(p-1)}/2}$ uzima kao mašinski epsilon.Kao što je prikazano ovde , relativna greška je najgora za brojeve koji se zaokružuju na ${\displaystyle 1}$ , tako da se mašinski epsilon takođe naziva zaokrugljivač jedinica , što znači "maksimalna greška koja se može pojaviti pri zaokruživanju do vrednosti jedinice".Dakle , maksimalan razmak između normalizovanog broja plutajuće tačke ,${\displaystyle x}$ , i susednog normalizovanog broja je ${\displaystyle 2\epsilon }$ x ${\displaystyle |x|}$.

Aritmetički model

Brojčana analiza koristi mašinski epsilon za istraživanje efekata grešaka tokom zaokruživanja.Stvarne greške mašinske aritmetike su suviše komplikovane da bi se direktno proučavale , pa se zbog toga koristi sledeći jednostavni model.IEEE Aritmetički standard nalaže da su sve operacije sa plutajućim tačkama izvršene kao da je moguće odraditi beskonačno-preciznu operaciju , a zatim je broj zaokružen na broj sa plutajućim tačkama.Pretpostavimo da su (1) ${\displaystyle x}$ i ${\displaystyle y}$ brojevi sa plutajućim tačkama , da je (2) ${\displaystyle \bullet }$ aritmetička operacija brojeva sa plutajućim tačkama , kao što je deljenje ili množenje i (3) ${\displaystyle \circ }$ beskonačno-precizna operacija.Prema standardu , računar izračunava:

${\displaystyle x\bullet y={\mbox{round}}(x\circ y)}$

Prema značenju mašinskog epsilona , relativan greška zaokruživanja je većina mašinskog epsilona po veličini , tako da:

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

gde je ${\displaystyle z}$ u apsolutnoj magnitudi najviše ${\displaystyle \epsilon }$ ili u.Knjige Demmela i Highama u referencama se mogu konsultovati kako bi se videlo kako se ovaj model koristi za analizu grešaka , recimo , Gaussove eliminacije.

Varijante definicije

IEEE standard ne definiše  pojmove mašinskog epsilona i jedinice zaokruživanja, tako da se koriste različite definicije ovih termina, što može dovesti do zabune.

Definicija koja je ovde data za mašinski epsilon je ona koju koristi profesor Džejms Dimel u scenariju predavanja , njegov LAPACK linearni algebra pokret , numerički istraživački radovi i neki naučni računarski softveri . Većina numeričkih analitičara upotrebljava reči mašinski epsilon i jedinica zaokruživanja sa tim značenjem.

Sledeća različita definicija je mnogo šire rasprostranjena izvan akademije: Mašinski epsilon je definisan kao najmanji broj, kada se doda jednom, daje rezultad drugačiji od jednog. Po ovoj definiciji ,$\epsilon$ jednak je vrednosti jedinice na poslednjem mestu u odnosu na 1, tj. $b^{-(p-1)}$ i za proceduru zaokruživanja od kruga do najbliže, u$=\epsilon /2$$=\epsilon /2$$=\epsilon /2$${\displaystyle =\epsilon /2}$ .Prevalenca ove definicije korišćena je u njegovoj upotrebi u ISOC standardu za konstantne vezane za tipove sa plutajućim tačkama i odgovarajuće konstantne u drugim programskim jezicima . Takođe se široko koristi u naučnom računarskom softveru u numeričkoj i računarskoj literaturi i drugim akademskim resursima.

Kako odrediti mašinski epsilon

Gde standardi biblioteke ne pružaju predračunate vrednosti (kao što je <plutajuće.h> radi sa FLT_EPSILON,DBL_EPSILON i LDBL_EPSILON za C i<ograničenja>radi sa standardom : numeričko_ograničenje<T>:epsilon ()u C++), najbolji način za određivanje mašinskog epsilona je da se odnosi na tabelu,gore, i koristi odgovarajuća formula. Računarski mašinski epsilon se često daje kao vežba udžbenicima. Sledeći primeri izračunavanja mašinskog epsilona u smislu razmaka brojeva sa plutajućim tačkama na 1, a ne u smislu jedinice zaokruživanja.

Imajte na umu da rezultati zamise od određenog formata sa plutajućim tačkama, kao što su plutajuće,duple,duple duplei ili slično kao što su podržane od strane programskog jezika, prevodioca i biblioteke istraživanja za stvarnu platformu.

Neki formati koje podržava procesor možda ne podržava izabrani prevodilac i operativni sistem. Drugi formati mogu imitirati izvrsavanje biblioteke, uključujući i proizvoljne aritmetički dostupne na nekim jezicima i bibliotekama.

U striktnom smislu pojam mašinski epsilon znači tačnost 1+eps direktno podržana od strane procesora (ili koprocesora), ne nekih 1+eps  preciznosti koje podržava odeđeni prevodilac za određeni operativni sistem, ocim ako nije poznato da koristi najbolji format.

Oblici IEEE 754 sa plutajućim tačkama imaju svojstvo koje, kada se reinterpretiraju dva komplementarna cela broja iste širine , monotonično se povećava preko pozitivnih vrednosti i monotonično smanjuje negativne vrednosti (pogledajte binarno prdstavljanje 32-bitnih plovaka). Takođe imaju svojstvo da 0 < |f(x)| < ∞, and |f(x+1) − f(x)| ≥ |f(x) − f(x−1)|(gde je f(x) ranije pomenuti ceo broj reinterpretacije x). Na jezicima koji omogućavaju tip punjenja  i uvek koriste IEEE 754-1985, možemo to iskoristiti za izračunavanje mašinskog epsilona u konstantnom bremenu. Na primer, u C:

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;
}

Ovo će dati rezultat istog znaka kao i vrednost. Ako je pozitivan rezultat uvek poželjan, povratan izkaz mašinskog epsilona se može zameniti sa:

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

64-bitni dupli daju 2,220446e-16, što je 2-52 kao što se očekivalo.

Približnost

Sledeći jednostavni algoritam mpže se koristiti za približnost mašinskog epsilona u okviru faktora od dva(jedan red veličine)njegove istaknute vrednosti, koristeći linearnu pretragu:

epsilon = 1.0; 

while (1.0 + 0.5 * epsilon) <> 1.0: 
   epsilon = 0.5 * epsilon

Takođe pogledaj i

• Floating point (plutajuća tačka), opšta diskusija o tačnosti problema u aritmetici sa plutajućim tačkama.

• Unit in the last place (Jedinica na poslednjem mestu) (ULP).

Reference

• Anderson, E.; LAPACK Users' Guide, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, third edition, 1999.
• Cody, William J.; MACHAR: A Soubroutine to Dynamically Determine Machine Parameters, ACM Transactions on Mathematical Software, Vol. 14(4), 1988, 303-311.
• Besset, Didier H.; Object-Oriented Implementation of Numerical Methods, Morgan & Kaufmann, San Francisco, CA, 2000.
• Demmel, James W., Applied Numerical Linear Algebra, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997.
• Higham, Nicholas J.; Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, second edition, 2002.
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; and Flannery, Brian P.; Numerical Recipes in Fortran 77, 2nd ed., Chap. 20.2, pp. 881–886
• Forsythe, George E.; Malcolm, Michael A.; Moler, Cleve B.; "Computer Methods for Mathematical Computations", Prentice-Hall, ISBN 0-13-165332-6, 1977

Spoljašnje veze

• MACHAR , rutina ( u C i Fortranu) da bi se "dinamično izračunale mašinske konstante" (ACM algoritam 722)

• Dijagnostikovanje preciznosti kalkulacija plutajućih tokova , Implementacija MACHAR-a u Komponenti Paskal i Oberon bazirana na Fortran 77 verziji MACHAR-a objavljenom u Numerical Recipes (Press et al., 1992).