Eliminare gaussiană

Î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ă.

{\begin{bmatrix}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\to {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{bmatrix}}

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.^[1]^[2]^[3] A fost comentată de Liu Hui în secolul al III-lea.

După Grcar^[4] 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.^[4]^[5] Î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.^[6] Algoritmul care este predat în liceu a fost numit după Gauss abia în anii 1950, ca urmare a confuziei privind istoria materiei.^[7]

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.^[8]

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 descompunere matricială^⁠(d) 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 matrice Frobenius^⁠(d). Apoi, prima parte a algoritmului calculează o descompunere LU^⁠(d), î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:

{\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}

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:

{\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}

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ă $x$ din toate ecuațiile de sub $L 1$ , apoi se elimină $y$ din toate ecuațiile de sub $L 2$ . Aceasta va pune sistemul în formă superior triunghiulară. Apoi, folosind substituția inversă, fiecare necunoscută poate fi calculată.

Sistem de ecuații	Operații pe linii	Matricea extinsă
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}$		$\left[{\begin{array}{rrr\|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}$	$L_{3}+-4L_{2}\to L_{3}$	$\left[{\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$
Acum matricea este în formă superior triunghiulară.
${\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}$	${\begin{aligned}L_{1}-L_{3}&\to L_{1}\\L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\end{aligned}}$	$\left[{\begin{array}{rrr\|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&-1&1\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr\|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
${\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr\|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
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, $x$ este eliminat din $L 2$ prin adunarea a $3 / 2 L 1$ la $L 2$ . Apoi, $x$ este eliminat din $L 3$ prin adunarea a $L 1$ la $L 3$ . Aceste operații pe linii sunt etichetate în tabel ca

{\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}

Odată ce $y$ 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 $z = -1$ , $y = 3$ și $x = 2$ . Î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 $A$ produce o matrice superior triunghiulară $B$ , fie $d$ produsul scalarilor cu care a fost înmulțit determinantul, folosind regulile de mai sus. Atunci determinantul lui $A$ este câtul dintre produsul elementelor diagonalei lui $B$ și $d$ :

\det(A)={\frac {\prod \operatorname {diag} (B)}{d}}

Computațional, pentru o matrice $n \times n,$ această metodă necesită doar $O(n 3)$ operații aritmetice, în timp ce utilizarea formulei lui Leibniz pentru determinanți necesită $(n\,n!)$ 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ă $O(n 2 n)$ 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 $n > 20 .$

Inversarea unei matrice

Vezi și: 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ă $A$ este o matrice pătrată $n \times n,$ atunci se poate utiliza reducerea pe linii pentru a calcula matricea inversă, dacă există. Mai întâi, matricea unitate $n \times n$ formează extensia la dreapta lui $A$ , formând o matrice de blocuri $n \times 2 n$ $[A | I]$ . Acum, prin aplicarea operațiilor elementare pe linii, se obține forma superior triunghiulară redusă a acestei matrice $n \times 2 n$ . Matricea $A$ este inversabilă dacă și numai dacă blocul din stânga poate fi redus la matricea unitate $I$ ; în acest caz blocul din dreapta al matricei finale este $A -1$ . Dacă algoritmul nu poate reduce blocul din stânga la $I$ , atunci $A$ nu este inversabilă.

De exemplu, fie matricea:

A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}

Pentru a găsi inversa acestei matrice, se ia următoarea matrice extinsă cu unitatea și se reduce pe linii la o matrice $3 \times 6:$

[A|I]=\left[{\begin{array}{ccc|ccc}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{array}}\right]

Prin efectuarea operațiilor pe linii se poate verifica dacă forma superior triunghiulară redusă a acestei matrice extinse este

[I|B]=\left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right]

Fiecare operație pe linie poate fi considerată produsul la stânga cu o matrice elementară. Notând cu $B$ produsul cu aceste matrici elementare, se poate arăta că în membrul stâng $BA = I,$ prin urmare $B = A -1 .$ În membrul drept s-a ținut evidența lui $BI = B$ , despre care se știe că este inversa dorită. Această procedură pentru găsirea inversei funcționează pentru matrici pătrate de orice dimensiune.

Calcului rangurilor și al bazelor

Algoritmul de eliminare gaussiană poate fi aplicat oricărei matrice $m \times n,$ $A.$ De exemplu, unele matrice $6 \times 9$ pot fi transformate într-o matrice care are o formă superior triunghiulară, cum ar fi

T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0\end{bmatrix}}

unde asteriscurile sunt elemente arbitrare, iar $a, b, c, d, e$ sunt elemente nenule. Această matrice superior triunghiulară, $T,$ conține o multitudine de informații despre $A$ : rangul lui $A$ este 5, deoarece $T$ are 5 linii nenule; spațiul vectorial parcurs de coloanele lui $A$ are o bază formată din coloanele 1, 3, 4, 7 și 9 (coloanele cu $a, b, c, d, e$ din $T,$ ) iar asteriscurile arată cum celelalte coloane ale lui $A$ pot fi scrise drept combinații liniare ale coloanelor bazei.

Toate acestea se aplică și formei superior triunghiulare reduse, care este un format particular de formă superior triunghiulară.

Eficiența computațională

Numărul de operații aritmetice necesare pentru a efectua reducerea liniilor este o modalitate de a măsura eficiența computațională a algoritmului. De exemplu, pentru a rezolva un sistem de $n$ ecuații cu $n$ necunoscute prin efectuarea de operații pe linii asupra matricei până când aceasta ajunge în formă superior triunghiulară, și apoi rezolvarea pentru fiecare necunoscută în ordine inversă, sunt necesare $n (n + 1)/2$ împărțiri, $(2 n 3 + 3 n 2 - 5 n)/6$ înmulțiri și $(2 n 3 + 3 n 2 - 5 n)/6$ scăderi,^[9] în total aproximativ $2 n 3 /3$ operații. Astfel, are o „complexitate aritmetică ” (complexitate în timp), unde fiecare operație aritmetică se efectuează într-o unitate de timp, independent de conținutul elementelor, de $O(n 3)$ .

Această complexitate este o bună măsură a timpului necesar pentru întregul calcul atunci când timpul pentru fiecare operație aritmetică este aproximativ constant. Acesta este cazul atunci când coeficienții sunt numere reprezentate în virgulă mobilă sau când aparțin unui corp finit. Dacă coeficienții sunt reprezentați exact prin numere întregi sau numere raționale, elementele intermediare pot crește exponențial, astfel încât complexitatea biților este exponențială.^[10] Totuși, există și algoritmul Bareiss, care este o variantă a eliminării gaussiene care evită această creștere exponențială a elementelor intermediare. Cu aceeași complexitate aritmetică de $O(n 3)$ , are o complexitate pe biți de $O(n 5),$ prin urmare are o complexitate în timp polinomial.

Eliminarea gaussiană și variantele sale pot fi utilizate pe computere pentru sisteme cu mii de ecuații și necunoscute. Totuși, costul devine prohibitiv pentru sistemele cu milioane de ecuații. Aceste sisteme mari sunt în general rezolvate folosind metode iterative. Există metode specifice pentru sistemele ale căror coeficienți au un model regulat.

Algoritmul Bareiss

Primul algoritm în timp polinomial pentru eliminarea gaussiană a fost publicat în 1967 de Jack Edmonds.^[11]^(p37) Independent și aproape simultan, Erwin Bareiss a descoperit un alt algoritm, bazat pe următoarea observație, care se aplică unei variante fără diviziune a eliminării gaussiene.

În eliminarea gaussiană standard, se scade din fiecare linie $R_{i}$ sub linia pivot $R_{k}$ un multiplu al lui $R_{k}$ cu $r_{i,k}/r_{k,k},$ unde $r_{i,k}$ și $r_{k,k}$ sunt elementele din coloana pivot ale $R_{i},$ respectiv $R_{k}.$

Varianta Bareiss constă în înlocuirea lui $R_{i}$ cu ${\frac {r_{k,k}R_{i}-r_{i,k}R_{k}}{r_{k-1,k-1\,.}}}$ Asta produce o formă superior triunghiulară pe linii care are aceleași elemente nule ca și în eliminarea gaussiană standard.

Principala remarcă a lui Bareiss este că fiecare element din matricea generată cu această variantă este determinantul unei submatrice a matricei originale.

În cazul particular în care se începe cu elemente întregi, diviziunile care apar în algoritm sunt diviziuni exacte, rezultând numere întregi. Prin urmare, toate elementele intermediare și finale sunt numere întregi. Mai mult, inegalitatea lui Hadamard^⁠(d) oferă o limită superioară pentru valorile absolute ale elementelor intermediare și finale, prin urmare o complexitate pe biți de ${\tilde {O}}(n^{5}).$

Mai mult, deoarece se cunoaște o limită superioară a valorilor elementelor finale, o complexitate ${\tilde {O}}(n^{4})$ poate fi obținută prin calcul modular^⁠(d) urmat fie de calcularea resturilor chinezești, fie de o transformare Hensel.

Drept corolar, următoarele probleme pot fi rezolvate în timp polinomial cu aceeași complexitate pe biți:^[11]^(p40)

Verificarea dacă m vectori raționali dați sunt liniar independenți.
Calcularea valorii determinantului unei matrice raționale.
Calcularea unei soluții a unui sistem de ecuații raționale Ax = b.
Calcularea matricei inverse a unei matrice raționale nesingulare.
Calcularea rangului unei matrice raționale.

Instabilitatea numerică

O posibilă problemă este instabilitatea numerică, cauzată de posibilitatea împărțirii cu numere foarte mici. Dacă, de exemplu, pivotul unei linii este foarte aproape de zero, atunci, pentru a reduce matricea pe linii, ar trebui să se împartă la acel număr. Aceasta înseamnă că orice eroare care a existat pentru numărul apropiat de zero ar fi amplificată. Eliminarea gaussiană este numeric stabilă pentru matricile diagonal dominante^⁠(d) sau pozitiv definite. Pentru matricile generale, eliminarea gaussiană este de obicei considerată stabilă, atunci când se utilizează pivotarea (permutarea) parțială, chiar dacă există exemple de matrici stabile pentru care metoda este instabilă.^[12]

Generalizări

Eliminarea gaussiană poate fi efectuată asupra oricărui corp, nu doar asupra numerelor reale.

Algoritmul lui Buchberger^⁠(d) este o generalizare a eliminării gaussiene la sisteme de ecuații polinomiale. Această generalizare depinde în mare măsură de noțiunea de ordine monomială^⁠(d). Alegerea unei ordonări a variabilelor este deja implicită în eliminarea gaussiană, manifestându-se ca alegerea de a lucra de la stânga la dreapta la alegerea pivoților.

Calcularea rangului unui tensor de ordin mai mare decât 2 este NP-hard.^[13] Prin urmare, dacă $P \neq NP,$ nu poate exista un analog în timp polinomial al eliminării gaussiene pentru tensori de ordin superior (matricile sunt reprezentări tablou^⁠(d) ale tensorilor de ordinul 2).

Pseudocod

Așa cum s-a explicat mai sus, eliminarea gaussiană transformă o matrice dată, $A$ ( $m \times n$ ) într-o matrice superior triunghiulară.

În pseudocodul următor cu A[i, j] sunt notate elementele matricei $A$ din linia $i$ și coloana $j$ cu indicii pornind de la 1. Transformarea se efectuează „in situ”, ceea ce înseamnă că matricea originală se pierde și în final este înlocuită de forma sa superior triunghiulară.

h := 1 /* Inițializarea liniei pivot */
k := 1 /* Inițializarea coloanei pivot */

while h ≤ m and k ≤ n:
    /* Găsește al k-lea pivot: */
    i_max := argmax (i = h ... m, abs(A[i, k]))
    if A[i_max, k] = 0:
        /* Nu există pivot în această coloană, se trece la coloana următoare */
        k := k + 1
    else:
        swap rows(h, i_max)
        /* Pentru toate liniile de sub pivot: */
        for i = h + 1 ... m:
            f := A[i, k] / A[h, k]
            /* Pune zerouri în partea de jos a coloanei pivot: */
            A[i, k] := 0
            /* Pentru restul elementelor din linia curentă: */
            for j = k + 1 ... n:
                A[i, j] := A[i, j] - A[h, j] * f
        /* Treci la linia și coloana pivot următoare */
        h := h + 1
        k := k + 1

Acest algoritm diferă ușor de cel discutat anterior, prin alegerea unui pivot cu cea mai mare valoare absolută. O astfel de „pivotare parțială” poate fi necesară dacă în poziția pivotului elementul de matrice este nul. În orice caz, alegerea celei mai mari valori absolute posibile a pivotului îmbunătățește stabilitatea numerică a algoritmului atunci când numerele sunt reprezentate în virgulă mobilă (cazul uzual).^[14]

La finalizarea acestei proceduri, matricea va avea formă triunghiular superioară, iar sistemul corespunzător poate fi rezolvat prin substituția inversă.

Note

^ en „DOCUMENTA MATHEMATICA, Vol. Extra Volume: Optimization Stories (2012), 9-14”. www.emis.de. Accesat în 2 decembrie 2022.
^ Calinger 1999, pp. 234–236. }
^ en Timothy Gowers; June Barrow-Green; Imre Leader (8 septembrie 2008). The Princeton Companion to Mathematics. Princeton University Press. p. 607. ISBN 978-0-691-11880-2.
^ ^a ^b Grcar 2011a, pp. 169–172.
^ Grcar 2011b, pp. 783–785.
^ Lauritzen, p. 3.
^ Grcar 2011b, p. 789.
^ en Althoen, Steven C.; McLaughlin, Renate (1987), „Gauss–Jordan reduction: a brief history”, The American Mathematical Monthly, Mathematical Association of America, 94 (2): 130–142, doi:10.2307/2322413, ISSN 0002-9890, JSTOR 2322413
^ Farebrother 1988, p. 12.
^ en Fang, Xin Gui; Havas, George (1997). On the worst-case complexity of integer Gaussian elimination. ISSAC '97. Proceedings of the 1997 international symposium on Symbolic and algebraic computation. Kihei, Maui, Hawaii, United States: ACM. pp. 28–31. doi:10.1145/258726.258740 . ISBN 0-89791-875-4.
^ ^a ^b en Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, 2 (ed. 2nd), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419
^ Golub & Van Loan 1996.
^ en Hillar, Christopher; Lim, Lek-Heng (7 noiembrie 2009). „Most tensor problems are NP-hard”. arXiv:0911.1393  [cs.CC].
^ en Kurgalin, Sergei; Borzunov, Sergei (2021). Algebra and Geometry with Python. Cham. doi:10.1007/978-3-030-61541-3. ISBN 978-3-030-61540-6.

Bibliografie

en Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (ed. 2nd), New York: John Wiley & Sons, ISBN 978-0471624899 .
en Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006), Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (ed. 2nd), Wiley-Interscience, ISBN 978-0-471-79156-0 .
en Calinger, Ronald (1999), A Contextual History of Mathematics, Prentice Hall, ISBN 978-0-02-318285-3 .
en Farebrother, R.W. (1988), Linear Least Squares Computations, STATISTICS: Textbooks and Monographs, Marcel Dekker, ISBN 978-0-8247-7661-9 .
en Lauritzen, Niels, Undergraduate Convexity: From Fourier and Motzkin to Kuhn and Tucker .
en Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (ed. 3rd), Johns Hopkins, ISBN 978-0-8018-5414-9 .
en Grcar, Joseph F. (2011), „How ordinary elimination became Gaussian elimination”, Historia Mathematica, 38 (2): 163–218, arXiv:0907.2397 , doi:10.1016/j.hm.2010.06.003
en Grcar, Joseph F. (2011), „Mathematicians of Gaussian elimination” (PDF), Notices of the American Mathematical Society, 58 (6): 782–792
en Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (ed. 2nd), SIAM, ISBN 978-0-89871-521-7 .
en Katz, Victor J. (2004), A History of Mathematics, Brief Version, Addison-Wesley, ISBN 978-0-321-16193-2 .
en Kaw, Autar; Kalu, Egwu (2010). „Numerical Methods with Applications: Chapter 04.06 Gaussian Elimination” (PDF) (ed. 1st). University of South Florida. Arhivat din original (PDF) la 7 septembrie 2012.
en Lipson, Marc; Lipschutz, Seymour (2001), Schaum's outline of theory and problems of linear algebra, New York: McGraw-Hill, pp. 69–80, ISBN 978-0-07-136200-9
en Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), „Section 2.2”, Numerical Recipes: The Art of Scientific Computing (ed. 3rd), New York: Cambridge University Press, ISBN 978-0-521-88068-8, arhivat din original la 19 martie 2012, accesat în 8 august 2011

Vezi și

Procedeul Gram–Schmidt

Legături externe

Portal Matematică

en Interactive didactic tool

[1] „DOCUMENTA MATHEMATICA, Vol. Extra Volume: Optimization Stories (2012), 9-14”. www.emis.de. Accesat în 2 decembrie 2022.

[2] Calinger 1999, pp. 234–236. }

[princeton-3] Timothy Gowers; June Barrow-Green; Imre Leader (8 septembrie 2008). The Princeton Companion to Mathematics. Princeton University Press. p. 607. ISBN 978-0-691-11880-2.

[G169-4] Grcar 2011a, pp. 169–172.

[5] Grcar 2011b, pp. 783–785.

[6] Lauritzen, p. 3.

[7] Grcar 2011b, p. 789.

[8] Althoen, Steven C.; McLaughlin, Renate (1987), „Gauss–Jordan reduction: a brief history”, The American Mathematical Monthly, Mathematical Association of America, 94 (2): 130–142, doi:10.2307/2322413, ISSN 0002-9890, JSTOR 2322413

[9] Farebrother 1988, p. 12.

[10] Fang, Xin Gui; Havas, George (1997). On the worst-case complexity of integer Gaussian elimination. ISSAC '97. Proceedings of the 1997 international symposium on Symbolic and algebraic computation. Kihei, Maui, Hawaii, United States: ACM. pp. 28–31. doi:10.1145/258726.258740 . ISBN 0-89791-875-4.

[:0-11] Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, 2 (ed. 2nd), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419

[12] Golub & Van Loan 1996.

[13] Hillar, Christopher; Lim, Lek-Heng (7 noiembrie 2009). „Most tensor problems are NP-hard”. arXiv:0911.1393  [cs.CC].

[14] Kurgalin, Sergei; Borzunov, Sergei (2021). Algebra and Geometry with Python. Cham. doi:10.1007/978-3-030-61541-3. ISBN 978-3-030-61540-6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]