Inversa Unei Matrice 3p2ex

CAPITOLUL II METODE DIRECTE DE CALCUL A INVERSEI UNEI MATRICE 2.1. Metoda complemenţilor algebrici Dacă A = (aij) ∈ Mn (C), pentru aflarea inversei matricei date se procedează astfel: se calculează transpusa matricei şi apoi se înlocuiesc elementele sale prin complemenţii algebrici ai lor. Matricea astfel obţinută se numeşte matrice adjunctă (sau asociată, sau reciprocă) matricei A şi se notează A*. Inversa matricei A este A-1 =

1 A*. d

Explicit, această metodă decurge astfel:  a11 a12   a 21 a 22 A=  . .   an1 an 2 

... a1n   ... a 2 n  ... .   ... ann 

Calculăm det A. Dacă d = det A ≠ 0, atunci matricea A este inversabilă. Scriem matricea transpusă a matricei A, schimbând în matricea A liniile cu coloanele.  a11 a 21   a12 a 22 t A=  . .   a1n a 2 n 

... an1   ... an 2  ... .   ... ann 

Scriem matricea adjunctă a matricei A, notată A*, înlocuind fiecare element al matricei transpuse tA prin complementul său algebric, notat dij = (-1)i+jAij, i, j = 1, n , unde Aij este minorul elementului aij din matricea tA (determinantul obţinut din tA prin eliminarea liniei i şi a coloanei j). Complemenţii algebrici se mai numesc şi cofactori. Deci:  d 11 d 21   d 12 d 22 A* =  . .   d 1n d 2 n 

... dn1   ... dn 2  ... .   ... dnn 

Împărţim toate elementele matricei A* prin valoarea determinantului d (d = detA) şi matricea obţinută este A-1. Avem: A-1 =

1 A* sau, explicit: d  d 11   d  d 12 A-1 =  d  .  d 1n   d

d 21 d d 22 d . d 2n d

dn1   d  dn 2  ... d , d ≠ 0 ... .  dnn  ...  d  ...

−1 −1 Se verifică că are loc: A ⋅ A = A ⋅ A = I n

Pentru exemplificare, considerăm matricea:  2 1 − 3   A=  1 5 4   − 1 2 − 3   Să se determine inversa matricei A şi apoi să se verifice prin calcul direct relaţia: A ⋅ A −1 = A −1 ⋅ A = I n Calculăm determinantul său şi obţinem: 2 1 −3 d = detA = 1 5 4 = − 30 − 6 − 4 − (15 − 3 + 16) = −40 − 28 = −68 ≠ 0 −1 2 − 3 −1 Determinantul său fiind nenul, matricea sa este inversabilă şi A =

1 * A d

Scriem transpusa: t

 2 1 − 1   A=  1 5 2   − 3 4 − 3  

Determinăm complemenţii algebrici ai elementelor matricei tA, de forma d ij = ( − 1) d11 = ( − 1)

1+1

d12 = ( − 1)

1+ 2

5 2 = 1 ⋅ ( − 15 − 8) = −23 4 −3 1 2 = ( − 1) ⋅ ( − 3 + 6 ) = ( − 1) ⋅ 3 = −3 −3 −3

i+ j

Aij

d13 = ( − 1)

1+ 3

d 21 = ( − 1)

2 +1

d 22 = ( − 1)

2+ 2

d 23 = ( − 1)

2+3

d 31 = ( − 1)

3+1

d 32 = ( − 1)

3+ 2

d 33 = ( − 1)

3+ 3

1 5 = 1 ⋅ ( 4 + 15) = 19 −3 4 1 −1 = −1 ⋅ ( − 3 + 4 ) = −1 ⋅ 1 = −1 4 −3 2 −1 = 1 ⋅ ( − 6 − 3) = −9 −3 −3 2 1 = ( − 1) ⋅ ( 8 + 3) = −11 −3 4 1 −1 = 1 ⋅ ( 2 + 5 = 7) 5 −2 2 −1 = ( − 1) ⋅ ( 4 + 1) = −5 1 2 2 1 1 5

= 1 ⋅ (10 − 1) = 9  − 23 − 3 19    A =  − 1 − 9 − 11  7 − 5 9   *

 23   − 23 − 3 19   68  1  1 −1 Deci, A = − ⋅  − 1 − 9 − 11 =  68  68 − 5 9   − 7  7   68

3 68 9 68 5 68

− 19   68  11  68  −9   68 

 23   2 1 − 3   68   1 −1 Se constată că: A ⋅ A =  1 5 4  ⋅   − 1 2 − 3   68   −7   68

3 68 9 68 5 68

− 19   68   1 0 0   11   = 0 1 0 = I3 68    − 9  0 0 1  68 

- înmulţim linia 1 cu coloana 1 şi obţinem: 2 ⋅ 23 1 − 3 ⋅ ( − 7 ) 46 + 1 + 21 68 + + = = =1 68 68 68 68 68 - înmulţim linia 1 cu coloana 2 şi obţinem: 2 ⋅ 3 9 3 ⋅ 5 6 + 9 − 15 0 + − = = =0 68 68 68 68 68 - înmulţim linia 1 cu coloana 3 şi obţinem: 2 ⋅ ( − 19 ) 11 3 ⋅ 9 − 38 + 11 + 27 0 + + = = =0 68 68 68 68 68

- înmulţim linia 2 cu coloana 1 şi obţinem: 23 5 4 ⋅ 7 23 + 5 − 28 0 + − = = =0 68 68 68 68 68 - înmulţim linia 2 cu coloana 2 şi obţinem: 3 5 ⋅ 9 4 ⋅ 5 3 + 45 + 20 68 + − = = =1 68 68 68 68 68 - înmulţim linia 2 cu coloana 3 şi obţinem: − 19 5 ⋅ 11 4 ⋅ 9 − 19 + 55 − 36 0 + − = = =0 68 68 68 68 68 - înmulţim linia 3 cu coloana 1 şi obţinem: − 23 2 3 ⋅ 7 − 23 + 2 + 21 0 + + = = =0 68 68 68 68 68 - înmulţim linia 3 cu coloana 2 şi obţinem: − 3 2 ⋅ 9 3 ⋅ 5 − 3 + 18 − 15 0 + − = = =0 68 68 68 68 68 - înmulţim linia 3 cu coloana 3 şi obţinem: 19 2 ⋅ 11 3 ⋅ 9 19 + 22 + 27 68 + + = = =1 68 68 68 68 68 −1 Analog, se arată că A ⋅ A = I 3

2.2. Metoda ecuaţiei caracteristice Această metodă poartă acest nume pentru că, în cele ce urmează, vom calcula inversa matricei A ∈ M n ( C ) , nesingulară, cu ajutorul ecuaţiei ei caracteristice. Determinantul caracteristic al matricei A, det (λE – A), este de fapt un polinom de gradul n în raport cu λ. Ecuaţia det (λE – A) = 0 se numeşte ecuaţia caracteristică a matricei A. Utilizând coeficienţii polinomului, precum şi puterile A, A2, A3, ......, An-1 ale matricei −1 A, se poate obţine relativ uşor inversa A ∈ M n ( C ) n n −1 (2.2.1.) det (λE – A) = λ + p1λ + ... + p n −1λ + p n

Atunci, conform identităţii lui Hamilton-Cayley, avem:

n n −1 (2.2.2.) A + p1 A + ... + p n −1 A + p n E = 0 , 0 ∈ M n ( C )

Înmulţind (2.2.2.) cu A −1 obţinem: n −1 n −2 (2.2.3.) A + p1 A + ... + p n −1 A + E = 0 , p n = 0

Din această ecuaţie determinăm pe A −1 : −1 (2.2.4.) A = −

(

1 A n −1 + p1 A n −2 + ... + p n −1 E pn

)

Deci, cunoscând coeficienţii polinomului caracteristic al matricei A şi calculând puterile acestei matrice până la a n-1 putere, matricea A-1 se calculează după formula (2.2.4.) Această metodă de inversare se utilizează în cazul matricelor de ordin nu prea mare, pentru că în acest caz ridicarea la putere devine anevoioasă, fapt pentru care se propune o metodă iterativă: 1   (2.2.5.) Ak +1 = A Ak − ∆( Ak ) E  , unde A1 = A k   ∆( Ak ) reprezintă suma elementelor diagonalei matricei Ak şi se numeşte de obicei „urma” matricei Ak . Inversa căutată se determină prin formula: −1 (2.2.6.) A =

n  1  An −1 − S ( An −1 ) E   S ( An )  n −1 

care prezintă avantajul că în loc să calculăm puterile matricei A: A, A2, ..., An-1, se calculează şirul A, A1, ..., An, după (2.2.5.).

2.3. Metoda eliminării Gauss-Jordan Definiţia 2.3.1. Fie matricea A ∈ M m,n ( C ) , A = ( aij ) Se numeşte pas Gauss-Jordan modificat transformarea elementelor matricei după algoritmul următor: (i)

alegerea unui element nenul ( aij ) , numit pivot;

(ii)

înlocuirea pivotului cu 1;

(iii)

înlocuirea celorlalte elemente ale coloanei pivot cu 0;

(iv)

împărţirea celorlalte elementei ale liniei pivot la pivot;

(v)

calcularea celorlalte elemente ale matricei după regula determinantului de ordin 2, considerând diagonala principală diagonala pivotului şi împărţire la elementul pivot.

Observaţii (2.3.1.) (i)

dacă pivotul nu e în prima linie şi prima coloană, se efectuează schimbări de linii şi coloane;

(ii)

prin efectuarea unui pas Gauss-Jordan modificat, rangul matricei se păstrează. Teorema 2.3.1. Dacă A = ( aij ) ∈ M m ,n ( C ) , atunci rang A = numărul maxim de paşi Gauss-Jordan modificaţi ce se pot efectua cu elementele matricei A. Observaţia 2.3.2. Dacă A ∈ M m,n ( C ) şi rang A = n, ⇒ A este inversabilă, atunci există A-1. Inversa lui A se găseşte efectuând cei n paşi Gauss-Jordan modificaţi cu elementele matricei (A, In).  1 0 ... 0     0 1 ... 0  In =  este matricea unitate de ordin n. . . ... .    0 0 0 1   După efectuarea lor, în locul matricei A se obţine matricea unitate In, iar în locul matricei unitate se obţine A-1. Pentru exemplificare, considerăm matricea: 1 1 1    A = 1 2 3  1 4 9    Să se afle inversa matricei şi apoi să se verifice prin calcul direct relaţia: A −1 ⋅ A = I 3 = A ⋅ A −1 , unde I3 este matricea unitate de ordin 3.

I II

III

1 1 1 1 0 0 1 0 0

A 1 2 4 1 1 3 0 1 0

1 3 9 1 2 8 -1 2 2

1 0 0 1 -1 -1 2 -1 2

1

0

0

3

0

1

0

-3

0

0

1

1

I3 0 1 0 0 1 0 -1 1 -3 5 − 2 -4 3 − 2

0 0 1 0 0 1 0 0 1 1 − 2 -1 1 2

I3 A-1 Prin bordare asupra pivotului, obţinem, succesiv: Iteraţia I: 1 1 = 2 − 1 = 1; 1 : 1 = 1 1 2 1 1 = 3 −1 = 2 ; 2 : 1 = 2 1 3 1 1 = 4 −1 = 3 ; 3 : 1 = 3 1 4 1 1 = 9 −1 = 8 ; 8 : 1 = 8 1 9 1 1 = 0 − 1 = −1 ; -1 : 1 = -1 1 0 1 0 = 1− 0 = 1; 1 : 1 = 1 1 1 1 0 = 0; 0 : 1 = 0 1 0 1 1 = 0 − 1 = −1 ; -1 : 1 = -1 1 0 1 0 = 0; 0 : 1 = 0 1 0 1 0 = 1− 0 = 1; 1 : 1 = 1 1 1

Iteraţia II: 1 1 = 1 − 0 = 1 ; 1 : 1 = 1; 0 1

1 1 = 1 − 2 = −1 ; -1 : 1 = -1 1 2

1 1 = 1 + 1 = 2 ; 2 : 1 = 2; 1 −1

1 0 = 0 − 1 = −1 ; -1 : 1 = -1 1 1

1 0 = 0 ; 0 : 1 = 0; 1 0

0 1 = 0−0 = 0; 0 : 1 = 0 0 3

1 2 = 8 − 6 = 2 ; 2 : 1 = 2; 3 8

1 −1 = −1 + 3 = 2 ; 2 : 1 = 2 3 −1

1 1 = −3 ; -3 : 1 = -3; 3 0

1 0 = 1; 1 : 1 = 1 3 1

Iteraţia III: 1 −1 2 = 2 ⇒ = 1; 0 2 2

0 −1 0 =0 ⇒ =0 0 2 2

0 2 0 = 0 ⇒ = 0; 0 2 2

1 2 2 = 2−0 = 2 ⇒ =1 0 2 2

−1 2 6 = 4 + 2 = 6 ⇒ = 3; 2 2 2

−1 1 1 = 2 − 3 = −1 ⇒ − 2 −3 2

−1 0 1 = 0 +1 = 1⇒ ; 2 1 2

2 −1 6 = −2 − 4 = −6 ⇒ − = −3 2 2 2

2

2 0

1

2 −3

= 2+6 =8⇒

8 = 4; 2

2 1

= 0 − 2 = −2 ⇒ −

2 = −1 2

Verificare: 5  1 1 1   3 − 2    A ⋅ A −1 = 1 2 3  ⋅  − 3 4 1 4 9   1 − 3    2 

1  2 − 1 = 1 2 

 1 1  5  3  1 ⋅ 3 + 1 ⋅ ( − 3) + 1 ⋅ 1 1 ⋅  −  + 1 ⋅ 4 + 1 ⋅  −  1 ⋅ + 1 ⋅ ( − 1) + 1 ⋅  2 2  2  2   1 1  5  3 = 1 ⋅ 3 + 2 ⋅ ( − 3) + 3 ⋅ 1 1 ⋅  −  + 2 ⋅ 4 + 3 ⋅  −  1 ⋅ + 2 ⋅ ( − 1) + 3 ⋅  = 2 2  2  2  1 ⋅ 3 + 4 ⋅ ( − 3) + 9 ⋅ 1 1 ⋅  − 5  + 4 ⋅ 4 + 9 ⋅  − 3  1 ⋅ 1 + 4 ⋅ ( − 1) + 9 ⋅ 1       2 2   2  2  5 3  − +4−  3 − 3 +1 4 2  5 9  = 3−6+3 − +8−  2 2  5 27  3 − 12 + 9 − + 16 − 2 2 

1 1 −1+  2 2 1 3 −2+  = 2 2 1 9 −4+  2 2

8   1−1  1 4 − 2   1 0 0   4  = 0 8−7 − 2  =  0 1 0 = I3   2    0 0 1  10 0 16 − 16 − 4   2  

−1 Analog se verifică şi că A ⋅ A = I 3 , ceea ce confirmă corectitudinea aflării lui A −1 .

2.4. Metoda de eliminare a lui Gauss Fie matricea A ∈ M n ( C ) , detA ≠ 0 (matrice pătrată de ordinul n), A = ( aij ) , a cărei inversă vrem s-o determinăm. Pentru aceasta se utilizează relaţia principală: A ⋅ A −1 = I n −1 −1 (2.4.1.) A = ( xij ) , A ∈ M n ( C )

In este matricea unitate de ordinul n:

I n = ( e1 , e2 ,..., ei ,..., en )

1  0 . = 0 .  0 

... ... ... ... ... ...

0 0 . 1 . 0

... ... ... ... ... ...

0  0 .  0 .  1 

Înmulţind matricele A şi A-1 se obţin n sisteme de ecuaţii liniare cu n necunoscute. Coeficienţii acestor sisteme sunt elementele matricei A-1, xij, i, j = 1, n , iar termenii liberi sunt elementele matricei unitate In. Se observă că aceste sisteme se pot scrie sub următoarea formă:  a11 X 1 + a12 X 2 + ... + a1n X n = e1 a X + a X + ... + a X = e 22 2 2n n 2  21 1  ... (2.4.2.)   ai1 X 1 + ai 2 X 2 + ... + ain X n = ei  ...  a n1 X 1 + a n 2 X 2 + ... + a nn X n = en

unde

X 1 = ( x11 , x 21 ,..., x n1 ) şi e1 = (1,0,0,...,0 ) X 2 = ( x12 , x 22 ,..., x n 2 ) şi e2 = ( 0,1,0,...,0 ) .......... X n = ( x1n , x 2 n ,..., x nn ) şi en = ( 0,0,0...,1)

Cele n sisteme de n ecuaţii liniare, având aceeaşi matrice A, se pot rezolva simultan prin metoda Gauss.

Metoda constă în a elimina la fiecare pas câte o necunoscută, obţinându-se un sistem echivalent cu sistemul iniţial, sistem de n-1 ecuaţii cu n-1 necunoscute. La ultimul pas, sistemul se transformă într-un sistem echivalent, format dintr-o singură ecuaţie cu o singură necunoscută. Se începe apoi determinarea necunoscutelor în sens invers, începând cu determinarea ultimei necunoscute din sistemul intermediar. Construim tabela formată din matricea A şi de coloanele termenilor liberi e1, e2, ..., en. e

ei

..

1

. ..

0

. ..

0

. 1

0

. ..

0

...

... ..

..

. ..

... ...

ain

0

. ..

. 1

. ..

... bi

..

. ..

... ...

. ..

. 0

. ..

1

1

e

a1

..

1

1

e

a2

2

1

..

...

. ..

ai1

. ..

..

. ..

a1 j

a2

.. . ..

a1 n

a2

..

...

. ..

aij

. ..

...

. ..

...

. ..

...

. ... ..

. e

an

. ..

an

. ..

an

0

n

1

.

j

.

n

. ei

j

n

.

.

e

b

n

0

b 1

b 2

b n

Descriem calculele din această tabelă, care se numeşte „tabela cu împărţire”. Împărţim elementele primei linii la primul ei element a11 ≠ 0, astfel: a 1 a a11 a = v1,0,0 = 1 , 12 = b12 , ..., 1 j = b1 j ,..., 1n = b1n , a11 a11 a11 a11 a11 Elementele astfel obţinute: 1, b12, ..., b1j, ..., b1n, v1, 0, 0, ..., 0 se trec în linia n+1 a tabelei. Când a11 = 0 se face o permutare de linii sau coloane. Înmulţim elementele 1, b12, ..., b1j, ..., b1n, v1, ..., 0 cu elementul conducător a21, iar produsele obţinute le scădem din elementele corespunzătoare liniei a doua. Obţinem astfel linia întâi din primul sistem intermediar Sn-1. Apoi înmulţim tot elementele 1, b12, ..., b1j, ..., b1n, v1, ..., 0 cu elementul conducător a31 şi scăzând produsele obţinute din elementele liniei a treia se obţine astfel a doua linie din sistemul Sn-1. În general, înmulţind elementele 1, b12, ..., b1j, ..., b1n, v1, ..., 0 cu elementul conducător ai1, scăzând produsele obţinute din linia i, obţinem linia i-1 din sistemul Sn-1.

Procedând analog cu sistemul intermediar Sn-1, găsim al doilea sistem intermediar Sn-2, ş.a.m.d. Continuând în acest mod obţinem un sistem Sn, ca urmare a împărţirii ecuaţiilor: ( n −1) ε 1 , ε 2( 1) ,..., ε n( n −1) , respectiv cu a11 , a12( 1) ,...a nn . În tabelă vom nota coeficienţii ecuaţiilor care

formează acest sistem cu bik, unde bii = 1.

Observaţie: ' Dacă în sistemul dat Sn facem transformarea xij = xij + 1 , (i = 1, 2, ..., n) atunci '

'

obţinem sistemul transformat S n cu necunoscutele xi . Se observă că cele două sisteme au aceeaşi matrice A, ele deosebindu-se doar prin termenii liberi. Termenul liber din ecuaţia i a '

sistemului S n se obţine făcând suma coeficienţilor şi termenului liber din ecuaţia i a sistemului Sn şi se mai numeşte suma de control pentru ecuaţia i a lui Sn. Aceste sume de control se trec în coloana notată Σ. La fiecare pas în rezolvarea problemei se obţine un sistem intermediar pentru sistemul ale cărui necunoscute sunt xij unde ' i, j = 1, n , cât şi pentru sistemul ale cărui necunoscute sunt xij . Construind aceste sisteme

intermediare se verifică dacă într-adevăr suma de control dintr-o linie coincide cu suma elementelor, inclusiv şi termenul liber din linia respectivă. În caz afirmativ, se continuă să se calculeze. Se procedează analog şi când se trece la determinarea necunoscutelor, adică se ' trece la calcularea necunoscutei următoare doar dacă xij = xij + 1 .

Numărul operaţiilor. Pentru calculul matricei inverse A-1 avem de rezolvat cele n sisteme din formula (2.4.2.) Pentru transformarea matricei A într-o matrice triunghiulară efectuăm: n( n − 1) ∑ ( i − 1) = 2 n

i =1

∑ ( i − 1) n

i =1

2

=

împărţiri

n ( n − 1)( 2n − 1) înmulţiri şi tot atâtea adunări. 6

Pe lângă acestea, pentru calculul termenilor liberi avem: -

la sistemul Sn : 1 împărţire, n-1 înmulţiri, 0 adunări;

-

la sistemul Sn-1: 2 împărţiri, 2(n-2) înmulţiri, n-2 adunări;

-

la sistemul Sn-2: 3 împărţiri, 3(n-3) înmulţiri, 2(n-3) adunări;

-

.................................................................................................

-

la sistemul Sn-i: i+1 împărţiri, (i+1)(n-i+1) înmulţiri, i(n-i-1) adunări.

-

.................................................................................................

Obţinem: n( n − 1) ∑ ( i + 1) = 2 n −1

i =0

împărţiri,

n ∑ ( i + 1)( n − i + 1) = 6 ( n − 1)( n + 1) n −1

i =0

n ∑ i( n − i − 1) = 6 ( n − 1)( n − 2) n −1

înmulţiri şi

adunări.

i =0

Deci, pentru a ajunge la ultimul Sn (cu matricea triunghiulară) efectuăm n2 împărţiri, 2 n 2 ( n − 1) n( n − 1) înmulţiri şi adunări. 2 2

Vom calcula numărul operaţiilor necesare pentru rezolvarea celor n sisteme Sn, care diferă unele de altele doar prin termenii liberi. Rezolvarea unui astfel de sistem cere

n( n − 1) 2

( 1)

înmulţiri. În ceea ce priveşte numărul adunărilor, la rezolvarea primului sistem S n cu prima coloană a termenilor liberi, avem

n( n − 1) ( 2) adunări, în cazul sistemului S n (cu a doua coloană 2

a termenilor liberi) avem nevoie de

liberi din coloana i, avem nevoie de

n( n − 1) − 1 adunări. În mod analog, în cazul termenilor 2 n( n − 1) − i + 1 adunări. 2

Astfel, pentru rezolvarea celor Sn sisteme sunt necesare:

n⋅

n( n − 1) n( n − 1) − 1 − 2 − ... − ( n − 1) = 2 2

n( n − 1) înmulţiri şi 2

2

adunări.

Deci, pentru calcularea matricei A prin această metodă se cer în total: n 2 împărţiri; n 2 ( n − 1) înmulţiri; 2 n( n − 1) adunări.

2.5. Algoritm pentru calculul inversei unei matrice Se expune metoda pentru matricele pătrate A de ordin 3, cazul general fiind apoi evident. Dacă A-1 există, adică A ≠ 0 , aducem matricea A la forma eşalon E printr-un număr finit de transformări elementare. α 1 ∗  A → E =  0 α2 0 0 

∗  ∗ α 3 

Cum A ≠ 0 , avem α i ≠ 0 , 1 ≤ i ≤ 3 În continuare, normalizăm pivoţii lui E, aplicându-i transformările elementare: Li ← α i−1 Li , 1 ≤ i ≤ 3

( )

−1 ceea ce revine la înmulţiri la stânga pe E cu matricele elementare, M i α i , 1 ≤ i ≤ 3 .

Matricea E devine matricea E ' , care are forma:  1 b12  E = 0 1 0 0  '

b13   b23  1 

Efectând acum asupra lui E ' transformările elementare L2 ← L2 − b23 L3 L1 ← L1 − b13 L3 L1 ← L1 − b12 L2 matricea E ' devine matricea unitate I 3 . Acum este evident rezultatul din teorema următoare: Teorema 2.5.1. Fie A o matrice pătrată de ordin n, astfel încât A ≠ 0 . Există un număr finit de matrice elementare U1, U2, ..., Up de tip I, II sau II, astfel încât: U p ...U 2U 1 A = I n Mai mult, A −1 = U p ...U 2U 1

Ţinând seama de modul în care se înmulţesc matricele partiţionate în blocuri, din egalitatea din enunţul teoremei rezultă că:

(

) (

U p ...U 2U 1 ( A I n ) = U p ...U 2U 1 A U p ...U 2U 1 = I n A −1 Aşadar, efectuând asupra liniilor matricei

(AI ) n

)

transformările elementare

corespunzătoare matricelor elementare U1, U2, ... respectiv Up, se obţine în final, în cel de-al doilea compartiment matricea A-1.

CAPITOLUL III METODE ITERATIVE DE CALCUL A INVERSEI UNEI MATRICE

3.1. Metoda lui Schultz pentru matrice nesingulare Fiind dată o matrice nesingulară A ∈ M n ( C ) , propunem să-i determinăm inversa, A −1 . Presupunem că am găsit printr-o metodă oarecare aproximarea iniţială x0 pentru A −1 , −1 adică x0 ≈ A pentru care norma matricei F0 = E − AX 0 este strict subunitară ( E = I n ) .

(3.1.1.) F0 < q < 1

Norma utilizată, pe lângă proprietăţile (1.3.6.1.) – (1.3.6.4.) este supusă condiţiilor E =1 (3.1.2.) A ⋅ B ≤ A ⋅ B

−1 Dacă F = 0, atunci X 0 = A .

Pentru îmbunătăţirea preciziei, se utilizează procesul iterativ al lui Schultz, de următoarea formă: (3.1.3.) X k = X k −1 ( 2 E − AX k −1 ) , k = 1, 2, ... Ţinând cont că F0 = E − AX 0 , vom face în (3.1.3.) următoarea substituţie: X k = X k −1 ( 2 E − Ak −1 ) = X k ( E + E − AX k −1 ) = X k −1 + X k −1 ( E − AX k −1 ) Notând cu Fk eroarea corespunzătoare la pasul k, Fk = E − AX k Obţinem:  X k = X k −1 + X k −1 Fk −1  (3.1.4.)  Fk = E − AX k  F = E − AX 0  0

, k = 1, 2, 3, ...

În cele ce urmează, vom arăta că procedeul (3.1.4.) converge în ipoteza F0 < q < 1 , unde ⋅ norma canonică oarecare cu proprietăţile (3.1.2.) Se arată că: lim k →∞ X k = A −1 Propoziţia 3.1.1. Are loc relaţia următoare: Fk = F02

k

F0 = E − AX 0 Fk = E − AX k Demonstraţie: Vom folosi metoda inducţiei: k=1 F1 = E − AX 1 = E − A( X 0 + X 0 F0 ) = E − AX 0 ( E + F0 ) = E − ( E − F0 ) ⋅ ( E + F0 ) =

(

)

= E − E − F02 = E − E + F02 = F02 k=2 F2 = E − AX 2 = E − A( X 1 + X 1 F1 ) = E − AX 1 ( E + F1 ) = E − ( E − F1 ) ⋅ ( E + F1 ) =

(

)

= E − E − F12 = E − E + F12 = F12 = F02 Presupunem adevărată relaţia pentru k-1. Fk −1 = F02

k −1

şi demonstrăm pentru k: Fk = E − AX k = E − A( X k −1 + X k −1 Fk −1 ) = E − AX k −1 ( E + Fk −1 ) =

(

)

= E + ( E − Fk −1 ) ⋅ ( E + Fk −1 ) = E − E − Fk2−1 = = E − E + Fk2−1 = F02

k −1

= F02

k −1

−2

= F02

k

Deci propoziţia este demonstrată Dar F0 < q < 1 . Din formulele corespunzătoare şi din proprietăţile normei rezultă: k

Fk = F02 ≤ F0

2k

≤ q2

k

Dar q < 1 , deci lim k →∞ Fk = 0 şi din Fk = E − AX k , obţinem: lim k →∞ Fk = lim k →∞ ( E − AX k ) = E − A ⋅ lim k →∞ X k = 0 −1 De aici E = A ⋅ A −1 , lim k →∞ X k = A , E fiind matricea unitate de ordinul n. Deci

procedeul (3.1.4.) este convergent. Observaţia 3.1.1. În particular, elementele matricei F0 = ( f ij ) verifică inegalitatea f ij ≤

q , unde n este n

ordinul matricei A şi 0 < q < 1 , utilizarea m a normei arată că este verificată condiţia (3.1.1.), deci (3.1.4.) converge. Am

demonstrat

că

lim k →∞ X k = A −1 ,

evaluând

şi

rapiditatea

convergenţei

aproximaţiilor succesive. Acum presupunem că (3.1.1.) este verificată şi vom face o evaluare a erorii în cazul în care ne oprim la pasul k: Rk = A −1 − X k ≤ A −1 ⋅ E − AX k = A −1 ⋅ Fk ≤ A −1 ⋅ q 2

k

Cum AX 0 = E − F0 , rezultă că: A −1 = X 0 ( E − F0 )

−1

(

)

= X 0 E + F0 + F02 + ...

 q  A −1 ≤ X 0 ⋅ E + q + q 2 + ... = X 0 ⋅  E +  1− q 

{

Dar E = 1 şi A −1 =

}

X0 1− q −1

,

(3.1.6.) Rk = A − X k ≤

X0 1− q

⋅ Fk ≤

X0 1− q

k

q

2k

q2 = X0 1− q

Din definiţia (3.1.1.) rezultă că procedeul (3.1.4.) are ordinul de convergenţă 2.

CAPITOLUL IV APLICAŢII ALE INVERSEI UNEI MATRICE

4.1. Modelul economic al lui Leontief În anul 1973, premiul Nobel pentru economie a fost atribuit lui W. Leontief (economist american, originar din Rusia), care a elaborat o procedură de modelare matematică numită analiză input-output, adecvată pentru un sistem economic complex, formată cu un număr mare de sectoare între care există interacţiuni. Pentru a simplifica prezentarea, presupunem că avem un sistem economic E, format cu trei sectoare, în care sunt fabricate respectiv produsele P1, P2, P3. O parte din producţia sistemului economic E este folosită în interiorul sistemului ca resurse, iar o altă parte este rezervată pentru a onora o cerere externă. Notăm cu aij numărul unităţilor din produsul Pi care sunt folosite pentru realizarea unei unităţi din produsul Pj. Numerele aij cuantifică interacţiunile dintre sectoarele S1, S2, S3. Matricea:  a11  A =  a 21 a  31

a12 a 22 a 32

a13   a 23  a33 

se numeşte matricea tehnologică sau matricea input-output. Dacă xj este nivelul producţiei lui Pj (adică numărul de unităţi din produsul Pj realizate), atunci vectorul 3-dimensional:  x1    P =  x2  x   3 se numeşte vectorul producţie. Produsul:  a11  AP =  a 21 a  31

a12 a 22 a32

a13   x1   a11 x1 + a12 x 2 + a13 x3       a 23  ⋅  x 2  =  a 21 x1 + a 22 x 2 + a 23 x3  a33   x3   a 31 x1 + a32 x 2 + a33 x3 

reprezintă consumul intern, pentru că a11 x1 + a12 x 2 + a13 x3 reprezintă partea din producţie x1 a lui S1 consumată în interiorul sistemului E, ş.a.m.d. Rezultă că P − AP este partea de producţie disponibilă, care poate fi folosită pentru a onora o cerere externă. Presupunem că în afara sistemului economic E există o comandă de cj unităţi din  C1    produsul Pj, 1 ≤ j ≤ 3 şi fie C =  C 2  numit vectorul-comandă. C   3 Problema fundamentală care se pune este de a planifica nivelul producţiei P de aşa natură încât P − AP = C , ceea ce se mai scrie ( I 3 − A) P = C . Dacă matricea

( I 3 − A) P = C

( I 3 − A)

este inversabilă, atunci înmulţind la stânga egalitatea

cu ( I 3 − A) , se obţine P = ( I 3 − A) ⋅ C . −1

−1

4.2. Codificarea mesajelor Inversa unei matrice are aplicaţii şi în criptografie, disciplină care are ca obiect elaborarea metodelor de codificare a mesajelor pentru secretizarea acestora. Pentru exemplificare, vom folosi matricea A şi inversa sa, A-1. −1 1 2    A =  1 1 − 1 0 1 1  

3 − 1 2   A =  −1 −1 1  1 1 0   −1

şi mesajul „SOSESC JOI”. Atribuim literelor alfabetului latin câte un număr natural pozitiv şi blancului

numărul 0, de exemplu: A B C D E F G H I ↓ ↓ 0 1

↓ ↓ ↓ 2 3 4

↓ ↓ ↓ 5 6 7

↓ 8

J

..

↓ ↓ 9 1 0

O

..

S

..

Y

Z

. ↓ ..

↓ 1

. ↓ ..

↓ 1

. ↓ ..

↓ 2

↓ 2

.

5

.

9

.

5

6

Mesajul se împarte în blocuri de lungimi egale (în cazul nostru 3), luând în consideraţie şi spaţiile libere (blancuri). Se adaugă, eventual la sfârşitul mesajului, câteva blancuri pentru a obţine blocuri de lungimi egale: SOSESC

JOI

Semnele din blancuri sunt înlocuite cu numere asociate. Se formează o matrice numerică M cu trei coloane şi tot atâtea linii câte blocuri are mesajul. Se înmulţeşte M cu A, M ⋅ A = C , matricea C fiind mesajul codificat care se transmite.

În cazul nostru: S O S E S C J I

19 15 19   − 4 15 42     −1 −1 2     14 17 − 6   5 19 3   1 1 =   0 10 15  ⋅  1 10 25 5      0 1 1    9 0 0 −9 −9 8      M

A

C

La recepţie, pentru decodificare (decriptare), se efectuează produsul CA-1 şi se obţine

(

)

−1 −1 −1 M, deoarece CA = ( MA) A = M AA = MI 3 = M .

 − 4 15 42  19 15 19    2  3 − 1    5 19 3   14 17 − 6   −1 CA =  ⋅ −1 −1 1  =   10 25 5     0 10 15    1 1 0  9 0 0  − 9 − 9 18      A-1

C

S O S E S C J I

M

4.3. Rezolvarea sistemelor de tip Cramer scrise sub formă matriceală Definiţia 4.3.1. Un sistem de n ecuaţii liniare cu n necunoscute se numeşte sistem de tip Cramer dacă determinantul matricei este nenul. Considerăm un sistem Cramer de trei ecuaţii cu trei necunoscute: a11 x1 + a12 x 2 + a13 x3 = b1  (S) a 21 x1 + a 22 x 2 + a 23 x3 = b2 a x + a x + a x = b 32 2 33 3 3  31 1

 a11  Dacă A =  a 21 a  31

a12 a 22 a 32

a13   x1   b1       a 23  este matricea sistemului (S), x =  x 2  şi b =  b2  , atunci x  b  a33   3  3

sistemul (S) se scrie sub formă matriceală astfel: (S) Ax = b . Cum A ≠ 0 , există A-1 şi înmulţind la stânga cu A-1 egalitatea de mai sus obţinem: x = A −1b Rezultă că (S) are soluţie unică, anume x = A −1b .

4.4. Ecuaţii matriceale Definiţia 4.4.1. O ecuaţie de forma AX=B, unde A este o matrice pătrată inversabilă de ordin n, B este o matrice de tip m x n, iar X este necunoscuta (tot o matrice), se numeşte ecuaţie matriceală. Propoziţia 4.4.1. Ecuaţia matriceală AX = B , unde A ∈ M n ( C ) este ireversibilă, iar B ∈ M m×n ( C ) , are o soluţie unică X ∈ M m×n ( C ) de forma X = A −1 ⋅ B . Demonstraţie: Înmulţim la stânga ambii termeni cu A −1 : A −1 ( AX ) = A −1 B Folosind asociativitatea înmulţirii matricelor, rezultă:

(A

−1

)

⋅ A X = A −1 B

I n X = A −1 B X =A −1 B

Observaţia 4.4.1. Deoarece înmulţirea matricelor nu este comutativă, ecuaţia XA = B , unde A este o matrice pătrată inversabilă, are soluţia unică X = BA −1 . Demonstraţie: Înmulţim la dreapta ambii termeni cu A −1 :

( XA) A −1 = BA −1 Folosind asociativitatea înmulţirii matricelor obţinem:

(

)

X A ⋅ A −1 = BA −1 XI n = BA −1 − 1

X =BA

Observaţia 4.4.2. Ecuaţia AXB = C , unde A şi B sunt matrice inversabile, are soluţia unică X = A −1CB −1 . Demonstraţie: Înmulţind la stânga ambii termeni ai ecuaţiei cu A −1 şi la dreapta ambii termeni ai ecuaţiei cu B −1 , obţinem: A −1 AXBB −1 = A −1CB −1 Folosind asociativitatea înmulţirii matricelor, rezultă:

( A A) X ( BB ) = A −1

−1

−1

CB −1

I n XI n = A −1CB −1 X = A −1CB −1