Eliminazione gaussiana

Home | Lezioni | Algebra Lineare | Matrici e vettori

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?

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 , ci concentreremo all'eliminazione del primo elemento della terza riga .

- 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 esima colonna utilizzeremo, all'altezza della riga 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 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 che occupa la posizione 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 . 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, lo ritroveremo spessissimo. Ecco alcuni utilizzi fondamentali:

Risoluzione dei sistemi lineari per eliminazione gaussiana

Se abbiamo un sistema lineare 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 , il vettore dei termini noti: . Tramite l'algoritmo di Gauss trasformeremo questa matrice in una matrice triangolare superiore .

La matrice ottenuta rappresenta il sistema che è equivalente a , 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= \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 .

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

..........

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