Lucrarea de laborator nr.1

Tema lucr ării: Erori în rezolvarea problemelor numerice

1.Caracterizarea lucrării

De cele mai multe ori, algoritmii cu caracter numeric, după implementarea lor pe un sistem de calcul, determină o aproximare a soluţiei exacte a problemei în discuţie.

Scopul lucrării: a) a evidenţia modul în care pot fi caracterizate erorile numerice;b) a sublinia sursele şi modalităţile de apariţie ale acestor erori;c) a studia procesul de propagare a erorilor numerice.

În această lucrare sunt studiate: 1) erorile inerente;2) erorile de rotunjire;3) erorile de trunchiere.

2. Principiul lucrării

Pentru a caracteriza abaterea unei variabile numerice de la valoarea sa exactă se utilizează eroarea absolută: (1), unde x reprezintă valoarea exactă, iar

, o aproximare a sa. Ţinînd cont că de regulă valoarea exactă x nu este cunoscută, se utilizează o

margine superioară a erorii absolute: (2) şi astfel, în locul valorii exacte x, se operează cu intervalul: (3).

O mai bună caracterizare din punct de vedere calitativ a abaterii de la valoarea

exactă a unei variabile numerice, o furnizează eroarea relativă:

(4) sau o margine superioară a acesteia: (5).

În unele aplicaţii (mai ales cu caracter teoretic), se poate considera: (6) şi

(7).

2.1. Erori inerente

Datele de intrare utilizate în soluţionarea unor probleme tehnice provin, în multe situaţii, din determinări experimentale. Rezultatul oricărei masurători este susceptibil de erori.

Erorile datelor de intrare într-un algoritm numeric se numesc erori inerente. Aceste erori se propagă în procesul de calcul şi de cele mai multe ori afectează rezultatul final.

Un algoritm de calcul nu poate fi făcut responsabil de existenţa erorilor inerente, în schimb, el poate influenţa precizia soluţiei.În acest sens, dacă eroarea relativă a soluţiei obţinute depăşeşte erorile relative ale datelor de intrare, se spune că algoritmul este numeric instabil (în astfel de situaţii, abateri mici ale

fatelor de intrare pot determina abateri mare ale soluţiei numerice, făcând-o practic inutilizabilă).

2.2. Erori de rotunjire

Una dintre cauzele frecvente de eroare în calculele cu numere reale se datorează reprezentării finite a acestora în sistemele de calcul.

Într-un sistem de calcul, un număr real se reprezintă printr-o pereche (f,e) unde şi (7) (funcţia se numeşte mantisă iar e se n

umeşte exponent). Cadrul în care are loc această reprezentare, F=(10,t,p) se numeşte format virgulă mobilă, iar (f,e) se numeşte număr în VM.Valoarea sa reală este: (8).

Eroarea relativă (care în acest caz se numeşte eroare de reprezentare) se setează cu şi satisface următoarea inegalitate: , unde: , dacă funcţia de rotunjire

utilizată este cea prin trunchiere şi , dacă este utilizată rotunjirea simetrică.

Această eroare relativă de rotunjire, specifică sistemului de calcul (calculator+medii de programare) este cel mai mare număr real care adăugat la unitate nu modifică valoarea acestuia.

Ordinul de mărime al în sistemele uzuale de calcul este de şi poate fi determinat, pe fiecare sistem de calcul, cu următorul algoritm:

;calculează eroarea relativă de rotunjirereal errerr=1repetă

err=err/2pînă cînd (1+err=1)scrie err

2.3. Erori de trunchiere

Soluţionarea unei probleme fizice (PF), utilizînd o metodă numerică, presupune parcurgerea următoarelor etape:

- obţinerea, pe baza ecuaţiilor fizicii matematice, a modelului matematic (PM)- reducerea (PM) la o problemă discretă (PD) (i.e. a cărei rezolvare impune:

parcurgerea unui număr finit de paşi într-o perioadă de timp determinată şi obţinerea unei aproximări uniforme a soluţiei exacte)

- proiectarea unui algoritm (i.e. ansamblu de reguli, ce transformă datele de intrare în date finale pe baza unei succesiuni unic determinate de operaţii aritmetice elementare) pentru rezolvarea (PD).Vom prezenta (pe scurt) ce presupune calculul numeric al unei limite de şir, respectiv a unei sume de serii.

a) Fie Pentru o anumită eroare impusă eps, utilizînd

caracterizarea limitei unui şir, va exista un rang n (dependent de eps) a.î. (9)

Astfel, putem concluziona că, după evaluarea unui număr suficient de mare de termeni n, se poate considera: (10).

Viteza de convergenţă a unui algoritm utilizat depinde de legătura existentă între n şi eps. Astfel, vom spune că viteza de convergenţă a unui algoritm este de ordinul p, dacă:

(10)

b) Vom considera dezvoltarea în serie Taylor a funcţiei y=sinx:

, unde (11)

(12)

Vom evalua eroarea obţinută prin aproximarea funcţiei sin prin: . Astfel,

avem: (13)

Rezultă următorul pseudocod pentru evaluarea funcţiei sin cu o eroare de trunchiere mai mică decît eroarea de rotunjire err:

funcţia sinus(x)real x,t,sîntreg kt=xs=tk=1repetă

k=k+2t=-t*x*x-k*(k-1)s=s+t

pînă cînd întoarce s

Se poate observa că efortul de calcul pentru evaluarea funcţiei sin creşte odata cu scăderea erorii impuse şi cu creşterea lui .

2.4. Propagarea erorilor

Vom analiza propagarea erorilor în cazul celor patru operaţii aritmetice elementare, într-un FVM(10,t,p) fixat.a) Adunarea: Fie Atunci: şi ; iar

(14)

Dacă şi au acelşi semn, + este o operaţie stabilă numeric şi din (14), obţinem : (15)

b) Scăderea: În aceleaşi ipoteze, şi iar

(16)

Scăderea este o operaţie instabilă numeric dacă poate depăşi eroarea termenilor: dacă şi au acelaşi semn, cu multe ordine de mărime, prin fenomenul de anulare prin scădere).c)Înmulţirea:

(17)

d) Împărţirea:

(18) În aceste evaluări ale erorilor, s-a considerat că toate calculele se efectuează exact.

În realitate, eroarea relativă a rezultatului se obţine prin adăugarea erorii de rotunjire la cea de calcul.

Dacă eroarea unui calcul numeric prezintă o importanţă deosebită, se va utiliza tip abstract de date ce permite controlul propagării erorii.În acest tip de date, numerele reale x sunt reprezentate prin valoarea x şi marginea erorii relative prin intervalul:

(19)

tip înregistrare intervalreal val ;valoarereal er ;marginea erorii relativeprocedura suma(x,y,s) ;calculează s=x+y

interval=x,y,ss.val=x.val+y.vals.er=err+(|x.val*x.er|+|y.val*y.er|)/|s.val|

returprocedura dif(x,y,d) ;calculează d=x-y

interval x,y,dd.val=x.val-y.vald.er=err+(|x.val*x.er|+|y.val*y.er|)/|d.val|

returprocedura prod(x,y,p) ;calculează p=x*y

interval x,y,pp.val=x.val*y.valp.er=err+|x.er|+|y.er|

returprocedura rap(x,y,c) ;calculează c=x/y

interval x,y,c

c.val=x.val/y.valc.er=err+|x.er|+|y.er|

retur

3.Chestiuni de studiat

a) De terminarea erorii relative de rotunjire a sistemului de calcul;b) Analiza propagării erorilor inerente;c) Analiza erorii de trunchiere;d) Implementarea unor algoritmi numerici ce controlează eroare.

4. Modul de lucru

Pentru desfăşurarea lucrării se introduce comanda:Erori <Enter>

în urma căreia se lansează un program cu următorul meniu

1. Îndrumar2. Erori de rotunjire3. Calcule cu controlul erorii4. Erori de trunchiere5. Implementare algoritmi6. Testare cunoştinţe7. Ieşire

a) Determinarea erorii relative de rotunjire a sistemului de calcul

Se selectează opţiunea 2 (Erori de rotunjire), care are ca efect calculul şi afişarea erorii relative de rotunjire a sistemului de calcul.

b) Analiza propagării erorilor inerente

Se selectează opţiunea 3 (Calcule cu controlul erorii).

c) Analiza erorii de trunchiere

Se selectează opţiunea 4 (Erori de trunchiere), care are ca efect lansarea unui program, ce realizează sumarea următoarelor serii:

Taylor pentru funcţia exponenţială;Taylor pentru funcţia sinus;Taylor pentru funcţia logaritm natural;Armonica alternantă.

După selectarea funcţiei şi alegerea valorii variabile independente x, programul calculează şi afişează: suma parţială a seriei; eroarea absolută de trunchiere pentru diferite ordine. Se calculează apoi: eps(1), exp(10), esp(-10), sin(1), sin(10), ln(1.1). Se comentează rezultatele. Se apreciează viteza de convergenţă.d) Implementarea unor algoritmi cu controlul erorii

Se generează pseudocodul funcţiei cos, determinată prin serie Taylor trunchiată pentru a atinge o eroare de trunchiere impusă. Se implementează acest algoritm într-un limbaj de programare sub forma unei funcţii cosinus (x,ert), cu ert: eroarea de trunchiere impusă. Se implementează algoritmul de determinare a erorii relative de rotunjire err Se implementează algoritmul de determinare a erorii de trunchiere ert=err

5. Întrebări şi probleme