Metodo di eliminazione di Gauss

In matematica, il metodo di eliminazione di Gauss, spesso abbreviato in MEG, è un algoritmo, che prende il nome dal matematico tedesco Carl Friedrich Gauss, usato in algebra lineare per determinare le soluzioni di un sistema di equazioni lineari, per calcolare il rango o l'inversa di una matrice.

L'algoritmo, attraverso l'applicazione di specifiche operazioni sulle righe (o sulle colonne) dette operazioni elementari, riduce la matrice in una forma detta a scalini. La matrice in forma a scalini rende immediato il calcolo del rango della matrice (che sarà uguale al numero di pivot) e particolarmente semplice la risoluzione del sistema lineare a essa associato.

Un'estensione a tale metodo, nota come metodo di eliminazione di Gauss-Jordan, dal matematico tedesco Wilhelm Jordan, riduce ulteriormente la matrice in una forma detta a scalini ridotta, permettendo di calcolarne anche l'inversa.

Nonostante sia comunemente attribuito a Gauss, una prima applicazione del MEG compare già nel II secolo a.C. all'interno del Jiuzhang Suanshu (Nove capitoli sulle arti matematiche), scritto da matematici cinesi durante la dinastia Han.

Matrice completa dei coefficienti

Un sistema di equazioni lineari:

$\left\{{\begin{matrix}a_{1,1}x_{1}+a_{1,2}x_{2}+\cdots +a_{1,n}x_{n}&=&b_{1}\\a_{2,1}x_{1}+a_{2,2}x_{2}+\cdots +a_{2,n}x_{n}&=&b_{2}\\&\vdots &\\a_{m,1}x_{1}+a_{m,2}x_{2}+\cdots +a_{m,n}x_{n}&=&b_{m}\end{matrix}}\right.$

può essere rappresentato mediante una matrice:

${\begin{pmatrix}a_{1,1}&\cdots &a_{1,n}&b_{1}\\\vdots &\ddots &\vdots &\vdots \\a_{m,1}&\cdots &a_{m,n}&b_{m}\end{pmatrix}}$

detta matrice completa dei coefficienti del sistema. I coefficienti del sistema lineare (e quindi gli elementi della matrice) sono elementi di un campo $K,$ quale ad esempio quello dei numeri reali $\mathbb {R}$ o complessi $\mathbb {C} .$ L'ultima colonna è la colonna dei termini noti.

Operazioni elementari per riga

Le operazioni elementari per riga sono operazioni che modificano una matrice in uno dei modi seguenti:

• scambiando due righe;
• moltiplicando una riga per un numero diverso da zero;
• sommando una riga ad un multiplo di un'altra riga.

Le righe della matrice qui sono intese come vettori dello spazio vettoriale $K^{n}$, e quindi si possono moltiplicare per un numero oppure sommare, semplicemente termine a termine.

Le operazioni elementari per riga hanno la seguente importante proprietà: se applicate alla matrice completa (cioè con termini noti) di un sistema lineare, non modificano l'insieme delle soluzioni del sistema. In altre parole, cambia il sistema ma le soluzioni restano invariate: un vettore ${\textstyle (x_{1},\ldots ,x_{n})}$ è soluzione del sistema iniziale se e solo se lo è del sistema a cui abbiamo applicato le operazioni elementari per riga.

D'altra parte è semplice notare che le operazioni elementari per riga applicate alla matrice completa corrispondono, nella classica maniera di esprimere un sistema di equazioni (con la parentesi graffa), alle seguenti operazioni sulle equazioni:

• scambiare l'ordine di scrittura di due equazioni;
• moltiplicare entrambi i membri di un'equazione per un numero diverso da zero;
• sommare a entrambi i membri di un'equazione la stessa quantità.

Matrice a scalini

Una matrice a scalini è una matrice $A$ avente le proprietà seguenti:

1. ogni riga, dopo la prima, inizia con almeno uno 0 in più della riga soprastante;
2. se una riga è nulla, allora ogni riga sottostante è nulla.

Ad esempio, la matrice:

${\begin{pmatrix}3&0&4&7\\0&-1&0&0\\0&0&0&5\\0&0&0&0\end{pmatrix}}$

è ridotta a scalini, mentre la matrice:

${\begin{pmatrix}3&0&4&7\\0&8&0&0\\0&6&2&0\end{pmatrix}}$

non lo è. Il primo elemento diverso da zero su ogni riga (se presente) è detto pivot. Ad esempio, la matrice a scalini descritta sopra ha tre pivot: 3, -1 e 5.

Algoritmo di Gauss

L'algoritmo di Gauss trasforma una qualsiasi matrice in una matrice a scalini tramite operazioni elementari per riga. Funziona nel modo seguente:

1. Se la prima riga ha il primo elemento nullo, scambiala con una riga che ha il primo elemento non nullo. Se tutte le righe hanno il primo elemento nullo, vai al punto 3.
2. Per ogni riga $A_{i}$ con primo elemento non nullo, eccetto la prima ($i>1$), moltiplica la prima riga per un coefficiente scelto in maniera tale che la somma tra la prima riga e $A_{i}$ abbia il primo elemento nullo (quindi coefficiente = $-A_{i1}/A_{11}$). Sostituisci $A_{i}$ con la somma appena ricavata.
3. Adesso sulla prima colonna tutte le cifre, eccetto forse la prima, sono nulle. A questo punto ritorna al punto 1 considerando la sottomatrice che ottieni cancellando la prima riga e la prima colonna.

Il risultato dell'algoritmo non è sempre lo stesso, dipende dalle scelte effettuate. Durante lo svolgimento è importante avere in mente l'obiettivo finale cioè ottenere una matrice a scalini.

Si mostra qui un esempio:

${\begin{aligned}{\begin{pmatrix}1&-1&0\\1&2&0\\0&6&-4\end{pmatrix}}&\to {\begin{pmatrix}-1&1&0\\1&2&0\\0&6&-4\end{pmatrix}}\\&\to {\begin{pmatrix}-1&1&0\\0&3&0\\0&6&-4\end{pmatrix}}\\&\to {\begin{pmatrix}-1&1&0\\0&-6&0\\0&6&-4\end{pmatrix}}\\&\to {\begin{pmatrix}-1&1&0\\0&-6&0\\0&0&-4\end{pmatrix}}\end{aligned}}$

Dalla matrice di partenza si è moltiplicata la prima riga per -1, sommato la prima riga con la seconda (scrivendo il risultato nella seconda riga in modo da ottenere uno zero in prima posizione), moltiplicato la riga ottenuta per -2 ed infine sommata alla terza riga.

Questa procedura, scritta e utilizzata come sopra, può essere usata per risolvere un sistema lineare (applicando le operazioni elementari per riga alla matrice completa dei coefficienti del sistema) o per calcolare il rango di una generica matrice.

Nel caso in cui si voglia utilizzare questo metodo per il calcolo del determinante di una generica matrice quadrata $A$, si deve prima triangolarizzare la matrice $A$ ottenendo una matrice triangolare $B$, poi si fa il prodotto degli elementi sulla diagonale principale dividendolo per $d$, cioè

$\det A={\frac {1}{d}}\prod _{i}b_{ii},$

dove $d$ è ottenuto nel seguente modo: prima di iniziare l'operazione di riduzione si pone $d=1$. Poi a seconda dell'operazione di riduzione utilizzata, si pone:

• $d\mapsto -d$ se si scambiano due righe;
• $d\mapsto nd$ se si moltiplica una riga per un numero $n$ diverso da zero;
• $d\mapsto d$ (cioè $d$ resta invariato) se si somma una riga a un multiplo di un'altra riga.

Per il calcolo del rango e del determinante si può operare l'algoritmo di Gauss anche sulle colonne.

Di seguito un esempio per il calcolo del determinante sulla stessa matrice sopra:

${\begin{pmatrix}1&-1&0\\1&2&0\\0&6&-4\end{pmatrix}}\to {\begin{pmatrix}1&-1&0\\0&3&0\\0&6&-4\end{pmatrix}}\to {\begin{pmatrix}1&-1&0\\0&3&0\\0&0&-4\end{pmatrix}}$

Dalla matrice di partenza si è sommato alla seconda riga la prima riga moltiplicata per -1 per azzerare il primo elemento (lasciando la prima riga invariata); la terza riga ha già uno zero come primo elemento a sinistra quindi si è sommato alla terza riga la seconda riga moltiplicata per -2 per azzerare il secondo elemento (lasciando la seconda riga invariata). Adesso si può calcolare facilmente il determinante che è il prodotto degli elementi sulla diagonale principale, cioè vale -12 ed è lo stesso determinante di quello della matrice iniziale.

Nell'esempio precedente invece si otterrebbe -24 dal prodotto degli elementi diagonali cioè -12 moltiplicato per un fattore 2: questo fattore 2 è proprio il prodotto $-1\times -2,$ i fattori per cui si erano moltiplicate le righe nell'esempio sopra.

Il calcolo del determinante tramite questa procedura è il sistema meno impegnativo che si conosca dal punto di vista computazionale (crescita polinomiale $O(n^{3})$ invece che fattoriale $O(n!)$) ed è l'unico applicabile quando le dimensioni delle matrici diventano grandi.

Algoritmo di Gauss-Jordan

Dopo aver ridotto la matrice a scalini, è possibile usare una versione dell'algoritmo di Gauss in senso inverso, cioè dal basso verso l'alto, per ottenere una matrice che in ogni colonna contenente un pivot abbia solo il pivot come numero non nullo, (questa matrice risultante è anche detta matrice a scalini in forma ridotta): basta usare ogni riga, partendo dall'ultima, per eliminare tutte le cifre diverse da zero che stanno sopra al pivot di questa riga. Infine, sempre con mosse di Gauss (moltiplicando righe), si può ottenere che ogni pivot abbia valore 1.

Ad esempio, portando avanti l'algoritmo descritto sopra si ha:

${\begin{aligned}{\begin{pmatrix}-1&1&0\\0&-6&0\\0&0&-4\end{pmatrix}}&\to {\begin{pmatrix}-1&1&0\\0&-1&0\\0&0&-4\end{pmatrix}}\\&\to {\begin{pmatrix}-1&0&0\\0&-1&0\\0&0&-4\end{pmatrix}}\\&\to {\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}.\end{aligned}}$

Soluzioni del sistema

L'algoritmo di Gauss-Jordan trasforma la matrice dei coefficienti di un sistema in una matrice fatta nel modo seguente: le variabili corrispondenti alle colonne che non contengono pivot sono dette libere; ogni altra variabile compare in una sola equazione, e quindi può essere espressa in funzione delle variabili libere e dei termini noti. Lo spazio delle soluzioni si ottiene assegnando valori arbitrari alle variabili libere, e calcolando le altre variabili di conseguenza.

Se i termini noti $b_{i}$ sono tutti nulli, l'insieme delle soluzioni è un sottospazio vettoriale di $K^{n}$. Altrimenti si ottiene da un sottospazio vettoriale tramite traslazione, cioè è un sottospazio affine.

Inversa di una matrice

L'algoritmo di Gauss-Jordan è anche usato per trovare (quando esiste) l'inversa di una matrice. Funziona nel modo seguente: sia $A$ una matrice invertibile. Si consideri la matrice $B=(A|I)$, con $n$ righe e $2n$ colonne, costruita affiancando $A$ e la matrice identità $I$. A questo punto, dopo aver reso la matrice a scalini con uno o più passi dell'algoritmo di Gauss, si applica la variante di Gauss-Jordan alla nuova $B$ per ottenere nella parte sinistra $I$.

Poiché $A$ è invertibile, le sue colonne sono indipendenti, e quindi conterranno tutte dei pivot alla fine dell'algoritmo. Quindi il risultato sarà una matrice del tipo $(I|C)$. Ebbene la matrice $C$ è proprio l'inversa di $A$. Infatti se si considera la matrice $(A|e_{i})$, il sistema associato ha come unica soluzione un vettore $x_{i}$ che per definizione di inversa è la $i$-esima colonna della matrice inversa di $A.$ Con le operazioni elementari la si trasforma nella matrice $(I|B^{i})$ la cui soluzione è sempre il vettore $x_{i}$ (perché l'insieme delle soluzioni di un sistema lineare rimane invariato usando le operazioni elementari). Questo equivale a dire che $Ix_{i}$ è uguale a $B^{i},$ ossia $B^{i}=x_{i}$. Questo vale per ogni colonna. Quindi, dato che il vettore $x_{i}$ è la $i$-esima colonna della matrice inversa, allora $C=A^{-1}$

L'esempio seguente mostra che l'inversa di ${\textstyle A={\begin{pmatrix}1&2\\2&3\end{pmatrix}}}$ è ${\textstyle C={\begin{pmatrix}-3&2\\2&-1\end{pmatrix}}}$:

${\begin{aligned}{\begin{pmatrix}1&2&\|&1&0\\2&3&\|&0&1\end{pmatrix}}&\to {\begin{pmatrix}-2&-4&\|&-2&0\\2&3&\|&0&1\end{pmatrix}}\\&\to {\begin{pmatrix}-2&-4&\|&-2&0\\0&-1&\|&-2&1\end{pmatrix}}\\&\to {\begin{pmatrix}-2&-4&\|&-2&0\\0&4&\|&8&-4\end{pmatrix}}\\&\to {\begin{pmatrix}-2&0&\|&6&-4\\0&4&\|&8&-4\end{pmatrix}}\\&\to {\begin{pmatrix}1&0&\|&-3&2\\0&1&\|&2&-1\end{pmatrix}}.\end{aligned}}$

Nel primo passaggio si è moltiplicata la prima riga per -2, nel secondo si è sommata alla seconda riga la prima, nel terzo si è moltiplicata la seconda riga per -4, nel quarto passaggio si è sommata alla prima riga la seconda e infine nell'ultimo passaggio si è divisa la prima riga per -2 e la seconda per 4. In questo modo si è partiti da una matrice di $(A|I)$ e si è arrivati a $(I|C)$. Si ha che $C$ è l'inversa di $A$.

Proprietà

• Il rango di una matrice è uguale al numero dei pivot di una qualsiasi matrice a scalini ottenuta da questa tramite operazioni elementari per riga (o per colonna).
• L'insieme delle soluzioni del sistema lineare associato alla matrice non cambia tramite operazioni elementari per riga.
• Per estrarre da un insieme di vettori in $K^{n}$ un sottoinsieme massimale di vettori indipendenti, dunque anche una base del sottospazio da essi generato, basta applicare l'algoritmo di Gauss alla matrice ottenuta considerando questi vettori come le colonne della matrice. Quindi prendere solo quei vettori iniziali sulla cui colonna corrispondente nella matrice a scalini (alla fine dell'algoritmo) compare un pivot.

Bibliografia

• (EN) Timothy Gowers, June Barrow-Green e Imre Leader, The Princeton Companion to Mathematics, Princeton University Press, 8 settembre 2008, p. 607, ISBN 978-0-691-11880-2.
• (EN) Bareiss, E. H. Multistep Integer-Preserving Gaussian Elimination. Argonne National Laboratory Report ANL-7213, May 1966.
• (EN) Bareiss, E. H. Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination. Math. Comput. 22, 565-578, 1968.
• (EN) Garbow, B. S. Integer-Preserving Gaussian Elimination. Program P-158 (3600F), Applied Mathematics Division, Argonne National Laboratory, Nov. 21, 1966.
• (EN) Gentle, J. E. "Gaussian Elimination." §3.1 in Numerical Linear Algebra for Applications in Statistics. Berlin: Springer-Verlag, pp. 87–91, 1998.

Voci correlate

• Matrice
• Determinante
• Rango (algebra lineare)
• Sistema di equazioni lineari
• Teorema di Rouché-Capelli

Altri progetti

Altri progetti

• Wikibooks

• Wikibooks contiene testi o manuali sul metodo di eliminazione di Gauss

Collegamenti esterni

• Gauss, metodo di eliminazione di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Opere riguardanti Gaussian elimination, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Gaussian Elimination, su MathWorld, Wolfram Research.
• Programma che calcola l'inversa di una matrice, su evinive.altervista.org. URL consultato il 22 luglio 2021 (archiviato dall'url originale il 22 aprile 2016).
• Programma interattivo o automatico per utilizzare l'algoritmo di Gauss-Jordan, su ww2.unime.it. URL consultato il 14 febbraio 2008 (archiviato dall'url originale il 1º febbraio 2008).
• (EN) Eliminazione gaussiana su MathWorld
• (EN) Eliminazione di Gauss-Jordan MathWorld
• (EN) Eliminazione gaussiana Archiviato il 20 giugno 2010 in Internet Archive. su PlanetMath
• (EN) Xin Gui Fang e George Havas, On the worst-case complexity of integer Gaussian elimination (PDF), in Proceedings of the 1997 international symposium on Symbolic and algebraic computation, ISSAC '97, Kihei, Maui, Hawaii, United States, ACM, 1997, pp. 28–31, DOI:10.1145/258726.258740, ISBN 0-89791-875-4.

Controllo di autorità	GND (DE) 4156110-7