Operazioni sulle matrici¶
Vettori e matrici · Capitolo 4.2 · Dispensa (PDF) · Esercizi: Operazioni sulle matrici · Slide (PDF) · App: Metodo di Gauss · App: Determinante · App: Perché serve il pivoting
1. Operazioni elementari di riga e di colonna¶
- Le operazioni elementari di riga e di colonna sono strumenti fondamentali dell'algebra lineare. Sono utilizzate in molti algoritmi, tra cui l'eliminazione di Gauss, il calcolo della matrice inversa e le fattorizzazioni di matrici (come la decomposizione LU)
Data una matrice \(\boldsymbol A \in \R^{m \times n}\), le operazioni elementari di riga sono:
-
Scambio di righe: si scambiano le righe \(i\) e \(k\).
\[ R_i \leftrightarrow R_k \] -
Moltiplicazione di una riga per uno scalare: si moltiplica la riga \(i\) per uno scalare non nullo \(\lambda \neq 0\).
\[ R_i \leftarrow \lambda R_i \] -
Somma di righe: si sostituisce la riga \(i\) con la somma della riga \(i\) e di \(\lambda\) volte la riga \(k\) (con \(i \neq k\)).
\[ R_i \leftarrow R_i + \lambda R_k \]
Esempio 1: Scambio di righe
Consideriamo la matrice
Scambiando le righe 1 e 3, cioè \(R_1 \leftrightarrow R_3\), otteniamo:
Esempio 2: Moltiplicazione di una riga per uno scalare
Consideriamo la matrice
Moltiplicando la riga 2 per \(\lambda = -2\), cioè \(R_2 \leftarrow -2R_2\), otteniamo:
Esempio 3: Somma di righe
Consideriamo la matrice
Sostituendo la riga 2 con la riga 2 meno 4 volte la riga 1, cioè \(R_2 \leftarrow R_2 - 4R_1\), otteniamo:
Infatti:
Data una matrice \(\boldsymbol A \in \R^{m \times n}\), le operazioni elementari di colonna sono:
-
Scambio di colonne: si scambiano le colonne \(j\) e \(k\).
\[ C_j \leftrightarrow C_k \] -
Moltiplicazione di una colonna per uno scalare: si moltiplica la colonna \(j\) per uno scalare non nullo \(\lambda \neq 0\).
\[ C_j \leftarrow \lambda C_j \] -
Somma di colonne: si sostituisce la colonna \(j\) con la somma della colonna \(j\) e di \(\lambda\) volte la colonna \(k\) (con \(j \neq k\)).
\[ C_j \leftarrow C_j + \lambda C_k \]
Esempio 4: Scambio di colonne
Consideriamo la matrice
Scambiando le colonne 1 e 3, cioè \(C_1 \leftrightarrow C_3\), otteniamo:
Esempio 5: Moltiplicazione di una colonna per uno scalare
Consideriamo la matrice
Moltiplicando la colonna 2 per \(\lambda = 3\), cioè \(C_2 \leftarrow 3C_2\), otteniamo:
Esempio 6: Somma di colonne
Consideriamo la matrice
Sostituendo la colonna 3 con la colonna 3 più 2 volte la colonna 1, cioè \(C_3 \leftarrow C_3 + 2C_1\), otteniamo:
Infatti:
2. Effetto delle operazioni elementari sul determinante¶
Sia \(\boldsymbol A \in \R^{n \times n}\) una matrice quadrata. Le operazioni elementari di riga agiscono sul determinante nel modo seguente:
-
Scambio di righe: \(R_i \leftrightarrow R_k\) cambia il segno del determinante.
\[ \det(\text{nuova matrice}) = -\det(\boldsymbol A) \] -
Moltiplicazione di una riga per uno scalare: \(R_i \leftarrow \lambda R_i\) (con \(\lambda \neq 0\)) moltiplica il determinante per \(\lambda\).
\[ \det(\text{nuova matrice}) = \lambda \det(\boldsymbol A) \] -
Somma di righe: \(R_i \leftarrow R_i + \lambda R_k\) (con \(i \neq k\)) non cambia il determinante.
\[ \det(\text{nuova matrice}) = \det(\boldsymbol A) \]
Esempio 7: Effetto dello scambio di righe sul determinante
Consideriamo la matrice
Il determinante è:
Scambiando le righe 1 e 2, cioè \(R_1 \leftrightarrow R_2\), otteniamo:
Il determinante della nuova matrice è:
Esempio 8: Effetto della moltiplicazione di una riga per uno scalare sul determinante
Consideriamo la matrice
Il determinante è:
Moltiplicando la riga 1 per \(\lambda = 2\), cioè \(R_1 \leftarrow 2R_1\), otteniamo:
Il determinante della nuova matrice è:
Esempio 9: Effetto della somma di righe sul determinante
Consideriamo la matrice
Il determinante è:
Sostituendo la riga 2 con la riga 2 meno 3 volte la riga 1, cioè \(R_2 \leftarrow R_2 - 3R_1\), otteniamo:
Il determinante della nuova matrice è:
Sia \(\boldsymbol A \in \R^{n \times n}\) una matrice quadrata. Le operazioni elementari di colonna agiscono sul determinante nel modo seguente:
-
Scambio di colonne: \(C_j \leftrightarrow C_k\) cambia il segno del determinante.
\[ \det(\text{nuova matrice}) = -\det(\boldsymbol A) \] -
Moltiplicazione di una colonna per uno scalare: \(C_j \leftarrow \lambda C_j\) (con \(\lambda \neq 0\)) moltiplica il determinante per \(\lambda\).
\[ \det(\text{nuova matrice}) = \lambda \det(\boldsymbol A) \] -
Somma di colonne: \(C_j \leftarrow C_j + \lambda C_k\) (con \(j \neq k\)) non cambia il determinante.
\[ \det(\text{nuova matrice}) = \det(\boldsymbol A) \]
Esempio 10: Effetto dello scambio di colonne sul determinante
Consideriamo la matrice
Il determinante è:
Scambiando le colonne 1 e 2, cioè \(C_1 \leftrightarrow C_2\), otteniamo:
Il determinante della nuova matrice è:
Esempio 11: Effetto della moltiplicazione di una colonna per uno scalare sul determinante
Consideriamo la matrice
Il determinante è:
Moltiplicando la colonna 2 per \(\lambda = 3\), cioè \(C_2 \leftarrow 3C_2\), otteniamo:
Il determinante della nuova matrice è:
Esempio 12: Effetto della somma di colonne sul determinante
Consideriamo la matrice
Il determinante è:
Sostituendo la colonna 2 con la colonna 2 più 2 volte la colonna 1, cioè \(C_2 \leftarrow C_2 + 2C_1\), otteniamo:
Il determinante della nuova matrice è:
-
Queste proprietà discendono dal fatto che il determinante di una matrice è uguale al determinante della sua trasposta (si vedano le proprietà dei determinanti nel capitolo sulle matrici) e che un'operazione di colonna su una matrice corrisponde alla relativa operazione di riga sulla sua trasposta. Di conseguenza, le operazioni di colonna hanno sul determinante lo stesso effetto delle corrispondenti operazioni di riga.
-
Questi risultati sono fondamentali per comprendere come si comporta il determinante rispetto alle operazioni elementari, aspetto cruciale in algoritmi come l'eliminazione di Gauss e la fattorizzazione di matrici.
3. Eliminazione di Gauss e forma a scala¶
- Le operazioni elementari di riga permettono di trasformare qualsiasi matrice in una matrice con una struttura “a scala”, dalla quale si possono leggere facilmente molte proprietà della matrice originale (per esempio, il suo determinante). La procedura sistematica che realizza questa trasformazione si chiama eliminazione di Gauss.
Definizione 1: Forma a scala per righe
Una matrice \(\boldsymbol U \in \R^{m \times n}\) è in forma a scala (per righe) se:
-
tutte le sue righe nulle (se presenti) si trovano sotto tutte le sue righe non nulle;
-
il primo elemento non nullo di ogni riga non nulla (detto pivot della riga) si trova strettamente a destra del pivot della riga precedente.
-
Di conseguenza, tutti gli elementi sotto un pivot sono uguali a zero.
-
Una matrice quadrata in forma a scala è triangolare superiore.
Eliminazione di Gauss. Data \(\boldsymbol A \in \R^{m \times n}\), si esaminano le colonne da sinistra verso destra. A ogni passo, considerando le righe non ancora utilizzate come righe pivot:
-
si individua la prima colonna che contiene un elemento non nullo in queste righe; se necessario, si porta tale elemento nella prima di queste righe con uno scambio di righe \(R_k \leftrightarrow R_i\) (questo elemento non nullo è il pivot);
-
per ogni riga \(i\) sotto la riga pivot \(k\), si crea uno zero sotto il pivot con la somma di righe
\[ R_i \leftarrow R_i - \frac{a_{ij}}{a_{kj}}\, R_k, \]dove \(a_{kj}\) è il pivot e \(a_{ij}\) è l'elemento da eliminare (nella matrice corrente);
-
si ripete il procedimento sulle righe rimanenti.
Al termine, la matrice è in forma a scala. Si utilizzano soltanto scambi di righe e somme di righe.
Osservazione 1: Determinante tramite eliminazione di Gauss
Sia \(\boldsymbol A \in \R^{n \times n}\) e sia \(\boldsymbol U\) una forma a scala di \(\boldsymbol A\) ottenuta con l'eliminazione di Gauss mediante \(s\) scambi di righe (e un numero qualsiasi di somme di righe). Allora
In particolare, \(\det(\boldsymbol A) = 0\) se e solo se \(\boldsymbol U\) ha uno zero sulla diagonale.
Dimostrazione
Ogni somma di righe non cambia il determinante e ogni scambio di righe ne cambia il segno. Quindi \(\det(\boldsymbol U) = (-1)^{s}\det(\boldsymbol A)\), cioè \(\det(\boldsymbol A) = (-1)^{s}\det(\boldsymbol U)\). Poiché \(\boldsymbol U\) è quadrata e in forma a scala, essa è triangolare superiore, e il suo determinante è il prodotto degli elementi diagonali. □
Esempio 13: Determinante tramite eliminazione di Gauss
Consideriamo
Riduciamo \(\boldsymbol A\) in forma a scala con l'eliminazione di Gauss.
La matrice è ora in forma a scala. Abbiamo effettuato \(s=1\) scambio di righe, quindi
Infatti, con lo sviluppo di Laplace lungo la prima riga: \(\det(\boldsymbol A) = 0\cdot(3-1) - 1\cdot(3-2) + 2\cdot(1-2) = -3\).
Provalo nel laboratorio
lo stesso calcolo passo per passo: cambia la matrice e guarda come cambiano i passaggi.
4. Pivoting e pivoting parziale¶
-
Negli algoritmi numerici, come le fattorizzazioni di matrici e i metodi di riduzione per righe, il pivoting è una tecnica utilizzata per migliorare la stabilità numerica ed evitare divisioni per zero.
-
L'elemento pivot è l'elemento utilizzato come divisore nel processo di eliminazione.
4.1 Pivoting¶
Il pivoting è il procedimento con cui si sceglie un opportuno elemento pivot in una matrice per eseguire i passi di eliminazione negli algoritmi di riduzione per righe.
Quando si esegue l'eliminazione per righe su una matrice \(\boldsymbol A \in \R^{n \times n}\), al passo \(k\):
-
L'elemento pivot è l'elemento \(a_{kk}\) (l'elemento diagonale in posizione \((k,k)\)).
-
Se \(a_{kk} = 0\), non possiamo usarlo come divisore, quindi dobbiamo scambiare la riga \(k\) con una riga \(i > k\) tale che \(a_{ik} \neq 0\).
-
Questo scambio di righe si chiama pivoting.
Esempio 14: Pivoting nell'eliminazione per righe
Consideriamo la matrice:
Non possiamo usare \(a_{11} = 0\) come primo pivot. Dobbiamo scambiare la riga 1 con una riga che abbia un elemento non nullo nella prima colonna.
Scambiamo le righe 1 e 2 (cioè \(R_1 \leftrightarrow R_2\)):
Ora \(a_{11} = 1 \neq 0\) e possiamo procedere con l'eliminazione:
Usiamo ora \(a_{22} = 2\) come secondo pivot:
La matrice è ora in forma triangolare superiore.
4.2 Pivoting parziale¶
Il pivoting parziale è una strategia per migliorare la stabilità numerica che consiste nello scegliere come pivot l'elemento disponibile di valore assoluto massimo.
Al passo \(k\) dell'eliminazione di Gauss:
-
Si trova la riga \(i \ge k\) tale che \(|a_{ik}|\) sia massimo tra tutti i \(|a_{jk}|\) con \(j \ge k\).
-
Si scambia la riga \(k\) con la riga \(i\) (cioè \(R_k \leftrightarrow R_i\)).
-
Si usa il nuovo \(a_{kk}\) come pivot.
In questo modo:
-
Il pivot è l'elemento di valore assoluto massimo nella sua colonna, tra gli elementi sulla diagonale o sotto di essa.
-
La divisione per un numero più grande riduce gli errori di arrotondamento nell'aritmetica in virgola mobile.
-
Il metodo è numericamente più stabile.
Esempio 15: Pivoting parziale nell'eliminazione per righe
Consideriamo la matrice:
Passo 1: troviamo l'elemento di valore assoluto massimo nella prima colonna.
Il massimo è \(|a_{21}| = 3\), quindi scambiamo le righe 1 e 2:
Eliminiamo ora gli elementi sotto il pivot \(a_{11} = 3\):
Passo 2: troviamo l'elemento di valore assoluto massimo nella seconda colonna (righe 2 e 3).
Il massimo è \(\left|\frac{11}{3}\right|\), quindi scambiamo le righe 2 e 3:
Eliminiamo l'elemento sotto il pivot \(a_{22} = \frac{11}{3}\):
La matrice è ora in forma triangolare superiore (forma a scala).
Esempio 16: Confronto: senza e con pivoting parziale
Consideriamo la matrice:
Senza pivoting parziale:
Usando \(a_{11} = \frac{1}{10000}\) come pivot:
Si ottiene:
Il moltiplicatore elevato \(10000\) può causare errori di arrotondamento significativi nell'aritmetica in virgola mobile.
Con pivoting parziale:
Poiché \(|a_{21}| = 1 > |a_{11}| = \frac{1}{10000}\), scambiamo le righe:
Eliminiamo ora usando \(a_{11} = 1\) come pivot:
Il moltiplicatore \(\frac{1}{10000}\) è molto più piccolo, e ciò porta a una migliore stabilità numerica.
-
Il pivoting parziale è cruciale nell'algebra lineare numerica per garantire che gli algoritmi producano risultati accurati, specialmente quando si lavora con matrici i cui elementi hanno ordini di grandezza molto diversi.
-
La maggior parte dei software numerici moderni (come MATLAB, NumPy, CPLEX, Gurobi) utilizza automaticamente il pivoting parziale nell'eliminazione di Gauss e nella fattorizzazione LU.
-
Il costo computazionale del pivoting parziale è minimo rispetto al beneficio in termini di stabilità numerica.
Provalo nel laboratorio
lo stesso calcolo passo per passo: cambia la matrice e guarda come cambiano i passaggi.
Esercizi e laboratorio¶
- Esercizi · il foglio di esercizi di questo capitolo: 10 esercizi con le soluzioni svolte
- Laboratorio · Metodo di Gauss — Porta una matrice in forma a scala (o ridotta) mostrando ogni operazione elementare.
- Laboratorio · Determinante — scegli il metodo «Eliminazione di Gauss»: l'effetto di ogni operazione elementare sul determinante
- Laboratorio · Perché serve il pivoting — Lo stesso sistema con e senza pivoting parziale, in virgola mobile.