M ETODE NUM ERICE DE CALCUL A L DETERM INANŢILO R SI REZOLVAREA SISTEMELOR DE ECUAŢII LINIARE

M ETODE NUM ERICE DE CALCUL A L DETERM INANŢILO R SI REZOLVAREA SISTEMELOR DE ECUAŢII LINIARE După studierea acestui capitol, veţi fi capabili să: • descrieţi metodele numerice de calcul al determinanţilor şi algoritmii pentru implementarea acestor metode; • descrieţi metodele numerice de rezolvare a sistemelor de ecuaţii liniare; • descrieţi algoritmii de rezolvare a sistemelor de ecuaţii liniare prin metoda Cramer şi metoda Gauss; • elaboraţi programe pentru calculul determinanţilor de ordinul n; • elaboraţi programe pentru rezolvarea sistemelor de ecuaţii liniare de ordinul n; • combinaţi metodele studiate pentru elaborarea algoritmilor eficienţi de rezolvare a sistemelor de ecuaţii liniare şi a programelor care realizează aceşti algoritmi. 4.1. Determinanţi numerici Fie dată o matrice pătratică arbitrară de ordinul n: «1,1 «1,2 - «!,„" A = «2,1 «2,2 - «2,n • (1) ,«„,1 «„,2 •" «n,n, Fiecărei din matricele de acest tip îi este asociată o valoare numerică numită determinant. Determinantul poate fi definit în mod inductiv. Notaţia folosită pentru determinantul matricei A este det(A). Pentru a defini determinantul unei matrice de ordinul n, se va folosi noţiunea de minor. Se numeşte m in o r d e o rd in u l n -1 al elementului a al matricei A de rang n(n>1) determinantul matricei de rang n-1, obţinută din matricea A prin excluderea rîndului i şi a coloanei j. Vom nota minorul elementului a prin A,, unde i indică rîndul, iar j - coloana la intersecţia cărora se află elementul ay. Astfel, pentru a calcula în matricea din exemplu minorul A12 al elementului a1,2 se exclude din matrice linia 1 şi coloana 2: A = 0 -1 - f r -2- A, 2 = det 2^ 1 = 2. 36 Se numeşte determinant al matricei A de rang n n valoarea expresiei ^ ( —1 ) U Ja XjA l y.. ------- 7=1 Conform definiţiei «u «1,2 ' • «l,o A = det(T) = «2,1 «2,2 •• «2,o = î( - i r j^ A ,j j=i ««,1 «n,2 •• «0,0 Astfel, pentru matricea de ordinul 4: ' « u « 1 ,2 «1,3 «1,4 " A = « 2 ,1 « 2 , 2 «2,3 «2,4 «3,1 «3,2 «3,3 «3,4 v« 4 ,l «4,2 «4,3 «4,4 det(A) = a, i4,i - “n A, 2 + « 1 A _ 3^1,3 Fiecare dintre minorii Ax-, j = 1, ..., 4 este determinantul unei matrice de ordinul 3 şi poate fi calculat direct. Algoritmul de calcul al determinanţilor numerici Fie dată matricea (1). Algoritmul de calcul al determinantului unei matrice de ordinul n se bazează direct pe definiţia determinantului: det(^) = £ ( - l ) 1+X A 7 - „ 7-1 În această formulă elementele necunoscute sînt minorii elementelor din prima linie. Fie un minor arbitrar A . El este determinantul unei matrice de ij ordinul n-1. Pentru a-l calcula, urmează să fie rezolvată o problemă echivalentă cu problema iniţială, dar de dimensiune mai mică. Deoarece la un moment dat se ajunge la calculul unui determinant de ordinul 1,2 sau 3, care se calculează direct, se respectă regula de consistenţă şi poate fi aplicat un algoritm recursiv: Fie matricea A are ordinul R. ALGORITM CRD (A, R) {Calcul recursiv determinant al matricei A de ordin R.} Cazul elementar Dacă ordinul matricei A este 1, (R = 1), atunci CRD <= axj, altfel: Ne amintim! Pentru matricea A de ordinul 1, formată dintr-un singur element au , determinantul va fi chiar valoarea acestui element. Exemplu: A = (7); det(A) = 7. Pentru o matrice de ordinul 2, A = V «21 *11J determinantul va fi egal cu valoarea expresiei fl11fl22 - a12a21. Exemplu: A ■ 2 5 ; det(A) = 9. vl 7, Pentru o matrice de ordinul 3, ' « i i « 1 2 «13 A = « 2 1 « 2 2 «23 ^«31 «32 «33 y determinantul poate fi calculat folosind regula lui Sarrus (regula diagonalelor şi a triunghiurilor). Astfel, pentru o matrice de ordinul 3 determinantul poate fi calculat direct după formula: det(A) = flUfl2,2fl3,3+flUfl2,1fl3,2+ Exemplu: \ 0 3 7 0 0 2 V-l 2 1, ; det(A) = -10. Regula de consistenţă: 1. Există un caz elementar: matricea ce corespunde minorului curent are ordinul 1. 2. La nivelul kse fac k apeluri pentru calculul determinanţilor de ordinul k-1. Prin urmare, procesul converge spre un caz elementar. 37 Cazul de reducere 1. Valoarea determinantului A se iniţializează cu 0 (A<=0). 2. Pentru toţi j de la 1 la R: a) Se formează matricea MXj prin excluderea din matricea curentă A a liniei 1 şi a coloanei j. (Ordinul M1j. este R-1. Matricea dată corespunde minorului A j) b) Se calculează determinantul D: . al matricei MXj prin apelul CRD (M1j, R-1). c) Se actualizează valoarea A ^ A+ (-1)1+j x D1 .. 3. . SFÎRŞIT. , j Implementarea algoritmului Fie date declaraţiile: const nmax=10; type matrice=array[1..nm ax,1..nm ax] of rea l; Matricea pentru care se calculează determinantul va fi stocată în tabloul X de tip m at . Ordinul maxim al matricei pentru care se calculează determinantul este limitat de constanta nmax . Minorul M . care se generează în cadrul apelului curent, este stocat în variabila m inor , de tip m at . Semnul valorii (-1)* 1+j CRD (M , R-1) este determinat de paritatea variabileij , prin urmare, valoarea calculată va fi adăugată pentru j impar şi scăzută pentru j par. O realizare posibilă în limbajul Pascal a funcţiei recursive de calcul al determinanţilor este următoarea: function cdet( var x : m a t r i c e ; t : i n t e g e r ) : r e a l ; var i , j, k: in te g e r; s : r e a l ; m i n o r : m a t r i c e ; begin if t=1 then cdet:=x[1,1] {caz elementar} else begin s : =0; for k:=1 to t do begin {Se e x c l u d e l i n i a 1 s i c o l o a n a k p e n t r u a f o r m a m a t r i c e a , care corespunde minorului elementului x[1,k]} for i:=1 to t-1 do for j:=1 to k-1 do m inor[i , j ] : =x[i+1, j ]; for i:=1 to t-1 do for j:=k to t-1 do m i n o r [i , j ] : = x [i + 1 , j + 1 ] ; {apelul recursiv} if odd(k) then s:=s+x[1,k]*cdet(m inor, t-1) else s:=s-x[1,k]*cdet(m inor, t-1 ); end; c d e t : = s ; end; end; 38 Numărul de operaţii necesare pentru calculul recursiv al determinantului unei matrice de ordinul n este determinat de numărul de apeluri recursive, precum şi de numărul de operaţii în cadrul unui apel. Dezvoltarea unei matrice de ordinul n după o linie presupune formarea a n minori de ordinul n-1. Consecutiv, la dezvoltarea fiecăruia dintre ei vor apare n-1 minori de ordinul n-2 şi aşa mai departe. Numărul total de apeluri va fi determinat de valoarea n x (n-1) x x (n-2) x ... x 3 x 2 x 1 = n! Numărul de operaţii în cadrul fiecărui apel este proporţional cu n Prin urmare, complexitatea finală a subprogramului recursiv este O(n2n!), ceea ce face ca algoritmul să fie puţin eficient pentru valori mari ale lui n. Există şi un algoritm de complexitate polinomială, care permite calculul iterativ al determinanţilor. Algoritmul foloseşte transformările elementare aplicate consecutiv asupra matricei iniţiale pentru a o transforma într-o matrice triunghiulară. Determinantul acesteia din urmă este egal cu produsul valorilor elementelor de pe diagonala principală. Pentru a obţine elemente cu valoare nulă sub elementul diagonal din coloana j (j =1, ..., n-1), elementele liniei i (i = j+1, ..., n) se vor aduna cu elementele respective -a.. ale liniei j înmulţite cu coeficientul - ^ . Dacă elementul a . are valoarea 0, se încearcă permutarea liniei j şi a liniei k (j < k), astfel încît akj ^ 0. Dacă o asemenea linie nu există, se poate spune cu certitudine că determinantul matricei este zero. Neajunsul metodei este numărul considerabil de împărţiri efectuate, care în cazul oscilaţiilor mari ale valorilor elementelor matricei pot genera erori, ceea ce nu se întîmplă în cazul algoritmului recursiv. O posibilă implementare a acestui algoritm este realizată în funcţia CID: function CID(x:matrice; r:integer): real; var i,j,k:integer; q:real; begin {CID} for i: =1 to r-1 do begin {se verifica valoarea elementului diagonal din linia i} if x[i,i]=0 then {daca e nula, se cauta o linie pentru inlocuire} begin k: =i; for j:=i+1 to r do if x[j,i]<>0 then k:=j; {daca nu exista linie pentru inlocuire} if k=i then begin CID:=0; exit; end {altfel are loc permutarea liniilor i, k} else for j :=1 to r do begin q :=x[i, j ] ; x [ i,j ] :=x[k,j] ; x[k, j] :=-q; end; end; {modificarea liniilor in scopul obtinerii elementelor cu valoare nula in coloana i} 39 for j:=i+1 to r do begin q:=-x[j,i]/x [i,i] ; for k:=i to r do x[j,k]:=x[j,k]+x[i,k]*q end; end; {calculul valorii determinantului pentru matricea triunghiulara} q : =1; for i:=1 to r do q:=q*x[i,i]; CID:=q; end; Întrebări si exerciţii y > O Explicaţi legătura dintre matrice si determinantul ei. e Elaboraţi o funcţie pentru calculul determinanţilor de ordinul 3, utilizînd regula lui Sarrus. e Descrieţi algoritmul de calcul al determinanţilor de ordinul n prin dezvoltare după elementele unei linii arbitrare. O Elaboraţi un program pentru calculul determinanţilor de ordinul n (n< 10), în care veţi folosi funcţia cdet, descrisă în paragraful curent. Ordinul matricei şi valorile elementelor sale se vor introduce de la tastatură. e Calculaţi, cu ajutorul programului elaborat, determinanţii următoarelor matrice: a) ' 2 5' b) (1 0 3' c) ( \ 2 3 4) ,4 - l / 5 8 2 / 2 1 0 5 ,6 -1 4y 3 6 9 6 / ,4 5 8 7, d) ' l 2 3 0' e ) (1 1 1 f | f ) f - 4 9 -4 6 - 5' 0 0 0 2 1 -1 1 -1 - 1 7 5 5 8 0 6 0 6 / 2 -3 4 1 / 9 -6 8 - 6 2 ,4 4 3 o, ,3 4 -3 9, 2 5 2 3 9 g ) '1 -1 3 2 ' h) ' 6 5 3 -2 -7 r V 1 3 1 5 - 2, 1 -1 6 5 1 4 -1 8 -6 -5 1 -1 -9 - 10 / 4 -3 1 10 9 -3 ,1 -1 2 - K 6 4 6 7 7 9 -8 6 4 -1 -5 6 , 1 4 5 6 - 6 3 , © În programul realizat în exerciţiul 4, transformaţi parametrul variabilă x al funcţiei cdet în parametru valoare. Observaţi ce se va întîmpla în cazul calculului aceluiaşi determinant pentru diferite tipuri ale parametrului x. Explicaţi diferenţa observată. © Încercaţi să aplicaţi programul realizat pentru calculul determinanţilor matricelor cu dimensiuni n, n > 20, cu elemente de tip real. Ce se va întîmpla? Explicaţi. 40 4.2. Metoda Cramer de rezolvare a sistemelor de ecuaţii liniare * Formulele Cramer1 Capacitatea de a calcula determinanţii numerici de ordinul n permite rezolvarea unei game largi de probleme din diverse domenii. Una dintre aplicaţiile practice ale calculului determinanţilor este rezolvarea sistemelor de ecuaţii liniare. Fie dat sistemul din n ecuaţii liniare cu n necunoscute: aux1+al2x2+... + aknxn=b1 ' (1) + an,2X2 + ' . + a x , nji i = b Pentru transcrierea sistemului în formă matriceală vor fi folosite următoarele notaţii: A = fll,l a i,2 • a 2 ,l a 2,2 • r R R cT ţT - matricea . , o = h - vectorul termenilor V *2 ^a n ,\ a n,2 ■■ U n ,n , coeficienţilor, A , liberi, - vectorul soluţiilor. În formă matriceală sistemul (1) poate fi scris Ax = b. (2) În cazul cînd determinantul A este diferit de 0, există matricea inversă A"1. În urma înmulţirii ambelor părţi ale egalităţii (2) la A-1, se obţine: ceea ce este echivalent cu A 1Ax = A 1b, x = A-1b. Această formulă permite calculul soluţiilor sistemului (1) în cazul în care matricea A a sistemului este nesingulară. Formula detaliată pentru calcularea componentelor vectorului soluţie rezultă nemijlocit din (3) şi proprietăţile matricei inverse: X i = A* A 2 = 1, . a i,i • ■ • a \,i-\ b\ a i,i+l 0 then begin for p:=1 to n do sol[p]:= transforma(a,n,p)/de; for p:=1 to n do writeln('x[',p,']=',sol[p]:0:3); end else writeln('Calcul imposibil'); end. Rezultate: x[1]=1.000 x[2]=3.000 x[3]=2.000 [3 Întrebări si exerciţii y > O Pentru rezolvarea căror probleme pot fi folosite formulele Cramer? Care sînt condiţiile cînd ele nu pot fi aplicate? © Explicaţi sensul elementelor A si A, din formulele Cramer. © În baza exemplului cn11 elaboraţi un program pentru calculul soluţiei unui sistem din n ecuaţii liniare cu n (n < 10) necunoscute, utilizînd formulele Cramer: a) Numărul de ecuaţii n, valorile coeficienţilor ecuaţiilor sistemului si ale termenilor liberi se introduc de la tastatură; b) Datele iniţiale vor fi citite din fişierul text sistem.in care va conţine pe prima linie un număr întreg n - numărul de ecuaţii în sistem. Fiecare din următoarele n linii va conţine cîte n+1 numere întregi, separate prin spaţiu: coeficienţii ecuaţiilor în ordinea apariţiei lor şi termenii liberi. © Rezolvaţi următoarele sisteme de ecuaţii, utilizînd programul realizat în exerciţiul 3: a) c) e) x ,+ x 2 + x 3 + x 4 = 10 -4 x j + 9 x2 - 4 x3 + 6 x 4 - 5x5 = - 8 xI - x 2+ x3- x 4 = - 2 -Xj + 7 x2 + 5x3 + 5x4 + 8 x 5 = 199 2xx - 3x2 + 4x3 +x4 = 12 b) 1 9xj - 6 x 2 + 8 x 3 - 6 x 4 + 2 x 5 = 52 3x1+4x2- 3 x3+9x4 = 38 2 xj + 5x2 + 2 x3 + 3x4 + 9x5 = 198 x, + 3x2 + Xj + 5x4 - 2 x5 = 33 6xj + 5x2 + 3x3 - 2 x4 - 7 x5 + x 6 = —48 Xj - x 2 + 3 x3 + 2 x4 = 1 X[ + 4 x2 - x3 + 8 x 4 - 6 x 5 - 5x6 = --106 Xj - x 2 + 6 x 3 + 5x4 = 0 4 x j - 3 x2 + x 3 + 1 0 x4 + 9 x5 - 3 x6 = 70 d )i) pentru care ari * 0. Dacă o astfel de linie nu există, se trece la pasul 3. b) Pentru fiecare din liniile j de la i+1 la n se repetă procedura (P): -a , t I. se calculează ; au, II. pentru toţi l de la 1 la n+1 ajt ^ ajt + k x ajV Pasul 3. Dacă i0 then k:=j; if k=i then goto linie_urmatoare else for j:=1 to t+1 do begin r :=x[i,j]; x [i,j]:=x[k,j]; x[k,j]:=r; end; end; for j:=i+1 to t do begin r :=-x[j,i]/x[i,i]; for k:=i to t+1 do x[j,k]:=x[j,k]+x[i,k]*r; end; linie_urmatoare: end; end; {direct} procedure invers (var q:vect); var i,j: integer; s: real; 47 begin for i:=n downto 1 do begin s : =0; for j:=i+1 to n do s:=s+a[i,j]*q[j]; if a [i,i]<>0 then q[i]:=(a[i,n+1] -s)/a[i,i] else q[i]:=0; end; end; begin citeste(a,n); direct(a,n); invers(s); for i:=1 to n do writeln('x[',i,']=',s[i]:0:3); end. Teste: 3 x j + 2 x 2 - x 3 = 1 ■ 6 x , + 4x2 - 2x3 = 1 4 X j - 6 x 2 + 2 x 3 = - 1 3 - 8 X [ + 9 x 2 - x 3 + 9 x 4 - 5 x 5 - 4 x j - 9 x 2 + 9 x 3 + 2 x 4 - 2 x 5 ■ -4xj - 4 x2 + 7x3 + 3x4 + 4 x5 - 3 xj + 6 x 2 - 7x3 - 6 x 4 + 9x5 X j - 9 x 2 - 9 x 3 - 7 x 4 - 6 x 5 Întrebări si exerciţii j j Rezultate: x [1 ]= 0 .8 0 0 x [2 ]= 2 .3 0 0 x [3 ]= 0 .0 0 0 = -111 x [1 ]= 9 .0 0 0 = 88 x [2 ]= -3 .0 0 0 = 64 x [3 ]= 1 1 .0 0 0 = -1 1 0 x [4 ]= 1 .0 0 0 = -8 2 x [5 ]= 2 .0 0 0 Note: Se observă prezenţa a două ecuaţii cu coeficienţi proporţionali. Programul detectează variabila liberă x [ 3 ] , pe care o stabileşte fiind egală cu 0. Determinantul matricei coeficienţilor sistemului este diferit de 0. Prin urmare există o singură soluţie a sistemului. Prin verificare directă se stabileşte corectitudinea soluţiei date de program. O Descrieţi etapele algoritmului de calcul al soluţiei unui sistem din n ecuaţii liniare cu n necunoscute, utilizînd metoda Gauss. e Indicaţi care sînt resursele de memorie necesare pentru calculul soluţiei unui sistem din n ecuaţii liniare cu n necunoscute prin metoda Gauss. e Elaboraţi un program pentru calculul soluţiei unui sistem din n ecuaţii liniare cu n (n < 10) necunoscute prin metoda Gauss. O Estimaţi complexitatea temporală a algoritmului de rezolvare a sistemelor de ecuaţii liniare prin metoda Gauss. Folosiţi programul cn12. © Efectuaţi o modificare a programului cn12, care ar permite determinarea soluţiilor sistemelor de forma: a) «1,1*1 + « 1 ,2 *2 + «1,3*3 + ••• + « l,n * n = k « 2 ,2 * 2 « 2 ,3 *3 + ••■ + « 2 ,n *n = ^2 « n - l,n - l* n - l « n -l,n * n ^ B -l a „ „ x „ = h n,n n n b) «1,1*1 =h Q>2 + ^2 2^2 = ^2 « n - l,2 *2 « n - l,3*3 + ■••+ « „ - !,„ * „ = ^n-1 « n ,l* l + « n ,2 *2 + « n ,3*3 + - + « n ,n *n = K © Realizaţi o modificare a programului cn12, care ar permite atribuirea aleatorie a valorilor variabilelor libere. 48 Test de evaluare l î Selectaţi răspunsul corect: 1. Determinantul este o caracteristică numerică, pe care o posedă matricele: a) numai de rangul 1; b) de orice rang; c) numai de rang mai mic sau egal cu 3. 2. Pentru calculul determinanţilor pot fi folosiţi algoritmi recursivi: a) adevărat; b) fals. 3. Pentru a stoca în memoria calculatorului o matrice de dimensiunea 10 x 10, elementele căreia sînt numere reale, vor fi necesari: a) 640 octeţi; d) 400 octeţi; b) 1 024 octeţi; e) 200 octeţi. c) 600 octeţi; 4. Metoda Cramer poate fi utilizată doar în cazul cînd determinantul matricei coeficienţilor sistemului este: a) diferit de 0; c) pozitiv; b) egal cu 0; d) un număr întreg. 5. 6. Fie A - determinantul matricei coeficienţilor unui sistem din n ecuaţii liniare cu n necunoscute, iar A1 - determinantul matricei coeficienţilor sistemului, în care prima coloană a fost înlocuită cu vectorul termenilor liberi. Metoda Cramer utilizează următoarea formulă de calcul pentru componenta x1 a vectorului soluţie: A c) ; Ai 1 A K (A i - A ) d) . A i ; Metoda Gauss de rezolvare a sistemelor de ecuaţii liniare conţine: a) o singură etapă; c) trei etape; b) două etape; d) numărul etapelor nu poate fi estimat apriori. 7. În cadrul metodei Gauss, la etapa directă, pentru un sistem cu n ecuaţii, necunoscuta x. este exclusă din toate ecuaţiile cu indicii: a) de la 1 la ; b) de la 1 la i +1; c) de la la n; d) de la +1 la n. 8. Fie sistemul de ecuaţii liniare, unde a.. ^ 0 (i = 1,..., n). «1, 1*1 + «1, 2* 2 + «1, 3*3 + - + « 1, »- ! * »- ! + « l , n * n « 2 , 2 * 2 + « 2, 3* 3 + - + «2, n—l * n —1 + « 2 , n X n = k = b2 a , i + u„ i „x„ n —i tn —i n —i n —i , n n «n,M*n [9 Metoda Gauss presupune determinarea componentei x, a vectorului soluţie prin formula: b, ~ Z avxj a) ; c) b i ~ Z a V x J j= i+ i bi + Z avxj - b t + X b) x ,.= ------ ^ -------; d) . a u ' a u Ci Calculaţi folosind programele elaborate anterior. Pentru fiecare soluţie calculată se va afişa o linie care va conţine cuvîntul „Răspuns:", urm at, după un spaţiu, de soluţia calculată: 1. Determinanţii matricelor: ■ 1 4 0 ' '4 -1 2 5' a) 2 3 7 ; b) 2 2 1 4 -4 1 - 2 0 3 5 6 _2 -1 4 1 2. Soluţiile sistemelor (metoda Cramer): -6 x j - 3x 2 - 3x 3 = -6 3 -7 x ! + 8x2 + 6x3 = 10 b) 2xj + 6x2 - 7 x 3 = - 6 4 9x2 - 8 x 3 + 2x 4 8x, - 7 x2+ 9x3 + 8x4 - 3 x t - 7 x2 + 3x3 + 4x 4 - x l - 9x3 + x4 3. Soluţiile sistemului (metoda Gauss): 5x 2 + x4 + 5x 5 = 89 - 8 x 3 + 4x 2 - x4 + 4x 5 = 87 1 Oxj + 3x2 - 9x3 - 3x 4 - 2x5 = -1 3 -7 x j + 6 x 2 - 6 x 3 + 7x 4 + 7x 5 = 217 -7 X j + 6 x 2 + 8 x 3 - 7x 4 + x5 =