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 in una matrice triangolare superiore
.
Eliminazione gaussiana e matrici triangolari superiori
Rinfreschiamoci la memoria ricordando cos'è una matrice triangolare superiore.
Una matrice è triangolare superiore se e solo se tutti gli elementi che stanno sotto gli elementi
, con
sono nulli.
Esempio: la matrice
è una matrice triangolare superiore.
è anch'essa una matrice triangolare superiore. Non è invece una matrice triangolare
perché sotto l'elemento troviamo un valore che non è zero, vale a dire
.
Chiarito questo concetto, iniziamo a descrivere come funziona la procedura di eliminazione gaussiana.
Consideriamo una qualsiasi matrice a componenti reali
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 . Come facciamo?
Prima di tutto ci assicuriamo che , se è uguale a zero effettuiamo un cambio con una riga il cui primo elemento è non nullo. Per semplicità di esposizione supponiamo che
, dunque dobbiamo eliminare il primo elemento della seconda riga:
- se lasciamo così com'è la riga
, ci concentreremo all'eliminazione del primo elemento della terza riga
.
- Se sostituiamo la seconda riga con la differenza tra essa e la prima riga moltiplicata per il coefficiente
Così facendo la nuova seconda riga avrà come primo elemento ed al primo passo dell'algoritmo otterremo la matrice:
Proviamo a generalizzare il processo considerando l'i-esima riga:
- se lasciamo la riga così com'è e ci prodigheremo nell'annullamento del primo elemento della riga successiva.
- se sostituiamo l'i-esima riga con la differenza tra essa e la prima riga moltiplicata per il fattore
Utilizzando la relazione per tutte le righe arriveremo a scrivere:
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 . Ripeteremo lo stesso identico ragionamento precedente, utilizzeremo la formula:
con la quale verranno elimitati tutti i termini sotto l'elemento .
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
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
L'elemento è non nullo, lo prenderemo come pivot.
La seconda riga ha come primo elemento 2, quindi per eliminarlo eseguiamo la seguente operazione:
La prima colonna presenta ancora termini non nulli sotto , in particolare l'elemento
. Applichiamo la formula:
che conduce a
Ottimo! La prima colonna è andata. Consideriamo ora il secondo pivot, che è l'elemento che occupa la posizione
nella precedente matrice:
Lo utilizzeremo per annullare il termine che occupa la cella . In che modo? Semplice:
Sostituendo la terza riga con quella appena trovata arriveremo a scrivere:
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
- è la matrice dei coefficienti;
- è il vettore delle incognite;
- è 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
La matrice dei coefficienti è
, mentre il vettore
è
La matrice completa è
Applicando il metodo di Gauss arriveremo a scrivere (i passaggi intermedi li lasciamo al lettore)
cambiamo la seconda riga con la terza:
La matrice completa è ridotta a scala. Ad essa associamo il sistema:
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 , 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.