next up previous contents
Next: Analisi all'indietro Up: Backward analysis Previous: Il metodo di eliminazione   Indice

Fattorizzazione con l'eliminazione di Gauss

Siano $A \in \textbf{R}^{n \times n}$, con det$(A)\neq 0$ e det $(A_k) \neq 0, \forall k=1, \ldots, n-1$. Consideriamo le matrici elementari $L_{ij}$ cosí definite:

\begin{displaymath}
\mbox{\tiny [GAUSS1]}\hspace{5mm}L_{ij}=I+m_{ij}e_ie_j^T,i>j
\end{displaymath} (3.7)

dove $I$ é ;a matrice identitá di dimensione $n\times n$, mentre $e_i$ e $e_j$ sono rispettivamente l'$i$-esimo ed il $j$-esimo vettore canonico. Quindi, $L_{21}$ sará

\begin{displaymath}L_{21}=\pmatrix{1 & 0 & \ldots & \ldots & 0 \cr
m_{21} & 1 &...
...\vdots & \ddots & \ddots & \vdots \cr
0 & 0 & \ldots & 0 & 1}\end{displaymath}

Moltiplicandola ora per $A$ abbiamo che:

\begin{displaymath}L_{21}A=\pmatrix{a_{11} & a_{12} & \ldots & \ldots & a_{1n} \...
...ots & \vdots \cr
a_{n1} & a_{n2} & \ldots & a_{nn-1} & a_{nn}}\end{displaymath}

Segliendo oppurtunamtamente $m_{21}$ possiamo azzerare il primo elemento della seconda riga di $AL_21$. Scegliamo quindi

\begin{displaymath}m_{21}=-\frac{a_{21}}{a_{11}}\end{displaymath}

ed indichiamo con $a_{2j}^{(2)}$ gli elementi che sono stati modificati dal prodotto $L_{21}A$. Piú precisamente avremo

\begin{displaymath}a_{2j}^{(2)}=a_{2j}+m_{21}a_{1j}=a_{2j}-\frac{a_{21}}{a_{11}}.\end{displaymath}

Similmente possiamo costruire scegliendo $m_{31}$ con lo stesso criterio di $m_{21}$, ovvero

\begin{displaymath}m_{31}=-\frac{a_{31}}{a_{11}}.\end{displaymath}

Svolgendo poi il prodotto $L_{31}(L_{21}A)$ otteniamo cosí

\begin{displaymath}L_{31}(L_{21}A)=\pmatrix{a_{11} & a_{12} & \ldots & \ldots & ...
...ots \cr
a_{n1} & a_{n2} & a_{n3} & \ldots & a_{nn-1} & a_{nn}}\end{displaymath}

con

\begin{displaymath}a_{3j}^{(2)}=a_{3j}-a_{1j}\frac{a_{31}}{a_{11}}.\end{displaymath}

Occorre ora continuare fino a costruire $L_{n1}$, ed avremo azzerato la prima colonna. Quindi,

\begin{displaymath}A^{(2)}=\pmatrix{a_{11} & a_{12} & \ldots & \ldots & a_{1n} \...
...cr
0 & a^{(2)}_{n2} & \ldots & a^{(2)}_{nn-1} & a^{(2)}_{nn} }\end{displaymath}

con

\begin{displaymath}a^{(2)}_ij=a_{ij}-a_{1j}\frac{a_{i1}}{a_{11}}.\end{displaymath}

Sia ora $L1$ il prodotto di tutte le matrici create $L_{i1}$. Quindi:

\begin{displaymath}L_{1}=\pmatrix{1 & 0 & \ldots & \ldots & 0 \cr
m_{21} & 1 & ...
...s & \ddots & \ddots & \vdots \cr
m_{n1} & 0 & \ldots & 0 & 1}\end{displaymath}

e


\begin{displaymath}L_{1}^{-1}=\pmatrix{1 & 0 & \ldots & \ldots & 0 \cr
-m_{21} ...
...& \ddots & \ddots & \vdots \cr
-m_{n1} & 0 & \ldots & 0 & 1}.\end{displaymath}

Per ottenere una matrice triangolare superiore dobbiamo continuare il procedimento per tutte le colonne, ottenendo cosí la succession $L_1L_2, \ldots,L_{n-1}$

\begin{displaymath}L_{n-1}L_{n-2}\ldots L_{1}A=A^{(n)}=\pmatrix{ a_{11} & a_{12}...
...ots & a^{(n-1)}_{n-1n} \cr
0 & 0 & \ldots & 0 & a^{(n)}_{nn} }\end{displaymath}

ed abbiamo finito! Ponendo ora $R=A_n$ e $L^{-1}=L_{n-1}L_{n-2}\ldots L_1$ possiamo scrivere che $A=LR$ e quindi riolvere il sistema $Ax=b$ equivale a risolvere il sistema
\begin{displaymath}
\mbox{\tiny [GAUSS2]}\hspace{5mm}\left\{
\begin{array}{lc}
Ly=b \cr
Ux=y
\end{array} \right.
\end{displaymath} (3.8)

Il costo totale della fattorizzazione $LR$ eseguita con il metodo di eliminazione di Gauss equivale ad .
next up previous contents
Next: Analisi all'indietro Up: Backward analysis Previous: Il metodo di eliminazione   Indice
2002-06-26