Sistemi lineari, matrici e metodo di Gauss
Un solo algoritmo — il MEG — risolve tutti i sistemi lineari: dice se ci sono soluzioni, quante, e quali. Tutto il resto della sezione serve a spiegare perché funziona e come si legge il risultato.
Un sistema è difficile da guardare, una matrice a scala è facile. Le operazioni elementari permettono di passare dal primo alla seconda senza cambiare le soluzioni, e il MEG garantisce che ci si arrivi sempre in un numero finito di passi. A quel punto basta leggere.
Riduzioni a scala e ranghi (anche con un parametro), la dimostrazione sulle matrici $2\times n$ di rango $\lt2$, tre sistemi e la parabola per tre punti, con le soluzioni del tutor verificate: sono gli esercizi G1.5–G1.11 della palestra.
Checklist del programma
1 · Che cos'è un sistema lineare
Un sistema lineare di $m$ equazioni in $n$ incognite $x_1,\dots,x_n$ è un sistema della forma
$$(*)\qquad\begin{cases}a_{11}x_1+a_{12}x_2+\dots+a_{1n}x_n=b_1\\ a_{21}x_1+a_{22}x_2+\dots+a_{2n}x_n=b_2\\ \ \vdots\\ a_{m1}x_1+a_{m2}x_2+\dots+a_{mn}x_n=b_m\end{cases}$$ovvero, in forma compatta, $\displaystyle\sum_{j=1}^{n}a_{ij}x_j=b_i$ per $i=1,\dots,m$. Gli $a_{ij}$ si dicono coefficienti, i $b_i$ termini noti; sono costanti, cioè non dipendono dalle incognite.
Una soluzione di $(*)$ è un valore del vettore incognito $\vx:=(x_1,\dots,x_n)$ per cui tutte le equazioni sono uguaglianze valide. Le soluzioni sono dunque elementi di $\R^{n}$, oppure di $\C^{n}$ se si ammettono soluzioni complesse.
Quando un argomento vale sia sul campo $\R$ sia sul campo $\C$, il campo si indica con $\K$. Tutta questa sezione è scritta su $\K$: il MEG usa solo somma, prodotto e divisione per elementi non nulli, che esistono in entrambi.
Terminologia. Il sistema si dice compatibile se ammette almeno una soluzione, incompatibile altrimenti. Si dice omogeneo se $b_1=\dots=b_m=0$; un sistema omogeneo è sempre compatibile, perché $\vx=\vzero$ lo risolve.
Dalla scrittura alla matrice
Le incognite non servono a nulla durante i calcoli: servono solo i numeri e la loro posizione. Si buttano via i simboli e si tiene la tabella.
$$A=[a_{ij}]=\begin{bmatrix}a_{11}&\cdots&a_{1n}\\ \vdots&&\vdots\\ a_{m1}&\cdots&a_{mn}\end{bmatrix}\ \ \text{(matrice dei coefficienti, tipo } m\times n),$$ $$[A\,|\,\vb]=\left[\begin{array}{ccc|c}a_{11}&\cdots&a_{1n}&b_1\\ \vdots&&\vdots&\vdots\\ a_{m1}&\cdots&a_{mn}&b_m\end{array}\right]\ \ \text{(matrice completa)}.$$ Il sistema si scrive allora in forma matriciale come $\ A\vx=\vb$.
2 · Operazioni elementari e sistemi equivalenti
- scambiare due righe: $R_i\leftrightarrow R_k$;
- moltiplicare una riga per uno scalare $\lambda\ne0$: $R_i\to\lambda R_i$;
- sommare a una riga un multiplo di un'altra: $R_i\to R_i+\lambda R_k$ (con $i\ne k$).
Se $[A'\,|\,\vb']$ si ottiene da $[A\,|\,\vb]$ mediante operazioni elementari sulle righe, i due sistemi sono equivalenti: hanno esattamente lo stesso insieme di soluzioni.
Dimostrazione a passi coperti
3 · Matrici a scala
Per ogni riga $i$ sia $\ell_i$ il numero di zeri iniziali della riga (con $\ell_i=n$ se la riga è tutta nulla). La matrice è a scala se
$$\ell_1<\ell_2<\ell_3<\dots\qquad\text{finché }\ell_i\lt n,$$cioè gli zeri iniziali crescono strettamente, e le eventuali righe nulle stanno tutte in fondo.
Pivot
Il pivot di una riga non nulla è il suo primo elemento non nullo, che occupa il posto $(i,\ \ell_i+1)$. In una matrice a scala i pivot si spostano verso destra scendendo di riga.
4 · Il metodo di eliminazione di Gauss
Esiste un algoritmo — il metodo di eliminazione di Gauss — che trasforma una matrice qualsiasi in una matrice a scala mediante un numero finito di operazioni elementari sulle righe.
- Individua la prima colonna non tutta nulla (da sinistra, sotto la riga corrente).
- Porta in posizione, con uno scambio, una riga che abbia lì un elemento non nullo: è il pivot.
- Annulla tutti gli elementi sotto il pivot con l'operazione (3).
- Ripeti sulla sottomatrice rimanente, ignorando la riga e la colonna appena sistemate.
Perché l'algoritmo termina?
Perché a ogni passo la sottomatrice da trattare perde almeno una riga e una colonna. Dopo al più $\min\{m,n\}$ passi non resta nulla da fare. È questo a garantire che il numero di operazioni sia finito — la parte dell'enunciato che si dà spesso per scontata.
Laboratorio: il MEG passo per passo
I pivot cerchiati in rosso sono quelli della matrice dei coefficienti; un pivot arancione nella colonna dopo la barra è uno 0-pivot e segnala che il sistema è incompatibile. La riga evidenziata è quella modificata dall'operazione corrente.
5 · Leggere la matrice ridotta
Il criterio dello 0-pivot risultato centrale
Sia $[A\,|\,\vb]\xrightarrow{\text{MEG}}[U\,|\,\vb']$ a scala. Il sistema è incompatibile se e solo se in $[U\,|\,\vb']$ compare un pivot nella colonna dei termini noti, cioè una riga $$[\,0\ \ 0\ \cdots\ 0\ \,|\ c\,]\qquad\text{con }c\ne0.$$
Dimostrazione
Se c'è uno 0-pivot, quella riga è l'equazione $0\cdot x_1+\dots+0\cdot x_n=c$ con $c\ne0$, cioè $0=c$: falsa per ogni $\vx\in\K^n$. Il sistema ridotto non ha soluzioni, e per il teorema sulle operazioni elementari nemmeno quello di partenza.
Se non c'è, ogni riga non nulla ha il pivot in una colonna dei coefficienti. Si assegnano valori arbitrari alle incognite libere e si ricavano le altre con la sostituzione all'indietro: ogni pivot è non nullo, quindi ogni divisione è lecita, e si ottiene almeno una soluzione. $\blacksquare$
Solo alla matrice già completamente ridotta a scala. Una riga può sembrare impossibile a metà riduzione e sistemarsi dopo, o viceversa. Il criterio è una proprietà della forma a scala, non del processo.
Rango, incognite di base e incognite libere risultato centrale
Il rango $r=\rg A$ è il numero di pivot di una riduzione a scala di $A$. Le incognite corrispondenti alle colonne con pivot si dicono di base (o pivotali); le altre libere, e sono $n-r$.
$$r\le m\qquad\text{e}\qquad r\le n,\qquad\text{dunque}\qquad r\le\min\{m,n\}.$$
Dimostrazione (due righe)
$r\le m$ perché ogni riga contiene al più un pivot (il suo primo elemento non nullo).
$r\le n$ perché in una matrice a scala gli indici di colonna dei pivot sono strettamente crescenti, quindi due pivot non stanno mai nella stessa colonna: il numero di pivot non supera il numero di colonne. $\blacksquare$
La forma a scala di $A$ non è unica: scelte diverse durante il MEG danno matrici diverse. È però unico il numero di pivot, e questo si ammette a lezione. Senza quel fatto, «il rango di $A$» non sarebbe neppure una definizione sensata.
Mettiti alla prova
Errori tipici della Sezione 1
- Scrivere $\ell_1\le\ell_2\le\dots$ La crescita degli zeri iniziali dev'essere stretta.
- Moltiplicare una riga per $0$ «per semplificare». Non è un'operazione elementare.
- Cercare lo 0-pivot prima di aver finito la riduzione.
- Contare le incognite libere come $n-m$ invece di $n-r$.
- Confondere $\rg A$ con $\rg[A\,|\,\vb]$. Differiscono al più di $1$, e differiscono esattamente quando c'è uno 0-pivot.
- Dividere per un coefficiente che contiene un parametro senza discutere il caso in cui si annulla.
- Dimenticare che le operazioni si fanno sulle righe, non sulle colonne: scambiare colonne cambia l'ordine delle incognite.