cn - curs 08 - 2015
Post on 07-Nov-2015
235 Views
Preview:
DESCRIPTION
TRANSCRIPT
-
Calcul Numeric
Cursul 8
2015
Anca Ignat
-
1
Metode iterative pentru matrici simetrice i pozitiv definite
Considerm cazul sistemelor liniare cu matricea sistemului simetric i pozitiv definit:
= matrice simetrica = , = 1,2,T ij jiA A a a i j n
11 12 13 1 11 21 31 1
21 22 23 2 12 22 32 2
31 32 33 3 13 23 33 3
1 2 3 1 2 3
= = =
n n
n nT
n n
n n n nn n n n nn
a a a a a a a aa a a a a a a aa a a a a a a aA A
a a a a a a a a
= =T TA A A L D L
-
2
11
2211 22
0 00 0
= diag[ , , , ] =
0 0
nn
nn
aa
D a a a
a
12 13 1
23 221
331 32
11 2 3
00 0 0 0
0 00 0 0
0 0 00 0= =
0 0 00
0 0 0 0
n
n
nT
n nn n n
a a aa a
aa
a aL L
aa a a
-
3
Definiii Matricea simetric n nA se numete pozitiv semidefinit (A 0): , 0n nAx x x . Matricea simetric A se numete pozitiv definit (A > 0) dac:
, 0 , 0n nAx x x x . Propoziie Dac matricea n nA este pozitiv definit atunci matricea A este nesingular. Demonstraie: Presupunem prin reducere la absurd c matricea A este pozitiv definit i singular. Atunci, sistemul de ecuaii liniare
-
4
Ax=0 are pe lng soluia banal x=0 i o soluie x0 0 . Avem: 0 0 0 00 0 , 0, 0 contradic ie!x Ax x x
0 , 0 1, ,ii i iA a Ae e i n Lem
Fie n nA o matrice simetric i n nB o matrice nesingular astfel nct matricea P = B + BT - A este pozitiv definit. Fie matricea M = In - B-1A. Atunci raza spectral a matricii M este strict subunitar dac i numai dac matricea A este pozitiv definit:
( ) < 1 > 0M A
-
5
Teorem
Fie n nA o matrice simetric, nesingular, cu diagonala pozitiv, aii > 0, = 1, ,i n i nb vectorul termenilor liberi. Atunci metoda lui Gauss-Seidel genereaz iruri convergente la soluia * 1=x A b , x(0) dac i numai dac A este pozitiv defnit.
Demonstraie: Din teorema de convergen avem: ( ) * , ( ) < 1kx x k M
Dac matricea A se scrie sub forma:
= TA L D L matricile B i C sunt date de:
= , = = TB L D C B A L
-
6
Matricea iteraiei M este: 1 1 1= = ( ) = nM B C B B A I B A
ncercm s aplicm Lema de mai sus. Pentru aceasta verificm
dac matricea P este pozitiv definit:
= = ( ) =T T TP B B A L D L D L D L D 2
=1( , ) = ( , ) = (( ) ,( ) ) =n n n
n
pp p p i i ii ii
Px x Dx x a x x a x > 0 ( , ) > 0 , 0 > 0n niia i Px x x x P
Putem aplica Lema de unde deducem convergena irului construit cu metoda Gauss-Seidel doar n cazul n care matricea A este pozitiv definit:
pozitiv definit( ) * , ( ) < 1kx x k M A
-
7
Metodele relaxrii
Fie n nA o matrice real ptratic de dimensiune n, simetric, A=AT i pozitiv definit, A > 0 i nb un vector real. Considerm sistemul de ecuaii liniare:
Ax = b
Deoarece matricea A este pozitiv definit sistemul de mai sus are soluie unic, * 1=x A b . Vom considera funcia : nf : ( ) ( ), ,n nf y A x y x y y Din faptul c matricea A este pozitiv definit avem:
( ) 0 , i ( ) ( ) ,nf y y f y f x y x
-
8
Prin urmare x* este i unica soluie a problemei de minimizare: min ( ) ; 0 ( )nf y y f x
Vom cuta soluia sistemului Ax=b, * 1=x A b ca fiind soluia problemei de minimizare de mai sus folosind o metod de tip relaxare de forma:
(0) ( 1) ( )
( 1) ( ) ( 1) ( )
dat, , 0,1,
, ,
n k kk l k
k k k kj j l l k
y y y c e l l k
y y j l y y c
Constanta ck se determin astfel nct ( 1) ( )( ) ( )k kf y f y n sperana c irul y(k) astfel construit converge la x*.
-
9
Notm cu :
r(k) = b - Ay(k) vectorul reziduu. Avem:
( ) ( ) ( ) ( )( )k k k kr b Ay Ax Ay A x y
( 1) ( ) ( ) 2( ) ( ) 2k k kk l k llf y f y c r c a
Pentru ca ( 1) ( )( ) ( )k kf y f y este necesar i suficient s alegem ck astfel ca:
( ) ( )2 ( )
( )
2 ( 0) 0, 2 sau 2 , 0
, cu 0,2
k kk l l
k ll k l ll kll ll
kl
k k kll
r rc a c r a ca a
rca
-
10
Metoda de relaxare obinut este urmtoarea:
( )(0) ( 1) ( )dat, 0,1, , 0,2kn k k lk l kll
ry y y e ka
Pentru a aproxima x* se deduce o clas de metode numite metodele relaxrii successive. Aceste metode se obin aplicnd metodele de relaxare de mai sus. Vom considera:
,k k Vom construi un ir ( )k nx astfel:
-
11
(0) (0)
(0)(1) (0) 1
111(1)
(2) (1) 22
22
( 1)( ) ( 1)
(1) ( )
un vector din dat
1
2
n
nn n n
nnn
n
x yrl y y earl y y ea
rl n y y ea
x y
-
12
Trecerea de la iteraia k la iteraia urmtoare se face astfel:
( ) ( )
( )( 1) ( ) 1
111
( 1)( 2) ( 1) 2
222
( 1)( ) ( 1)
( 1) (( 1) )
1
2
, 0,1,2,
k kn
knkn kn
knkn kn
kn nkn n kn n n
nnn
k k n
x yrl y y ea
rl y y ea
rl n y y ea
x y k
-
13
Acum putem scrie dependena vectorului x(k+1) de x(k): (0)
1( 1) ( ) ( 1) ( )
1
1( 1) ( ) ( 1) ( )
1 1
0,2 date,
, 1,2, , ,
) , 1,2, , ,
n
i nk k k k
i i i ij j ij jj j iii
i nk k k k
i i i ij j ij jj j iii
x
x x b a x a x i na
x x b a x a x i na
k
0,1,2,
Metodele de mai sus poart numele de metodele relaxrii successive. Pentru 1 obinem metoda Gauss-Seidel.
-
14
o 0 1 metodele se numesc de sub-relaxare i pot fi folosite n
cazul cnd metoda Gauss-Seidel diverge. o 1 2 metodele se numesc de supra-relaxare i pot fi folosite
pentru accelerarea convergenei n cazul cnd metoda Gauss-Seidel converge.
Rearanjnd formulele de mai sus avem:
1( 1) ( 1) ( 1) ( ) ( )
1 1
( )
(1 )i nk k k k kiiij j i ii i ij j ii
j j i
kii
aa x x B x a x a x b
C x b
Matricea A fiind simetric, poate fi scris sub forma:
-
15
21
1 2 1
11 22
0 0 00 0
cu ,
0
diag , , ,
T
n n n n
nn
aA L D L L
a a a
D a a a
Cu aceste notaii, matricile B i C de mai sus pot fi scrise astfel:
1 1, TB L D C D L
Vom verific dac metodele relaxrii succesive se nscriu n clasa general de metode iterative, adic vom verifica dac A=B-C :
-
16
1 1 T TB C L D D L L D L A
Convergena irului x(k) la soluia x*=A-1b ? Teorem Fie o matrice n nA , simetric, A=AT cu detA 0, aii>0 ,
1, ,i n , nb un vector real i 0,2 . Atunci irul x(k) construit cu o metoda de relaxare successiv converge la soluia x* a sistemului liniar Ax=b oricare ar fi iteraia iniial x(0) dac i numai dac matricea A este pozitiv definit.
( ) (0), , ) 0 , 0k nx x k x Ax x x x
-
17
Demonstraie: Vom verifica dac raza spectral a matricii iteraiei este subunitar folosind Lema. Avem: 1 1 1nM B C B B A I B A
11 221 1, det 0 ( 0 , )nn iinB L D B a a a a i
Matricea A este simetric iar matricea B este nesingular. Pentru a fi ndeplinite ipotezele Lemei trebuie s verificm c matricea P este pozitiv definit:
1 1 2T T TP B B A L D L D L D L D
-
18
2
1
(2 ), 0 0 0, )
(2 ) 0 0,2
n
ii i iii
Px x a x x a i
Toate ipotezele lemei sunt ndeplinite, prin urmare avem convergena dorit.
-
19
Valori i vectori proprii (eigenvalues, eigenvectors)
Definiie Fie n nA . Numrul complex se numete valoare proprie a matricii A dac exist un vector , 0nu u astfel ca:
Au=u Vectorul u se numete vector propriu asociat valorii proprii . Pentru existena vectorului 0u este necesar i suficient ca matricea (In A) s fie singular , adic det(In A)=0.
-
20
Polinomul de grad n: detA np I A se numete polinom caracteristic al matricii A. Propoziia 1 Fie rdcinile polinomului caracteristic 1, 2, ..., n distincte, i j pentru 1 i j n i 1 2, , , nu u u vectorii proprii corespunztori. Atunci 1 2, , , nu u u sunt liniar independeni. (demonstraia se face prin inducie)
-
21
Propoziia 2 Fie valorile proprii i ale matricii n nA distincte. Atunci exist o matrice nesingular T astfel ca:
11 2diag[ , , , ]nT AT .
Demonstraie. Fie 1 2, , , nu u u vectorii proprii ai matricii A. Considerm matricea T ale crei coloane sunt vectorii proprii ui ,
1 2 ]nu u u . Deoarece vectorii proprii sunt liniar independeni conform propoziiei 1 rezult c matricea T este nesingular. Vom avea: 1 2 1 1 2 2 1 2.diagn n n nAT Au Au Au u u u T nmulind cu T-1 obinem concluzia propoziiei 2.
-
22
Definiie Matricile A i B sunt asemenea (notaie AB) dac i numai dac exist o matrice nesingular T (det T 0) astfel ca:
A=T B T -1 Propoziia 3 .A BA B p p Demonstraie.
1 1 1
1 1
det( ) det det
det det( )det detA n n
n n B
p I A I TBT TT TBT
T I B T T I B T p
Propoziia 3 ne spune c matricile asemenea au acelai polinom caracteristic i aceleai valori proprii.
top related