Metodo di Gauss con pivoting totale, perché si devono riordinare le soluzioni?
Buonasera, sto studiando l'argomento del titolo, e trovo difficoltà nel comprendere a pieno come portare a termine il metodo di Gauss nella sua variante con pivoting totale. Per farvi capire, vi propongo questo esempio di esercizio che ho tentato di svolgere.
Determina le soluzioni del sistema lineare:
\(\quad\begin{pmatrix} 1 & 2 & 3 \\3 & 4 & 6 \\ 10 & 5 & -3 \end{pmatrix}\begin{pmatrix} x \\y\\ z \end{pmatrix} = \begin{pmatrix} 1 \\3\\ -4 \end{pmatrix}\quad\)
utilizzando il metodo di Gauss con variante del pivoting totale.
Io faccio in questo modo: Nel primo passaggio il massimo in valore assoluto della matrice si trova in posizione $\{3,1\}$ per cui ricordo in due "array" separati gli scambi di righe e colonne effettuati:
$righe = [3, x]$
$\mbox{colonne} = [1,x]$
dove con x nel vettore intendo un don't care e non l'incognita.
Riduco separatamente la matrice dei coefficienti e il vettore dei termini noti. Effettuando lo scambio di righe e colonne che ho trovato trovo questa matrice:
\(\quad\begin{pmatrix} 10 & 5 & -3 \\3 & 4 & 6 \\ 1 & 2 & 3 \end{pmatrix}\quad\) e uso come moltiplicatori rispettivamente $\frac{3}{10}$ e $\frac{1}{10}$.
Per non occupare ulteriori risorse li memorizzo nel triangolo inferiore della matrice; arrivo dopo aver effettuato il primo passaggio a questa:
\(\quad\begin{pmatrix} 10 & 5 & -3 \\\frac{3}{10} & \frac{5}{2} &\frac{69}{10} \\ \frac{1}{10} & \frac{3}{2} & \frac{33}{10} \end{pmatrix}\quad\)
Adesso ricerco il massimo di \(\quad\begin{pmatrix} \frac{5}{2} &\frac{69}{10} \\ \frac{3}{2} & \frac{33}{10} \end{pmatrix}\quad\) in valore assoluto, che è $\frac{69}{10}$.
Per portarlo in posizione $\{2,2}$ devo scambiare la seconda colonna con la terza. Aggiorno i vettori:
$righe = [3, 2]$
$\mbox{colonne} = [1,3]$
Dopo lo scambio ottengo:
\(\quad\begin{pmatrix} 10 & -3 & 5 \\\frac{3}{10} & \frac{69}{10} &\frac{5}{2} \\ \frac{1}{10} & \frac{33}{10} & \frac{3}{2} \end{pmatrix}\quad\) e uso come moltiplicatore $\frac{11}{23}$
Arrivo a questa:
\(\quad\begin{pmatrix} 10 & -3 & 5 \\\frac{3}{10} & \frac{69}{10} &\frac{5}{2} \\ \frac{1}{10} & \frac{11}{23} & \frac{7}{23} \end{pmatrix}\quad\) dopodiché adopero la riduzione con lo stesso metodo sul vettore dei termini noti.
\(\quad\begin{pmatrix} 1 \\3\\ -4 \end{pmatrix}\quad\) diventa, ricordando che ho scambiato la prima riga con la terza al primo passaggio \(\quad\begin{pmatrix} -4 \\1\\ 3 \end{pmatrix}\quad\)
Adesso riduco coi moltiplicatori nella prima colonna:
\(\quad\begin{pmatrix} -4 \\\frac{21}{5}\\ \frac{7}{5} \end{pmatrix}\quad\)
Dato che non ho scambiato righe al passaggio 2, proseguo con la riduzione col moltiplicatore nella seconda colonna e ottengo
\(\quad\begin{pmatrix} -4 \\\frac{21}{5}\\ -\frac{14}{23} \end{pmatrix}\quad\)
Adesso risolvo il sistema
\(\quad\begin{pmatrix} 10 & -3 & 5 \\0 & \frac{69}{10} &\frac{5}{2} \\ 0 & 0 & \frac{7}{23} \end{pmatrix}\begin{pmatrix} x \\y\\ z \end{pmatrix} = \begin{pmatrix} -4 \\\frac{21}{5}\\ -\frac{14}{23} \end{pmatrix}\quad \)
Con il metodo di sostituzione all'indietro e ho:
$(x,y,z) = (1,\frac{4}{3},-2)$ mentre il testo riporta $(x,y,z) = (1,-2,\frac{4}{3})$ da cui deduco la necessità di effettuare qualche scambio nelle soluzioni (i risultati sono uguali se scambio). Allora che scambi devo fare? C'è qualche ordine preciso?
Determina le soluzioni del sistema lineare:
\(\quad\begin{pmatrix} 1 & 2 & 3 \\3 & 4 & 6 \\ 10 & 5 & -3 \end{pmatrix}\begin{pmatrix} x \\y\\ z \end{pmatrix} = \begin{pmatrix} 1 \\3\\ -4 \end{pmatrix}\quad\)
utilizzando il metodo di Gauss con variante del pivoting totale.
Io faccio in questo modo: Nel primo passaggio il massimo in valore assoluto della matrice si trova in posizione $\{3,1\}$ per cui ricordo in due "array" separati gli scambi di righe e colonne effettuati:
$righe = [3, x]$
$\mbox{colonne} = [1,x]$
dove con x nel vettore intendo un don't care e non l'incognita.
Riduco separatamente la matrice dei coefficienti e il vettore dei termini noti. Effettuando lo scambio di righe e colonne che ho trovato trovo questa matrice:
\(\quad\begin{pmatrix} 10 & 5 & -3 \\3 & 4 & 6 \\ 1 & 2 & 3 \end{pmatrix}\quad\) e uso come moltiplicatori rispettivamente $\frac{3}{10}$ e $\frac{1}{10}$.
Per non occupare ulteriori risorse li memorizzo nel triangolo inferiore della matrice; arrivo dopo aver effettuato il primo passaggio a questa:
\(\quad\begin{pmatrix} 10 & 5 & -3 \\\frac{3}{10} & \frac{5}{2} &\frac{69}{10} \\ \frac{1}{10} & \frac{3}{2} & \frac{33}{10} \end{pmatrix}\quad\)
Adesso ricerco il massimo di \(\quad\begin{pmatrix} \frac{5}{2} &\frac{69}{10} \\ \frac{3}{2} & \frac{33}{10} \end{pmatrix}\quad\) in valore assoluto, che è $\frac{69}{10}$.
Per portarlo in posizione $\{2,2}$ devo scambiare la seconda colonna con la terza. Aggiorno i vettori:
$righe = [3, 2]$
$\mbox{colonne} = [1,3]$
Dopo lo scambio ottengo:
\(\quad\begin{pmatrix} 10 & -3 & 5 \\\frac{3}{10} & \frac{69}{10} &\frac{5}{2} \\ \frac{1}{10} & \frac{33}{10} & \frac{3}{2} \end{pmatrix}\quad\) e uso come moltiplicatore $\frac{11}{23}$
Arrivo a questa:
\(\quad\begin{pmatrix} 10 & -3 & 5 \\\frac{3}{10} & \frac{69}{10} &\frac{5}{2} \\ \frac{1}{10} & \frac{11}{23} & \frac{7}{23} \end{pmatrix}\quad\) dopodiché adopero la riduzione con lo stesso metodo sul vettore dei termini noti.
\(\quad\begin{pmatrix} 1 \\3\\ -4 \end{pmatrix}\quad\) diventa, ricordando che ho scambiato la prima riga con la terza al primo passaggio \(\quad\begin{pmatrix} -4 \\1\\ 3 \end{pmatrix}\quad\)
Adesso riduco coi moltiplicatori nella prima colonna:
\(\quad\begin{pmatrix} -4 \\\frac{21}{5}\\ \frac{7}{5} \end{pmatrix}\quad\)
Dato che non ho scambiato righe al passaggio 2, proseguo con la riduzione col moltiplicatore nella seconda colonna e ottengo
\(\quad\begin{pmatrix} -4 \\\frac{21}{5}\\ -\frac{14}{23} \end{pmatrix}\quad\)
Adesso risolvo il sistema
\(\quad\begin{pmatrix} 10 & -3 & 5 \\0 & \frac{69}{10} &\frac{5}{2} \\ 0 & 0 & \frac{7}{23} \end{pmatrix}\begin{pmatrix} x \\y\\ z \end{pmatrix} = \begin{pmatrix} -4 \\\frac{21}{5}\\ -\frac{14}{23} \end{pmatrix}\quad \)
Con il metodo di sostituzione all'indietro e ho:
$(x,y,z) = (1,\frac{4}{3},-2)$ mentre il testo riporta $(x,y,z) = (1,-2,\frac{4}{3})$ da cui deduco la necessità di effettuare qualche scambio nelle soluzioni (i risultati sono uguali se scambio). Allora che scambi devo fare? C'è qualche ordine preciso?
Risposte
Sinceramente non ho "seguito" il tuo percorso che mi sembra un po' troppo complicato, però giungo alla soluzione del libro ...
Il metodo è pensato per essere scritto in forma algoritmica consentendo di risolvere più sistemi lineari al variare del solo vettore dei termini noti (utile ad esempio per calcolare l'inversa di una matrice). Te lo scrivo sotto forma di algoritmo:
1. Trova il massimo in valore assoluto nella sottomatrice ottenuta eliminando le prime $k-1$ righe e colonne (k = numero dello step).
2. Salva in un vettore l'indice di riga del massimo. In questo modo, se il vettore in un certo indice $k$ ha una componente maggiore di $k$ stesso si sa che è stato effettuato uno scambio tra la riga $k$ e la riga $\mbox{righe(k)}$. Stesso per le colonne;
3. Salva nella posizione ${i,k}$ della matrice il moltiplicatore $\frac{a_{ik}}{a_{kk}}$; in questo modo si conservano i moltiplicatori nel triangolo inferiore per poi poter risolvere lo stesso sistema con vettori di termini noti diversi;
4. Modifica le componenti della sottomatrice ottenuta eliminando le prime $k$ righe e colonne secondo la regola: [size=150]$a_{ij}^{(k)} = a_{ij}^{(k-1)}-\frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}a_{kj}^{(k-1)}$[/size]
siccome nella posizione $\{i,k\}$ della matrice ci mettiamo il moltiplicatore $\frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}$ quella di prima diventa:
[size=100]$a_{ij}^{(k)} = a_{ij}^{(k-1)}-a_{ik}^{(k-1)}a_{kj}^{(k-1)}$[/size]
5. Riordinamento termini noti: si scambia il termine noto in posizione $k$ con quello in posizione $righe(k)$ e si riduce secondo i moltiplicatori nel triangolo inferiore della matrice di prima. Si ripete questo procedimento per $n-1$ volte se la matrice è di ordine $n\timesn$
6. Si applica il metodo di sostituzione all'indietro.
1. Trova il massimo in valore assoluto nella sottomatrice ottenuta eliminando le prime $k-1$ righe e colonne (k = numero dello step).
2. Salva in un vettore l'indice di riga del massimo. In questo modo, se il vettore in un certo indice $k$ ha una componente maggiore di $k$ stesso si sa che è stato effettuato uno scambio tra la riga $k$ e la riga $\mbox{righe(k)}$. Stesso per le colonne;
3. Salva nella posizione ${i,k}$ della matrice il moltiplicatore $\frac{a_{ik}}{a_{kk}}$; in questo modo si conservano i moltiplicatori nel triangolo inferiore per poi poter risolvere lo stesso sistema con vettori di termini noti diversi;
4. Modifica le componenti della sottomatrice ottenuta eliminando le prime $k$ righe e colonne secondo la regola: [size=150]$a_{ij}^{(k)} = a_{ij}^{(k-1)}-\frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}a_{kj}^{(k-1)}$[/size]
siccome nella posizione $\{i,k\}$ della matrice ci mettiamo il moltiplicatore $\frac{a_{ik}^{(k-1)}}{a_{kk}^{(k-1)}}$ quella di prima diventa:
[size=100]$a_{ij}^{(k)} = a_{ij}^{(k-1)}-a_{ik}^{(k-1)}a_{kj}^{(k-1)}$[/size]
5. Riordinamento termini noti: si scambia il termine noto in posizione $k$ con quello in posizione $righe(k)$ e si riduce secondo i moltiplicatori nel triangolo inferiore della matrice di prima. Si ripete questo procedimento per $n-1$ volte se la matrice è di ordine $n\timesn$
6. Si applica il metodo di sostituzione all'indietro.
Grazie per il pensiero (nessuna ironia) ma mi viene il mal di testa solo a pensare di analizzarlo ... 
Solo una cosa: premesso che mi sembra più un quesito di analisi numerica o di informatica, perché c'è la necessità di un algoritmo specifico per risolvere sistemi con colonne diverse di termini noti quando ti basta risolvere un'unica matrice "allungata" con tutte le colonne dei termini noti (come si fa, in un certo senso, per trovare l'inversa) ?
Solo una cosa: premesso che mi sembra più un quesito di analisi numerica o di informatica, perché c'è la necessità di un algoritmo specifico per risolvere sistemi con colonne diverse di termini noti quando ti basta risolvere un'unica matrice "allungata" con tutte le colonne dei termini noti (come si fa, in un certo senso, per trovare l'inversa) ?
Per calcolare ad esempio l'inversa di una matrice, eseguendo una volta sola la riduzione della matrice, che richiede circa $\frac{2}{3}n^{3}$ operazioni. Se si vuole calcolare l'inversa di una matrice si devono risolvere $n$ sistemi lineari del tipo $Ax = e_i$ se $e_i$ è l'i-esimo elemento della base canonica. La soluzione di uno di questi sistemi fornisce l'i-esima colonna dell'inversa. In poche parole, per risparmiare risorse (si fa la riduzione una volta sola invece di n)!
"Moralizzatore":
Se si vuole calcolare l'inversa di una matrice si devono risolvere $n$ sistemi lineari ...
Sicuro? Io so che per trovare, per esempio, l'inversa della matrice che hai postato, ti basta ridurre con Gauss questa $((1,2,3,1,0,0),(3,4,6,0,1,0),(10,5,-3,0,0,1))$ e prendere le ultime tre colonne ...
Nel caso particolare, se fai caso, le due cose coincidono, ma in un caso generale come faresti? Nel senso: data la matrice dei coefficienti e diversi vettori dei termini noti, come risolvi tutti i sistemi riducendo la prima solo una volta?
Non ho capito bene cosa intendi ma quello che ho descritto non è un caso particolare ma un metodo (relativamente semplice) per calcolare l'inversa di una matrice (quando esiste, ovviamente).
Trovata l'inversa $A^(-1)$ della matrice $A$, per trovare la soluzione del sistema lineare $A\bar(x)=\bar(b)$ basta calcolare $\bar(x)=A^(-1)\bar(b)$
Quindi trovi l'inversa una volta sola (per esempio col metodo che ho descritto) e poi moltiplichi, in pratica i termini noti sono le soluzioni della matrice inversa.
Trovata l'inversa $A^(-1)$ della matrice $A$, per trovare la soluzione del sistema lineare $A\bar(x)=\bar(b)$ basta calcolare $\bar(x)=A^(-1)\bar(b)$
Quindi trovi l'inversa una volta sola (per esempio col metodo che ho descritto) e poi moltiplichi, in pratica i termini noti sono le soluzioni della matrice inversa.
L'idea che stavo cercando di farti passare è ad esempio questa:
Risolvi il sistema con matrice associata
\(\quad\begin{pmatrix} a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} &a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix}\quad\)
Poi risolvi (utilizzando il metodo di Gauss con pivoting totale)
\(\quad\begin{pmatrix} a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} &a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} b_1^{(1)} \\ b_2^{(1)} \\ b_3^{(1)} \end{pmatrix}\quad\)
E poi ancora
\(\quad\begin{pmatrix} a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} &a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} b_1^{(2)} \\ b_2^{(2)} \\ b_3^{(2)} \end{pmatrix}\quad\)
e via dicendo, cambiando soltanto il vettore dei termini noti, e mantenendo la matrice dei coefficienti. Quello dell'inversa era un esempio di un'idea generale!
PS: Sono riuscito a sbrogliare la situazione. Alla fine, senza comunque capire perché, mi sono accorto che basta riprodurre gli scambi di colonne sul vettore dei termini noti, nell'ordine inverso (dall'ultimo scambio al primo).
Ad esempio se ho scambiato nella riduzione le colonne $1$ con la $3$ e la $2$ con la $4$ (in ordine "cronologico") scambio la quarta soluzione con la seconda, poi sul nuovo vettore delle soluzioni, scambio la terza con la prima. Così arrivo all'ordine giusto!
Risolvi il sistema con matrice associata
\(\quad\begin{pmatrix} a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} &a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix}\quad\)
Poi risolvi (utilizzando il metodo di Gauss con pivoting totale)
\(\quad\begin{pmatrix} a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} &a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} b_1^{(1)} \\ b_2^{(1)} \\ b_3^{(1)} \end{pmatrix}\quad\)
E poi ancora
\(\quad\begin{pmatrix} a_{11} & a_{12} & a_{13} \\a_{21} & a_{22} &a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} b_1^{(2)} \\ b_2^{(2)} \\ b_3^{(2)} \end{pmatrix}\quad\)
e via dicendo, cambiando soltanto il vettore dei termini noti, e mantenendo la matrice dei coefficienti. Quello dell'inversa era un esempio di un'idea generale!
PS: Sono riuscito a sbrogliare la situazione. Alla fine, senza comunque capire perché, mi sono accorto che basta riprodurre gli scambi di colonne sul vettore dei termini noti, nell'ordine inverso (dall'ultimo scambio al primo).
Ad esempio se ho scambiato nella riduzione le colonne $1$ con la $3$ e la $2$ con la $4$ (in ordine "cronologico") scambio la quarta soluzione con la seconda, poi sul nuovo vettore delle soluzioni, scambio la terza con la prima. Così arrivo all'ordine giusto!
"Moralizzatore":
PS: Sono riuscito a sbrogliare la situazione. Alla fine, senza comunque capire perché, mi sono accorto che basta riprodurre gli scambi di colonne sul vettore dei termini noti, nell'ordine inverso (dall'ultimo scambio al primo).
Ad esempio se ho scambiato nella riduzione le colonne $1$ con la $3$ e la $2$ con la $4$ (in ordine "cronologico") scambio la quarta soluzione con la seconda, poi sul nuovo vettore delle soluzioni, scambio la terza con la prima. Così arrivo all'ordine giusto!
Perché se hai
$P_n*P_(n-1)*...*P_2*P_1*A=I $
$rArr A^(-1)=P_1^(-1)*P_2^(-1)*...*P_(n-1)^(-1)*P_n^(-1)*I qquad$[nota]Infatti: ($AB)^(-1)=B^(-1)A^(-1), qquad AA A,B in GL_n(RR)$[/nota]
$rArr A^(-1)=P_1^(-1)*P_2^(-1)*...*P_(n-1)^(-1)*P_n^(-1)*I qquad$[nota]Infatti: ($AB)^(-1)=B^(-1)A^(-1), qquad AA A,B in GL_n(RR)$[/nota]
$A, I, P in GL_n(RR)$ dove con $P$ si intendono le matrici elementari.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo