Esistenza delle soluzioni e fattorizzabilità

Si è precedentemente ipotizzato che la matrice $A$ si possa sempre scomporre in due matrici $L$ ed $U$. Questo non è in generale possibile per tutte le matrici. Mostreremo di seguito che la matrice dei coefficienti $A$ utilizzata nell' applicazione del metodo implicito rispetta delle condizioni grazie alle quali è possibile applicare il metodo di Gauss. I primi tre teoremi presentati in questa sezione sono stati estratti dal testo `` Metodi numerici per l' algebra lineare'' di Bini, Capovani e Menchi. Il teorema ci garantisce che è i sistemi ottenuti dalla fattorizzazione LU ammettono una soluzione.

Una matrice $A$ si dice non singolare se esiste una matrice $A^{-1}$ tale che $A^{-1} A = A A^{-1} = Id$ oppure analogamente se il suo determinante è diverso da zero ( $Det(A) \not = 0$.) Data una matrice $A \in \mathbb{R}^{n \times n}$, una sottomatrice principale di testa di ordine $k \leq n$ di $A$ è una matrice $k \times k$ formata dagli elementi $a_{i,j}$, $i,j = 1, \dots, k$.

Teorema 2.5.1   Se $A$ è una matrice a predominanza diagonale stretta per righe, cioè vale che

$$\vert a_{i,i}\vert > \sum_{\substack{ j = 1\\ j \not = i}}^n \vert a_{i,j}\vert \forall i = 1,\dots,n$$

allora $A$ è non singolare.

Dimostrazione. [Dimostrazione.] Se $A$ è a predominanza diagonale in senso stretto allora, dal primo teorema di Gerschgorin [14], risulta che i cerchi di Gerschgorin (cerchi nel piano complesso di centro centro $a_{i,i}$ e raggio $\sum_{\substack{ j = 1 \\ j \not = i}}^n \vert a_{i,j}\vert$) avendo raggio minore della distanza del centro dall' origine del piano complesso non possono includere l' origine, quindi $A$ è non singolare. $\qedsymbol$

Se $A$ è una matrice a predominanza diagonale stretta lo saranno anche tutte le sue sottomatrici principali di testa e quindi, applicando il teorema precedente, saranno anch' esse non singolari.

Teorema 2.5.2   Sia $A$ una matrice di ordine $n$ e siano $A_k$ le sue sottomatrici principali di testa di ordine $k$. Se $A_k$ è non singolare per $k = 1, \dots, n-1$, allora esiste ed è unica la fattorizzazione LU di $A$.

Dimostrazione. [Dimostrazione.] Si procede per induzione. Se $n = 1$, $A_1 = [a_{1,1}]$ e quindi si ha $L = [1]$ e $U = [a_{1,1}]$, univocamente. Se $n = k > 1$, la matrice $A_k$ può essere partizionata nel modo seguente

$$A_k = \begin{pmatrix}A_{k-1} & \boldsymbol{d}\\ \boldsymbol{c}^T & \alpha \end{pmatrix}$$

In cui $A_{k-1} = L_{k-1}U_{k-1}$, con $L_{k-1}$ matrice triangolare inferiore con elementi principali uguali ad $1$ e $U_{k-1}$ triangolare superiore. Posto

$$L_k = \begin{pmatrix}L_{k-1} & \boldsymbol{0}\\ \boldsymbol{u}^T & 1 \end{pmatrix}, U_k = \begin{pmatrix}U_{k-1} & \boldsymbol{v}\\ \boldsymbol{0}^T & \beta \end{pmatrix},$$

occorre determinare $\boldsymbol{u}$, $\boldsymbol{v}$ e $\beta$ in modo che $A_k = L_k U_k$. Poiché risulta

$$L_k U_k = \begin{pmatrix}L_{k-1} U_{k-1} & L_{k-1} \boldsymbol{v}\\ \boldsymbol{u}^T U_{k-1} & \boldsymbol{u}^T \boldsymbol{v}+\beta \end{pmatrix},$$

si ha che la relazione $A_k = L_k U_k$ è verificata se e solo se

$$L_{k-1} \boldsymbol{v} = \boldsymbol{d},$$

$$U_{k-1}^T \boldsymbol{u} = \boldsymbol{c},$$

$$\boldsymbol{u}^T \boldsymbol{v} + \beta = \alpha .$$

I vettori $\boldsymbol{u}$ e $\boldsymbol{v}$ risultano determinati univocamente dalle prime due relazioni, poiché $Det(L_{k-1}) = 1$ e $Det(U_{k-1}) = Det (A_{k-1}) \not = 0$ in quanto $A_{k-1}$ è non singolare. Dalla terza relazione si ricava univocamente $\beta = \alpha - \boldsymbol{u}^T \boldsymbol{v}$. $\qedsymbol$

Teorema 2.5.3   Se esiste una fattorizzazione LU di $A$ allora il metodo di Gauss è applicabile.

La nostra matrice $A$, che ricordiamo essere $A = 2\, Id +(- B')$, ha predominanza diagonale stretta, infatti $\forall i = 1,\dots,n$ si ha

$$\sum_{j=1 , j \not = i}^n \vert a_{i,j}\vert \leq$$

$$\vert- \lambda_y\vert +\vert- \lambda_x\vert+\vert- \lambda_x\vert+\vert-\lambda_y\vert =$$

$$\lambda_y + \lambda_x + \lambda_x + \lambda_y <$$

$$2 + \lambda_x + \lambda_y = \; a_{i,i}$$

Teorema 2.5.4   Se A è fattorizzabile LU allora i sistemi Ly = b ed Ux = y ammettono entrambi una soluzione.

Dimostrazione. [Dimostrazione.] Sia $A$ una matrice quadrata e siano $L$ ed $U$ due matrici tali che $A = LU$ si ha che $Det(A) = Det(LU) = Det(L) Det(U)$. Dato che $L$ è triangolare inferiore unitaria il suo determinante è uno ( $Det(L) = 1$). Si ha quindi $Det(U) = Det(A) \not = 0$ allora sia $L$, sia $U$ sono non singolari quindi i sistemi ammettono una soluzione. $\qedsymbol$