CN - curs 04 - 2015
-
Upload
alexbulgaru -
Category
Documents
-
view
231 -
download
0
description
Transcript of CN - curs 04 - 2015
-
Calcul Numeric
Cursul 4
2015
Anca Ignat
-
1
Algoritmul de eliminare Gauss
Algoritmul se realizeaz n n-1 pai prin transformarea sistemului dat ntr-un sistem echivalent cu matrice triunghiular superior. Pas 1
la acest pas se obine sistemul:
unde1 1 1,A x b Ax b A are prima coloan n form superior triunghiular.
-
2
Pas 2 se construiete sistemul
unde2 2 2,A x b Ax b A are primele dou coloane n form superior triunghiular.
Pasul r se obine sistemul unde,r r rA x b Ax b A are primele r coloane n form superior triunghiular.
Pasul n-1 : se obine sistemul
unde1 1 1,n n nA x b Ax b A are primele n-1 coloane n form superior triunghiular.
-
3
Dac la un anumit pas matricea A(r) nu poate fi construit aceasta ne va arta c matricea A este singular. n realizarea acestor pai se utilizeaz urmtoarele operaii elementare: nmulirea unei ecuaii cu un factor i adunarea la alt
ecuaie;
interschimbarea a dou linii i/sau dou coloane n matricea A.
-
4
Pasul 1
Intrare : sistemul Ax=b Ieire : sistemul 1 1 ,A x b Ax b matr A(1) are prima coloan n form superior triunghiular. Fie ecuaia i, cu i=1,,n
1 1 2 2:i i i in n iE a x a x a x b . Presupunem 11 0a . Operaiile efectuate au ca obiectiv anularea coeficienilor lui x1 din ecuaiile de la 2 la n i sunt descrise n continuare:
-
5
1 1211 2 2 21
11
0aE E E aa
1 111 1
11
0i i i iaE E E a
a
1 111 1
11
0n n n naE E E a
a
-
6
Sistemul obinut prin aceste operaii are forma:
1 1 1 111 1 12 2 1 1
1 1 122 2 2 2
1 1 12 2
1 1 12 2
n n
n n
i in n i
n nn n n
a x a x a x b
a x a x b
a x a x b
a x a x b
sau
-
7
1 11 1 1 1
1 11
11
11
1 11
11
, 1, , , .
, 2, , ; 2, , .
0, 2, , .
, 2, , .
j j
iij ij j
i
ii i
a a j n b b
aa a a i n j na
a i nab b b i na
-
8
Pas 2
Intrare : 1 1A x b Ieire : 2 2 2,A x b Ax b A are primele dou coloane n form superior triunghiular. Se presupune 122 0a i se urmrete anularea elementelor 2 2 232 42 2, , , na a a (transformarea coloanei 2 n form superior
triunghiular). Operaiile efectuate asupra ecuaiilor 1 , 3, ,iE i n sunt urmtoarele :
-
9
11 1 2 232
2 3 3 32122
11 1 2 22
2 2122
11 1 2 22
2 2122
0;
0;
0;
ii i i
nn n n
aE E E aa
aE E E aa
aE E E aa
-
10
Obinem pentru matricea A(2) i vectorul b(2) relaiile:
21 1
2 12 2
12 1 12
2122
21
22
2 2 11 1 2 2
12 1 (1)2
2122
, 1, ,
, 2, ,
, 3, , ; 3, ,
0, 2, ,
0, 3, ,
,
, 3, , .
j j
j j
iij ij j
i
i
ii i
a a j n
a a j n
aa a a i n j na
a i n
a i n
b b b b
ab b b i na
-
11
Se observ c nu se schimb forma superior triunghiular a primei coloane.
Pas r
Intrare : 1 1r rA x b Ieire : ,r r rA x b Ax b A are primele r coloane n form superior triunghiular.
-
12
Sistemul are forma urmtoare:
1 1 1 111 1 1 1 1
1 1 1
1 1 11 1 1
r r r rr r n n
r r rrr r rn n r
r r rr r r r n n r
rir
a x a x a x b
a x a x b
a x a x b
a
1 1 1
1 1 1
r rr in n i
r r rnr r nn n n
x a x b
a x a x b
-
13
Presupunem 1 0.rrra
Vom urmri anularea elementelor 1 2, , , .r r r
r r r r nra a a
11 11
1 1 11
11 1
1
11 1
1
0;
0;
0;
rr r r rr r
r r r r rrrr
rr r r rir
r i i irrrr
rr r r rnr
r n n nrrrr
aE E E aa
aE E E aa
aE E E aa
-
14
1 1
1
11 1
1
1 1
1
11 ( 1
21
, 1, , ,
, 2, , , , ,
, 1, , ; 1, , .
0, 1, , , 1, , .
,
, 2, , ,
rj j
r kkj kj
rr r rir
ij ij rjrrr
rij
r
r jj j
rr r rir
i i rrr
a a j n
a a k r j k n
aa a a i r n j r na
a j r i j n
b b
b b j r
ab b ba
) , 1, , .i r n
-
15
Se observ c nu se schimb forma superior triunghiular a primelor r-1 coloane. La fiecare pas s-a fcut ipoteza 1 0rrra
. Elementul 1rrra poart numele de pivot. n cazul n care elementul pivot este nul se pot aplica urmtoarele strategii, numite de pivotare:
-
16
Pivotare ( ( 1) 0 ?rrra )
10 Fr pivotare Se caut primul indice 0 , 1, ,i r r n astfel nct
0
1 0ri ra . Se interschimb liniile i0 i r.
S observm c n procesul de calcul la pasul r intervine
factorul 11r
rra astfel c valori mici ale lui
1rrra conduc la
amplificarea erorilor de calcul. Pentru a asigura stabilitatea numeric a procesului de calcul este de dorit ca 1rrra
s fie
mare.
-
17
20 Pivotare parial Se determin indicele i0:
0 1 1max ; , ,r ri r ira a i r n i se interschimb liniile dac0 0, .i r i r 30 Pivotare total Se determin indicii i0 i j0:
00 1 1max ; , , , , ,r ri j ija a i r n j r n i se interschimb liniile dac0 0,i r i r i coloanele
dac0 0,j r j r
-
18
Schimbarea coloanelor implic schimbarea ordinii variabilelor astfel nct n final va trebui refcut ordinea iniial a variabilelor. Dac dup pivotare elementul pivot rmne nul, 1 0 ,rrra atunci putem deduce c A(r-1) este singular.
n adevr, dac n procesul de pivotare parial 1 0 ,rrra atunci
-
19
11 12 1
( 1)
1 1 1 111 22 1 1
00
det det 0
0
n
rr rnr
nn
rn
r r r rr r
nn
a a a
a aA
aa
A a a a
a
-
20
Deoarece operaiile efectuate (cele de inetrschimbare de linii i/sau coloane) nu au schimbat dect semnul determinantului avem:
1det det 0 det 0rA A A prin urmare matricea A iniial este singular. i n cazul procesului de pivotare total dac 1 0 ,rrra atunci:
-
21
11 12 1
( 1)
1 1 1 111 22 1 1
0
00 00 0
det det 0
0 0
n
rrr
r r r rr r
a a a
aA
A a a a
1det det 0rA A A este matrice singular.
-
22
1;pivotare( );while ( -1 i | | > )
// Pas rfor 1, ,
- ;
for 1, , * ;
rr
ir
rr
ij ij rj
rr
r n a
i r nafa
j r na a f a
( 1) ( 1)
0; * ; 1;
pivotare( );if (| | ) 'MATRICE SINGULARA'
else { ,se rezolv sistemul triunghiular superior
ir
i i r
rrn n
ab b f b
r rr
aA A b b
Ax
}b
-
23
Numrul de operaii efectuate la pasul r i n total este:
1 12
1 11 1
2
1 1
3 32 2
( ) 1 1 1
1 2 5M : 2 ,
61 1A : ,
3
M : ; :3 3
n n
r rn n
r r
n r M n r A n r M A M
n n nn r n r
n n nn r n r
n nn n
-
24
Eliminarea chinezeasc 200-100 .Cr. 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
-
25
Notaia actual: Notaia chinezeasc
1 2 3
1 2 3
1 2 3
3 2 392 3 34
2 3 26
b b bb b b
b b b
1 2 32 3 23 1 126 34 39
-
26
Pasul 1 Se nmulete coloana a doua cu 3 i se scade din ea coloana a treia att timp ct este posibil. Se nmulete prima coloan cu 3 i se scade din ea coloana a treia att timp ct este posibil. Se ajunge la forma:
0 0 34 5 28 1 139 24 39
-
27
Pasul 2 Se nmulete prima coloan cu 5 i se scade din ea coloana a doua att timp ct este posibil. Se ajunge la forma:
0 0 30 5 236 1 199 24 39
Pentru rezolvare se folosete metoda substituiei inverse pe sistemul obinut mai sus.
-
28
Descompuneri LU
n nA , A=LU, L inferior triunghiular i U superior triunghiular
, n nL U soluiasoluia
1== = ,=
Ly b yAx b LUx b x A b
Ux y x
-
29
Fie minorul principal principal al matricii A:
11 12 1
21 22 2
1 2
, 1, ,
p
p p pp
p p pp
a a a
a a aA p n
a a a
-
30
Teorem (descompunere LU) Fie n nA o matrice real ptratic de dimensiune n astfel nct det 0pA , = 1, ,p n . Atunci exist o unic matrice inferior triunghiular , =1,...,= ( )ij i j nL l cu = 1, = 1, ,iil i n i o unic matrice superior triunghiular , =1,...,= ( )ij i j nU u astfel nct A = LU (1)
Demonstraie. Existena: demonstraia se face prin inducie dup n dimensiunea matricii A.
-
31
Algoritmul Doolittle de calcul al descompunerii LU
Fie n nA o matrice real ptratic de dimensiune n care satisface ipotezele teoremei de mai sus. Algoritmul de calcul al matricilor L i U are n etape. La fiecare pas se determin simultan:
- cte o linie din matricea U i - cte o coloan din matricea L.
Descriem n continuare, un pas oarecare. Pasul p ( = 1,2, ,p n )
Se determin elementele liniei p ale matricii U , , = , ,piu i p n , i elementele coloanei p ale matricii L,
-
32
, = 1, ,ipl i p n = 1ppl (upi= lip =0, i=1,,p-1). lin. a matr. 10 0 pp pp pnu u u p U
col. a matr.
1
00
1
p p
np
p Ll
l
-
33
Se cunosc de la paii anteriori: - elementele primelor p-1 linii din U (elemente kju cu = 1, , 1,k p j ) i - elementele primelor p-1 coloane din L (elemente ikl cu = 1, , 1,k p j ).
Calculul elementelor liniei p din matricea U,
= , ,piu i p n se face folosind elementul api i (LU)pi. Avem:
=1 =11
=1
= ( ) ( = 0, = 1, , ) = =pn
pi pi pk ki pk pk kik k
p
pp pi pk kik
a LU l u l k p n l u
l u l u
-
34
Pentru = , ,i p n avem:
1
1, , ,
p
pi pi pk kik
u a l u i p n
(2)
( = 1ppl , pkl , kiu = 1, , 1k p sunt elemente de pe coloane din L i linii din U calculate la paii anteriori) Calculul elementelor coloanei p din matricea L:
, = 1, ,ipl i p n ( = 0 , = 1, , 1 , = 1ip ppl i p l ) se face analog:
-
35
=1 =11
=1
= ( ) ( = 0, = 1, , ) = =pn
ip ip ik kp kp ik kpk k
p
ip pp ik kpk
a LU l u u k p n l u
l u l u
Dac 0ppu putem calcula elementele nenule ale coloanei p din matricea L astfel:
1
1( )
, 1, ,
p
ip pk kik
ippp
a l ul i p n
u
(3) (elementele pkl , kiu = 1, , 1k p sunt calculate anterior pasului p)
-
36
Dac = 0ppu , calculele se opresc, descompunerea LU nu poate fi calculat - matricea A are un minor pA cu determinantul 0. Unicitatea: Demonstraie prin reducere la absurd. Facem observaia c inversa unei matrici nesingulare triunghiular inferior (superior) este o matrice de acelai tip. Presupunem c 1 1A L U L U (4)
-
37
Din ipoteza A nesingular rezult existena inverselor matricilor 1 1, , ,L L U U . nmulind egalitatea (4) la stnga cu L-1i cu 11U la dreapta obinem
1 11 1U U L L .
Matricea 1 1L L este inferior triunghiular cu elementele
diagonale egale cu 1 iar matricea 11U U este superior
triunghiular. Rezult c: 1 11 1 nU U L L I
, deci L=L1 , U=U1.
-
38
Descompunerea Cholesky
O matrice n nA se numete pozitiv definit dac:
, 0 , 0n nAx x x x Notaie: A > 0
Fie n nA o matrice simetric (A=AT ) i pozitiv definit. Descompunerea Cholesky pentru matricea A este de forma:
A = LLT , L matrice inferior triunghiular
-
39
11 11 21 111 1
21 22 22 2
11 2
0 00 0
0 0
nn
nT
n nnn n nn nn
l l l la a
l l l lA LL
a al l l l
Matricea L se calculeaz n n pai, coloan dup coloan.
-
40
Pas r (r=1,,n) Se calculeaz elementele coloanei r a matricii L: nti elementul diagonal lrr apoi celelalte elemente lir (i=r+1,n) Coloana r a matricii L: 10 0 Trr r r ir nrl l l l - se cunosc elementele primelor (r-1) coloane ale matricii L
-
41
Calcul lrr:
1
1
1 1 1
12 2 2 2 21 2 1
1
0 00
0
r
rrT
rr r rr rr rrrr
r
r r rr rr rr rr rkk
l
la LL l l l l
l l l l l a l
-
42
Calcul lir (i=r+1,,n):
1
1
1 1
1
11 1 2 2 1 1
00
0
r
rrT
ir i ir ir ii rrir
r
ir ik rkk
i r i r ir rr ir rr irrr
l
la LL l l l l l
a l ll l l l l l l l l
l
-
43
Algoritmul de eliminare Gauss fr schimbare de linii descompunere LU
Presupunem c la fiecare pas al algoritmului de eliminare
Gauss pivotul este nenul ( ( 1) 0rrra ), deci nu e nevoie de
schimbare de linii.
Algoritmul se poate scrie astfel:
-
44
for 1, , 1for 1, ,
;
/ /for 1, ,
;
0;;
ir
rr
i i r
ij ij rj
ir
i i r
r ni r n
afa
E E f Ej r na a f a
ab b f b
Considerm vectorul i matricea:
-
45
( ) ( )( )
1
( )
0
0, :r n r T n nr r n r
r
rn
t T I t et
t
-
46
col r
lin
( )( )
( )11
( )( )
0 0 0 0 0
0 0 0 0 00 1 0 00 0 0 1)
0 0 0
r Trr
rrr
rrn
n
t et t r
t t
-
47
Matricea Tr este matrice triunghiular inferior cu 1 pe diagonala principal:
( )1
( )
col
1 0 0 00 1 0 0
0 0 1rr
r
rn
r
Tt
t
-
48
Inversa matricii Tr este
1 ( )r Tr n rT I t e .
1 ( ) ( ) ( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( )( )
(0 )
r T r T r T r T r T r Tr r n r n r n r r r r
r r T r T rn r r n r r
T T I t e I t e I t e t e t e t e
I t t e I t e t
Dac A este o matrice oarecare, vrem s vedem cum se poate construi matricea B=Tr A fr a face nmulire matricial. Vom studia legtura ntre liniile matricilor A i B.
-
49
( ) ( )
( )
( ) ( )
( )
T T T r T T T r Ti i r i n r i i r
T r Ti i r
e B e T A e I t e A e A e t e A
e A t e A
Linia i a noii matrici B se obine din linia i a matricii A la care se adaug linia r a matricii A nmulit cu factorul ( )rit .
( )
( )
1, , ( 0)
( ) 1, ,
T ri iT
i T r Ti i r
e A i r te B
e A t e A i r n
.
-
50
Operaia TrA descrie Pasul r al algoritmului de eliminare Gauss dac:
( ) ( )( )( ) ( ) ( )1
1 ( ) ( ) ( ), , , ,r rr
r r rir nrr rr i nr r r
rr rr rr
a aat t ta a a
.
Algoritmul de eliminare Gauss fr schimbare de linii poate fi descris astfel:
cu ( )1 2 1r T
n r n rT T T A U T I t e , ( ) ( )( )
( ) 1( ) ( ) ( )0 0 ( ) ( ) ( )
Tr rrr ir nrr r
r r rrr rr rr
a aata a a
.
-
51
Avem:
1 1 1 1 1 11 2 1 1 2 1, :n nA T T T U LU L T T T
1 1 (1) (2) (1) (2) (1) (2)1 2 1 2 1 2 1 2
(1) (2) (1) (2) (1) (2) (2)1 2 1 2 1 2 1
( )( )
( 0)
T T T T T Tn n n
T T T T Tn n
T T I t e I t e I t e t e t e t e
I t e t e t t e I t e t e t
Prin inducie se arat c:
1 1 1 (1) (2) ( 1)1 2 1 1 2 1
T T n Tn n nL T T T I t e t e t e
-
52
21
11(1)
31 32(1)
11 22
1
11
1 0 0 0
1 0 0
0 0
r
aaa aa a
L aa
(1)2
(1)22
(1) ( 1)11 12 1
(1) ( 1)11 22
(1) ( 1)1 2
(1) ( 1)11 22
0
0
r
rr r r r
rrr
rn n nr
rrr
aa
a a aa a a
a a aa a a