Sistemi lineari e metodo di eliminazione di Gauss
Forma matriciale, significato geometrico, operazioni elementari, riduzione a scala, sistemi impossibili e indeterminati, Gauss-Jordan e il costo dell'algoritmo.
Risolvere un sistema di equazioni lineari è il problema più frequente della matematica applicata: le correnti di una rete elettrica, le forze in una struttura reticolare, l’interpolazione di dati, la simulazione di un circuito in SPICE si riducono tutti lì. In questa lezione vediamo come si scrive un sistema in forma matriciale, che cosa significa geometricamente e come lo si risolve con il metodo di eliminazione di Gauss, che è anche l’algoritmo usato dai computer.
Sistemi lineari e forma matriciale
Un sistema di 
equazioni lineari in 
incognite si scrive
![\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1\\ \quad\vdots\\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \end{cases} \qquad\Longleftrightarrow\qquad A\,\mathbf x = \mathbf b \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-181bc7f9cceb6088cd47c5d79c0a38e0_l3.png "Rendered by QuickLaTeX.com")
dove 
è la matrice dei coefficienti ( righe, colonne), 
il vettore delle incognite e 
quello dei termini noti. Affiancando ad si ottiene la matrice completa 
. Se 
il sistema è omogeneo e ha sempre almeno la soluzione nulla.
Il significato geometrico
Con due incognite ogni equazione è una retta nel piano, e risolvere il sistema vuol dire trovare i punti comuni. Ci sono solo tre possibilità.
Lo stesso vale in generale: un sistema lineare ha una soluzione, nessuna o infinite. Non può averne esattamente due, perché se 
e 
sono soluzioni lo è anche ogni punto della retta che li unisce, 
: infatti 
. Con tre incognite ogni equazione è un piano, e le soluzioni sono un punto, una retta, un piano o niente.
Le operazioni elementari
Le soluzioni di un sistema non cambiano se si applicano alle sue equazioni (cioè alle righe della matrice completa) queste operazioni elementari:
- scambiare due righe;
- moltiplicare una riga per un numero diverso da zero;
- sommare a una riga un multiplo di un’altra riga.
Ogni operazione è invertibile (si annulla con un’operazione dello stesso tipo), quindi ogni soluzione del sistema nuovo è soluzione del vecchio e viceversa.
Il metodo di Gauss
L’idea è usare le operazioni elementari per portare la matrice completa in forma a scala: ogni riga comincia con più zeri della precedente. Il primo elemento non nullo di ogni riga si chiama pivot. A quel punto il sistema si risolve dal basso verso l’alto, per sostituzione all’indietro.
Esempio.
![\[ \begin{cases} x + 2y + z = 4\\ 2x + 5y + 3z = 11\\ -x + y + 4z = 9 \end{cases} \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-cefe53043f6b96b9ae845cdf8c95c385_l3.png "Rendered by QuickLaTeX.com")
![\[ \left(\begin{array}{ccc|c} 1 & 2 & 1 & 4\\ 2 & 5 & 3 & 11\\ -1 & 1 & 4 & 9 \end{array}\right) \xrightarrow[R_3 + R_1]{R_2 - 2R_1} \left(\begin{array}{ccc|c} 1 & 2 & 1 & 4\\ 0 & 1 & 1 & 3\\ 0 & 3 & 5 & 13 \end{array}\right) \xrightarrow{R_3 - 3R_2} \left(\begin{array}{ccc|c} 1 & 2 & 1 & 4\\ 0 & 1 & 1 & 3\\ 0 & 0 & 2 & 4 \end{array}\right) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-a5ec65e30d67b2a31fc0504ecb4e31f8_l3.png "Rendered by QuickLaTeX.com")
Dall’ultima riga 
, quindi 
. Dalla seconda 
. Dalla prima 
. Soluzione: 
. Conviene sempre verificarla nella terza equazione originale: 
. Corretto.
Sistemi impossibili e indeterminati
La forma a scala dice subito come stanno le cose.
- Se compare una riga
con 
, cioè l’equazione 
, il sistema è impossibile. - Altrimenti è risolubile. Le incognite che corrispondono ai pivot si ricavano; le altre sono parametri liberi. Con incognite e
pivot le soluzioni dipendono da 
parametri: si dice che sono 
.
Esempio. 
, 
, 
. Con 
e 
si ottengono le righe 
e ; con 
l’ultima diventa tutta zero. Restano due pivot e tre incognite: 
libero, 
, 
. Le soluzioni sono la retta 
.
Se l’ultima riga fosse stata 
(per esempio con termine noto 7 al posto di 6 nella terza equazione), il sistema sarebbe stato impossibile: i tre piani non avrebbero un punto comune.
Il metodo di Gauss-Jordan
Proseguendo l’eliminazione anche verso l’alto e dividendo ogni riga per il suo pivot si arriva alla forma a scala ridotta: pivot uguali a 1 e zeri sopra e sotto ogni pivot. Le soluzioni si leggono direttamente, senza sostituzione. Lo stesso procedimento, applicato alla matrice 
, calcola la matrice inversa (lo vedremo nella lezione sulle matrici).
Quanto costa
Per un sistema 
l’eliminazione richiede circa 
operazioni. Con 
sono poco meno di un miliardo, una frazione di secondo per un computer. Le librerie numeriche (LAPACK, usata da MATLAB e NumPy) usano proprio Gauss, in una versione detta fattorizzazione LU, con lo scambio parziale delle righe: a ogni passo si sceglie come pivot l’elemento più grande in valore assoluto della colonna, per non dividere per numeri piccolissimi e limitare gli errori di arrotondamento.
Una nota per gli elettronici
Con il metodo dei nodi, ogni nodo di un circuito lineare dà un’equazione lineare nelle tensioni di nodo (legge di Kirchhoff delle correnti). Un circuito con 500 nodi è un sistema 
, e un simulatore come SPICE, a ogni passo temporale, non fa altro che costruirlo e risolverlo con l’eliminazione di Gauss, sfruttando il fatto che la matrice è quasi tutta fatta di zeri.
