Algoritmo di Gauss-Jordan

Da Wikipedia, l'enciclopedia libera.

In matematica, l'algoritmo di Gauss-Jordan è un algoritmo, che prende il nome dai due matematici Carl Friedrich Gauss e Wilhelm Jordan, 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 trasforma una matrice tramite mosse di Gauss, e si svolge in due tempi. La prima parte, detta semplicemente algoritmo di Gauss, consiste nel ridurre la matrice a scalini, ed è sufficiente per calcolare il rango della matrice, che sarà pari al numero di scalini (o dei pivot). Nella seconda parte si semplifica ulteriormente la matrice.

Nonostante sia attribuito a Gauss e Jordan, il primo matematico ad aver usato questo algoritmo è Liu Hui nel 263.

[modifica] Matrice 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 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 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.

[modifica] Mosse di Gauss

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'altra.

Le righe della matrice qui sono intese come vettori dello spazio vettoriale Kⁿ, 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 dei coefficienti 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₁, ..., x_n) è soluzione del vecchio sistema se e solo se lo è del nuovo.

[modifica] Matrice a scalini

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.

[modifica] Algoritmo di Gauss

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

Prendi una riga avente il primo elemento diverso da zero e scambiala con la prima. Se tutte le righe hanno il primo elemento nullo, vai al punto 3.
Per ogni riga A_i partendo dalla seconda (i > 1): moltiplica la prima riga per un coefficiente in modo che, sommandola ad A_i, ne cancelli il primo coefficiente.
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. Le mosse di Gauss successive andranno comunque fatte su tutta la matrice.

Mostriamo 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 abbiamo moltiplicato 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 e infine sommata alla terza riga.

[modifica] 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: 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), possiamo ottenere che ogni pivot abbia valore 1.

Ad esempio, portando avanti l'algoritmo descritto sopra otteniamo:

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

[modifica] 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; 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ⁿ'. Altrimenti sono ottenute da un sottospazio vettoriale tramite traslazione.

[modifica] 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. Costruiamo la matrice B = (A | I) con n righe e 2n colonne, costruita affiancando A e la matrice identità I. A questo punto applichiamo l'agoritmo di Gauss-Jordan alla nuova B.

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

[modifica] Proprietà

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ⁿ un sottoinsieme di vettori indipendenti, 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.

[modifica] Voci correlate

Estratto da "http://it.wikipedia.org../../../a/l/g/Algoritmo_di_Gauss-Jordan_4d5a.html"

Categorie: Algebra lineare | Algoritmi