c1mnb

Metode Numerice

profesor Valeriu Iorgaasistenţi Florin Pop

Mihai MogoşGeorgiana Cornoiu

Diana Petrescu Vlad Dascălu

Curs 1 Prezentare generală

Obiectivele cursuluiPrezentarea unor metode de aproximare eficientă a soluţiilor problemelor exprimabile prin modele matematiceAnaliza erorilor metodelor discutateImplementarea metodelor prezentate în MATLAB

Evaluarea studenţilorTeme de casă 20%Laborator 5%Seminar 5%Examen parţial 30%Examen final 40%

Curs 1 Prezentare generală

RestricţiiExamenul parţial se susţine în săptămâna 8-a cu tot anul şi constă din mai multe probleme, acoperind capitolele sisteme de ecuaţii liniare, interpolare, aproximare uniformă şi aproximare în sensul celor mai mici pătrate. Refacerea examenului parţial se face înainte de începerea sesiunii.Condiţiile de promovare:

• Media ponderată >= 4.5• Nota la examenul final > 3 (din 10)• Număr prezenţe laborator >= 5• Număr teme de casă predate >=3 (din 5)• Laboratorul se încheie cu un colocviu cu ponderea de 1

punct din nota finală

Curs 1: Prezentare generală

BibliografieV.Iorga, B.Jora -Metode Numerice,

Ed.Albastră, 2004B.Dumitrescu, C.Popeea, B.Jora -

Metode de Calcul Numeric Matriceal.Algoritmi fundamentali Ed.ALL, 1998

Curs 1: Prezentare generală

Capitolele cursuluiSisteme de ecuaţii lineare.Interpolare polinomială.Aproximare uniformă.Aproximare în sensul celor mai mici pătrateIntegrare şi derivare numericăIntegrarea ecuaţiilor diferenţiale..Valori proprii şi vectori proprii..Descompunerea valorilor singulare..

Obiectul calculului numeric

Formularea problemei fizice-în limbaj natural, evidenţiind intrările şi ieşirile.Stabilirea modelului matematic-în limbajul formulelor matematiceDiscretizarea modelului matematiccontinuu, obţinându-se un model discretizatAnaliza erorilorProiectarea algoritmului şi implementarea în MATLAB

Formularea problemei fizice

Problema fizicăSă se studieze propagarea temperaturii

într-o bară AB de lungime l, cunoscând:

- temperaturile la momentul iniţial în orice punct al barei θ0(x), x∈[0, l]

- temperaturile la cele două capete τA(t)şi τB(t) în orice moment t ∈[0, t1]

Stabilirea modelului matematic

Să se determine funcţia:

care satisface următoarele condiţii

( )[ ] [ ] Rt,l,

)t,x(θt,x:θ→×

→100

Stabilirea modelului matematic

ecuaţia lui Fourier

condiţiile iniţiale, condiţiile pe frontieră

S = spaţiul funcţiilor de 2 oriderivabile pe [0, l] X [0, t1]

tθK

xθ

∂∂

∂∂

⋅=2

201

)x(θ),x(θ 00 02 =

)t(τ)t,(θ A=030

)t(τ)t,l(θ B=04

Sθ∈05

Discretizarea modelului matematic

, reţeaua de discretizare

valoarea discretizată

aproximare derivate

Mlx =∆

)tn,xi(θθni ∆∆=

Ntt 1

=∆

211

2

2

1

2x

θθθ)tn,xi(xθ

tθθ)tn,xi(

tθ

ni

ni

ni

ni

ni

∆+⋅−

=∆∆

∆−

=∆∆

−+

+

∂∂∂∂

Discretizarea modelului matematicSă se determine cucare satisface condiţiile:

1+niθ 1011 −<<−<< Nn,Mi

211

10 21

)x(θθθK

tθθ n

ini

ni

ni

ni

∆+⋅−

⋅=∆− −+

+

)xi(θθi ∆= 0002

)tn(τθ An ∆=0

03

)tn(τθ BnM ∆=04

K)x(t

⋅≤

∆∆

21

5 20

Tipuri de erorierori de problemă (inerente) care apar la trecere de la modelul fizic la cel matematicerori de metodă introduse prindiscretizarea modelului matematic,erori de trunchiere provin din natura infinităa unor procese care descriu soluţiaproblemeierori de rotunjire specifice rezolvăriiproblemei pe calculatorul numeric, care utilizează aritmetica în virgulă mobilămobilă

Analiza erorilor☺ Eroarea absolută ex=|x-x~|

x = mărimea exactă, x~ =aproximarea lui x

☺ Eroarea relativă dacă x≠0, x~=x~±ex

☺ Eroarea în x: e=x~-x cu |e|=ex şi x~=x+e

☺ Eroarea relativă în x: ,| ε |= εx,x~=x(1+ ε)

xxx

ε~

x

−=

xxxε

~ −=

Reprezentarea în virgulă mobilăO bună reprezentare asigură:

un domeniu mare de valori reprezentate,o eroare relativă mică a reprezentării,o distribuţie uniformă a erorii relative.

Valoarea exactă admite reprezentarea:

⎟⎠

⎞⎜⎝

⎛+=⋅= ∑ ∑

−

=

∞

=

−−−−−

1

0 12101

n

i i

ii

iin βaβasaaasax KK

Reprezentarea în virgulă mobilă

β este baza reprezentării; în mod uzual β=2,f este fracţia (sau mantisa) asigurând o preciziede t cifre semnificative,e este exponentul Emin < e < Emax

Condiţia de normalizare a mantisei asigură o reprezentare unică:

( ) e~ βfxflx ⋅==

.βf,f,f...ff.f

,fβ

i

t

<≤≠=

<≤

00

0

11

1

21

Reprezentarea în virgulă mobilăElementele reprezentării sunt : baza, precizia şi limitele exponentului , saubaza, precizia şi numărul de cifre al exponentuluim<|x~|<Mm=βEmin, M= βEmax.(1- β-t)Emin=-ρ… ρ, cu ρ= β-1Emax=-Emin


FL={x∈R|x are reprezentare exactă în VM}∪{0}Funcţia de rotunjire R :x ∈[-M,M]→x~=fl(x)∈FL

Strategii de rotunjire- rotunjirea prin tăiere - care se obţineluând numai primele t cifre ale fracţiei.- rotunjirea simetrică - obţinută prinadăugarea adăugarea unei unităţi la f dacăft+1> β/2 .


Rotunjirea prin tăiere:( ) ,ββfβfβff.x ee ⋅+⋅+⋅=⋅= −− KK 2

21

1210

( ) ( ) et

tett ββfβββfβfβfx KK +++++= −

+−−−− 1

12

21

1

teetet

et βfβfβf.βfff.x −−

+ ⋅′+⋅=⋅+⋅= KK 121 00te~ βfxx −⋅′+=

tete~x ββfxxe −− <⋅′=−=

te

te

emin

x^x

x βββ

ββf

exeε −

−

−

=⋅

<⋅

<= 11

Reprezentarea în virgulă mobilăPentru rotunjire simetrică:

Definim unitatea de rotunjire prin:

⎪⎩

⎪⎨⎧

= −

−

simetricãrotunjireapentruβ

tãiereprinrotunjireapentruβu t

t

1

1

21

tex βe −⋅<

21 t

x βε −⋅< 1

21

Reprezentarea în virgulă mobilăfl(x)=x.(1+ρ), | ρ |<K.β-t, cu K de ordinul unităţii

Standardul IEEE pentru formatul de virgulămobilă, în precizie simplă este (2,24,7), iar înprecizie dublă este (2,53,10). Numărul cifrelorzecimale semnificative este 7, respective 16

( )εx)x(flεx

)x(flxm1⋅=⇒±=

−

Aritmetica în virgulă mobilă

Operaţiile în VM dau rezultate în mulţimea , FLdeci nu sunt exacte.fl(x op y)=(x op y).(1+ρ), | ρ | < K.β-t

Dacă rezultatul are modulul >M, aparedepăşire superioară (overflow), iar dacă rezultatul este <m apare depăşire inferioară (underflow).Depăşirea superioară duce la oprirea calculelor. Depăşirea inferioară produce rezultatul 0


În standardul IEEE există valori speciale: Inf(Infinity) – care provine dintr-o depăşire superioară şi NaN(Not a Number) – provine din nedeterminări de forma 0/0sau ∞/ ∞. Două ipoteze:1. precizia de t cifre este nu este satisfăcătoare, dar calculele exact.


2. Precizia de t cifre este satisfăcătoare, dar calculele se fac aproximativ

Cazul 1:valoarea exactă x va avea o reprezentare aproximativă x~ şi ex=x-x~

x+y=(x~+ex)+(y~+ey)=x~+y~+(ex+ey)Deoarece calculele se fac exact:(x+y)~=x~+y~

x+y=(x+y)~+ex+y

ex+y=ex+ey


(x~+y~)εx+y=x~ εx+y~ εy

În mod asemănător avem relaţiile:ex-y=ex+ ey

y~~

~

x~~

~

yx εyx

yε

yxx

ε ⋅+

+⋅+

=+

y~~

~

x~~

~

yx εyx

yε

yxx

ε ⋅−

+⋅−

=−


Ex*y=y~ex+x~eyεx*y= εx+ εy

εx/y= εx+ εyCazul 2: În operaţiile cu numere reale apar

erori de rotunjire. Astfel, adunareanumerelor reale decurge în modul următor:

2~

y~

~x

y/xy

ex

ye

e −=


- numărul cu exponent mai mic este adus la exponentul mai mare, operaţie numitădenormalizare;- se adună mantisele;- se normalizează rezultatul.Dacă acumulatorul maşinii este simplu (adicăpoate păstra numai t cifre semnificative) , prindenormalizare se pierd din fracţie un numărde cifre egal cu diferenţa exponenţilor


x1=f1βe1, x2=f2 βe2, e1>e2x1+x2= βe1(f1+ βe2-e1f2)= βe1(f1+ β-(e1-e2)f1)Prin denormalizare se pierd e1-e2 cifre deci în loc de x2 apare x2~ :x2~=x2(1+ε2), ε2<β1-t,fl(x1+x2)=x1+x2(1+ ε2)Dacă |x1+x2+e2|> βe1, prin denormalizare se mai pierd cifre semnificative şi:fl(x1+x2)=(x1+x2.(1+ ε2)).(1+ ε)


Dacă acumulatorul maşinii este dublu (păstrează 2t cifre semnificative, aşa că la denormalizare nu se mai produce nici o eroare), eroarea de rotunjire se manifestă numai la normalizarea rezultatului şi:fl2(x1+x2)=(x1+x2)(1+ε), ε<u

Condiţionarea problemelor

Condiţionarea problemei dă sensibilitatea soluţieiîn raport cu perturbarea datelor de intrare, în ipoteza unor calcule exacte (indiferent de algoritmul folosit pentru rezolvarea problemei.x - datele exacte de intrare, x~- o aproximaţie cunoscută a acestoraf(x) – soluţia exactăf(x~) - soluţia calculată, în ipoteza unor calcule exacte.


Factorul Lipschitz:

pentru x ≠ 0,f(x) ≠0

O valoare k(x) mică caracterizează o problemă bine-condiţionată.

xxx)x(f

)x(f)x(f

)x(k ~

~

−

−

=


Dacă funcţia este Lipschitz continuă:

Condiţionarea este o proprietate locală – o problemă bine condiţionată este bine condiţionată în orice punct

( ) ( ) yxLyfxf −⋅≤−

)x(f

xL)x(k ⋅≤

Stabilitatea numerică a algoritmilorPentru rezolvarea unei probleme f, calculatorul execută un algoritm f~

Calculele sunt afectate de erori aşa că f(x)≠f~(x).Stabilitatea numerică exprimă mărimea erorilor numerice introduse de algoritm, în ipoteza unor date de intrare exacte.Un algoritm numeric stabil are o eroarerelativă de ordinul erorii de rotunjire.

Stabilitatea numerică a algoritmilor☺ Stabilitatea numerică exprimă mărimea

erorilor numerice introduse de algoritm, în ipoteza unor date de intrare exacte .Un algoritm destinat rezolvării problemei este numeric stabil, dacă este îndeplinită una dintre condiţiile:10. f~(x)≈f(x) pentru orice intrare x, adică soluţia calculată aproximează bine soluţia exactă.20. există x~ apropiat de x astfel încât f~(x)≈f(x~) – soluţia calculată de algoritmul cu date de intrare exacte este soluţia exactă, cu date uşor perturbate

Stabilitatea numerică a algoritmilorUn algoritm numeric stabil aplicat uneiprobleme bine condiţionate conduce la un rezultat cu precizie foarte bună .

x f(x)x~

f~(x)=f(x~)

Preliminarii matematiceDefiniţie 1: f(h) este O(g(h)) scris f(h)=O(g(h))

dacă ∃c>0, ∃h0>0 a.î.|f(h)|≤c.|g(h)|, pentru orice h ≤h0

Definiţie 2: Fie şirurile {xn} şi {yn}xn=O(yn) dacă ∃c>0, ∃N>0 a.î.|xn|≤c.|yn|, pentru orice n ≥N

Definiţie 3: Fie f(h) aproximat prin p(h) şi ∃M>0, n>0 a.î.

|f(h)-p(h)| / |hn| < M pentru h mic

Preliminarii matematice

Spunem că p(h) aproximează pe f(h) cu ordinul de aproximare O(hn) şi scriem:f(h)=p(h)+O(hn)

Teorema lui Taylor:

( )( ) ( ) ( )∑

=

++⋅=+n

0k

1nk0k

0 hOh!k

xfhxf

c1mnb

Documents