Requisiti algebrici della fattorizzazione

Prestiamo attenzione ai requisiti algebrici di questa fattorizzazione. Scriviamo la matrice A come

$$A=\left( \begin{array}{c\vert c} A_i & B_i \\ \hline C_i ... ... & \vdots \\ a_{i1} & \cdots & a_{ii} \end{array} \right)$$

i-esima sottomatrice principale di A.

Adesso possiamo scrivere

$$A=LU$$

come

$$\left( \begin{array}{c\vert c} A_i & B_i \\ \hline C_i & ... ...iH_i \\ \hline F_iU_i & F_iH_i + G_iH_i \end{array} \right)$$

e questo significa che $A_i=l_iU_i \quad \forall i=1,\cdots,n$ con $l_i$ matrice triangolare inferiore a diagonale unitaria e $U_i$ matrice triangolare superiore; definiamo ora il minore principale di ordine $i$ come il determinante della sottomatrice principale di ordine $i$, allora

$$det(A_i)=det(l_iU_i)=det(l_i)det(U_i)=det(U_i)$$

$$\forall i \quad det(A_i)=det(U_i)=\prod_{j=1}^{i}a_{jj}^{(j)}... ...i-1}a_{jj}^{(j)} \right) a_{ii}^{(i)}=det(A_{i-1})a_{ii}^{(i)}$$

Quanto appena scritto ci consente un'utile interpretazione: la condizione $det(A_{i-1}) \neq 0$ ci consente di arrivare fino al passo i-esimo, mentre $a_{ii}^{(i)} \neq 0$ ci consente di eseguire proprio il passo i-esimo.

La fattorizzazione $LU$ è quindi definita se e solo se tutti i minori principali sono non nulli, e questa è una condizione molto forte: il problema originario $Ax=b$ è ben posto solo se il minore principale di ordine massimo è non nullo (la matrice dei coefficienti è non singolare). Questo vincolo può essere formulato sotto forma di teorema che sancisce la condizione necessaria e sufficiente affinchè la fattorizzazione esista:

Teorema 12   $A$ è fattorizzabile $LU$ se e solo se tutti i minori principali di $A$ sono non nulli

Guardiamo adesso come è fatta la matrice $L$. Dall'applicazione dell'algoritmo precedente quello che otteniamo è

$$L_{n-1}L_{n-2} \cdots \cdots \cdot L_2L_1=L^{-1}$$

ma naturalmente eseguire esplicitamente il prodotto delle $n-1$ matrici per poi calcolare l'inversa, ed ottenere così $L$, risulta eccessivamente complesso; ricordandoci le proprietà delle matrici inverse otteniamo che

$$L={(L_{n-1} \cdots \cdots \cdot L_2L_1)}^{-1}=L_1^{-1} L_2^{-1} \cdots \cdots L_{n-1}^{-1}$$

decisamente più semplice da ottenere, vediamone le ragioni:

$$L_i^{-1}=I+g_ie_i^T$$

e quindi otteniamo

$$\begin{array}{lcl} L & = & (I+g_1e_1^T) \cdots (I+g_{n-1}e... ...ma }\\ \\ & & ( g_ie_i^Tg_je_j^T \quad j>i) \end{array}$$

ma $e_i^Tg_j=0$ per $j>i$ e quindi quel ``qualcosa'' si riduce a zero, perciò la matrice $L$ che cerchiamo è

$$L=I+g_1e_1^T+\cdots+g_{n-1}e_{n-1}^T$$

$$L= \left( \begin{array}{cccccccc} 1 & & & & & & & 0 \\ &... ...ni}^{(i)}}{a_{ii}^{(i)}} & & \ast & & 1 \end{array} \right)$$

dove in colonna i-esima troviamo l'i-esimo vettore elementare di Gauss.

Questo metodo è detto metodo di eliminazione di Gauss visto l'utilizzo delle matrici e dei vettori elementari dello stesso Gauss