Buna ziua !

Intampin probleme cand incerc sa calculez inversa unei matrice de ordin 3.
Prin metoda "clasica" , invatata in liceu :

, pot rezolva rapid inversa, insa doresc sa stiu cum se poate calcula aceasta prin metoda Jordan-Gauss. Tin sa precizez ca am cautat cateva surse pe Internet pentru a ma clarifica, dar, in final, tot la dumneavoastra apelez, in speranta ca ma puteti ajuta .

Va multumesc pentru timpul acordat.
O zi buna in continuare.
Bogdan

http://en.wikipedia.org/wiki/Gauss-Jordan_elimination

Sa incercam impreuna.

Idea este relativ simpla, trebuie mai intai inteles modul in care se rezolva un sistem de n ecuatii cu n necunoscute prin metoda de eliminare completa. (Gauss)

Exista o schema cunoscuta prin care se face acest lucru.
La facultate, am fost obligat sa folosesc aceasta metoda (cum ni s-a explicat la seminar), dar daca nu as fi stiut-o in prealabil mi s-ar fi parut o catastrofa.
Asadar, inteleg foarte bine retinerile celor ce sunt "obligati" sa inteleaga schema. Incerc cu incetinitorul.

Ne legam de un sistem cu doua ecuatii si doua necunoscute.
(Acest "baby step" este tot ce ne trebuie!)

Sa ziem ca avem de rezolvat sistemul

ax + by = s
cx + dy = t

unde a,b,c,d;s,t sunt parametrii fixati. Ca sa scap de probleme aici in expunere, sa zicem ca avem a, ad-bc numere reale NENULE.

Rescriem

[ a b ] [x]
[ c d ] [y]

pentru... si la fel pe partea cealalta a egalurilor. (Ca sa tiparesc frumos, trebuie sa intru in latex... timpul...)

Operatia numita "inmultim prima linie cu u" revine la inmultirea din STANGA cu matricea
[u 0]
[0 1]

Operatia numita "inmultim a doua linie cu v" revine la inmultirea din STANGA cu matricea
[1 0]
[0 v]

Operatia numita "inmultim prima linie cu -c/a si o adunam la a doua" (prima linie NU se schimba, a doua se schimba cu operatia liniara descrisa) revine la inmultirea din STANGA cu matricea "E"lementara E(2,1;r) unde r se alege...
[1 0]
[r 1]

Atunci d se inlocuieste cu d - bc/a .
Forma ( ad - bc ) / a ar trebui sa ne aduca aminte de ceva...

Pe scurt:
a nenul se numeste "PIVOT".

Daca avem mai multe randuri si situatia

a ... b ...
:
c ... d ...

atunci se inlocuieste ce vedem mai sus cu

a ... b ...............
:
0 ... (d - bc/a) ......

Numim acest pas "pas Gauss". A se vedea pozitia de "dreptunghi" elementelor din matrice. "Acelasi lucru" il facem daca linia sau coloana pivotului nu este "prima".
Este excelent daca ne putem aranja cu pivotul a = unu .

Exemplu de rezolvare de sistem:
Sa se rezolve

2x + 7y = 15
3x + 10 y = 3 .

Scriem
2 7 | 15
3 11| 3 apoi (cu pivotl 2, de obicei incercuit)

2 7 | 15
0 D | S unde D = 11 - 3.7/ 2 sau ( 11.2 -3.7 )/2 si S = 3 - 3.15/2 = ...

dam de solutia urata destul de repede. Dar ceea ce ma intereseaza aici este eliminarea totala. Sa inmultim a doua linie cu 2 pentru a da de

2 7 | 15
0 1 | -39
Ne uitam la acel unu ca pivot, eliminam pe prima linie.

In loc de 2 dam (pas gauss) de 2 - 0.7/1 deci tot de 2. (Cand vedem un zero...)
7 sta pe loc.
15 devine 15 - 7 .(-39) / 1 = 288

Rescriem deci dupa pasul de eliminare completa:
2 0 | 288
0 1 | -39

apoi
1 0 | 144
0 1 | -39 .

E clar care este solutia...

----------------------------------

Sa calculam acum cu aceeasi metoda inversa unei matrici cu intrarle a,b,c,d.
Scriem schema:

a b | 1 0
c d | 0 1

si ne facem ca rezolvam un sistem doua sisteme de doua ecuatii in acelasi timp, anume cele pentru schema de plecare

a b | 1
c d | 0

si

a b | 0
c d | 1

Idea este de a intelege ce facem aici si in cazul general.
In general, scriem ceva de forma

A | E

unde A este o matrice nxn arbitrara si E este matricea nxn identica, 1 pe diagonala, in rest 0. De aici ne vom muta cu pasi Gauss mereu in alte perechi de matrici scrise

B | S

unde mereu (ca si la inceput) avem relatia
B = SA .

Trecem de la B | S la ceva de forma B' | S' prin operatii ca cele simple descrise mai sus de inmultire de exemplu din STANGA cu o matrice elementara E(i,j;r) . Desigur ca relatia

B = SA implica
E(i,j;r) B = E(i,j;r) SA = E(i,j;r)S A , deci
B' = S'A .

Aplicam astfel de pasi pana ce in locul lui B dam de matricea identica E.
Atunci pe partea cealalta...

Exemplu de calcul a inversei matricii

2 3
3 7

Plecam cu

2 3 | 1 0
3 7 | 0 1 si dam succesiv de... (iau pivotul 2)

2 3 | 1 0
0 D | S T cu D = 7 - 9/2 = 5/2, S = 0 - 3/2 , T = 1 - 0 = 1, apoi dupa "ori 2"

2 3 | 1 0
0 5 |-3 2 luam aici 5 pivot,

2 0 | U V unde U = 1 - (-3).3/5 = 1 + 9/5 = 14/5 si V = 0 - 2.3 / 5
0 5 |-3 2

luam acum prima linie "ori 5/2" (de fapt doar 1/2, dar atunci pierd formatarea) si dam de

5 0 | 7 -3
0 5 |-3 2

si acum impartim fiecare din linii cu 5 ...

Am lucrat mult pentru a da de solutia simpla. Da, in acest caz scriem solutia simpla. Dar daca avem de lucru cu o matrice 3x3 lucrurile se schimba. (Mai ales daca izolam pivoti si minori 2x2 cu determinanti mici cu ochiul liber la inceput.)

In orice caz, sper ca principiul e clar.
De la o vreme, acele multe intrari egale cu zero se vad imediat, ceea ce e scris mai sus cand mai aparea un 0 este o operatie imediata.

Sper ca principiul e clar, in orice caz.
Sa incercam sa inversam ceva explicit? (Daca da, cu incredere.)

Va multumesc mult pentru raspunsurile prompte.

Am pornit prima data sa inteleg o matrice 2x2 folosind exemplele date de dumneavoastra, urmand ca mai apoi sa ajung sa generalizez pentru o matrice 4x4. Daca am inteles bine, prin acesti asa numiti "pasi Gauss" ajung sa permut o matrice unitate

, dar schimband valori pentru termenii de pe o anumita linie, dupa formula

, formula care, si va citez domnule Gauss, "ar trebui sa ne aduca aminte de ceva..." ; doar ca semnificatia acelui determinant impatit la un element al matricei imi este inca necunoscuta, in ciuda cautarilor pe care le-am facut prin fisele de algebra clasei a XI-a. Va rog deci, daca s-ar putea sa faceti putina lumina in acest caz .

De asemenea, v-as ruga, daca doriti, sa-mi explicati ce anume se ascunde in spatele acestei metode. De ce ar alege cineva sa faca in unele cazuri simple acest calcul mai greoi din punctul meu de vedere, in defavoarea formulei clasice

?

[Citat] De ce ar alege cineva sa faca in unele cazuri simple acest calcul mai greoi din punctul meu de vedere, in defavoarea formulei clasice ?

Bogdane, tu ai citit postarea mea? Ai priceput care e algoritmul?

EDIT: Bogdan mi-a fost elev, a?a c? pot s?-l tutuiesc

Se pare ca nu stii. Complexitatea algoritmului de calcul a inversei e foarte mare. In literatura de specialitate acesta se noteaza cu O(si nu numai). S-a definit aceasta notiune din necesitatea de a numara pasii pentru un algoritm si a se vedea in ce categorie il bagam. Determinarea inversei cu adjuncta are complexitatea O(n^4) iar cea a inversei cu metoda lui Gauss are O(n^3) de aceea e cu mult peste Gauss decat clasica. In metoda lui Gauss : avem un indice care pastreaza linia pe care ne aflam, unul care pastreaza coloana curenta si un altu` pentru acele transformari. La metoda clasica gandeste-te asha: ai de calculat determinanti pana ti se face rau. Dupa ce-l faci pe ala mare de ordin n mai ai altii de calculat de ordin n-1 etc... pana la ordinul 1 sau 2. O(n^3) se zice ca e ultima complexitate admisa pentru calculatoare... deci O(n^4) e depasit... nu se mai implementeaza!

[Citat] Bogdane, tu ai citit postarea mea? Ai priceput care e algoritmul?

Algoritmul l-am inteles in cele din urma , domnule profesor , si va multumesc . Am reusit sa-l aplic si la diferite matrice 4x4 din tema, iar rezultatele mi-au dat corect, in caz contrar reusind sa identific greseala. Acum fac cateva exercitii facultative pentru a-mi fixa mai bine teoria asimilata.

Doream doar sa stiu de ce se prefera scrierea prin metoda Gauss in defavoarea celei care se invata in liceu, iar Dl Blaugranas mi-a explicat. Am o vaga idee de la informatica despre gradele de complexitate, insa nu indeajuns incat sa-mi dau seama exact ce se doresc a fi. Voi cauta insa sa inteleg :D

OK, succes!

Ma bucur ca esti curios. Daca vrei o documentatie scurta si la obiect... stii prietenul nostru wikipedia ne ajuta mereu in acest sens. Daca vrei ceva mai amplu dar mai pe neinteles incearca sa cauti despre Knuth pe net. El este parintele complexitatii, al Latex-ului, al programarii in limbaj-masina si multe altele... e cam taticu` in domeniu !

[Citat] ... dupa formula , formula care "ar trebui sa ne aduca aminte de ceva..."

Da, este doar vorba despre determinantul (ad-bc) care se afla in numarator.
Nu este nimic altceva. La seminarii a mai trebuit sa motivez de ce se ia

d - bc/a ,

asa ca din prima ma leg de o expresie cu numaratorul ad-bc cand incerc sa explic.
Formula ramane mai usor in minte si dupa ani.
d-ul se inlocuieste cu
"(un determinant anume, oare care anume?) supra pivot".

[Citat] OK, succes!

Va multumesc, domnule profesor. Toate cele bune !

[Citat] Ma bucur ca esti curios. Daca vrei o documentatie scurta si la obiect... stii prietenul nostru wikipedia ne ajuta mereu in acest sens. Daca vrei ceva mai amplu dar mai pe neinteles incearca sa cauti despre Knuth pe net. El este parintele complexitatii, al Latex-ului, al programarii in limbaj-masina si multe altele... e cam taticu` in domeniu !

Cand am citit pentru prima data raspunsul dumneavoastra nu l-am inteles. Am vizitat prima data google, iar prin intermediul lui, wikipedia, pentru o teorie a complexitatii. Din pacate formularea este cam greoaie : [url]http://ro.wikipedia.org/wiki/P_%28teoria_complexit%C4%83%C8%9Bii%29/ .
Caut inca o exprimare mai pe intelesul meu :D.