Fattorizzazione $A=LDL^T$

Sappiamo che se $A$ è una matrice simmetrica e definita positiva allora $A$ è fattorizzabile $LU$. Ciò che ci proponiamo adesso è scrivere $U$ come $D\hat{U}$ con $D$ matrice diagonale

$$D= \left( \begin{array}{ccc} u_{11} & & 0 \\ & \ddots &... ... 0 & & u_{nn} \\ \end{array} \right) \qquad d^i=u_{ii}e_i^T$$

e quindi $\hat{U}$ risulta essere la matrice $U$ di partenza scalata per gli elementi $u_{11},u_{22}, \cdots$, dove per scalata intendiamo che i suoi fattori di scala sono gli $u_{ii}$. Posto $U=D\hat{U}$, per la prima riga si ha

$$\begin{array}{lcl} (u_{11} \cdots u_{1n}) & = & u_{11}(e_1... ... & = & u_{11}(\hat{u}_{11} \cdots \hat{u}_{1n}) \end{array}$$

ed uguagliando componente per componente otteniamo

$$\begin{array}{l} \hat{u}_{11}=1 \\ \\ \hat{u}_{1j}=\frac{u_{1j}}{u_{11}} \end{array}\mbox{.}$$

Questo risultato è valido per ogni riga, perciò la matrice $\hat{U}$ avrà elementi diagonali pari ad uno

$$\hat{U}= \left( \begin{array}{ccc} 1 & & \ast \\ & \ddots & \\ 0 & & 1 \end{array} \right)$$

ed è una matrice triangolare superiore a diagonale unitaria. L'operazione appena eseguita è lecita solo se $u_{ii} \neq 0$, ma ciò è garantito dalla possibilità di fattorizzazione $LU$.

$$A=LU=LD\hat{U}$$

ricordandosi che $A$ è simmetrica

$$A=A^T=(LD\hat{U})^T={\hat{U}}^TDL^T$$

ma $DL^T$ che forma ha? E' una matrice triangolare superiore con diagonale $u_{ii}$. Unendo le due espressioni sopra otteniamo

$$LD\hat{U}={\hat{U}}^TDL^T \qquad \Longleftrightarrow \qquad L={\hat{U}}^T, \quad \hat{U}=L^T\mbox{.}$$

Perciò se $A$ è simmetrica definita positiva conviene cercare una fattorizzazione nella forma $LDL^T$; la matrice $U$ non ci serve, necessitiamo solo della sua diagonale e di $L$.

Quello che ci proponiamo di fare è riorganizzare i passi della fattorizzazione $LU$ senza calcolare $U$ e supporremo di avere a disposizione solo la porzione triangolare inferiore di $A$, in modo che

$$A=(a_{ij}) \quad \mbox{noti per } j \leq i \mbox{.}$$

Sapendo che $j \leq i$

$$a_{ij}=e_i^TAe_j$$

e dal momento che cerchiamo la fattorizzazione $LDL^T$, che sappiamo esistere, possiamo scrivere:

$$\begin{eqnarray*} a_{ij} & = & e_i^TLDL^Te_j = (e_i^TL)D(L^Te_j) \\ a_{ij} & ... ..._{ik}l_{jk}d_k \\ a_{ij} & = & \sum_{k=1}^{j} l_{ik}l_{jk}d_k \end{eqnarray*}$$

$$\forall j\leq i \quad a_{ij}=\sum_{k=1}^{j} l_{ik}l_{jk}d_k=... ...=1}^{j-1} l_{ik}l_{jk}d_k + l_{ij}\underbrace{l_{jj}}_{1}d_j$$

Si presentano dunque due casi:

$i=j$ $\rightarrow$ $d_j=a_{jj}-\sum_{k=1}^{j-1} {(l_{jk})}^2d_k \qquad (l_{jj}=1)$

$i=j+1 \cdots n$ $\rightarrow$ $l_{ij}=\frac{a_{ij}-\sum_{k=1}^{j-1} l_{ik}l_{jk}d_k}{d_j} \qquad d_j \neq 0$

Quindi, durante il primo passo viene calcolato $d_1$ e poi tutta la prima colonna di $L$, e poi l'algoritmo procede nello stesso modo.