Download - CN - curs 03 - 2015
-
Calcul Numeric
Cursul 3
2015
Anca Ignat
-
1
Surse de erori n calculule numerice
1. Erori n datele de intrare:
- msurtori afectate de erori sistematice sau
perturbaii temporare,
- erori de rotunjire: 1/3 , , 1/7, 2. Erori de rotunjire n timpul calculelor:
- datorate capacitii limitate de memorare a datelor,
operaiile nu sunt efectuate exact.
-
2
3. Erori de discretizare:
- limita unui ir , suma unei serii , funcii neliniare
aproximate de funcii liniare, aproximarea derivatei
unei funcii
4. Simplificri n modelul matematic
- idealizri , ignorarea unor parametri.
5. Erori umane i erori ale bibliotecilor folosite.
-
3
Eroare absolut , eroare relativ
a valoarea exact,
valoarea aproximativ.
Eroare absolut : a- sau |a - | sau a a = Da , |a - | Da Eroare relativ: a 0 sau saua a a
a a a
aa
a ( a se exprim de regul n %).
-
4
n aproximrile 1kg 5g, 50g5g erorile absolute sunt egale dar pentru prima cantitate eroarea relativ este 0,5% iar
pentru a doua eroarea relativ este 10%.
1 2
1 2
1 2 1 2
1 1 2 2
1 2 1 2
, ,
( )
.
a a
a a
a a a a
a a
a a
a1 cu eroare relativ 1a
i a2 cu eroare relativ 2a
: a = a1 * a2 sau 1
2
aa
rezult 1 2a a a
.
-
5
Condiionare stabilitate Condiionarea unei probleme caracterizeaz sensibilitatea
soluiei n raport cu perturbarea datelor de intrare, n ipoteza
unor calcule exacte (independent de algoritmul folosit pentru
rezolvarea problemei).
Fie x datele exacte de intrare, x o aproximaie cunoscut a acestora, P(x) soluia exact a problemei i ( )P x soluia problemei cu x ca date de intrare. Se presupune c s-au fcut calcule exacte la obinerea soluiilor P(x) i ( )P x .
-
6
O problem se consider a fi prost condiionat dac P(x)
i ( )P x difer mult chiar dac eroarea relativ || |||| ||x x
x este
mic.
Condiionarea numeric a unei probleme este exprimat
prin amplificarea erorii relative:
-
7
|| ( ) ( ) |||| ( ) ||( ) pentru 0 si ( ) 0|| ||
|| ||
P x P xP xk x x P xx x
x
O valoare mic pentru k(x) caracterizeaz o problem
bine-condiionat.
Condiionarea este o proprietate local (se evalueaz
pentru diverse date de intrare x). O problem este
bine-condiionat dac este bine-condiionat n orice punct.
-
8
Pentru rezolvarea unei probleme P, calculatorul execut un
algoritm P . Deoarece se folosesc numere n virgul mobil, calculele sunt afectate de erori:
( ) ( )P x P x Stabilitatea numeric exprim mrimea erorilor numerice
introduse de algoritm, n ipoteza unor date de intrare exacte,
|| ( ) ( ) ||P x P x sau || ( ) ( ) |||| ( ) ||
P x P xP x .
-
9
O eroare relativ de ordinul erorii de rotunjire caracterizeaz
un algoritm numeric stabil.
Un algoritm numeric stabil aplicat unei probleme bine
condiionate conduce la rezultate cu precizie foarte bun.
Un algoritm P destinat rezolvrii problemei P este numeric stabil dac este ndeplinit una din condiiile:
-
10
1. ( ) ( )P x P x pentru orice intrare x;
2. exist x apropiat de x, astfel ca ( ) ( )P x P x x = datele exacte,
P(x) = soluia exact folosind date exacte,
( )P x = soluia calculat folosind algoritmul P cu date exacte de intrare
-
11
Rezolvarea sistemelor liniare Istoric
1900 .Hr. , Babilon - apar primele probleme legate de ecuaii liniare simultane
300 .Hr. Babilon - tbli cu urmtoarea problem:Avem dou cmpuri de arie total 1800 ha. Producia la hectar
pe primul cmp este de 2/3 buel (=36,3l) iar pe al doilea
este de 1/2 buel. Dac producia total este de 1100 bueli,
s se determine aria fiecrui teren n parte.
-
12
200-100 .Hr. China 9 capitole despre arta matematic metod de rezolvare foarte asemnatoare eliminrii Gauss
(Avem 3 tipuri de gru. tim c 3 baloturi din primul tip, 2 baloturi din al doilea tip i 1 balot din al treilea tip cntresc 39
msuri. Deasemenea, 2 baloturi din primul tip, 3 baloturi din al
doilea tip i 1 balot din al treilea tip cntresc 34 msuri i 1
balot din primul tip, 2 baloturi din al doilea tip i 3 baloturi din
al treilea tip cntresc 26 msuri. Cte msuri cntrete un
balot din fiecare tip de gru)
-
13
1545, Cardan n Ars Magna, propune o regul (regula de modo) pentru rezolvarea unui sistem de 2 ecuaii cu 2
necunoscute (seamn cu regula lui Cramer)
1683, Seki Kowa, Japonia - ideea de determinant- Method of solving the dissimulated problems. Calculeaz
ceea ce astzi cunoatem sub numele de determinant,
determinanii matricilor 2x2, 3x3, 4x4, 5x5 n legtur cu
rezolvarea unor ecuaii dar nu a sistemelor de ecuaii.
-
14
1683, Leibniz ntr-o scrisoare ctre lHpital explic faptul c sistemul de ecuaii:
10 11 12 020 21 22 030 31 32 0
x yx yx y
are soluie deoarece :
10*21*32+11*22*30+12*20*31=10*22*31+11*20*32+12*21*30
(condiia ca determinantul matricii coeficienilor este 0).
-
15
Leibniz era convins c o notaie matematic bun este
cheia progresului i experimenteaz mai mult de 50 de
moduri diferite de a scrie coeficienii unui sistem de
ecuaii. Leibniz folosete termenul de rezultant n loc de
determinant i a demonstrat regula lui Cramer pentru
rezultani. tia c orice determinant poate fi dezvoltat n
raport cu o coloan operaia se numete azi dezvoltarea
Laplace.
-
16
1750, Cramer prezint o formul bazat pe determinani pentru rezolvarea unui sistem de ecuaii liniare regula lui
Cramer Introduction in the analysis of algebraic curves
(d o regul general pentru sisteme n x n:
One finds the value of each unknown by forming n
fractions of which the common denominator has as
many terms as there are permutations of n things
1764 Bezout, 1771 Vandermonde, 1772 Laplace reguli de calcul al determinanilor
-
17
1773 Lagrange prima utilizare implicit a matricilor n legtur cu formele biliniare ce apar la optimizarea unei
funcii reale de 2 sau mai multe variabile (dorea s
caracterizeze punctele de maxim i minim a funciilor de
mai multe variabile)
-
18
1800-1801, Gauss introduce noiunea de determinant (determin proprietile formei ptratice) Disquisitiones
arithmeticae(1801); descrie operaiile de nmulire
matricial i invers a unei matrici n contextul tabloului
coeficienilor unei forme ptratice. Gauss dezvolt
eliminarea Gaussian pe cnd studia orbita asteroidului
Pallas de unde obine un sistem liniar cu 6 ecuaii cu 6
necunoscute.
-
19
1812, Cauchy folosete termenul de determinant n sensul cunoscut azi.
1826, Cauchy gsete valorile proprii i deduce rezultate legate de diagonalizarea unei matrici. Introduce noiunea de
matrici asemenea i demonstreaz ca acestea au aceeai
ecuaie caracteristic. Demonstreaz c orice matrice real
simetric este diagonalizabil.
-
20
1850, Sylvester introduce pentru prima data termenul de matrice (din latin, uter un loc unde ceva se formeaz
sau este produs, an oblong arrangement of terms)
1855, Cayley algebr matricial, prima definiie abstarct a unei matrici. Studiaz transformrile liniare i compunerea
lor ceea ce l conduce la operaiile cu matrici (adunare,
nmulire, nmulirea cu un scalar, inversa)
-
21
1858, Cayley n Memoriu asupra teoriei matricilor : Sunt multe lucruri de spus despre aceast teorie a matricilor i,
dup prerea mea, aceast teorie ar trebui s precead
teoria determinanilor
Jordan (1870 Treatise on substitutions and algebraic equations forma canonic Jordan), Frobenius (1878 On
linear substituions and bilinear forms, rangul unei matrici),
Peano
-
22
1890, Weierstrass On determinant theory, definiia axiomatic a determinantului
1925, Heisenberg reinventeaz algebra matricial pentru mecanica cuantic
1947, vonNeuman & Goldstine introduc numerele de condiionare atunci cnd analizeaz erorile de rotunjire
1948, Turing introduce descompunerea LU a unei matrici 1958, Wilkinson dezvolt factorizarea QR ....
-
23
Evaluarea erorii n rezolvarea sistemelor liniare
(condiionarea sistemelor liniare)
Fie , ,n n n nA b x i sist. de ec. liniare: Ax b
1 nesingular det 0 sol. sist. A A x A b Pentru erorile n datele de intrare facem notaiile:
eroarea absolut pentrun nA A ; eroarea absolut pentrunb b ;
-
24
n realitate se rezolv sistemul: A A x b b
soluia fiind x : x x x
n mod natural se ridic urmtoarele probleme : 1. dac A nesingular, ?A a.. A A s fie nesingular
? 2. Pp. A i A A nesingulare care sunt relaiile ntre
,A bA b i x
x ?
-
25
1. Pp. A nesingular.
1
1 nesingular nesingularn
n
A A A I A A
A A I A A
Propoziia 5
Fie A nesingular i 11A
A . Atunci I+A-1A este
nesingular i avem:
11 111nI A A A A
-
26
Demonstraie. Avem:
Pr .4 11 1 111 1A A A A A I A AA
11 1 11 11 1I A A A A A A . Pp. c A este nesingular i 1
1AA
.
-
27
11 1 1
11 1
1
1 (1)1
A A x x b b A A x Ax A x b b
A I A A x b A x x I A A A b A x
x I A A A b A x
Ax b Ax xA A
Din Ax =b obinem 1 Ab A xx b
i innd seam
de acest rezultat, din (1) deducem: 1
1 .1A Ax b A
x b AA A
-
28
k(A) = ||A-1|| ||A|| numrul de condiionare al matricii A.
Propoziia 6
Dac matricea A este nesingular i 11A
A atunci:
1k Ax b A
Ax b Ak AA
.
Din In =A A-1 rezult 11 .nI A A k A k(A) 1, A dar dep. de norma matricial natural utilizat.
-
29
O matrice A pentru care numrul de condiionare este mare se
numete matrice prost condiionat (k(A) mare).
Ax=b cu k(A) mare xx poate fi mare chiar dac erorile
relative ib Ab A sunt mici.
-
30
Fie A o matrice simetric TA A , nesingular. Utiliznd norma matricial subordonat normei vectoriale euclidiene:
22
12 2
TA A A A
k A A A
Matricea simetric A are valorile proprii reale 1 2, n , A2 are valorile proprii 2 2 21 2, n A-1 are valorile proprii
1 2
1 1 1, , ....,n .
-
31
11 21
1.... in nA A
1 12 21
1,T nA A A A A A ,
12 2 21
|| || || || nk A A A
numr de condiionare spectral. A matrice ortogonal k2(A)=1
1T T TnA A A A I A A
2 21T TA A A I A
12 2 22 2 1 ,Tk A A A A A
-
32
Matrice aproape singular dar cu numr de condiionare mic 100 100 99 99
1 12 2 2 2 2
diag [1,0.1,0.1, ...,0.1] det 1 (0.1) 10|| || 1 , || || 10 ( ) || || || || 10A A
A A k A A A
-
33
Matrice foarte prost condiionat cu det. nenul (det A=1) 1 2 0 00 1 2 0
,0 0 0 20 0 0 1
A
1 1
2 21
1 2 4 ( 2) ( 2)0 1 2 ( 2) ( 2)
0 0 0 0 1
i n
i n
A
-
34
11 1 1
11 1 100
1 1
|| || || || 3 ,
|| || || || 1 2 2 2 1
100 ( ) || || || || || || || || 3 (2 1)det 1
n n
A AA A
n k A A A A AA
-
35
2 2, ( ) 4002
1.001 2 1.001 2.0012 , 0 1 , 1
x y x yk A
x y x yx y x y
400 201 200 401 201 200, ( ) 4002
800 401 200 800 401 200100 , 200 40000 , 79800
x y x yk A
x y x yx y x y
-
36
2
8
8
1.2969 0.8648 0.86422 , 2 ( ) 249730000
0.2161 0.1441 0.1440
0.9911, 0.4870 ,
0.8642 1.2969 0.8648 0.9911 100.1440 0.1441 0.1441 0.4870 10
x yx y k A
x y
x y
r b Az
-
37
Matricea Hilbert
12
, 10
1( ) ,1
n i jij i j ijH h h x dxi j
4( 1)
3.52 15
4
( 2 1)( )2
nn
nk H en
-
38
n k2(Hn) n k2(Hn) 1 1 7 4.7531082 19.281 8 1.52610103 5.241 102 9 4.93210114 1.551104 10 1.60210135 4.766105 11 5.22010146 1.495107 12 1.6781016
1
2( 1) ( 1)! ( 1)!( )
( 1) ( 1)!( 1)! ( )!( )!
i j
ij ijn i n jH g g
i j i j n i n j
-
39
Metode numerice de rezolvarea sistemelor liniare
Fie matricea nesingular n nA i nb . Rezolvarea sistemului de ecuaii liniare Ax=b se poate face folosind
regula lui Cramer:
det ( ) , 1, ,det
ii
A bx i nA
, n care Ai(b) se obine din matricea A prin nlocuirea coloanei
i cu vectorul b.
Algoritmul dat de regula lui Cramer este foarte costisitor din
punct de vedere al resurselor i instabil numeric.
-
40
Din aceste motive s-au cutat alte metode de aproximare a
soluiei x. Unul din cele mai folosii algoritmi este algoritmul
de eliminare Gauss :
Ax=b cuAx b A matrice superior triunghiular 1 1 (not m )x A b A b Ax b Ax b
-
41
Metoda substituiei
Fie sistemul liniar Ax = b unde matricea sistemului A este
triunghiular. Pentru a gsi soluia unic a sistemului, trebuie
ca matricea s fie nesingular. Determinantul matricilor
triunghiulare este dat de formula:
11 22det = nnA a a a det 0 , 0 = 1,2, ,iiA a i n
-
42
Vom considera nti cazul cnd matricea A este inferior
triunghiular. Sistemul are forma:
11 1 1
21 1 22 2 2
1 1 2 2
1 1 2 2
==
=
=
i i ii i i
n n ni i nn n i
a x ba x a x b
a x a x a x b
a x a x a x a x b
(1)
-
43
Necunoscutele 1 2, , , nx x x , se deduc folosind ecuaiile sistemului de la prima ctre ultima.
Din prima ecuaie se deduce x1:
1111
bxa
(2)
Din a doua ecuaie , utiliznd valoarea x1 din (2) , obinem x2:
2 21 12
22
= b a xxa
-
44
Cnd ajungem la ecuaia i:
1 1 2 2 1 1 =i i ii i ii i ia x a x a x a x b folosind variabilele 1 2 1, , , ix x x calculate anterior, avem:
1 1 1 1= i i ii iiii
b a x a xxa
Din ultima ecuaie se deduce xn astfel:
1 1 2 2 1 1= n n n nn nnnn
b a x a x a xxa
-
45
Algoritmul de calcul a soluiei sistemelor (1) cu matrice
inferior triunghiular este urmtorul: 1
1 , 1,2, , 1,
i
i ij jj
iii
b a xx i n n
a
Acest algoritm se numete metoda substituiei directe.
-
46
Vom considera, n continuare sistemul (1) cu matrice
superior triunghiular :
11 1 1 1 1 1 1 1
1 1
1 1 1 1 1
=
=
=
i i n n n n
ii i in n in n i
n n n n n n n
a x a x a x a x b
a x a x a x b
a x a x b
=nn n na x b
-
47
Necunoscutele 1 2, , , nx x x se deduc pe rnd, folosind ecuaiile sistemului, de la ultima ctre prima.
Din ultima ecuaie gsim xn:
nn
nn
bxa
Folosind valoarea lui xn dedus mai sus, din penultima
ecuaie obinem:
1 11
1 1
= n n n nnn n
b a xxa
-
48
Cnd ajungem la ecuaia i:
1 1 =ii i ii i in n ia x a x a x b se cunosc deja 1 2, , ,i i nx x x de unde ducem:
1 1= i ii i in niii
b a x a xxa
Din prima ecuaie gsim valoarea lui x1:
1 12 2 11
11
= n nb a x a xxa
-
49
Procedeul descris mai sus se numete de metoda substituiei
inverse pentru rezolvarea sistemelor liniare cu matrice
superior triunghiular:
1 , , 1, ,2,1.
n
i ij jj i
iii
b a xx i n n
a
M - numrul de operaii *, / (nmuliri/mpriri) efectuate
A - numrul operaiilor (adunri/scderi) efectuate.
-
50
Atunci pentru calculul componentei xi se efectueaz M=n-i+1, A=n-i i n total:
1
11 1
1
11 ,2
12
n
i n kn
i n k
n nM n i k
n nA n i k
Efortul de calcul pentru metoda substituiei directe este
1 1.
2 2n n n n
M A