CATEGORII DOCUMENTE |
ERORI IN METODELE NUMERICE
Introducere
Ne vom ocupa in acest capitol de cateva dintre sursele posibile de erori in metodele numerice.
Consideram important acest subiect ca urmare a doua elemente de care trebuie sa tinem cont in rezolvarea pe calculator a oricarei probleme:
aritmetica calculatoarelor nu este aceeasi cu aritmetica pe care am studiat-o la scoala; in orice calculator fiecare numar este reprezentat printr-un numar fix de cifre ceea ce, uneori, constituie o limita in calcule;
daca intr-un calcul de mica amploare, realizat cu o hartie si un creion, unele erori ale metodelor pot fi neglijate, in problemele complexe rezolvate pe un calculator si care implica milioane de operatii, aceste erori devin semnificative.
Exista doua categorii majore de erori in metodele numerice rezolvate pe calculator:
erorile prin trunchiere si
erorile prin rotunjire.
Erorile prin trunchiere sunt cauzate de aproximarile pe care le facem in procesul de deducere a formulelor matematice utilizate in metodele numerice. Unul dintre instrumentele importante de analiza a acestora il constituie seriile Taylor.
Erorile prin rotunjire apar datorita numarului limitat de cifre semnificative pe care il avem la dispozitie in calculator pentru reprezentarea oricarui numar real.
Inainte de a face o descriere a acestor erori, sa ne reamintim care sunt posibilitatile de exprimare a erorii intr-un calcul, indiferent de sursa care a generat-o.
Fie x rezultatul aproximativ obtinut intr-un calcul oarecare si x valoarea exacta a solutiei respective. Eroarea absoluta este data de expresia:
O alta posibilitate de exprimare a erorii este data de eroarea relativa, definita de relatia :
Eroarea relativa este o masura mai utila de evaluare a preciziei deoarece nu este influentata de ordinul de marime al numerelor.
2. Erori prin trunchiere
In analiza erorilor din metodele numerice, o importanta deosebita o au polinoamele Taylor care sunt date de urmatoarea teorema :
Teorema lui
Sa consideram functia f Cn+1[a,b]. Fie x0 [a,b]. Pentru orice x [a,b], exista un numar ξ(x) cuprins intre x0 si x pentru care
()
unde
si
Pn(x) poarta denumirea
de polinomul
In cazul in care x0 = 0, polinomul Taylor se numeste polinom Maclaurin iar seriile Taylor, serii Maclaurin.
Termenul de eroare prin trunchiere se refera, in general, la eroarea generata prin considerarea unui numar finit de termeni in aproximarea sumei unei serii infinite, aproximare des utilizata in metodele numerice.
De exemplu, dezvoltarile in serie Taylor pentru functiile ex, sin(x), cos(x), in vecinatatea punctului x0 = 1, sunt :
unde h = x-1
Considerand punctul x0 = 0, obtinem pentru aceleasi functii urmatoarele dezvoltari in serie Maclaurin :
Exemplul Eroarea prin trunchiere
Fie dezvoltarea in serie Maclaurin :
Sa
analizam eroarea prin trunchiere in cazul in care vom calcula ln(1,2) pe
baza dezvoltarii in serie
Conform
teoremei lui
Eroarea prin trunchiere, pentru x0 = 0, este :
unde θ (0,1), iar f(x) = ln(1+x).
Cum derivata de ordinul k a functiei f(x) = ln(1+x) este :
deducem
Rezulta urmatoarea expresie pentru restul Rn(x) :
Pentru n = 2 si x = 0,2 obtinem :
Deoarece
rezulta aproximarea
ln(1,2) = 0,18,
cu o precizie de doua zecimale.
Concluzia astfel rezultata este confirmata de valoarea exacta :
ln(1,2) = 0,1823215.
3. Reprezentarea numerelor in calculator
Consideram necesara cunoasterea catorva notiuni fundamentale in acest domeniu pentru o intelegere ulterioara mai buna a cauzelor care conduc la aparitia erorilor prin rotunjire. Cunoasterea acestor cauze permite, de multe ori, evitarea efectelor nedorite a erorilor prin rotunjire printr-o tehnica corecta de elaborare a algoritmilor.
3. Sisteme de numeratie
Sistemul de numeratie in care lucram zilnic este sistemul zecimal, in baza 10. Din motive tehnologice, calculatoarele electronice utilizeaza pentru reprezentarea interna a numerelor si pentru calcule sistemul de numeratie binar. Analizand limbajele interne ale calculatoarelor vom observa ca sunt utilizate si alte sisteme de numeratie, cum ar fi sistemul octal care are baza 8 si sistemul hexazecimal avand baza 16.
In sistemul binar fiecare cifra utilizata pentru reprezentarea unui numar are valoarea 0 sau 1, in sistemul octal cifrele sunt cuprinse in intervalul 0-7 iar in sistemul hexazecimal fiecare cifra este cuprinsa in intervalul 0-15, cifrele de la 10 la 15 fiind exprimate prin literele A,B,C,D,E si F. Valorile zecimale corespunzatoare cifrelor din sistemul hexazecimal sunt :
Zecimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Hexazecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F
Baza unui sistem de numeratie mai poarta si denumirea de radacina si poate fi specificata printr-un indice inferior. Utilizand scrierea pozitionala, un numar oarecare, cu parte fractionara, poate fi reprezentat intr-un sistem de numeratie cu baza b, in forma :
unde ai, i = -k,,-2,-1,0,1,,n-1, sunt cifre.
De exemplu (101,1101)2, (16C6,92)16
Numarul real din sistemul zecimal corespunzator unui numar exprimat intr-un sistem de numeratie oarecare este dat de urmatoarea relatie polinomiala :
De exemplu, numarului (101,11)2 ii corespunde in sistemul zecimal numarul real 5,75, deoarece :
Prima cifra diferita de zero de la stanga numarului se numeste prima cifra semnificativa.
3.2. Reprezentarea interna a numerelor in calculator
Am aratat anterior ca, din motive tehnologice, majoritatea calculatoarelor utilizeaza reprezentarea interna a numerelor in sistemul binar. Considerand un numar oarecare reprezentat in sistemul binar, cifrele 0 sau 1 poarta denumirea de bit.
Bit este acronimul pentru cifra binara (Binary digIT) si in ceea ce priveste calculatorul este utilizat atunci cand ne referim la un element al memoriei avand pozitia 'deschis' sau 'inchis'.
Byte este un set de opt biti si este considerat ca unitate de referinta.
Exista doua categorii de numere care pot fi utilizate in calculele efectuate pe un calculator : numere intregi si numere in virgula mobila (numere reale).
Ne vom referi in acest capitol numai la modul de reprezentare a numerelor pe un calculator, in limbajul de programare Turbo Pascal.
Numerele Intregi
Fie un intreg exprimat, pozitional, in sistemul binar:
unde ai, i= n, n-1, ,0 sunt cifre binare 0 sau
Intr-un calculator, valoarea maxima a numarului de biti pentru reprezentarea unui numar intreg este limitata. De obicei, se utilizeaza 2 bytes pentru reprezentarea unui intreg (variabile de tip integer). Primul bit din stanga inregistreaza semnul : 0 -> pozitiv si 1 -> negativ. Restul de 15 biti a14, a13,,a1, a0 sunt utilizati pentru reprezentarea cifrelor binare.
Astfel, cel mai mare intreg pozitiv este :
-------- ----- ------ -------------
bitul 0| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
-------- ----- ------ -------------
Numarul in binar 0| 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
-------- ----- ------ ----- ----- ----
Valoarea corespunzatoare in zecimal pentru acest numar este
Cel mai mic intreg negativ ce poate fi reprezentat pe 2 bytes este (-32767)10.
Limbajul de programare Turbo Pascal permite, in functie de necesitati, utilizarea urmatoarelor tipuri de date intregi :
| Tip | Domeniu | Forma de reprezentare |
| shortint | -127127 | 8 biti cu semn |
| |
| integer | -3276732767 | 16 biti cu semn |
| |
| longint |-21474836482147483647| 32 biti cu semn |
| |
| byte | 0255 | 8 biti fara semn |
| |
| word | 065535 | 16 biti fara semn |
Numere Reale
Reprezentarea numerelor reale in calculator se face in virgula mobila si in forma binara normalizata. In simpla precizie, se realizeaza pe 6 bytes (48 biti).
Sa consideram un numar binar oarecare, avand parte intreaga si parte fractionara, exprimat in scriere pozitionala, in forma generala :
In forma normalizata numarul este dat de relatia :
De exemplu, numarul binar (101,11) se va scrie in forma normalizata (0,10111) x 23. Numarul real corespunzator in zecimal numarului binar dat este :
In mod asemanator se vor reprezenta in forma normalizata si numerele binare subunitare. De exemplu (0,0001011)2 se va scrie in forma normalizat_ (0,1011) x
Revenind la reprezentarea interna a unui numar in virgula mobila (in Turbo Pascal), cei 48 de biti sunt utilizati dupa cum urmeaza : primul bit de la stanga pentru semn, urmatorii 8 biti pentru exponent si restul de 39 de biti pentru mantisa :
s| e e e e e e e e | m1 m2 m3 m37 m38 m39
8 biti pentru 39 biti pentru mantisa
exponent
1 bit pentru semn
s, e, m1,,m39 sunt cifre binare (0 sau 1).
Pornind de la aceasta reprezentare, un numar zecimal oarecare x, in virgula mobila este exprimat in urmatoarea forma normalizata :
unde am notat cu g
exponentul translabil si cu p
In particular, 0 si 255 sunt valori rezervate. Constanta p are valoarea 128 (in simpla precizie). Exprimand in acest mod exponentul lui 2 din forma normalizata se evita cerinta unui bit suplimentar pentru semnul acestui exponent.
In forma normalizata prima cifra semnificativa este intotdeauna 1, astfel incat numarul efectiv de cifre binare pentru mantisa este 40. Intervalul in care poate lua valori exponentul lui 2 in forma normalizat_ este -127 <= g - p <= +126, de unde
2-127 < 2(g - p) < 2126. Cel mai mic numar care poate fi reprezentat pe o mantis_ de 40 bi_i este (0,1)2 = 0,510 iar cel mai mare este (0,1..11)2 = (1 - 2-40)10.
Obtinem in acest mod cel mai mic numar in virgula mobila care poate fi reprezentat in calculator : 0,5 x 2-127 = 2,938x 10-39, respectiv cel mai mare numar in virgula mobila reprezentabil : (1 - 2-40) 2127 = 1,7014..x 1038.
Deoarece numarul de biti utilizat pentru reprezentarea mantisei si a exponentului este limitat, rezulta o prima concluzie importanta : pe un calculator, in simpla precizie, exista un numar finit de numere reale, in virgula mobila, care pot fi reprezentate exact:
Limbajele de programare ofera posibilitatea utilizarii si altor tipuri de date reale in functie de precizia de calcul solicitata in rezolvarea problemelor ( vezi tabelul 2.).
Tipul variabilei (in Turbo Pascal) |
Dimensiunea, in bytes, alocata in calculator pentru reprezentarea variabilei |
Numarul de cifre semnificative exacte rezultat, in zecimal |
Domeniul de definitie, in zecimal |
real |
x x |
||
single | |||
double | |||
extended |
|
4. Erori prin rotunjire
Am demonstrate, in capitolul anterior, ca exista un numar limitat de numere reale care pot fi reprezentate exact in calculator, altfel spus, numerele reale care pot fi reprezentate exact sunt insirate ca margelele pe axa numerelor reale. De exemplu, daca cel mai mic numar real, diferit de zero, care poate fi reprezentat exact in calculator este 2,938x10-39, rezulta ca numerele reale cuprinse in intervalul (0, 2,9 x 10-39) nu pot fi reprezentate exact (vom analiza mai jos cum sunt, in schimb, aproximate). Aceeasi afirmatie este valabila si pentru orice numar real, negativ, apartinand intervalului (-2,9 x
Cum putem determina intervalul dintre doua numere reale consecutive care pot fi reprezentate exact in calculator ?
Pentru aceasta vom afla mai intai o constanta importanta a oricarui calculator si anume constanta epsilon care reprezinta diferenta dintre numarul 1 si cel mai mic numar care este mai mare decat 1 si care este reprezentabil in calculator, altfel spus, cel mai mic numar real, pozitiv, care adunat la 1 va da in calculator un numar diferit de
Reprezentarea binara in forma normalizata pentru 1, in simpla precizie, este :
x
Cel mai mic numar, mai mare decat 1, care poate fi reprezentat pe mantisa de 40 biti este:
x
Numarul real zecimal corespunzator acestui numar binar este :
Rezulta astfel, in simpla precizie, urmatoarea valoare pentru constanta epsilon :
ε = 1,81898x 10-12.
In cazul in care nu cunoastem modul de reprezentare interna a numerelor in calculatorul pe care lucram, constanta epsilon poate fi dedusa prin rularea unui program elaborat pe baza urmatorului algoritm:
Algoritm pentru determinarea constantei epsilon a calculatorului
variabile definite: eps, eps1 ;
se va defini tipul variabilelor (real, single, double, extended)
eps = 1;
eps1 = 1;
cat timp eps1 > 0,
begin
eps = eps/2 ;
eps1 = eps*0,98+1 ;
eps1 = eps1-1
end ;
afiseaza Epsilon calculator = eps ;
De exemplu, pentru o reprezentare a variabilelor in simpla precizie (pe 8 bytes):
Epsilon calculator = 1,8189894035 x 10-12
Elaborati un program care sa calculeze constanta epsilon, in dubla precizie (declarati variabilele eps, eps1 : double) si in precizie multipla.
Cunoscand constanta epsilon a calculatorului, putem afla diferenta dintre orice numar real ri, care poate fi reprezentat exact in calculator si urmatorul numar real ri+1 , reprezentabil exact, pe baza relatiei :
ri+1 - ri ≈ epsilon x ri
Erori prin rotunjire in reprezentarea interna a numerelor
Principala cauza a erorilor prin rotunjire este generata de reprezentarea numerelor reale in forma binara printr-un numar limitat de biti.
Am aratat anterior ca nici un numar real cuprins intre 1 si 1+epsilon_calculator nu poate fi reprezentat exact in calculator, altfel spus. In acest caz, daca in urma unor calcule obtinem un numar de forma 1+α, unde α (0, ε), acest numar va fi aproximat, prin taiere, cu 1 daca
sau va fi rotunjit la valoarea 1 + daca
Acest proces de taiere sau rotunjire este cunoscut in literatura de specialitate si sub denumirea de rotunjire simetrica.
Sa generalizam. Fie intervalul dintre doua numere reale consecutive cu reprezentare exacta in calculator (ri, ri+1). Orice numar real de forma ri+ α, cuprins in acest interval
α (0, ri+1-ri)) va fi aproximat prin taiere la valoarea ri daca
sau va fi rotunjit la valoarea ri+1 daca
De exemplu, numarul 0,143 nu poate fi reprezentat exact in calculator si este aproximat, prin taiere, la valoarea 0,14299999986; numarul 0,1431 nu poate fi reprezentat exact si este aproximat prin rotunjire la valoarea 0,14310000025
Eroarea care se face la reprezentarea unui numar oarecare in calculator este aproximativ egala cu ε x r/2 daca numarul este aproximat prin rotunjire si ε x r daca este aproximat prin taiere.
4.2. Efecte si cauze ale erorilor prin rotunjire
Unul dintre efectele erorilor prin rotunjire se manifesta la adunarea si scaderea numerelor. In general scaderea si adunarea numerelor in virgula mobila, normalizate, ca urmare a modului in care se efectueaza, necesita reprezentarea rezultatului cu un numar mai mare de cifre semnificative decat al numerelor insumate pentru a obtine o precizie satisfacatoare.
Sa adunam numerele (1)10 si (0,0000001)10. Reprezentarea binara in forma normalizata a acestor numere este:
x
(0,00000001)10=(0,1010 0111 1100 0101 1010 1100 0110 1001 1100 1011)2 x 2-26
Pentru a aduna aceste doua numere este necesar sa le aducem la acelasi exponent (exponentul mai mare). Aceasta operatie conduce la denormalizarea numarului cu exponent mai mic, altfel spus se deplaseaza mantisa cu 27 de pozitii spre dreapta, aceste pozitii fiind ocupate de cifra 0.
Urmatoarea etapa consta in adunarea mantiselor. Evident ca rezultatul exact necesita o reprezentare pe o mantisa de 67 de biti. Mantisa pe care o avem la dispozitie fiind de numai 40 de biti se vor pierde ultimile 27 de cifre binare semnificative. Rezultatul real al adunarii este :
(0,1000 0000 0000 0000 0000 0000 0001 0100 1111 1000)2 x 21
ceea ce in zecimal inseamna (0,000000010008)10. Daca veti aduna (0,00000001)10 de 10000 de ori la 1, la fiecare adunare se va insuma si o eroare de 8 x 10-12. Rezultatul va fi 1,000100008.
O prima concluzie care se desprinde din acest exemplu este: evitati insumarea numerelor diferite considerabil ca ordin de marime.
In cazul in care aveti o problema in care trebuie sa realizati o suma de mai multi termeni diferiti ca ordin de marime, adunati mai intai termenii de ordin mic.
Sa analizam in continuare efectul erorii prin rotunjire la scaderea numerelor.
Se stie ca derivata unei functii intr-un punct x este definita de relatia :
astfel incat, pentru valori mici ale lui h, putem considera formula de aproximare :
Sa calculam pe baza acestei formule derivata functiei f(x)=cos(x) in punctul x = 1
Tabelul 3. contine rezultatele obtinute pentru diverse valori ale lui h (pentru calcule efectuate in simpla precizie).
Tabelul 3.
h cos'(1)=(cos(1+h)-cos(1))/h eroarea
Conform formulei utilizate rezultatele trebuie sa se imbunatateasca pe masura ce h scade. Se observa ca precizia aproximarilor creste pana la h = 10-6, in timp ce incepand cu valori mai mici decat 10-6 precizia incepe sa scada. In acest caz eroarea prin rotunjire influenteaza nefavorabil rezultatul scaderii a doua numere aproximativ egale.
Pentru o mai buna intelegere sa consideram doua numere reale x si y avand urmatoarea reprezentare binara in forma normalizata pe o mantisa de 40 de biti :
Rezultatul diferentei x - y este
unde
Ce efect are asupra rezultatului modul in care s-a efectuat scaderea ?
Mai intai trebuie sa tinem cont de faptul ca, intr-un calculator, un numar foarte mic de numere reale zecimale admit o reprezentare exacta in binar cu un numar finit de cifre binare. La scaderea a doua numere binare in virgula mobila in forma normalizata si avand valori apropiate, mantisa rezultatului se deplaseaza spre stanga cu un numar de pozitii egal cu numarul cifrelor semnificative comune celor doua numere care se scad iar exponentul se va micsora cu acest numar.
In partea drepta a mantisei va rezulta un numar de cifre binare 0 egal cu numarul pozitiilor cu care s-a deplasat mantisa spre stanga. In situatia in care cele doua numere reale care se scad sunt aproximativ egale, se va pierde un numar de cifre binare semnificative egal cu numarul pozitiilor cu care s-a deplasat mantisa spre dreapta.
Astfel, cu cat numerele care se scad sunt mai apropiate, numarul de cifre semnificative care se va pierde este mai mare.
Mai apar erori prin rotunjire si la scaderea numerelor mult diferite ca ordin de marime. Rezulta in acest fel o a doua regula de care trebuie sa se tina cont in elaborarea unui algoritm: evitati scaderea numerelor aproximativ egale sau mult diferite ca ordin de marime.
5. Concluzii
O analiza superficiala a erorilor prin rotunjire ne poate duce la concluzia gresita ca efectul acestora este neglijabil. In realitate, intr-o problema complexa care implica milioane de calcule, erorile prin rotunjire se pot propaga, afectand considerabil rezultatul final.
Acest efect poate fi evitat prin elaborarea unor algoritmi stabili numeric. Un algoritm este stabil numeric daca modificari mici ale datelor de intrare vor genera modificari mici ale rezultatului final.
Din pacate, nu exista o regula unica care sa ne permita elaborarea unor algoritmi stabili. Cateva strategii posibil de aplicat astfel incat sa se reduca efectul erorilor prin rotunjire sunt :
Efectuarea calculelor in dubla sau multipla precizie. Dezavantajul acestei alegeri consta in cresterea considerabila a timpului de calcul si in faptul ca erorile prin rotunjire nu sunt eliminate ci numai diminuate.
2. Metoda gruparii. De exemplu am vazut in capitolul 4.2. ca daca adunam de 10000 de ori 0,00000001 la 1 vom obtine 1,00100008. Daca veti efectua calculele adunand de cate o suta de ori 10-8, rezultatul adunandu-l de o suta de ori la 1, veti obtine rezultatul corect - 1,00
3. Rescrierea ecuatiilor pe baza carora se elaboreaza algoritmul.
O analiza mai detaliata a instabilitatilor numerice si a altor posibitati de evitare a erorilor prin rotunjire se gaseste in [ 5 ].
PROGRAMUL CONVERSIA DIN ZECIMAL IN BINAR
I. Explica_ii
Acest program face conversia din zecimal in reprezentarea binar_ in forma normalizat_ in virgul_ mobil_ pe o mantis_ de 24 de bi_i (programul poate fi u_or modificat _i pentru o mantis_ de 40 de bi_i). Aceast_ conversie poate fi exprimat_ sub forma:
(A)
|
unde x este num_rul zecimal introdus, m1,,m40 sunt cifre binare 0 sau 1 iar exp este exponentul lui 2 in zecimal.
Datele se introduc interactiv.
II. Listing
program zecimal_binar;
var
a:array[0..255] of integer;
i,k,l,m_exp,n:integer;
putere2,s,zecimal,y:real;
ch:char;
function log(x:real):real;
begin
log:=ln(x)/ln(10);
end;
function putere(baza,n:real):real;
begin
putere:=exp(n*ln(baza));
end;
begin
writeln ;
writeln(' Program de conversie Zecimal‑Binar ');
writeln;
repeat
write ('Introduceti valoarea in baza zece:');
readln (zecimal);
l:=0;
k:=1;
i:=trunc(log(zecimal)/log(2.0))+3;
repeat
i:=i‑1;
if (i<‑200) then exit;
putere2:=putere(2.0,i‑1);
if zecimal>=putere2 then
begin
a[k]:=1;
zecimal:=zecimal‑putere2;
if l=0 then
begin
m_exp:=i;
l:=1;
end;
end
else
if k>1 then a[k]:=0;
if l>0 then k:=k+1;
until k>=25;
writeln('‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑');
writeln('Binar');
write(' Mantisa = 0.');
for k:=1 to 24 do
begin
write(a[k]);
if (k mod 4)=0 then
write(' ');
end;
writeln;
writeln(' Exponent= ',m_exp);
writeln('‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑‑');
write('Continuati? (d/n):');
readln(ch);
until (ch='n') or (ch='N');
end.
EXEMPLE RULARE
Program de conversie Zecimal‑Binar
Introduceti valoarea in baza zece:0.4
Binar
Mantisa = 0.1100 1100 1100 1100 1100 1100
Exponent= ‑1
Continuati? (d/n):D
Program de conversie Zecimal‑Binar
Introduceti valoarea in baza zece:55
Binar
Mantisa = 0.1101 1011 1111 1111 1111 1111
Exponent= 6
Continuati? (d/n):D
Program de conversie Zecimal‑Binar
Introduceti valoarea in baza zece:0.0003264
Binar
Mantisa = 0.1010 1011 0010 0000 1010 1010
Exponent= ‑11
Continuati? (d/n):N
III. Comentarii
Am ales ca exemple de rulare conversia numerelor reale 0,4; 55; 0,0003264. Datele de ie_ire vor fi interpretate conform rela_iei (A).
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2755
Importanta:
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved