Metodo di eliminazione di Gauss

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Algoritmo 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 operazioni elementari dette mosse di Gauss, riduce la matrice in una forma detta a scalini. La matrice così ridotta permette il calcolo del rango della matrice (che sarà pari al numero di scalini/pivot) nonché la risoluzione del sistema lineare ad essa associato.

Un'estensione a tale metodo, nota come metodo di eliminazione di Gauss-Jordan, dal matematico tedesco Wilhelm Jordan, riduce ulteriormente la matrice, 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), steso da matematici cinesi durante la dinastia Han.[1]

Matrice completa dei coefficienti[modifica | modifica sorgente]

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 descritto tramite 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 della matrice) sono elementi di un campo K, quale ad esempio quello dei numeri reali \R o complessi \C. L'ultima colonna è la colonna dei termini noti.

Mosse di Gauss[modifica | modifica sorgente]

Le mosse di Gauss 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 mosse di Gauss hanno la seguente importante proprietà: se applicate alla matrice completa(con termini noti) di un sistema lineare, non modificano lo spazio delle soluzioni del sistema. In altre parole, cambia il sistema ma le soluzioni restano invariate: un vettore (x_1, \dots , x_n) è soluzione del sistema iniziale se e solo se lo è del sistema a cui abbiamo applicato le mosse di gauss.

D'altra parte è semplice notare che le mosse di Gauss applicate alla matrice completa(con termini noti) corrispondono, nella classica maniera di esprimere un sistema di equazioni (con la parentesi graffa), a nient'altro se non:

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

Matrice a scalini[modifica | modifica sorgente]

Una matrice a scalini è una matrice A avente la proprietà seguente: il primo elemento diverso da zero di una riga deve essere più a destra del primo elemento diverso da zero della riga precedente. 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 (quando c'è) è detto pivot. Ad esempio, la matrice a scalini descritta sopra ha tre pivot, contenenti le cifre 3, -1 e 5.

Algoritmo di Gauss[modifica | modifica sorgente]

L'algoritmo di Gauss trasforma una qualsiasi matrice in una matrice a scalini tramite mosse di Gauss. Funziona nel modo seguente:

  • 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.
  • 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.
  • 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 scala.

Si mostra qui un esempio:

\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}

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 ed utilizzata come sopra, funziona per risolvere un sistema lineare applicando le mosse di Gauss alla matrice completa dei coefficienti del sistema o per capire quale sia il rango di una generica matrice in esame. Nel caso in cui si voglia sfruttare questa procedura per il calcolo veloce del determinante di una generica matrice quadrata (una volta triangolarizzata si fa il prodotto degli elementi diagonali) si devono fare un numero pari di scambi di righe altrimenti il determinante cambia segno! Ci si deve inoltre limitare a sommare ad una riga un'altra riga eventualmente moltiplicata per un numero diverso da zero, lasciando la seconda riga invariata: nel calcolo del determinante, sfruttando questa procedura, se moltiplicassimo semplicemente una riga per una costante il determinante cambierebbe! Cambierebbe proprio del fattore per cui si moltiplica la riga! Infine applicando la procedura per il calcolo veloce del determinante si può operare 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 diagonali 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 x -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 invece che fattoriale) ed è l'unico applicabile quando le dimensioni delle matrici diventano grandi.

Algoritmo di Gauss-Jordan[modifica | modifica sorgente]

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{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}

Soluzioni del sistema[modifica | modifica sorgente]

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; ciascuna 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, le soluzioni sono un sottospazio vettoriale di K^n. Altrimenti sono ottenute da un sottospazio vettoriale tramite traslazione.

Inversa di una matrice[modifica | modifica sorgente]

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.

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

 \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}

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à[modifica | modifica sorgente]

  • Il rango di una matrice è pari al numero dei pivot di una qualsiasi matrice a scalini ottenuta da questa tramite mosse di Gauss
  • Lo spazio delle soluzioni non cambia tramite mosse di Gauss
  • Per estrarre da un insieme di vettori in K^n un sottoinsieme di vettori indipendenti, dunque anche una base del sottospazio da essi generato basta applicare l'algoritmo di Gauss alla matrice ottenuta affiancando questi vettori, e quindi prendere solo quei vettori iniziali sulla cui colonna compare (alla fine dell'algoritmo) un pivot.

Note[modifica | modifica sorgente]

  1. ^ (EN) Storia dell'uso delle matrici e dei determinanti su MacTutor

Bibliografia[modifica | modifica sorgente]

  • (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[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica