next up previous contents
Next: Il simulatore Up: Aspetti matematici Previous: Sostituzione in avanti e   Indice

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

$\displaystyle \vert a_{i,i}\vert > \sum_{\substack{ j = 1\\ j \not = i}}^n \vert a_{i,j}\vert$   $\displaystyle \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

$\displaystyle 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

$\displaystyle L_k = \begin{pmatrix}L_{k-1} & \boldsymbol{0}\\ \boldsymbol{u}^T & 1 \end{pmatrix},$   $\displaystyle 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

$\displaystyle 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

$\displaystyle L_{k-1} \boldsymbol{v} = \boldsymbol{d},$    
$\displaystyle U_{k-1}^T \boldsymbol{u} = \boldsymbol{c},$    
$\displaystyle \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

$\displaystyle \sum_{j=1 , j \not = i}^n \vert a_{i,j}\vert \leq$      
$\displaystyle \vert- \lambda_y\vert +\vert- \lambda_x\vert+\vert- \lambda_x\vert+\vert-\lambda_y\vert =$    
$\displaystyle \lambda_y + \lambda_x + \lambda_x + \lambda_y <$    
$\displaystyle 2 + \lambda_x + \lambda_y =$ $\displaystyle \; 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$

next up previous contents
Next: Il simulatore Up: Aspetti matematici Previous: Sostituzione in avanti e   Indice
2006-02-17