Esercizio - pivoting parziale su una matrice 3x3 con scambio di righe

Teoria: Fattorizzazione LU, pivoting e CholeskyRisolvere $A\mathbf x=\mathbf b$ con Gauss equivale a fattorizzare $A=LU$ ($L$ triangolare inferiore con $1$ sulla diagonale e i moltiplicatori $l_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}$ sotto la diagonale, $U$ la matrice a scala finale) e poi risolvere $L\mathbf y=\mathbf b$ (in avanti) e $U\mathbf x=\mathbf y$ (all'indietro). Esiste (ed è unica) se i minori principali di testa $\det A_k$, $k<n$, sono $\ne0$. Costo $\frac23n^3$ flop per la fattorizzazione, $2n^2$ per ogni termine noto; $\det A=\prod u_{kk}$. Con un pivot piccolo l'algoritmo è instabile: il pivoting parziale (scambio di righe che porta in posizione di pivot l'elemento di modulo massimo della colonna) dà $PA=LU$ con $|l_{ik}|\le1$ ed esiste per ogni $A$ invertibile. Se $A$ è simmetrica definita positiva esiste $A=LL^T$ (Cholesky), con $l_{jj}=\sqrt{a_{jj}-\sum_{k<j}l_{jk}^2}$ e $l_{ij}=\frac{a_{ij}-\sum_{k<j}l_{ik}l_{jk}}{l_{jj}}$; costo $\frac13n^3$, senza pivoting.Fattorizzazione LU, pivoting e Cholesky →.

Testo.

1. Per $A=\begin{pmatrix}1&3&2\\4&2&1\\2&2&3\end{pmatrix}$ e $\mathbf b=(5,7,3)^T$ calcolare con il pivoting parziale la fattorizzazione $PA=LU$, risolvere $A\mathbf x=\mathbf b$ e calcolare $\det A$.
2. Dire cosa succederebbe senza pivoting (moltiplicatori).
3. Per $C=\begin{pmatrix}0&1&2\\1&1&1\\2&1&3\end{pmatrix}$ mostrare che la LU senza scambi non esiste e calcolare $PC=LU$ con il pivoting parziale. Calcolare $\det C$.

Soluzione

1. Passo 1. La colonna 1 è $(1,4,2)^T$: il massimo in modulo è $4$ (riga 2). Si scambiano le righe 1 e 2: $$\begin{pmatrix}4&2&1\\1&3&2\\2&2&3\end{pmatrix},\qquad l_{21}=\frac14,\quad l_{31}=\frac24=\frac12 .$$ Riga 2 $-\frac14$ riga 1: $(0,\ 3-\frac12,\ 2-\frac14)=(0,\ 2{,}5,\ 1{,}75)$. Riga 3 $-\frac12$ riga 1: $(0,\ 2-1,\ 3-\frac12)=(0,\ 1,\ 2{,}5)$.

Passo 2. Nella colonna 2 (dalla riga 2 in giù) si confrontano $2{,}5$ e $1$: vince $2{,}5$ (già in posizione), nessuno scambio. $l_{32}=\frac1{2{,}5}=0{,}4$; riga 3 $-0{,}4$ riga 2: $(0,0,\ 2{,}5-0{,}4\cdot1{,}75)=(0,0,\ 2{,}5-0{,}7)=(0,0,1{,}8)$. $$P=\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix},\quad L=\begin{pmatrix}1&0&0\\0{,}25&1&0\\0{,}5&0{,}4&1\end{pmatrix},\quad U=\begin{pmatrix}4&2&1\\0&2{,}5&1{,}75\\0&0&1{,}8\end{pmatrix}.$$ Verifica: riga 2 di $LU$ = $0{,}25\cdot(4,2,1)+(0,2{,}5,1{,}75)=(1,\ 0{,}5+2{,}5,\ 0{,}25+1{,}75)=(1,3,2)$ = riga 2 di $PA$ ✓ (cioè la riga 1 di $A$); riga 3 = $0{,}5\cdot(4,2,1)+0{,}4\cdot(0,2{,}5,1{,}75)+(0,0,1{,}8)=(2,\ 1+1,\ 0{,}5+0{,}7+1{,}8)=(2,2,3)$ ✓.

Sistema. $P\mathbf b=(7,5,3)^T$. Avanti: $y_1=7$, $y_2=5-0{,}25\cdot7=3{,}25$, $y_3=3-0{,}5\cdot7-0{,}4\cdot3{,}25=3-3{,}5-1{,}3=-1{,}8$. Indietro: $x_3=\frac{-1{,}8}{1{,}8}=-1$, $x_2=\frac{3{,}25-1{,}75\cdot(-1)}{2{,}5}=\frac{5}{2{,}5}=2$, $x_1=\frac{7-2\cdot2-1\cdot(-1)}4=1$. Soluzione $\mathbf x=(1,2,-1)^T$.

Determinante. Un solo scambio: $\det A=(-1)^1\cdot4\cdot2{,}5\cdot1{,}8=-18$. Controllo con la formula di Sarrus: $1(6-2)-3(12-2)+2(8-4)=4-30+8=-18$ ✓.

2. Senza pivoting il pivot sarebbe $1$ e i moltiplicatori $l_{21}=4$, $l_{31}=2$: l'algoritmo funziona (nessun pivot nullo), ma il nuovo elemento $a_{22}^{(2)}=2-4\cdot3=-10$ è più grande in modulo di tutti i dati di partenza (il massimo è $4$): in generale moltiplicatori $>1$ amplificano gli errori di arrotondamento. Col pivoting $|l_{ik}|\le1$ ($0{,}25;\,0{,}5;\,0{,}4$) e gli elementi di $U$ restano dello stesso ordine di grandezza di $A$.

3. Pivot nullo. In $C$ è $c_{11}=0$: il moltiplicatore $\frac{c_{21}}{c_{11}}$ non esiste, la LU senza scambi è impossibile (pur essendo $\det C\ne0$, come si vede sotto).

• Passo 1: massimo della colonna $(0,1,2)^T$ è $2$ (riga 3): si scambiano le righe 1 e 3. Ordine delle righe originali: $(3,2,1)$. Matrice: $\begin{pmatrix}2&1&3\\1&1&1\\0&1&2\end{pmatrix}$, $l_{21}=\frac12$, $l_{31}=0$. Riga 2 $-\frac12$ riga 1: $(0,\ \frac12,\ -\frac12)$; riga 3 invariata $(0,1,2)$.
• Passo 2: fra $\frac12$ (riga 2) e $1$ (riga 3) il massimo è $1$: si scambiano le righe 2 e 3, insieme ai moltiplicatori già calcolati ($l_{21}=\frac12\leftrightarrow l_{31}=0$). Ordine originale delle righe: $(3,1,2)$. Ora $l_{21}=0$, $l_{31}=\frac12$, $l_{32}=\frac{1/2}1=\frac12$. Riga 3 $-\frac12$ riga 2: $(0,0,\ -\frac12-\frac12\cdot2)=(0,0,-\frac32)$. $$P=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix},\quad L=\begin{pmatrix}1&0&0\\0&1&0\\\frac12&\frac12&1\end{pmatrix},\quad U=\begin{pmatrix}2&1&3\\0&1&2\\0&0&-\frac32\end{pmatrix}.$$ Verifica: $PC$ ha righe (riga 3, riga 1, riga 2 di $C$) $=(2,1,3),(0,1,2),(1,1,1)$; riga 3 di $LU$ = $\frac12(2,1,3)+\frac12(0,1,2)+(0,0,-\frac32)=(1,\ \frac12+\frac12,\ \frac32+1-\frac32)=(1,1,1)$ ✓. Determinante: $P$ corrisponde alla permutazione $(3,1,2)$, un ciclo di 3 elementi cioè due scambi ($s=2$): $\det C=(+1)\cdot2\cdot1\cdot(-\frac32)=-3$. Controllo diretto: $0(3-1)-1(3-2)+2(1-2)=-1-2=-3$ ✓.

Risultati: $\mathbf x=(1,2,-1)^T$ e $\det A=-18$; per $C$: $\det C=-3$, con due scambi.

Errori tipici. Scambiare le righe di $A$ ma non quelle già calcolate di $L$ (nel passo 2 di $C$); dimenticare $(-1)^s$ nel determinante; applicare $L\mathbf y=\mathbf b$ invece di $L\mathbf y=P\mathbf b$.