CALCUL MATRICIAL - INVERSARE SI FACTORIZARE - Proiect la disciplina Matematici asistate de calculator

CALCUL MATRICIAL - INVERSARE SI FACTORIZARE

Proiect la disciplina Matematici asistate de calculator

 

Aspecte introductive

Matlab (Matrix Laboratory) este un pachet de programe, produs de firma The MathWorks, dedicat calculului numeric si reprezentarilor grafice in stiinta si inginerie.

Elementul de baza cu care opereaza Matlab este matricea. O matrice poate fi definita in Matlab fie element cu element, ca o lista, fie in cazul unor matrice de tip special, prin instructiuni specifice.

Principalele operatii cu matrice sunt: adunarea si scaderea, inmultirea, ridicarea la putere, impartirea la dreapta, respectiv la stanga, transpunerea.

Inversa unei matrice

Fie o matrice patratica de ordinul n: A. Se numeste inversa matricei A, o matrice patratica de ordinul n, notata cu A^-1 care satisface relatia:

A*A^-1 = A^-1*A = I

, unde I este matricea unitate.

Pentru ca matricea A sa fie inversabila este necesar ca A sa fie matrice nesingulara (determinantul sa fie nenul), A^-1 exprimandu-se sub forma:

, unde A⁺ este adjuncta matricei A, adica este transpusa matricei obtinute prin inlocuirea elementelor cu complementii lor algebrici; complementul algebric a elementului A(i,j) este minorul inmultit cu (-1)^i+j. Minorul de ordinul n, m_ij, este determinantul de ordinul n-1 obsinut prin eliminarea liniei i si a coloanei j.

Proprietatiile operatiei de inversare:

Factorizarea unei matrice

Prin factorizarea LU se intelege ca o matrice patratica de ordinul n, A se descompune in produsul a doua matrice patratice, de acelasi ordin cu A,L si U, unde L este o matrice inferior triunghiulara, iar U superior triunghiulara.

Exemple de factorizari LU: factorizare Doolittle, factorizarea Crout, factorizarea Cholesky.

Prin factorizarea Doolittle matricea A se descompune in produsul a doua matrici dupa cum urmeaza:

A = L*U

, unde L este o matrice inferior triunghiulara care are pe diagonala principala 1, iar U este o matrice superior triunghiulara.

Prin factorizarea Crout matricea A se descompune in produsul a doua matrice dupa cum urmeaza:

A = L*U

, unde L este o matrice inferior triunghiulara, iar U este o matrice superior triunghiulara care are pe diagonala principala 1.

Prin factorizarea Cholesky matricea A se descompune in produsul a doua matrice dupa cum urmeaza:

A = L*L^T

, unde L este o matrice inferior triunghiulara, iar L^T este transpusa lui L, adica o matrice superior triunghiulara.

Pentru ca A sa poata fi descompusa astfel, se impune conditia ca A sa fie simetrica si pozitiv-definita.

O matrice A patratica de ordinul n este simetrica daca A^T = A.

O matrice A patratica de ordinul n este pozitiv-definita daca x^T*A*x>0 oricare ar fi vectorul x de dimensiune n.

Prin factorizarea QR se intelege ca o matrice A se descompune in produsul a doua matrice Q si R, unde Q este o matrice ortonormala, iar R este o matrice superior triunghiulara.

A = Q*R

O matrice A este ortonormata (ortogonala) daca A^T = A^-1.

Prezentarea metodelor implementate

A.               Calculul inversei prin metoda eliminarii a lui Gauss-Jordan[1]

Fisierul functie care a fost realizat este: Gauss_Jordan.m. In acest fisier a fost implementat un program de calcul al inversei prin metoda eliminarii a lui Gauss Jordan pornind de la urmatorii pasi:

s-au facut initializarile: A⁰ = A

D⁰ = I

la pasul k, k = 1:n, s-au calculat elementele matricelor A^k si D^k, utilizand formulele:

, j = k+1:n

, j = 1:k.

a^k(i,i) = 1 , i = 1:k

d^k(i,i) = 1 ,i = k+1:n

a^k(i,j) = a^k-1(i,j)-a^k-1(i,k)*a^k(k,j) , i = 1:n, i≠k, j = k+1:n

d^k(i,j) = d^k-1(i,j)-a^k-1(i,k)*d^k(k,j) , i = 1:n, i≠k, j = 1:k

a^k(i,j) = 0 , i = 1:n, i≠j, j = 1:k

d^k(i,j) = 0 , i = 1:n, i≠j, j = k+1:n

in final se obtine matricea unitate si inversa:

I = Aⁿ

A^-1 = Dⁿ.

Observatii:

indicele superior reprezinta pasul de calcul

se observa ca numitorul fractiilor de la pasul (2) nu poate fi nul, in caz contrar, ar aparea probleme la efectuarea impartirilor.

Pentru implementarea algoritmului am folosit cicluri for si pentru testarea conditiilor if.

Mentionam ca in implementare indicele superior nu a fost scris, el fiind implicit.

B.        Factorizarea prin metoda Doolittle[2]

Fisierul functie care a fost implementat este: Doolittle.m.

In acest fisier a fost implementat un program de calcul al factorizarii unei matrice prin metoda Doolittle pe baza algoritmului:

la pasul k, k = 1:n s-au calculat elementele matricelor L si U astfel:

L(k,k) = 1

, j = k:n

, i = k+1:n

Pentru implementarea algoritmului si pentru calcularea sumelor am folosit cicluri for .

C.               Factorizarea prin metoda Crout[3]

Fisierul functie care a fost implementat este: Crout.m.

In acest fisier a fost implementat un program de calcul al factorizarii unei matrice prin metoda Crout pe baza algoritmului:

La pasul p, p = 1:n se formeaza o noua matrice A

s = A(i,1:p-1)*A(1:p-1,p) , i = p:n

A(i,p) = A(i,p)-s , i = p:n

s = A(p,1:p-1)*A(1:p-1,j) , j = p+1:n

, j = p+1:n

Pentru implementarea algoritmului am folosit cicluri for .

Observatie: acest algoritm are ca parametru de iesire matricea A care inglobeaza cele doua matrice, L (inferior triunghiulara) si U (superior triunghiulara cu 1 pe diagonala principala). De aceea a fost nevoie de cateva adaugari, si anume: pentru a obtine matricea L am utilizat functia tril(A) care a returnat partea de sub diagonala principala a matricei A, inclusiv elementele acesteia, iar pentru obtinerea matricei U am extras partea de deasupra diagonalei, inclusiv elementele acesteia cu functia triu(A) , dupa care am scazut elementele de pe diagonala principala folosind funtia diag(A) si am adaugat 1 pe diagonala principala utilizand functia eye(n).

D.               Factorizarea prin metoda Cholesky[4]

Fisierul functie care a fost implementat este: Cholesky.m.

In acest fisier a fost implementat un program de calcul al factorizarii unei matrice prin metoda Cholesky pe baza algoritmului:

-initializare:

, i = 2:n

-pentru k = 2:n

, k≠n, i = k+1:n

Ca functie Matlab utilizata mentionam sqrt(x) care returneaza radical de ordinul 2 din x. Sumele au fost calculate cu ajutorul unui ciclu for. Pasii au fost parcursi si ei in cicluri for, iar testarile s-au facut cu ajutorul instructiunei if.

Exemplificari

A.Calculul inversei prin metoda eliminarii a lui Gauss-Jordan

Consideram matricea A si parcuregem pasii descrisi la capitolul anterior.

Pornim de la :

la pasul k = 1 obtinem valorile:

(j = 2):

(j = 3):

(j = 1):

(j = 2):

(j = 3):

(i = 1): a¹(1,1) = 1

(i = 2): d¹(2,2) = 1

(i = 3): d¹(3,3) = 1

(i = 2;j = 2): a¹(2,2) = a⁰(2,2)-a⁰(2,1)*a¹(1,2) = -1-2*0.5 = -2

(i = 2;j = 3): a¹(2,3) = a⁰(2,3)-a⁰(2,1)*a¹(1,3) = 2-2*(-0.5) = 3

(i = 3;j = 2): a¹(3,2) = a⁰(3,2)-a⁰(3,1)*a¹(1,2) = 1-3*0.5 = -0.5

(i = 3;j = 3): a¹(3,3) = a⁰(3,3)-a⁰(3,1)*a¹(1,3) = 1-3*(-0.5) = 2.5

(i = 2;j = 1): d¹(2,1) = d⁰(2,1)-a⁰(2,1)*d¹(1,1) = 0-2*0.5 = -1

(i = 3;j = 1): d¹(3,1) = d⁰(3,1)-a⁰(3,1)*d¹(1,1) = 0-3*0.5 = -1.5

(i = 2;j = 1): a¹(2,1) = 0

(i = 3;j = 1): a¹(3,1) = 0

(i = 1;j = 2): d¹(1,2) = 0

(i = 1;j = 3): d¹(1,3) = 0

(i = 2;j = 3): d¹(2,3) = 0

(i = 3;j = 2): d¹(3,2) = 0

= >

-la pasul k = 2 obtinem valorile:

(j = 3):

(j = 1):

(j = 2):

(i = 1): a²(1,1) = 1

(i = 2): a²(2,2) = 1

(i = 3): d²(3,3) = 1

(i = 1;j = 3): a²(1,3) = a¹(1,3)-a¹(1,2)*a²(2,3) = -0.5-0.5*(-1.5) = 0.25

(i = 3;j = 3): a²(3,3) = a¹(3,3)-a¹(3,2)*a²(2,3) = 2.5-0.5*(-1.5) = 1.75

(i = 1;j = 1): d²(1,1) = d¹(1,1)-a¹(1,2)*d²(2,1) = 0.5-0.5*0.5 = 0.25

(i = 1;j = 2): d²(1,2) = d¹(1,2)-a¹(1,2)*d²(2,2) = 0-0.5*(-0.5) = 0.25

(i = 3;j = 1): d²(3,1) = d¹(3,1)-a¹(3,2)*d²(2,1) = -1.5+0.5*0.5 = -0.75

(i = 3;j = 2): d²(3,2) = d¹(3,2)-a¹(3,2)*d²(2,2) = 0+0.5*(-0.5) = -0.25

(i = 1;j = 2): a²(1,2) = 0

(i = 2;j = 1): a²(2,1) = 0

(i = 3;j = 1): a²(3,1) = 0

(i = 3;j = 2): a²(3,2) = 0

(i = 1;j = 3): d²(1,3) = 0

(i = 2;j = 3): d²(2,3) = 0

= >

-la pasul k = 3 obtinem valorile:

(j = 1):

(j = 2):

(j = 3):

(i = 1): a³(1,1) = 1

(i = 2): a³(2,2) = 1

(i = 3): a³(3,3) = 1

(i = 1;j = 1): d³(1,1) = d²(1,1)-a²(1,3)*d³(3,1) = 0.25-0.25*(-0.714) = 0.428

(i = 1;j = 2): d³(1,2) = d²(1,2)-a²(1,3)*d³(3,2) = 0.25-0.25*(-0.143) = 0.285

(i = 1;j = 3): d³(1,3) = d²(1,3)-a²(1,3)*d³(3,3) = 0-0.25*0.571 = -0.142

(i = 2;j = 1): d³(2,1) = d²(2,1)-a²(2,3)*d³(3,1) = 0.5+1.5*(-0.714) = -0.571

(i = 2;j = 2): d³(2,2) = d²(2,2)-a²(2,3)*d³(3,2) = -0.5+1.5*(-0.143) = -0.714

(i = 2;j = 3): d³(2,3) = d²(2,3)-a²(2,3)*d³(3,3) = 0+1.5*0.571) = 0.857

(i = 1;j = 2): a³(1,2) = 0

(i = 1;j = 3): a³(1,3) = 0

(i = 2;j = 1): a³(2,1) = 0

(i = 2;j = 3): a³(2,3) = 0

(i = 3;j = 1): a³(3,1) = 0

(i = 3;j = 2): a³(3,2) = 0

= >

Observatii

- parcurgerea iterativa "cu creionul pe hartie" consuma mult timp si deci nu este eficienta

- efectuand verificarea in Matlab, cu ajutorul functiei Gauss_Jordan implementate am observat ca am ajuns la aceleasi rezultate.

- se observa ca pe parcursul iteratiilor se schimba rolurile lui A si a lui D, in sensul ca D a fost la inceput matricea unitate, iar la sfarsit matricea A este matricea unitate, si plecand de la matricea A data ajungem la matricea D inversata.

B.Factorizarea prin metoda Doolittle

Consideram matricea A si parcuregem pasii descrisi la capitolul anterior.

-la pasul k = 1 obtinem urmatoarele valori:

L(1,1) = 1

(j = 1): U(1,1) = A(1,1) = 1

(j = 2): U(1,2) = A(1,2) = 1

(j = 3): U(1,3) = A(1,3) = 1

(i = 2):

(i = 3):

-la pasul k = 2 obtinem urmatoarele valori:

L(2,2) = 1

(j = 2): U(2,2) = A(2,2)-L(2,1)*U(1,2) = 2-0.5*1 = 1.5

(j = 3): U(2,3) = A(2,3)-L(2,1)*U(1,3) = 2-0.5*1 = 1.5

(i = 3):

-la pasul k = 3 obtinem urmatoarele valori:

L(3,3) = 1

(j = 3): U(3,3) = A(3,3)-L(3,1)*U(1,3)-L(3,2)*U(2,3) = 9-0.5*1-1*1.5 = 7

In final am obtinut matricele:

Se observa ca,parcurgand pasii nu obtinem si valorile de deasupra diagonalei principale pentru L, respectiv de sub diagonala principala pentru U, stiind ca trebuie ca L sa fie o matrice inferior triunghiulara, iar U o matrice superior triunghiulara se inlocuieste implicit cu 0.

Efectuand verificarea in Matlab, cu ajutorul functiei Doolittle implementate am observat ca exista o eroare, si anume U(2,3) = 1 si U(3,3) = 6,5. Pentru a vedea daca eroarea se mentine pe aceleasi pozitii mai luam un exemplu.

-la pasul k = 1 avem:

L(1,1) = 1

(j = 1): U(1,1) = A(1,1) = 9

(j = 2): U(1,2) = A(1,2) = 1

(j = 3): U(1,3) = A(1,3) = 5

(i = 2):

(i = 3):

-la pasul k = 2 avem:

L(2,2) = 1

(j = 2): U(2,2) = A(2,2)-L(2,1)*U(1,2) = 7-0.11*1 = 6.89

(j = 3): U(2,3) = A(2,3)-L(2,1)*U(1,3) = 1-0.11*5 = 0.45

(i = 3):

-la pasul k = 3 avem:

L(3,3) = 1

(j = 3): U(3,3) = A(3,3)-L(3,1)*U(1,3)-L(3,2)*U(2,3) = 8-0.55*5-0.06*0.45 = 5.23

In final = >

Observatie: Efectuand verificarea in Matlab, cu ajutorul functiei Doolittle implementate am observat ca din nou exista o eroare, in aceleasi pozitii, si anume U(2,3) = 0.33 si U(3,3) = 4.53.

Mentionam ca am implementat diferite metode, preluate din diverse documentatii. Nici una insa nu a avut rezultatul dorit, unele fiind cu mai multe sau mai putine erori. Dintre ele am ales-o pe aceasta ca fiind cea mai apropiata de adevar.

Remarca: toate metodele implementate pentru cazul Doolittle se gasesc pe cd, in directorul Adaugari.

C.Factorizarea prin metoda Crout

Consideram matricea A si parcuregem pasii descrisi la capitolul anterior.

-la pasul p = 1 obtinem urmatoarele valori:

(i = 1): s = A(1,1:0)*A(1:0,1) = 0

A(1,1) = A(1,1)-s = 2-0 = 2

(i = 2): s = A(2,1:0)*A(1:0,1) = 0

A(2,1) = A(2,1)-s = 1-0 = 1

(i = 3): s = A(3,1:0)*A(1:0,1) = 0

A(3,1) = A(3,1)-s = 1-0 = 1

(j = 2) s = A(1,1:0)*A(1:0,2) = 0

(j = 3) s = A(1,1:0)*A(1:0,3) = 0

-la pasul p = 2 se obtin urmatoarele valori:

(i = 2): s = A(2,1:1)*A(1:1,2) = 1*0.5 = 0.5

A(2,2) = A(2,2)-s = 2-0.5 = 1.5

(i = 3): s = A(3,1:1)*A(1:1,2) = 1*0.5 = 0.5

A(3,2) = A(3,2)-s = 2-0.5 = 1.5

(j = 3): s = A(2,1:1)*A(1:1,3) = 1*0.5 = 0.5

-la pasul p = 3 se obtin urmatoarele valori:

(i = 3):

A(3,3) = A(3,3)-s = 9-2 = 7

In final = >

-prin procedeul explicat la capitolul anterior retulta L si U:

Observatii: -efectuand verificarea in Matlab, cu ajutorul functiei Crout implementate am observat ca am ajuns la aceleasi rezultate.

-plecand de la aceeasi matrice si in cazul Crout si in cazul Doolittle am ajuns la aceleasi rezultate de unde ne dam seama ca algoritmul folosit la metoda Doolittle este corect, dar in functia implementata in Matlab pentru Doolittle undeva intervine o eroare. Mai mentionam ca, rezultatele celor doua metode nu sunt identice, in sensul ca matricea L rezultata pentru Doolittle este transpusa matricei U rezultate pentru Crout, respectiv matricea U rezultata pentru Doolittle este transpusa matricei L rezultate pentru Crout.

D.Factorizarea prin metoda Cholesky

Consideram matricea A si parcuregem pasii descrisi la capitolul anterior.

Initializare:

(i = 2):

(i = 3):

-pentru pasul k = 2 avem:

(i = 3):

-pentru pasul k = 3 avem:

= >

Observatii: -efectuand verificarea in Matlab, cu ajutorul functiei Gauss_Jordan implementate am observat ca am ajuns la aceleasi rezultate.

-Se observa ca,parcurgand pasii nu obtinem si valorile de deasupra diagonalei principale pentru L, stiind ca trebuie ca L sa fie o matrice inferior triunghiulara se inlocuieste implicit cu 0.

Concluzii

In directorul Implementari avem fisierele in care s-au realizat implementarile metodelor:

inversare: Gauss_Jordan

factorizare:

Doolittle

Crout

Cholesky

cu urmatoarele observatii:

Metoda eliminarii a lui Gauss Jordan este frecvent utilizata, nu apar erori, dar nu se mentioneaza conditia pentru ca matricea sa fie inversabila si anume:determinantul matricei pentru care calculam inversa sa fie nenul.

Algoritmul metodei de factorizare Doolittle nu este unul universal. Stiind ca trebuie sa descompunem matricea A in produsul a doua matrice de tip L (inferior triunghiulra) si U (superior triunghiulara) am gasit diferiti algoritmi pe care i-am implementat, si dintre acestia l-am ales pe cel din fisierul Doolittle.m ca avand cele mai mici si putine erori.

Algoritmul folosit pentru functia Crout este unul care duce la rezultate corecte.

Algoritmul folosit pentru functia Cholesky introduce niste erori pentru matrice de ordin mai mare sau egal cu 4. Efectuand cateva verificari am observat ca atunci cand inmultim matricele L si U rezultate, sub diagonala secundara apar erori.

Mentionam ca am implementat diferite metode, preluate din diverse documentatii. Nici una insa nu a avut rezultatul dorit, unele fiind cu mai multe sau mai putine erori. Dintre ele am ales-o pe aceasta ca fiind cea mai apropiata de adevar.

toate metodele implementate se gasesc pe cd, in directorul Adaugari, alaturi de cele de la metoda Doolittle)

In directorul Functii avem fisierele:

comparare_gauss_jordan : este un fisier functie care primeste ca parametru o matrice A pentru care se presupune ca s-a verificat ca admite inversa si returneaza doua valori reprezentand : prima timpul de executie al metodei Gauss_jordan implementate, in milisecunde si a doua timpul de executie a calcularii inversei cu ajutorul functiei predefinite inv(a) , in milisecunde.

comparare_doolittle : este un fisier functie care primeste ca parametru o matrice A pentru care se presupune ca s-a verificat ca admite factorizare de tip LU si returneaza doua valori reprezentand : prima timpul de executie al metodei Doolittle implementate, in milisecunde si a doua timpul de executie al factorizarii LU cu ajutorul functiei predefinite [l,u] = lu(a) , in milisecunde.

comparare_crout : este un fisier functie care primeste ca parametru o matrice A pentru care se presupune ca s-a verificat ca admite factorizare de tip LU si returneaza doua valori reprezentand : prima timpul de executie al metodei Crout implementate, in milisecunde si a doua timpul de executie al factorizarii LU cu ajutorul functiei predefinite [l,u] = lu(a) , in milisecunde.

comparare_cholesky : este un fisier functie care primeste ca parametru o matrice A pentru care se presupune ca s-a verificat ca admite factorizare de tip Cholesky (adica matricea este simetrica si pozitiv definita) si returneaza doua valori reprezentand : prima timpul de executie al metodei Cholesky implementate, in milisecunde si a doua timpul de executie al factorizarii Cholesky cu ajutorul functiei predefinite [l,u] = chol(a) , in milisecunde.

comparare_lu : este un fisier functie care primeste ca parametru o matrice A pentru care se presupune ca s-a verificat ca admite factorizare si returneaza trei valori reprezentand : prima timpul de executie al metodei Doolittle implementate, in milisecunde, a doua timpul de executie al metodei Crout implementate, in milisecunde si a treia timpul de executie al metodei Cholesky implementate, in milisecunde.

matr.m : este un fisier functie care nu primeste nici un parametru, dar returneaza o matrice simetrica de ordin 20x20 pentru ca aceasta indeplineste conditiile tuturor functiilor.

ex_gauss_jordan : este un fisier script in care am luat trei exemple pentru a verifica functia implementata. Efectul rularii acestui fisier este urmatorul: se afiseaza matricea pentru care calculam inversa, inversa calculata iterativ si inversa calculata cu functia predefinita inv(a). Un exemplu este cel al matricei folosita si la parcurgerea pas cu pas a algoritmului, alt exemplu este cel al matricei preluate din fisierul matr si alt exemplu este cel al unei matrice pentru care determinantul este 0. In acest ultim caz se afiseaza un mesaj de eroare.

ex_doolittle : este un fisier script in care am luat doua exemple pentru a verifica functia implementata. Efectul rularii acestui fisier este urmatorul: se afiseaza matricea pentru care calculam descompunerea LU, matricele L si U obtinute iterativ si matricea obtinuta prin verificare: A = L*U. Un exemplu este cel al matricei folosita si la parcurgerea pas cu pas a algoritmului, alt exemplu este cel al matricei preluate din fisierul matr.

ex_crout : este un fisier script in care am luat doua exemple pentru a verifica functia implementata. Efectul rularii acestui fisier este urmatorul: se afiseaza matricea pentru care calculam descompunerea LU, matricele L si U obtinute iterativ si matricea obtinuta prin verificare: A = L*U. Un exemplu este cel al matricei folosita si la parcurgerea pas cu pas a algoritmului, alt exemplu este cel al matricei preluate din fisierul matr.

ex_cholesky : este un fisier script in care am luat patru exemple pentru a verifica functia implementata. Efectul rularii acestui fisier este urmatorul: se afiseaza matricea pentru care calculam descompunerea LU, matricele L si U obtinute iterativ si matricea obtinuta prin verificare: A = L*U. Un exemplu este cel al matricei folosita si la parcurgerea pas cu pas a algoritmului, alt exemplu este cel al matricei preluate din fisierul matr, un al treilea exemplu este pentru o matrice nesimetrica si ultimul exemplu este pentru o matrice care nu este pozitiv definita. In ultimele doua cazuri se afiseaza un mesaj de eroare.

Observatii:

Pe un computer AMD Athlon cu procesor la 1,2 GHz si 256 MB de RAM am rulat functiile pe matricea din fisierul matr.m deoarece am vrut sa fim cat mai aproape de rezultatul real, si am observat:

pentru functia comparare_gauss_jordan :timpul pentru metoda iterativa:111,34 ms

timpul pentru inv(A) : 0,29 ms

pentru functia comparare_doolittle : timpul pentru metoda iterativa : 14,89 ms

timpul pentru [l,u] = lu(A) : 0,06 ms

pentru functia comparare_crout : timpul pentru metoda iterativa : 10,86 ms

timpul pentru [l,u] = lu(A) : 0,06 ms

pentru functia comparare_cholesky : timpul pentru metoda iterativa : 8,55 ms

timpul pentru [l,u] = chol(A) : 8,16 ms

pentru functia comparare_lu : timpul pentru metoda Doolittle iterativa : 14,74 ms

timpul pentru metoda Crout iterativa : 11,04 ms

timpul pentru metoda Cholesky iterativa : 8,11 ms

Se observa ca timpii pentru cele trei metode de factorizare sunt destul de apropiati, cel pentru cazul Cholesky fiind cel mai bun, dupa cum era de asteptat, dat fiind ca aceasta metoda impune cele mai multe conditii.

Pe un computer AMD Duron cu procesor la 1,6 GHz si 128 MB de RAM am rulat functiile pe matricea din fisierul matr.m deoarece am vrut sa fim cat mai aproape de rezultatul real, si am observat:

pentru functia comparare_gauss_jordan :timpul pentru metoda iterativa:80,89 ms

timpul pentru inv(A) : 0,20 ms

pentru functia comparare_doolittle : timpul pentru metoda iterativa : 10,83 ms

timpul pentru [l,u] = lu(A) : 0,04 ms

pentru functia comparare_crout : timpul pentru metoda iterativa : 8,20 ms

timpul pentru [l,u] = lu(A) : 0,04 ms

pentru functia comparare_cholesky : timpul pentru metoda iterativa : 6,08 ms

timpul pentru [l,u] = chol(A) : 6,08 ms

pentru functia comparare_lu : timpul pentru metoda Doolittle iterativa : 10,82 ms

timpul pentru metoda Crout iterativa : 8,15 ms

timpul pentru metoda Cholesky iterativa : 5,92 ms

Din nou, se observa ca timpii pentru cele trei metode de factorizare sunt destul de apropiati, cel pentru cazul Cholesky fiind cel mai bun, dupa cum era de asteptat, dat fiind ca aceasta metoda impune cele mai multe conditii.

Daca ar fii sa comparam aceste doua rezultate obtinute pe computere diferite, tragem concluzia, care era evidenta de fapt, ca timpii de executie ai tuturor metodelor depind in primul rand de tipul computerului si de "viteza de gandire" a acestuia.

Functii predefinite ale mediilor Matlab si Mathcad

A. Functii predefinite ale mediului Matlab

Functia Matlab care permite obtinerea inversei unei matrice este: inv(A).

Sintaxa : Inv(A) - functia returneaza inversa matricei patratice A.In cazul in care A nu este patratica Matlab ne pune la dispozitie functia pinv(A).

O alta modalitate de a obtine inversa lui A este urmatoarea:

Aeye(size(A)) , unde size(A) returneaza dimensiunea matricei A, iar eye(size(A)) returneaza matricea unitate de dimensiune size(A).

Instructiunea Matlab care se foloseste pentru factorizare LU este:

[L,U] = lu(A) : are ca rezultat o matrice superior triunghiulara U si o matrice inferior triunghiulara cu 1 pe diagonala principala L astfel incat A = L*U.

O alta sintaxa a acestei instructiuni este:

[L,U,P] = lu(A) : are ca rezultat o matrice superior triunghiulara U si o matrice inferior triunghiulara cu 1 pe diagonala principala L si permutarea matriciala P astfel incat P*A = L*U.

Pentru factorizarea QR se pot folosi instructiunile:

[Q,R] = qr(A) : are ca rezultat o matrice ortonormata Q de aceeasi dimensiune cu A si o matrice superior triunghiulara R astfel incat A = QR.

[Q,R,E] = qr(A) : are ca rezultat matricea permutata E a matricei superior triunghiulare R, cu elementele diagonalei descrescatoare si matricea ortonormata Q astfel incat AE = QR.

Pentru factorizarea Cholesky Matlab ne pune la dispozitie instructiunea:

L = chol(A) : matricea L este o matrice superior triunghiulara astfel incat A = L^TL.

La factorizarea Cholesky se impune conditia ca matricea A sa fie simetrica si pozitiv definita. Daca A nu este pozitiv definita se va afisa un msaj de eroare. Pentru a verifica daca A este pozitiv definita se poate folosi instruntiunea:

[A,p] = chol(A) unde p este 0 daca A este pozitiv definita si p are o valoare pozitiva in caz contrar.

B. Functii predefinite pentru mediul Mathcad

Functia Mathcad care permite obtinerea inversei unei matrice A este: geninv(A). Aceasta determina matricea A^-1 astfel incat A^-1*A = I, unde I este matricea unitate.

In Mathcad matricea unitate de ordinul n se obtine cu ajutorul functiei: identity(n).

Factorizarea LU a matricei patratice A se realizeaza cu ajutorul instructiunii: lu(A). Aceasta are ca rezultat o matrice ce este constituita din alipirea a trei matrice patratice P,L si U astfel incat P*A = L*U. Matricele P,L si U se pot extrage cu ajutorul functiei submatrix.

Factorizarea QR a matricei patratice A se realizeaza cu ajutorul instructiunii : qr(A). Aceasta are ca rezultat o matrice ce este constituita din alipirea a doua matrice Q si R, unde Q este o matrice ortonormata, iar R superior triunghiulara. Matricele Q si R se pot extrage cu ajutorul functiei submatrix.

Factorizarea Cholesky a matricei patratice A se realizeaza cu ajutorul instructiunii : cholesky(A). Aceasta are ca rezultat o matrice inferior triunghiulara L astfel incat A = L*L^T.

Bibliografie

Precup R.-E.,Dragomir L., Bulavitchi I.,"Matematici asistate de calculator. Aplicatii", Editura Politehnica, Timisoara, 2002

Ghinea M., Fireteanu V., "MATLAB.Calul numeric-Grafica-Aplicatii", Editura Teora 1997

Cira O., "Lectii de Mathcad", Editura Albastra, Cluj-Napoca, 2001

Naslau P., Negrea R., Cadariu L., Caruntu B., Popescu D., Balmez M., Dumitrascu C., "Matematici asistate de calculator-Matlab,Mathcad, Mathematica, Maple, Derive", Editura Politehnica, Timisoara 2005

cs.pub.ro/~mn/Cursuri/c4mn.ppt    (c2mnb din Bibliografie web)