thumb|Animație cu eliminarea gaussiană. Linia roșie anulează elemente din următoarele linii, liniile verzi sunt permutate În matematică eliminarea gaussiană este un algoritm de rezolvare a sistem de ecuații liniare. Aceasta constă dintr-o secvență de operații pe linii efectuate asupra matricei coeficienților. Această metodă poate fi utilizată și pentru a calcula rangul unei matrice, determinantul unei matrice pătrate și inversa unei matrice inversabile. Metoda este numită după Carl Friedrich Gauss.
Pentru a executa reducerea unei linii dintr-o matrice, se folosește o secvență de operații elementare pe linii, care modifică matricea până ce cât mai multe elemente din partea de stânga-jos a matricei devin zero. Există trei feluri de operații elementare pe linii: permutarea a două linii, înmulțirea unei linii cu un număr nenul, și adunarea multiplului unei linii la altă linie. Folosind aceste operații, o matrice poate fi întotdeauna transformată într-o matrice superior triunghiulară: fiecare linie nenulă este deasupra fiecărui linii nule, fiecare linie nenulă are elementul cel mai din stânga nenul egal cu 1, coloanele care conțin acești „1” au toate celelalte elemente 0, iar linia următoare are „1”-le în dreapta față de „1”-le de linia anterioară. Această formă finală este unică; cu alte cuvinte, este independentă de succesiunea de operații pe linii utilizate. De exemplu, în următoarea secvență de operații pe linii (unde se fac două operații elementare pe linii diferite la primul și al treilea pas) matricea finală este în forma unică de matrice superior triunghiulară redusă.
Utilizarea operațiilor pe linii pentru a transforma o matrice într-una superior triunghiulară este uneori numită „eliminare Gauss–Jordan”. În acest caz, termenul „eliminare gaussiană” se referă la procesul până când matricea a atins forma superior triunghiulară (neredusă). Din motive de calcul, atunci când se rezolvă sisteme de ecuații liniare, uneori este de preferat să fie oprite operațiile pe linii înainte ca matricea să fie complet redusă.
Istoric Metoda eliminării gaussiene apare în textul matematic chinezesc Calculul bețelor, capitolul opt: Tabele dreptunghiulare din Cele nouă capitole ale artei matematice, însă fără demonstrație. Utilizarea sa este ilustrată în optsprezece probleme, cu două până la cinci ecuații. Prima referință la cartea cu acest titlu este datată din anul 179 d.Hr., dar părți din ea au fost scrise încă din jurul anului 150 î.Hr. } A fost comentată de Liu Hui în secolul al III-lea.
După Grcar rezolvarea ecuațiilor liniare prin eliminare a fost inventată independent în mai multe culturi din Eurasia încă din antichitate, iar în Europa exemple concrete ale acestei proceduri au fost publicate deja la sfârșitul Renașterii (în anii 1550). Este foarte posibil ca deja pe atunci procedura să fie considerată de matematicieni elementară și neavând nevoie de explicații pentru profesioniști, așa că este posibil să se afle niciodată istoria sa detaliată, cu excepția faptului că până atunci era practicată în cel puțin câteva locuri din Europa.
Metoda din Europa provine din notițele lui Isaac Newton. În 1669-1670, Newton a scris că din toate cărțile de algebră cunoscute de el lipsea de o lecție pentru rezolvarea ecuațiilor simultane, lecție pe care Newton a furnizat-o apoi. În cele din urmă, în 1707 Universitatea Cambridge a publicat notițele sub titlul Arithmetica Universalis, mult după ce Newton părăsise viața academică. Notițele au fost imitate pe scară largă, ceea ce a făcut ca până la sfârșitul secolului al XVIII-lea (ceea ce se numește acum) eliminarea gaussiană să devină o lecție standard în manualele de algebră. Gauss a conceput în 1810 o notație pentru eliminarea simetrică, care a fost adoptată în secolul al XIX-lea de către calculatorii profesioniști pentru a rezolva ecuațiile normale ale problemelor celor mai mici pătrate. Algoritmul care este predat în liceu a fost numit după Gauss abia în anii 1950, ca urmare a confuziei privind istoria materiei.
Unii autori folosesc termenul „eliminare gaussiană” pentru a se referi doar la procedura până când matricea este în formă superior triunghiulară și folosesc termenul de „eliminare Gauss–Jordan” pentru a se referi la procedura care se termină în formă redusă. Acest nume este folosit deoarece este o variantă a eliminării gaussiene așa cum a fost descrisă de Wilhelm Jordan în 1888. Însă metoda apare și într-un articol de Clasen publicat în același an. Probabil Jordan și Clasen au descoperit independent eliminarea Gauss–Jordan.
Definiții și exemplu cu algoritmul Procesul de reducere pe linii utilizează operații elementare pe linii și poate fi împărțit în două părți. Prima parte (uneori numită „eliminarea directă”) reduce un sistem dat la forma superior triunghiulară, formă din care reiese dacă nu există soluții, dacă există o soluție unică sau un număr infinit de soluții. A doua parte (uneori numită „substituția inversă”) continuă să utilizeze operații pe linii până când se obține soluția; cu alte cuvinte, pune matricea în forma redusă.
Un alt punct de vedere, care se dovedește a fi foarte util pentru analiza algoritmului, este acela că reducerea pe linii produce o a matricei originale. Operațiile elementare pe linii pot fi văzute ca înmulțirea la stânga a matricei originale cu matrici elementare. Alternativ, o secvență de operații elementare care reduce o singură linie poate fi văzută ca înmulțirea cu o . Apoi, prima parte a algoritmului calculează o , în timp ce a doua parte scrie matricea originală ca produsul unei matrice inversabile determinate în mod unic și al unei matrice superior triunghiulare de linii reduse, determinate în mod unic.
Operații pe linii Există trei feluri de operații elementare pe linii care pot fi efectuate asupra unei matrice: permutarea a două linii, înmulțirea unei linii cu un număr nenul, și adunarea multiplului unei linii la altă linie.
Dacă matricea este asociată unui sistem de ecuații liniare, atunci aceste operații nu modifică soluțiile. Prin urmare, dacă scopul este de a rezolva un sistem de ecuații liniare, atunci utilizarea acestor operații pe linii ar putea facilita rezolvarea problemei.
Forma superior triunghiulară Pentru fiecare linie a unei matrice, dacă linia nu constă doar din zerouri, atunci elementul nenul cel mai din stânga se numește „pivotul” liniei respective. Dacă doi pivoți se află în aceeași coloană, atunci o operație pe linii de tip 3 poate fi utilizată pentru a anula unul dintre acești pivoți. Apoi, utilizând operația de permutare a liniilor, se pot ordona întotdeauna liniile astfel încât pentru fiecare linie diferită de zero, pivotil să fie la dreapta pivotului liniei precedente. Dacă acesta este cazul, se spune că matricea este în formă superior triunghiulară. În această formă, partea din stânga jos a matricei conține doar zerouri, iar toate liniile nule sunt sub liniile nenule.
De exemplu, următoarea matrice este în formă superior triunghiulară, iar pivoții săi sunt afișați cu roșu:
Este în formă superior triunghiulară deoarece linia zero este în partea de jos, iar pivotul celei de a doua linii (în a treia coloană) este în dreapta pivotului primei linii (în a doua coloană).
O matrice se spune că este în formă superior triunghiulară redusă dacă, în plus, toți pivoții sunt egali cu 1 (ceea ce poate fi realizat utilizând operația elementară pe linii de tip 2), iar în fiecare coloană care conține un pivot toate celelalte elemente din acea coloană sunt zero (ceea ce poate fi realizat utilizând operații elementare pe linii de tip 3).
Exemplu cu algoritmul Se presupune că scopul este de a găsi și descrie mulțimea soluțiilor pentru următorul sistem de ecuații liniare:
Tabelul de mai jos prezintă procesul de reducere a liniilor aplicat simultan sistemului de ecuații și matricei extinse asociate. În practică, de obicei nu se tratează sistemele drept ecuații, ci se utilizează matricea extinsă, care este mai potrivită pentru manipulările pe calculator. Procedura de reducere a liniilor poate fi rezumată după cum urmează: sw elimină din toate ecuațiile de sub , apoi se elimină din toate ecuațiile de sub . Aceasta va pune sistemul în formă superior triunghiulară. Apoi, folosind substituția inversă, fiecare necunoscută poate fi calculată. {| class="wikitable" |- ! Sistem de ecuații !! Operații pe linii !! Matricea extinsă |- align="center"
|- align="center"
|- align="center"
|colspan=3 align="center"| Acum matricea este în formă superior triunghiulară. |- align="center"
|- align="center"
|- align="center"
| colspan="3" align="center"|Acum matricea este în formă superior triunghiulară redusă
A doua coloană din tabel descrie operațiunile pe linii care tocmai au fost efectuate. La primul pas, este eliminat din prin adunarea a la . Apoi, este eliminat din prin adunarea a la . Aceste operații pe linii sunt etichetate în tabel ca
Odată ce este eliminat și din a treia linie, rezultatul este un sistem de ecuații liniare în formă triunghiulară, astfel încât prima parte a algoritmului este completă. Din punct de vedere computațional, este mai rapid să se rezolve variabilele în ordine inversă, un proces cunoscut sub numele de substituție inversă. Se observă că soluția este , și . În acest caz particular există o soluție unică la sistemul original de ecuații.
În loc să se oprească odată ce matricea este în formă superior triunghiulară, s-ar putea continua până când matricea este în formă superior triunghiulară „redusă”, așa cum se face în tabel. Procesul de reducere a liniilor până când matricea este redusă este uneori denumit eliminare Gauss-Jordan, pentru a-l distinge de oprirea după atingerea formei superior triunghiulare.
Aplicații Din punct de vedere istoric, prima aplicație a metodei de reducere pe linii este cea pentru rezolvarea sistemelor de ecuații liniare. Mai jos sunt prezentate alte câteva aplicații importante ale algoritmului.
Calculul determinanților Pentru a explica cum eliminarea gaussiană permite calcularea determinantului unei matrice pătrate, trebuie reamintit cum operațiile elementare pe linii modifică determinantul: permutarea a două linii înmulțește determinantul cu −1, înmulțirea unei linii cu un scalar nenul înmulțește determinantul cu același scalar, adunarea la o linie a unui multiplu scalar al altei linii nu modifică determinantul.
Dacă eliminarea gaussiană aplicată unei matrice pătrate produce o matrice superior triunghiulară , fie produsul scalarilor cu care a fost înmulțit determinantul, folosind regulile de mai sus. Atunci determinantul lui este câtul dintre produsul elementelor diagonalei lui și :
Computațional, pentru o matrice această metodă necesită doar operații aritmetice, în timp ce utilizarea formulei lui Leibniz pentru determinanți necesită operații (numărul de adunări din formulă înmulțit cu numărul de înmulțiri din fiecare produs), iar dezvoltarea Laplace recursivă necesită operații dacă subdeterminanții sunt memorați pentru a fi calculați o singură dată (numărul de operații dintr-o combinație liniară înmulțit cu numărul de subdeterminanți de calculat, care sunt determinați de coloanele lor). Chiar și pe cele mai rapide computere, aceste două metode sunt practic impracticabile pentru
Inversarea unei matrice
O variantă a eliminării gaussiene numită „eliminarea Gauss-Jordan” poate fi utilizată pentru a găsi inversa unei matrice, dacă aceasta există. Dacă este o matrice pătrată atunci se poate utiliza reducerea pe linii pentru a calcula matricea inversă, dacă există. Mai întâi, matricea unitate formează extensia la dreapta lui , formând o matrice de blocuri . Acum, prin aplicarea operațiilor elementare pe linii, se obține forma superior triunghiulară redusă a acestei matrice . Matricea este inversabilă dacă și numai dacă blocul din stânga poate fi redus la matricea unitate ; în acest caz blocul din dreapta al matricei finale este . Dacă algoritmul nu poate reduce blocul din stânga la , atunci nu este inversabilă.