c1mnB
-
Upload
danutzughe -
Category
Documents
-
view
12 -
download
3
description
Transcript of 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
Reprezentarea în virgulă mobilă
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 .
Reprezentarea în virgulă mobilă
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
Aritmetica în virgulă mobilă
Î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.
Aritmetica în virgulă mobilă
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
Aritmetica în virgulă mobilă
(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
ε ⋅−
+⋅−
=−
Aritmetica în virgulă mobilă
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 −=
Aritmetica în virgulă mobilă
- 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
Aritmetica în virgulă mobilă
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+ ε)
Aritmetica în virgulă mobilă
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.
Condiţionarea problemelor
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 ~
~
−
−
=
Condiţionarea problemelor
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