Informatica 5 Liceo Scientifico Scienze Applicate/Gauss Risoluzione Sistemi Lineari

Gauss e la risoluzione di un sistema di equazioni lineari
Metodo dell'eliminazione Gaussiana

Per risolvere un sistema di equazioni lineari ci sono diversi metodi, fra quelli diretti piu' semplici c'e' il metodo di Gauss.

Alla base del metodo c'e' la considerazione che dato un sistema di equazioni lineari e' possibile trasformarlo in un sistema di equazioni equivalenti (cioe' con le stesse soluzioni del precedente). Un sistema equivalente lo si ottiene

• scambiando 2 equazioni fra di loro,
• oppure moltiplicando una equazione per una costante,
• oppure sostituendo a una equazione la combinazione lineare della stessa equazione con un'altra ( un caso particolare di questa regola e' la sostituzione di una equazione con la somma della stessa e di un'altra).

Naturalmente l'intenzione e' quella di passare da un sistema a un sistema equivalente che sia piu' semplice da risolvere.

Se il sistema da risolvere fosse della forma :

sistema triangolarizzato

cioe' se la matrice dei coefficienti delle incognite fosse triangolare (superiormente) o detto in altri modi fossero nulli tutti i coefficienti al di sotto della diagonale principale, allora il sistema sarebbe semplice da risolvere, infatti partendo dall'ultima equazione possiamo nel nostro caso ricavare prima x4 dall'ultima equazione, poi sostituendo x4 nella terza equazione calcolare x3, poi sostituendo x4 e x3 nella seconda equazione ricavare x2 ed infine utilizzando la prima equazione sostituire x4 x3 e x2 e calcolare x1 (questa tecnica e' detta per sostituzione all'indietro backward substitution)

soluz sistema triangolarizzato

dove le soluzioni sono

soluzione sistema

Ora notata l'importanza che il sistema espresso in forma matriciale sia triangolare possiamo vedere come trasformare un sistema generico in un sistema triangolare.

passo1 soluzione sistema lineare con gauss

sostituiamo la seconda equazione con la combinazione lineare data dalla seconda equazione moltiplicata per -a11/a21 e sommata con la prima equazione Questa operazione comporta che il coefficiente della prima incognita della seconda equazione si annulli. Poi sostituiamo la terza equazione con la combinazione lineare data dalla terza equazione moltiplicata per -a11/a31 e sommata con la prima equazione Questa operazione comporta che il coefficiente della prima incognita della terza equazione si annulli. e analogamente ripetiamo per le equazioni successive, in questo modo tutti i coefficienti della x1 (ad esclusione della prima equazione si sono annullati). Ora escludendo dai nostri pensieri la prima riga e la prima colonna della nostra matrice possiamo riapplicare ricorsivamente il meccanismo alla parte di matrice rimasta, fermandoci quando la parte di matrice che rimane e' costituita da un sol numero.

passo2 soluzione sistema lineare con gauss

passo3soluzione sistema lineare con gauss

sistema triangolarizzato

Codifichiamo adesso la soluzione utilizzando Octave

A=[2 3 4 5 6; 3 7 8 9 2; 4 8 0 6 1;  5 9 6 4 3; 5 2 -4 4 3] 
b=[2; 3; 6; 0; 3 ]
nr=5;
nc=5;
%questa e' la soluzione calcolata con Cramer
%sol1=inv(A)*b 

%triangolarizzo

for r= 1 : nr-1
 for rx= r+1 : nc
  k= -A(r,r)/A(rx,r);
  A(rx,:)=k*A(rx,:)+A(r,:);
  b(rx,1)=k*b(rx,1)+b(r,1);
 end
end
%ricavo l'ultima incognita 
x(nr,1) = b(nr,1)/A(nr,nr);

%ricavo le rimanenti incognite iterativamente
for r= nr-1:-1:1
 somma=0;
 for k= r+1:nc
  somma=x(k,1)*A(r,k)+somma;
 end
  x(r,1)=( b(r,1)-somma)/A(r,r);
end

x

Quando si sceglie una equazione riga k (quelle delle righe gialle nelle immagini) che viene usata per realizzare una combinazione lineare con una equazione delle successive righe k+i al fine di eliminare l'incognita x_k, può capitare che nell'equazione k il coefficiente dell'incognita k sia nullo, allora non possiamo utilizzarla e si deve cercare fra le righe successive una equazione riga y con il coefficiente dell'incognita k diverso da zero e scambiare le due equazioni (riga y e riga k) fra loro. La scelta dell'equazione k da usarsi viene indicata come scelta della equazione di pivot. Certe volte e' conveniente scambiare l'equazione di riga k con una di riga y (successiva) anche se il coefficiente dell'incognita k non e' nullo ma molto piccolo, questo per evitare moltiplicatori nei passaggi successivi troppo grandi che aumentano gli errori di arrotondamento ( e' quello che succede nell'esempio del codice di Octave scritto prima), per aumentare la stabilita' del metodo risolutivo (algoritmo)come riga di pivot posso prendere quella con coefficiente nella colonna k che sia in modulo maggiore delle altre righe (da k in giu').