Eliminazione gaussiana

L'eliminazione di Gauss è uno degli strumenti più utilizzati nell'Algebra Lineare. Essa costituisce un algoritmo che ha come obiettivo quello di trasformare una matrice M\in \mathbb{R}^{n\times m} in una matrice triangolare superiore \tilde{M}\in \mathbb{R}^{n\times m}.

 

Eliminazione gaussiana e matrici triangolari superiori

 

Rinfreschiamoci la memoria ricordando cos'è una matrice triangolare superiore.

 

Una matrice U\in \mathbb{R}^{n\times m} è triangolare superiore se e solo se tutti gli elementi che stanno sotto gli elementi u_{i,i}, con i= 1,\cdots, \mbox{min}(n, m) sono nulli.

 

 

Esempio: la matrice

 

U= \begin{pmatrix}1&1&0\\0&1&0\end{pmatrix}

 

è una matrice triangolare superiore. 

 

U= \begin{pmatrix}2&1& 0\\ 0&1&0\\ 0&0&1\end{pmatrix}

 

è anch'essa una matrice triangolare superiore. Non è invece una matrice triangolare

 

S= \begin{pmatrix}1&1&1\\ 0&1&0\\ 1&0&0\end{pmatrix}

 

perché sotto l'elemento s_{1,1}=1 troviamo un valore che non è zero, vale a dire s_{3,1}=1 .

 

Chiarito questo concetto, iniziamo a descrivere come funziona la procedura di eliminazione gaussiana.

 

Consideriamo una qualsiasi matrice a componenti reali

 

A= \begin{pmatrix}a_{1,1}&a_{1,2}& \cdots &a_{1, m}\\a_{2,1}&a_{2,2}&\cdots &a_{2, m}\\ \vdots & \vdots & \ddots&\vdots\\ a_{i, 1}& a_{i, 2}&\cdots & a_{i, m}\\ \vdots&\vdots&\ddots &\vdots\\ a_{n,1}& a_{n,2}&\cdots & a_{n, m} \end{pmatrix}\begin{matrix}\to \mbox{prima riga }R_1\\ \to \mbox{seconda riga }R_2\\ \vdots\\ \to i\mbox{-esima riga } R_{i}\\ \vdots\\ \to n\mbox{-esima riga }R_n \end{matrix}

 

Il nostro obiettivo è quello di annullare tutti i termini che si trovano al di sotto della diagonale principale, e per farlo possiamo utilizzare quelle che si chiamano mosse elementari o mosse di Gauss. Riportiamole:

 

1. scambio di due righe;

2. moltiplicare una riga della matrice per uno scalare non nullo;

3. sostituire una riga della matrice con quella ottenuta sommando ad essa un multiplo di un'altra riga.

 

Il primo obiettivo è quello di annullare tutti i termini al di sotto di a_{1,1}. Come facciamo? Surprised

 

Prima di tutto ci assicuriamo che a_{1,1}\ne 0, se è uguale a zero effettuiamo un cambio con una riga il cui primo elemento è non nullo. Per semplicità di esposizione supponiamo che a_{1,1}\ne 0, dunque dobbiamo eliminare il primo elemento della seconda riga:

 

- se a_{2, 1}= 0 lasciamo così com'è la riga R_2, ci concentreremo all'eliminazione del primo elemento della terza riga R_3.

 

- Se a_{2, 1}\ne 0 sostituiamo la seconda riga con la differenza tra essa e la prima riga moltiplicata per il coefficiente \frac{a_{2, 1}}{a_{1,1}}

 

R_2^{(1)}= R_{2}- \frac{a_{2, 1}}{a_{1,1}} R_1

 

Così facendo la nuova seconda riga avrà come primo elemento a_{2,1}^{(1)}= 0 ed al primo passo dell'algoritmo otterremo la matrice:

 

A^{(1)}= \begin{pmatrix}a_{1,1}&a_{1,2}& \cdots &a_{1, m}\\0&a_{2,2}^{(1)}&\cdots &a_{2, m}^{(1)}\\ \vdots & \vdots & \ddots&\vdots\\ a_{i, 1}&a_{i,2}& \cdots& a_{i, m}\\ \vdots&\vdots&\ddots&\vdots\\ a_{n,1}& a_{n,2}&\cdots & a_{n, m} \end{pmatrix}\begin{matrix}\to \mbox{prima riga }R_1\\ \to \mbox{seconda riga }R_{2}^{(1)}\\ \vdots\\ \to i-\mbox{esima riga }R_i\\ \vdots \\\to n\mbox{-esima riga }R_n \end{matrix}

  

Proviamo a generalizzare il processo considerando l'i-esima riga:

 

- se a_{i, 1}= 0 lasciamo la riga così com'è e ci prodigheremo nell'annullamento del primo elemento della riga successiva.

 

- se a_{i, 1}\ne 0 sostituiamo l'i-esima riga con la differenza tra essa e la prima riga moltiplicata per il fattore \frac{a_{i, 1}}{a_{1,1}}

 

R_{i}^{(1)}= R_{i}- \frac{a_{i, 1}}{a_{1,1}} R_{1}\qquad (\heartsuit)

 

A^{(1)}= \begin{pmatrix}a_{1,1}&a_{1,2}& \cdots &a_{1, m}\\0&a_{2,2}^{(1)}&\cdots &a_{2, m}^{(1)}\\ \vdots & \vdots & \ddots&\vdots\\ 0& a_{i,2}^{(1)}&\cdots& a_{i, m}^{(1)}\\ \vdots& \vdots&\ddots&\vdots \\a_{n,1}& a_{n,2}&\cdots & a_{n, m} \end{pmatrix}\begin{matrix}\to \mbox{prima riga }R_1\\ \to \mbox{seconda riga }R_{2}^{(1)}\\ \vdots\\ \to  i\mbox{- esima riga }R_{i}^{(1)}\\ \vdots \\ \to n\mbox{-esima riga }R_n \end{matrix}

 

Utilizzando la relazione (\heartsuit) per tutte le righe arriveremo a scrivere:

 

A^{(1)}= \begin{pmatrix}a_{1,1}&a_{1,2}& \cdots &a_{1, m}\\0&a_{2,2}^{(1)}&\cdots &a_{2, m}^{(1)}\\ \vdots & \vdots & \ddots&\vdots\\ 0& a_{i,2}^{(1)}&\cdots& a_{i, m}^{(1)}\\ \vdots& \vdots&\ddots&\vdots \\0& a_{n,2}^{(1)}&\cdots & a_{n, m}^{(1)} \end{pmatrix}\begin{matrix}\to \mbox{prima riga }R_1\\ \to \mbox{seconda riga }R_{2}^{(1)}\\ \vdots\\ \to  i\mbox{- esima riga }R_{i}^{(1)}\\ \vdots \\ \to n\mbox{-esima riga }R_n^{(1)} \end{matrix}

 

Benissimo! Abbiamo annullato tutti i termini della prima colonna eccezion fatta per il primo elemento che alcuni professori chiamano pivot.

 

Ora dovremmo annullare tutti gli elementi che vivono al di sotto del termine a_{2,2}. Ripeteremo lo stesso identico ragionamento precedente, utilizzeremo la formula:

 

R_{i}^{(2)}= R_{i}^{(1)}-\frac{a_{i, 2}}{a_{2,2}} R_{2}^{(1)}\quad\mbox{ con }i= 3, \cdots , n

 

con la quale verranno elimitati tutti i termini sotto l'elemento a_{2,1}^{(1)}.

 

Il processo deve essere ripetuto così che tutti i termini che si trovano sotto la diagonale principale siano nulli. Se vogliamo quindi eliminare i termini della j-esima colonna utilizzeremo, all'altezza della riga i con i\textless j

 

R_{i}^{(j)}= R_{i}^{(j-1)}- \frac{a_{i,j}}{a_{j,j}} R_{j}^{(j-1)}

 

dove con l'indice (j) indichiamo il fatto che stiamo eliminando i termini della j-esima colonna.

 

Non è chiaro? Proviamo con un esempio.

 

Esempio di applicazione della procedura di eliminazione gaussiana

 

Vogliamo ridurre a scala la matrice

 

A= \begin{pmatrix}\color{red}1\color{black}&1& 0\\ 2&1& 1\\ 2&0&1\end{pmatrix}

 

L'elemento a_{1,1} è non nullo, lo prenderemo come pivot.

 

La seconda riga ha come primo elemento 2, quindi per eliminarlo eseguiamo la seguente operazione:

 

R_{2}^{(1)}= R_{2}- \frac{a_{2,1}}{a_{1,1}}R_1

 

R_{2}^{(1)}= \overbrace{(2, 1, 1)}^{R_2}-\overbrace{ 2}^{\frac{a_{2,1}}{a_{1,1}}} \overbrace{(1, 1, 0)}^{R_1}= (2-2,1-2, 1-0 )= (0, -1, 1)

 

 \begin{pmatrix}\color{red}1\color{black}&1& 0\\ 0&-1& 1\\ 2&0&1\end{pmatrix}

 

La prima colonna presenta ancora termini non nulli sotto a_{1,1}, in particolare l'elemento a_{3, 1}= 2. Applichiamo la formula:

 

R_3^{(1)}=R_3- \frac{a_{3,1}}{a_{1,1}} R_1

 

che conduce a 

 

R_3^{(1)}= (2,0,1)- 2 (1, 1, 0)= (2-2,0-2, 1-0)= (0, -2, 1)

 

\begin{pmatrix}\color{red}1\color{black}&1& 0\\ 0&-1& 1\\ 0&-2&1\end{pmatrix}

 

Ottimo! La prima colonna è andata. Consideriamo ora il secondo pivot, che è l'elemento -1 che occupa la posizione 2,2 nella precedente matrice:

 

\begin{pmatrix}\color{red}1\color{black}&1& 0\\ 0&\color{red}-1\color{black}& 1\\ 0&-2&1\end{pmatrix}

 

Lo utilizzeremo per annullare il termine che occupa la cella 3,2. In che modo? Semplice:

 

R_3^{(2)}= R_3^{(1)}- \frac{a_{3,2}^{(1)}}{a_{2, 2}} R_2^{(1)}

 

R_3^{(2)}= (0, -2,1)- 2(0, -1,1)= (0, -2+2, 1-2)= (0, 0, -1)

 

Sostituendo la terza riga con quella appena trovata arriveremo a scrivere:

 

\begin{pmatrix}\color{red}1\color{black}&1& 0\\ \color{blue}0\color{black}&\color{red}-1\color{black}& 1\\ \color{blue}0\color{black}&\color{blue}0\color{black}&\color{red}-1\color{black}\end{pmatrix}

 

Sotto gli elementi della diagonale principale (quelli segnati in rosso), abbiamo tutti zeri, quindi la matrice ottenuta è triangolare superiore, l'algoritmo di Gauss termina qui!

 

Utilizzi del metodo di eliminazione gaussiana

 

Come abbiamo annunciato all'inizio della lezione, l'algoritmo di Gauss ha molte applicazioni nell'Algebra Lineare... è il prezzemolino della matematica, Laughing lo ritroveremo spessissimo. Ecco alcuni utilizzi fondamentali:

 

Risoluzione dei sistemi lineari per eliminazione gaussiana

 

Se abbiamo un sistema lineare Ax= b dove

 

- A\in \mathbb{R}^{n\times m} è la matrice dei coefficienti;

- x\in \mathbb{R}^{m\times 1} è il vettore delle incognite;

- b\in \mathbb{R}^{n\times 1} è il vettore dei termini noti

 

costruiamo la matrice completa che si ottiene accostando alla matrice dei coefficienti A, il vettore dei termini noti: (A| b). Tramite l'algoritmo di Gauss trasformeremo questa matrice in una matrice triangolare superiore (A'|b').

 

La matrice ottenuta rappresenta il sistema A'x= b' che è equivalente a Ax= b, ossia i due sistemi hanno lo stesso insieme delle soluzioni.

 

Il vantaggio di questa tecnica è che ci consente di passare da sistema "pieno" di coefficienti non nulli, ad uno equivalente però triangolare e quindi di più facile risoluzione.

 

Esempio

 

Vogliamo risolvere il sistema

 

\begin{cases}x+ y+ z= 3\\ x+ y= 2\\ x+ z= 2\end{cases}

 

La matrice dei coefficienti è

 

A= \begin{pmatrix}1&1&1\\1&1&0\\1&0&1\end{pmatrix},  mentre il vettore  b è b= \begin{pmatrix}3\\2\\ 2\end{pmatrix}

 

La matrice completa è

 

(A|b)= \begin{pmatrix}1&1&1 &|&3\\1&1&0&|&2\\1&0&1&|&2\end{pmatrix} 

 

Applicando il metodo di Gauss arriveremo a scrivere (i passaggi intermedi li lasciamo al lettore)

 

(A|b)'= \begin{pmatrix}1&1&1 &|&3\\0&0&-1&|&-1\\0&-1&0&|&-1\end{pmatrix}

 

cambiamo la seconda riga con la terza:

 

(A|b)''= \begin{pmatrix}1&1&1 &|&3\\0&-1&0&|&-1\\0&0&-1&|&-1\end{pmatrix}

 

La matrice completa è ridotta a scala. Ad essa associamo il sistema:

 

\begin{cases}x+y+z= 3\\ -y= -1\\ -z= -1\end{cases}

 

che si risolve abbastanza agevolmente sostituendo all'indietro così da ottenere z= 1, y= 1, x= 1.

 

L'algoritmo di Gauss e rango di una matrice

 

Grazie all'algoritmo di Gauss possiamo anche determinare il rango di una matrice A\in\mathbb{R}^{n\times m}, ma a tal proposito vi rimandiamo alla lezione del precedente link.

 

 


 

Bene per ora è tutto gente, vi consigliamo vivamente di imparare per bene il metodo di Gauss perché vi sarà di grandissimo nella risoluzione degli esercizi. :) Nel frattempo per eventuali dubbi e problemi cercate le risposte che vi servono qui su YM, abbiamo risolto migliaia di esercizi e risposto ad altrettante domande...

 

In bocca al lupo!

Salvatore Zungri

 

Lezione precedente..........Esercizi correlati...........Lezione successiva


Tags: metodo di eliminazione gaussiana - come applicare la procedura di eliminazione gaussiana - a cosa serve il metodo di Gauss e matrici triangolari superiori.