3.4.1 Fattorizzazione $A=LU$

Per convenienza computazionale si considera che la matrice $L$ sia rappresentata con gli elementi della diagonale tutti uguali a $1$ (rappresentazione di Doolittle). Il sistema che dobbiamo risolvere adesso ? il seguente :

$$\bgroup\color{darkgreen} \left\{ \begin{array}{ll} Ly = b \\ Rx = y \end{array} \right. \egroup$$

A questo punto potremmo chiederci se la fattorizzazione che cerchiamo esiste sempre: vorremmo stabilire se ? possibile trovarla in tempo finito, o addirittura potremmo chiederci se ? unica o ve ne di sono multiple. La risposta ci viene fornita dal seguente teorema:

Teorema 3.15   Sia $A$ la matrice dei coefficienti del sistema lineare $Ax=b$ e sia $\det (A) \neq 0$. Allora A ammette una ed una sola fattorizzazione LU sse $\det(A_k)\neq 0$ per ogni $k = 1,\ldots,n-1.$

DIMOSTRAZIONE

$(\Leftarrow)$

Per induzione su n :

Base

$n = 1$, la fattorizzazione ? ovvia, immediatamente abbiamo infatti $L = [1]$ , $U = [a_{11}]$

Ipotesi induttiva

La tesi vale per $n-1$

Passo induttivo

Si spezza la matrice $A$ in:

$$\begin{array}{cc} &\\ &\\ \overline{v}^T&\rightarrow \end... ...n{array}{cc} &\\ \leftarrow & \overline{d} \\ & \end{array}$$

dove con $\overline{v}^T$ si indica l'ultima riga, mentre con $\overline{d}$ l'ultima colonna (ad eccezione per entrambi di $\alpha$). Per ipotesi induttiva $A_{n-1}$ ha una fattorizzazione unica $L_{n-1} U_{n-1}$. Quindi suppongo

$$L=\left( \begin{array}{cc\vert c} L_{n-1}&&\overline{0}\\... ...\hline \stackrel{}{\overline{0}^T}&&\beta \end{array}\right)$$

Devo provare che $\overline{u}^T, \overline{w}$ e $\beta$ sono univocamente determinati. Deve valere che :

a) $L_{n-1}\overline{w} = \overline{d}$, ma questo ? vero poich? $L_{n-1}$ ha determinante diverso da zero, e quindi le soluzioni del sistema lineare sono uniche (e cio? $\overline{w}$).

b) $\overline{u}^TU_{n-1} = \overline{v}^T \Longrightarrow U_{n-1}^T\overline{u} = \overline{v}$, con $U_{n-1}^T$ che ha determinante diverso da zero e quindi, anche in questo caso, le soluzioni sono univocamente determinate ($\overline{u}$).

c) $\overline{u}^T\overline{w} + \beta = \alpha$ che conosco in quanto ho il valore di $\overline{u},\overline{w}$ e $\alpha$.

$(\Rightarrow)$

Sappiamo che:

$$\left(\begin{array}{c\vert c} A_k & A_{12} \\ \hline A_{21} & A_{22} \end{array}\right)$$

quindi per ipotesi $\exists !\; A=LU$ dunque

$$L=\left(\begin{array}{c\vert c} L_k & 0 \\ \hline L_{21} ... ...t c} U_k & U_{12} \\ \hline 0 & U_{22} \end{array}\right)$$

Visto che $A=LU$ allora è vero che $\det(A)=\det(L)\cdot \det(U)$, ma per costruzione $\det(L)=1$ quindi $\det(A)=\det(U)$. Il precedente teorema è valido anche per le ridotte di entrambe le matrici poiché il $\det(L_k)=1\; \forall k$. $\Box$

Illustriamo passo per passo come funziona l'algoritmo di fattorizzazione $A=LU$, che utilizzando il metodo di eliminazione di Gauss trasforma un generico sistema lineare in un sistema triangolare equivalente (sempre che questo sia possibile) in un numero di passi finito.
Indicheremo con $A^{(i)}$ la matrice dei coefficienti del sistema di equazioni all' $i$-esimo passo.
Inizialmente abbiamo

$$\bgroup\color{darkgreen} A^{(1)}=A \egroup$$

Vediamo come passare ad $A^{(2)}$:

$$\bgroup\color{darkgreen} A^{(2)}=L_1 \cdot A^{(1)} \egroup$$

dove $L_1$, matrice elementare di Gauss, è cos? definita

$$\bgroup\color{darkgreen} L_1=I-\overline{g}_1 \cdot \overline{e}_1^T\qquad in\; cui\; (a_{11}\neq 0) \egroup$$

$$\bgroup\color{darkgreen} \overline{g}_1=\left(\begin{array}{... ...nd{array}\right)\qquad \overline{e}_1^T=(1,0,\ldots,0) \egroup$$

infatti $\overline{e}_1^T$ è il primo vettore della base canonica, mentre $\overline{g}_1$ è il vettore di Gauss al primo passo.
Quindi:

$$\bgroup\color{darkgreen} L_1=\left(\begin{array}{ccccc} 1 &... ...}^{(1)} & \cdots & a_{nn}^{(1)}\\ \end{array}\right) \egroup$$

Segue che, in generale

$$\bgroup\color{darkgreen} A^{(k)}=\left(\begin{array}{cccccc}... ...k}^{(k)}& \cdots & a_{nn}^{(k)}\\ \end{array}\right) \egroup$$

Riassumendo:

$$A^{(1)} = A$$

$$A^{(2)} = L_1 A^{(1)}$$

$$A^{(3)} = L_2 L_1 A^{(1)}$$

$$\vdots$$

$$A^{(n)} = L_{n-1} \cdots L_1 A^{(1)}$$

dove le matrici $L_i$ sono triangolari inferiori invertibili, $1\le i \le n-1$. Inoltre $A^{(n)}$ è del tipo

$$\bgroup\color{darkgreen} A^{(n)}=\left(\begin{array}{cccc} ... ...\ 0 & \cdots &0& a_{nn}^{(n)}\\ \end{array}\right) \egroup$$

Possiamo anche scrivere che:

$$\bgroup\color{darkgreen} \underbrace{L_1^{-1} \cdot L_2^{-1} \cdots L_{n-1}^{-1}}_{L}\cdot U=A \egroup$$

Vediamo come ? fatta la matrice L.

Teorema 3.16   Per un generico intero $k$, vale l'uguaglianza $L_k^{-1}=(I+\overline{g}_k\overline{e}_k^T)$

DIMOSTRAZIONE Per definizione e poiché stiamo trattando matrici invertibili

$$I = L_k \cdot L_k^{-1}=$$

$$= (I-\overline{g}_k\overline{e}_k^T)\cdot (I+\overline{g}_k\overline{e}_k^T)=$$

$$= I-\overline{g}_k\overline{e}_k^T + \overline{g}_k\overline{e}_k^T - \overline{g}_k\overline{e}_k^T \cdot \overline{g}_k\overline{e}_k^T = I$$

infatti il prodotto $\overline{g}_k \underbrace{\overline{e}_k^T \cdot \overline{g}_k}_{y}\overline{e}_k^T=0$ poiché $y$ è uno scalare, in particolare $y=0$, dal momento che il $k$-esimo elemento di $\overline{g}_k=0$. $\Box$
Possiamo allora scrivere che :

$$\bgroup\color{darkgreen} L=(I+\overline{g}_1\overline{e}_1^T... ...2^T) \ldots(I+\overline{g}_{n-1}\overline{e}_{n-1}^T) \egroup$$

Consideriamo quindi il primo prodotto:

$$\bgroup\color{darkgreen} (I+\overline{g}_1\overline{e}_1^T)(... ...ne{g}_1\overline{e}_1^T\overline{g}_2\overline{e}_2^T \egroup$$

dove l'ultimo addendo è zero (si veda dimostrazione teorema precedente).
Quindi dopo $n-1$ prodotti abbiamo

$$\bgroup\color{darkgreen} I+\sum_{k=1}^{n-1}\overline{g}_k\ov... ...riptstyle{\mbox{parti significative di Gauss}}}\right) \egroup$$

Si ha dunque

$$A^{(1)}x = b^{(1)}$$

$$A^{(2)}x = b^{(2)}\qquad con \; b^{(2)}=L_1 b$$

$$\vdots \qquad \qquad \qquad \quad\ \vdots$$

$$A^{(k)}x = b^{(k)}\qquad con \; b^{(k)}=L_{k-1}\cdots L_1 b$$

$$\vdots \qquad \qquad \qquad \quad\ \vdots$$

$$A^{(n)}x = b^{(n)}\qquad con \; b^{(n)}=L_{n-1}\cdots L_1 b$$

Analizziamo adesso il costo computazionale, ricordando che al $k$-esimo passo

$$\bgroup\color{darkgreen} A^{(k)}=\left(\begin{array}{cccccc}... ...k}^{(k)}& \cdots & a_{nn}^{(k)}\\ \end{array}\right) \egroup$$

Vediamo quanto costa un passo della computazione, infatti , dove $L_k=I-\overline{g}_k \cdot \overline{e}_k^T$, cio?:

$$\bgroup\color{darkgreen} L_k=\left(\begin{array}{cccccc} 1 ... ...^{(k)}}{a_{kk}^{(k)}} } & & & 1\\ \end{array}\right) \egroup$$

Quindi

$$\bgroup\color{darkgreen} A^{(k+1)}=\left(\begin{array}{ccccc... ... 0 & \cdots & 0 & \vdots & & \\ \end{array}\right) \egroup$$

Il calcolo di $a_{ij}^{(k+1)}$ è dato da

$$a_{ij}^{(k+1)} = a_{ij}^{(k)}-\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}} \cdot a_{kj}^{(k)}= \qquad i,j=k+1,\ldots,n <tex2html_comment_mark>$$

$$= a_{ij}^{(k)}-l_{ik}^{(k+1)}\cdot a_{kj}^{(k)}$$

Segue che ad ogni passo eseguo $2(n-k)^2$ operazioni elementari, difatti la complessit? ?:

$$\bgroup\color{darkgreen} 2\sum_{j=1}^{n-1}j^2=\frac{2(n-1)n(2n-1)}{6}\cong \frac{2}{3}n^3 \egroup$$

Questo valore ? il medesimo anche per la complessit? delle altre fattorizzazioni che si basano sul metodo di eliminazione di Gauss, come ad esempio $A=LDL^T$ o $PA=LU$. Si noti che nell'ultimo caso il numero di flops da eseguire ad ogni passo ? superiore poich? deve essere scambiato un numero di elementi pari a $2(n-i)$.
La fattorizzazione $LU$ è sempre possibile per due categorie di matrici:

1. Matrici con diagonale dominante: cioé quelle matrici in cui ogni elemento della diagonale è maggiore in modulo alla somma dei moduli degli elementi della colonna a cui tale elemento appartiene, cioé
   
   $$\vert a_{ii}\vert> \sum_{j=1}^{n}\vert a_{ji}\vert \quad con \; j\neq i \;\forall i = 1,\ldots,n$$
   
   

2. Matrici simmetriche e definite positive, delle quali abbiamo già mostrato le propriet?.

I seguenti teoremi dimostrano rispettivamente le affermazioni precedenti:

Teorema 3.17   Se una matrice $A$ è diagonale dominante allora $A$ è non singolare

DIMOSTRAZIONE:
Si suppone che $A$ sia singolare per assurdo. Allora esiste un vettore $\overline{x}\in \mathbb{R}^n$ non nullo tale che $A\overline{x}=\overline{0}$. Sia $x_i$ la componente di tale vettore di massimo modulo, cioé:

$$\bgroup\color{darkgreen} \vert x_i\vert\geq\vert x_j\vert\quad \forall j\neq i \egroup$$

Avremo dunque che $x_i\neq 0$.
Consideriamo la $i$-esima riga:

$$\bgroup\color{darkgreen} \sum_{j=1}^{n}a_{ij}x_{j}=0 \rightarrow a_{ii}x_{i}+\sum_{j\neq i}a_{ij}x_{j}=0 \egroup$$

quindi:

$$\bgroup\color{darkgreen} a_{ii}x_i=-\sum_{j\neq i}a_{ij}x_{j} \rightarrow \egroup$$

$$\bgroup\color{darkgreen} \vert a_{ii}\vert=\left\vert\sum_{j... ...\vert}_{\leq 1}\leq \sum_{j\neq i}\vert a_{ij}\vert \egroup$$

ma questo è assurdo poiché per ipotesi era a diagonale dominante $\Box$

Teorema 3.18   Sia $A$ una matrice definita positiva, allora $A$ é non singolare

DIMOSTRAZIONE: Supponiamo per assurdo che esista un vettore $\overline{x}\in \mathbb{R}^n$ tale che $A\overline{x}=\overline{0}$ (con $\overline{x}$ non nullo). Pre-moltiplicando per $\overline{x}^T$ ottengo

$$\bgroup\color{darkgreen} \overline{x}^T A\overline{x}=0 \egroup$$

ma questo è assurdo perché per ipotesi $A$ è definita positiva. $\Box$ [caption=Metodo di triangolarizzazione di Gauss, label=codici/gauss.m, showstringspaces=false, frame=tRBl, extendedchars=true, basicstyle=pcrm, numbers=left, commentstyle= , frameround=fttt, stepnumber=1, numberstyle=, keywordstyle= , language=Matlab]codici/gauss.m

Esempi di gauss.m da pag.

[caption=Risolvi sistema con fattorizzazione $A=LU$, label=codici/risolvi_ALU.m, showstringspaces=false, frame=tRBl, extendedchars=true, basicstyle=pcrm, numbers=left, commentstyle= , frameround=fttt, stepnumber=1, numberstyle=, keywordstyle= , language=Matlab]codici/risolvi_ALU.m

Esempi di risolvi_ALU.m da pag.