cn - curs 07 - 2015
DESCRIPTION
sdTRANSCRIPT
-
Calcul Numeric
Cursul 7
2015
Anca Ignat
-
1
Metode iterative pentru rezolvarea sistemelor de ecuaii liniare = , ,n n nAx b A b (1) se presupune cunoscut c A este nesingular, det A 0; soluia exact a sistemului (1) se noteaz cu *x :
* 1=x A b (2)
n - dimensiunea sistemului este "mare"; A este matrice rar - cu "puine" elemente 0ija ; pentru a aproxima soluia *x matricea A nu se schimb
(transform) ci doar se folosesc elementele nenule ale
matricii ;
se construiete un ir de vectori ( ){ }k nx , ir care n
-
2
anumite cazuri, converge la *x : ( ) * pentrukx x k
O schem general de deducere a unei metode iterative
Fie descompunerea:
= , , ,n nA B C B C R B uor inversabil (3) Ce nseamn B "uor" inversabil? Sistemul liniar, avnd ca matrice a sistemului matricea B:
=Bx f se rezolv uor (adic repede) ca n cazul sistemelor cu matrici diagonale sau triunghiulare, de exemplu.
-
3
* * *
* * * 1 * 1 *
= == = =
Ax b Bx Cx bBx Cx b x B Cx B b Mx d
unde 1 1:= , :=n n nM B C d B b (4) irul ( ){ }kx se construiete astfel: ( 1) ( ) (0):= , = 0,1,2, ales arbitrark k nx Mx d k x (5) Vectorul ( 1)kx poate fi privit i ca soluia sistemului liniar:
( )= cu := kBx f f Cx b (6)
-
4
Cunoscnd vectorul ( )kx , urmtorul element din ir, ( 1)kx , se poate construi fie utiliznd relaia (5) (dac putem construi matricea M explicit), fie rezolvnd sistemul liniar (6).
Matricea M poart numele de matricea iteraiei iar vectorul
(0) nx se numete iteraia iniial. Ne punem problema convergenei irului ( )kx :
( ) * ,kx x k Se tie c aceast convergen nu are loc pentru orice matrice B. Avem urmtorul rezultat general de convergen.
-
5
Teorema de convergen Fie n nA o matrice nesingular i , n nB C , det 0B ,
astfel ca A=B-C. Fie (0) nx un vector oarecare i ( ){ }kx irul de vectori dat de relaia (5) cu M i d dai de (4). Atunci:
( ) * (0), , ( ) < 1kx x k x M (7) unde = | |;( ) max valoare proprie a matriciiM M este raza spectral a matricii M. Dac exist o norm matricial natural
astfel ca ||M|| < 1 atunci irul ( ){ }kx converge la soluia *x a
sistemului (1).
01 , , .kM x x k x (8)
-
6
Demonstraie: Scznd relaiile (5) i x Mx d obinem:
( 1) * ( ) *= ( ) , = 0,1,2,k kx x M x x k Avem:
( ) * ( 1) * 2 ( 2) * (0) *= ( ) = ( ) = = ( )p p p px x M x x M x x M x x ( ) * (0) *= ( ) ,p px x M x x p
Prin urmare: ( ) * , 0 ,p px x p M p
0 , ( ) < 1pM p M Dac:
( ) * (0)|| ||< 1 0 , ,p pM M p x x p x
-
7
Evaluarea erorii absolute ( ) *|| ||kx x
Presupunem ||M||
-
8
( ) ( ) ( ) ( 1) ( 1) ( 2)
( 2) ( 1) ( 1) ( )
1( 1) ( )
=0
=
=
= ( )
k p k k p k p k p k p
k k k k
pk j k j
j
x x x x x x
x x x x
x x
1 1( ) ( ) ( 1) ( ) ( 1) ( )
=0 =0= ( ) = ( )( )
p pk p k k j k j j k k
j jx x x x M x x
Fcnd p obinem:
* ( ) ( ) ( 1)
=0= ( ) ( )k j k k
jx x M M x x
-
9
1
=0|| ||< 1 = ( )j n
jM M I M
Mai avem i evaluarea: 11 1|| ||< 1 || ( ) ||
1 || || 1 || ||nM I M
M M
Prin urmare:
* ( ) ( ) ( 1)|| |||| || || ||1 || ||
k k kMx x x xM
Aceast relaie ne spune c din punct de vedere practic putem opri
algoritmul atunci cnd diferena dintre dou iteraii succesive devine
suficient de mic, acest lucru asigurnd apropierea de soluie.
-
10
Memorarea matricilor rare
- se memoreaz doar valorile nenule i suficiente informaii despre indici astfel ca s se poat reconstitui complet matricea
Pp. c matricea A are NN elemente nenule. Memorare comprimat pe linii Se folosesc 3 vectori:
valori vector de numere reale de dimensiune NN ind_col vector de indici de dimensiune NN inceput_linii vector de ntregi de dimensiune n+1
n vectorii
-
11
valori se memoreaz elementele nenule ale matricii A n ordinea liniilor ind_col se memoreaz indicii de coloan ai elementelor din valori. inceput_linii se stocheaz indicele/poziia n vectorul valori/ind_col al/a primului element de pe linia i memorat n vectorii valori/ind_col.
- inceput_linii(n+1) = NN+1 - inceput_linii(i+1) inceput_linii(i) = numrul de elemente nenule de pe linia i, i=1,n
-
12
102.5 0.0 2.5 0.0 0.03.5 104.88 1.05 0.0 0.330.0 0.0 100.0 0.0 0.00.0 1.3 0.0 101.3 0.0
0.73 0.0 0.0 1.5 102.23
A
n=5, NN=12
valori = ( 102.5, 2.5, 0.33, 1.05, 104.88, 3.5, 100.0, 101.3, 1.3, 1.5, 0.73, 102.23 ) ind_col = ( 1, 3, 5, 3, 2, 1, 3, 4, 2, 4, 1, 5) inceput_linii = (1, 3, 7, 8, 10, 13)
-
13
Dac se tie c matricea are maxim n_max elemente nenule pe fiecare linie se pot folosi 2 matrici pentru memorarea rar: valori matrice de numere reale de dimensiune n x n_max ind_col matrice de indici de dimensiune n x n_max n matricea valori se memoreaz pe linia i elementele nenule de pe linia i a matricii A iar n matricea ind_col se memoreaz indicii de coloan ai elementelor corespunztoare din matricea valori.
-
14
102.5 0.0 2.5 0.0 0.00.0 104.88 1.05 0.0 0.330.0 0.0 100.0 0.0 0.00.0 1.3 0.0 101.3 0.0
0.73 0.0 0.0 1.5 102.23
A
102.5 2.5 0 1 3 0104.88 1.05 0.33 2 3 5
_100.0 0 0 3 0 0101.3 1.3 0 4 2 0102.23 1.5 0.73 5 4 1
valori ind col
-
15
Diagonalele matricii A:
0 11 22
1 12 23 1
1 21 32 1
2 13 24 2
2 31 42 2
: , , ,
: , , ,
: , , ,
: , , ,
: , , ,
nn
n n
nn
n n
nn
d a a a
d a a a
d a a a
d a a a
d a a a
Pentru matricile care au elementele nenule plasate pe cteva din diagonalele matricii A (n_d diagonale cu elemente nenule) se pot folosi pentru memorare o matrice i un vector: diag matrice cu numere reale de dimensiune n x n_d diag_no vector de ntregi de dimensiune n_d
-
16
n matricea diag se memoreaz pe coloane diagonalele cu elemente nenule iar n diag_no este specificat numrul diagonalei care e memorat n coloana j a matricii diag.
_ ( )( , ) i i diag no jdiag i j a
20.5 2.0 0.0 0.0 0.00.0 40.5 3.0 0.0 0.01.0 0.0 100.0 0.0 0.00.0 2.3 0.0 101.5 4.00.0 0.0 3.0 0.0 102.5
A
-
17
20.5 2.040.5 3.0
_ ( 2,0,1)1.0 100.0 0.02.3 101.5 4.03.0 102.5
diag diag no
Alte tipuri de memorri: http://publib.boulder.ibm.com/infocenter/clresctr/vxrx/index.jsp?topic=%2Fcom.ibm.cluster.essl.v5r1.essl100.doc%2Fam501_smstor.html (sparse matrix storage)
-
18
Metoda Jacobi pentru rezolvarea sistemelor liniare
Fie sistemul: = , ,n n nAx b A b
cu det 0 , 0 , = 1,2, ,iiA a i n
Alegem:
11
2211 22
0 00 0
= diag[ , , , ] =
0 0
nn
nn
aa
B a a a
a
11 22det = 0nnB a a a
-
19
11
122
11 22
1 0 0
10 01 1 1= diag[ , , , ] =
10 0
nn
nn
a
aBa a a
a
Matricea C este:
12 13 1
21 23 2
31 32 3
1 2 3
00
0= =
0
n
n
n
n n n
a a aa a aa a aC B A
a a a
-
20
daca
= ( ) =0 daca =
ijn nij ij
a i jC c c
i j
Matricea iteraiei se poate calcula i are forma:
13 112
11 11 11
23 221
22 22 221
31 32 3
33 33 33
1 2 3
0
0
:= = 0
0
n
n
n
n n n
nn nn nn
a aaa a a
a aaa a a
M B C a a aa a a
a a aa a a
-
21
( ) daca= ( ) =
0 daca =
ijn n
iiij ij
ai j
aM m mi j
Construim vectorul g:
( ) ( )1: , = ( )
k n k ni ig Mx Mx g
Componentele vectorului g sunt:
( ) ( ) ( )
=1 =1=1= = = ( ) / , 1, ,
n n nijk k k
i ij j j ij j iij jj iij i j i
ag m x x a x a i n
a
Vectorul d este:
-
22
11= = ( ) , = , 1, ,
n n ii i i
ii
bd B b d d i na
irul ( ){ }k nx se construiete folosind formula:
( 1) ( ) ( 1)= = , = 1, ,k k ki i ix Mx d x g d i n
( )
=1( 1) = , = 1, ,
nk
i ij jjj ik
iii
b a x
x i na
-
23
1( ) ( )
=1 = 1( 1)
( )= , = 1, ,
i nk k
i ij j ij jj j ik
iii
b a x a xx i n
a
(9)
Formula (9) descrie metoda lui Jacobi de aproximare a soluiei unui sistem liniar. Condiii suficiente de convergen
Propoziia 1
( ) *|| ||< 1 ,kM x x k .
Demonstraie. Fie *x soluia sistemului Ax=b. Din relaia A=B-C rezult * *Bx Cx b sau * * .x Mx d Procesul iterativ ( 1) ( )k kx Mx d conduce la relaia:
-
24
11 0* * * *kk k kx x M x x M x x M x x
n continuare vom aplica aceast propoziie pentru diverse norme.
Din 1
2 2
=1 =1|| || = ( ) < 1
n n
F iji j
M m deducem:
2( ) *
=1=1< 1 ,
n nij k
ji iij i
ax x k
a
Din 1=1
|| || = max{ | |; = 1, , } < 1n
iji
M m j n deducem: ( ) *
=1
| |< 1 = 1, , ,
| |
nij k
i iii j
aj n x x k
a
-
25
(Criteriul dominanei diagonalei pe linii)
Din =1
|| || = max{ | |; = 1, , } < 1n
ijj
M m i n deducem: ( ) *
=1
| |( ) < 1 = 1, , ,| |
nij k
j iij i
ai n x x k
a
( ) *
=1lim| |
-
26
Metoda Gauss-Seidel pentru rezolvarea sistemelor liniare
Considerm din nou sistemul liniar: = , ,n n nAx b A b
cu det 0 , 0 , = 1,2, ,iiA a i n
Putem deduce metoda Gauss-Seidel din metoda lui Jacobi astfel:
1( 1) ( ) ( )
=1 = 1
1( 1) ( 1) ( )
=1 = 1
= ( ) / , = 1, , Jacobi
= ( ) / , = 1, , Gauss-Seidel
i nk k k
i i ij j ij j iij j i
i nk k k
i i ij j ij j iij j i
x b a x a x a i n
x b a x a x a i n
Cnd calculm ( 1)kix cunoatem deja ( 1)1
kx ,, ( 1)1kix i putem folosi aceste valori n prima sum.
-
27
Deducerea metodei Gauss-Seidel din schema general se face lund:
11
21 22
31 32 33
1 2 3
0 0 00 0
0=
n n n nn
aa aa a aB
a a a a
daca
= ( ) =0 daca >
ijn nij ij
a j iB b b
j i
Matricea B este nesingular ( 0,iia i ):
11 22det = 0nnB a a a Matricea C este:
-
28
12 13 1
23 2
3
1
00 00 0 0
= =
0 0 00 0 0 0
n
n
n
n n
a a aa a
aC B A
a
daca