Salta al contenuto
Note per Studenti Esercizio - fattorizzazione LU di una matrice 3x3, sistema e determinante

Esercizio - fattorizzazione LU di una matrice 3x3, sistema e determinante

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 →, Eliminazione di GaussCon tre operazioni elementari sulle righe (scambio, moltiplicazione per uno scalare non nullo, somma di un multiplo di un'altra riga) ogni matrice si riduce a scala senza cambiare il rango; serve a calcolare ranghi, risolvere sistemi, trovare relazioni di dipendenza e matrici che riducono a scala.Eliminazione di Gauss →.

Testo. Sia A=(24−249−3−2−37).A=\begin{pmatrix}2&4&-2\\4&9&-3\\-2&-3&7\end{pmatrix}.

  1. Calcolare la fattorizzazione A=LUA=LU senza pivoting e verificarla.
  2. Risolvere Ax=bA\mathbf x=\mathbf b con b=(−6,−11,15)T\mathbf b=(-6,-11,15)^T.
  3. Risolvere con la stessa fattorizzazione Ax=cA\mathbf x=\mathbf c con c=(0,1,5)T\mathbf c=(0,1,5)^T e calcolare det⁡A\det A.
  4. Verificare con i minori principali di testa che la LU esiste e dire quante operazioni (≈\approx flop) si sono risparmiate nel punto 3.

Soluzione

1. Eliminazione. Passo 1, pivot a11=2a_{11}=2: l21=42=2l_{21}=\frac42=2, l31=−22=−1l_{31}=\frac{-2}2=-1.

  • Riga 2 −2⋅-2\cdot riga 1: (4−4, 9−8, −3−(−4))=(0,1,1)(4-4,\ 9-8,\ -3-(-4))=(0,1,1).
  • Riga 3 −(−1)⋅-(-1)\cdot riga 1 (cioè ++ riga 1): (−2+2, −3+4, 7−2)=(0,1,5)(-2+2,\ -3+4,\ 7-2)=(0,1,5).

Passo 2, pivot a22(2)=1a_{22}^{(2)}=1: l32=11=1l_{32}=\frac11=1. Riga 3 −1⋅-1\cdot riga 2: (0, 0, 5−1)=(0,0,4)(0,\ 0,\ 5-1)=(0,0,4). L=(100210−111),U=(24−2011004).L=\begin{pmatrix}1&0&0\\2&1&0\\-1&1&1\end{pmatrix},\qquad U=\begin{pmatrix}2&4&-2\\0&1&1\\0&0&4\end{pmatrix}. Verifica: riga 2 di LULU = 2⋅(2,4,−2)+1⋅(0,1,1)=(4,9,−3)2\cdot(2,4,-2)+1\cdot(0,1,1)=(4,9,-3) ✓; riga 3 = −1⋅(2,4,−2)+1⋅(0,1,1)+1⋅(0,0,4)=(−2, −4+1, 2+1+4)=(−2,−3,7)-1\cdot(2,4,-2)+1\cdot(0,1,1)+1\cdot(0,0,4)=(-2,\ -4+1,\ 2+1+4)=(-2,-3,7) ✓.

2. Soluzione. Avanti, Ly=bL\mathbf y=\mathbf b: y1=−6,y2=−11−2⋅(−6)=1,y3=15−(−1)(−6)−1⋅1=15−6−1=8.y_1=-6,\quad y_2=-11-2\cdot(-6)=1,\quad y_3=15-(-1)(-6)-1\cdot1=15-6-1=8 . Indietro, Ux=yU\mathbf x=\mathbf y: x3=84=2,x2=1−1⋅21=−1,x1=−6−4⋅(−1)−(−2)⋅22=−6+4+42=1.x_3=\frac84=2,\quad x_2=\frac{1-1\cdot2}1=-1,\quad x_1=\frac{-6-4\cdot(-1)-(-2)\cdot2}2=\frac{-6+4+4}2=1 . Soluzione x=(1,−1,2)T\mathbf x=(1,-1,2)^T. Controllo nella seconda equazione originale: 4⋅1+9⋅(−1)−3⋅2=4−9−6=−114\cdot1+9\cdot(-1)-3\cdot2=4-9-6=-11 ✓.

3. Altro termine noto e determinante. Non si rifà l'eliminazione: avanti y1=0y_1=0, y2=1−2⋅0=1y_2=1-2\cdot0=1, y3=5−(−1)⋅0−1⋅1=4y_3=5-(-1)\cdot0-1\cdot1=4; indietro x3=44=1x_3=\frac44=1, x2=1−1=0x_2=1-1=0, x1=0−4⋅0+2⋅12=1x_1=\frac{0-4\cdot0+2\cdot1}2=1. Soluzione x=(1,0,1)T\mathbf x=(1,0,1)^T (controllo: riga 1 2−2=02-2=0 ✓). det⁡A=det⁡L⋅det⁡U=1⋅(2⋅1⋅4)=8.\det A=\det L\cdot\det U=1\cdot(2\cdot1\cdot4)=8 .

4. Esistenza e costo. Minori di testa: det⁡A1=2≠0\det A_1=2\ne0, det⁡A2=2⋅9−4⋅4=2≠0\det A_2=2\cdot9-4\cdot4=2\ne0; la LU esiste. I pivot si riottengono come rapporti: u11=2u_{11}=2, u22=det⁡A2det⁡A1=22=1u_{22}=\frac{\det A_2}{\det A_1}=\frac22=1, u33=det⁡A3det⁡A2=82=4u_{33}=\frac{\det A_3}{\det A_2}=\frac82=4 ✓. Costo: la fattorizzazione richiede ≈23⋅33=18\approx\frac23\cdot3^3=18 flop, ogni coppia di sostituzioni 2⋅32=182\cdot3^2=18; per il sistema aggiuntivo si spendono ≈18\approx18 flop invece di 18+18=3618+18=36 rifacendo tutto (per n=1000n=1000 il rapporto sarebbe 2⋅1066,7⋅108≈0,3%\frac{2\cdot10^6}{6{,}7\cdot10^8}\approx0{,}3\%).

Osservazione: AA è simmetrica e i pivot 2,1,42,1,4 sono positivi, quindi A=LDLTA=LDL^T con D=diag⁡(2,1,4)D=\operatorname{diag}(2,1,4) e AA è definita positiva: ammette anche la fattorizzazione di Cholesky.

Risultati: LL, UU come sopra; x=(1,−1,2)T\mathbf x=(1,-1,2)^T per b\mathbf b e x=(1,0,1)T\mathbf x=(1,0,1)^T per c\mathbf c; det⁡A=8\mathbf{\det A=8}.

Errori tipici. Scrivere in LL il moltiplicatore col segno cambiato (−2-2 invece di 22); dimenticare di mettere 11 sulla diagonale di LL; non riusare LL e UU per il secondo termine noto.

Versione ripasso

(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 →)

A=(24−249−3−2−37)A=\begin{pmatrix}2&4&-2\\4&9&-3\\-2&-3&7\end{pmatrix}.

  • l21=2l_{21}=2, l31=−1l_{31}=-1: righe (0,1,1)(0,1,1) e (0,1,5)(0,1,5); l32=1l_{32}=1: (0,0,4)(0,0,4). L=(100210−111)L=\begin{pmatrix}1&0&0\\2&1&0\\-1&1&1\end{pmatrix}, U=(24−2011004)U=\begin{pmatrix}2&4&-2\\0&1&1\\0&0&4\end{pmatrix}.
  • b=(−6,−11,15)\mathbf b=(-6,-11,15): y=(−6,1,8)\mathbf y=(-6,1,8), x=(1,−1,2)\mathbf x=(1,-1,2). c=(0,1,5)\mathbf c=(0,1,5): y=(0,1,4)\mathbf y=(0,1,4), x=(1,0,1)\mathbf x=(1,0,1).
  • det⁡A=2⋅1⋅4=8\det A=2\cdot1\cdot4=8; minori di testa 2,2,82,2,8; u22=22u_{22}=\frac22, u33=82u_{33}=\frac82.
  • AA simmetrica con pivot 2,1,4>02,1,4>0: SPD, A=LDLTA=LDL^T.
  • Il secondo termine noto costa ≈18\approx18 flop invece di 3636.

Errori tipici: segno dei moltiplicatori; 11 sulla diagonale di LL; fattorizzare di nuovo per ogni b\mathbf b.

Teoria collegata