6.1.2 La factorización LU

Next: 6.1.3 Eliminación gaussiana básica Up: 6.1 Métodos de resolución Previous: 6.1.1 Sistemas fáciles de

6.1.2 La factorización LU

Supongamos que A se puede factorizar como el producto de una matriz triangular inferior L con una matriz triangular superior U:

A = LU

(51)

En este caso, el sistema de ecuaciones dado por (44) podría representarse en la forma:

LUx=b

(52)

Si denominamos z a la matriz columna de n filas resultado del producto de las matrices Ux, tenemos que la ecuación (52) se puede reescribir del siguiente modo:

Lz=b

(53)

A partir de las ecuaciones (52) y (53), es posible plantear un algoritmo para resolver el sistema de ecuaciones empleando dos etapas:

Primero obtenemos z aplicando el algoritmo de sustitución progresiva en la ecuación (53).
Posteriormente obtenemos los valores de x aplicando el algoritmo de sustitución regresiva a la ecuación

Ux = z

El análisis anterior nos muestra lo fácil que es resolver estos dos sistemas de ecuaciones triangulares y lo útil que resultaría disponer de un método que nos permitiera llevar a cabo la factorización A=LU. Si disponemos de una matriz A de $n \times n$ , estamos interesados en encontrar aquellas matrices:

$\begin{displaymath}\begin{array}{ll} L = \left( \begin{array}{ccccc} l_{11} &... ... 0 & 0 & 0 & \cdots & u_{nn} \end{array} \right) \end{array}\end{displaymath}$

tales que cumplan la ecuación (51). Cuando esto es posible, decimos que A tiene una descomposición LU. Se puede ver que las ecuación anterior no determina de forma única a Ly a U. De hecho, para cada i podemos asignar un valor distinto de cero a l_ii o u_ii (aunque no ambos). Por ejemplo, una elección simple es fijar l_ii=1 para $i=1,2,\dots,n$ haciendo de esto modo que L sea una matriz triangular inferior unitaria. Otra elección es hacer U una matriz triangular superior unitaria (tomando u_ii=1 para cada i).

Para deducir un algoritmo que nos permita la factorización LU de Apartiremos de la fórmula para la multiplicación de matrices:

$\begin{displaymath}a_{ij} = \sum_{s=1}^{n} l_{is}u_{sj} = \sum_{s=1}^{\mbox{\scriptsize {mín}}(i,j)} l_{is}u_{sj} \end{displaymath}$

(54)

en donde nos hemos valido del hecho de que l_is=0 para s >i y u_sj=0 para s>j.

En este proceso, cada paso determina una nueva fila de U y una nueva columna de L. En el paso k, podemos suponer que ya se calcularon las filas $1, 2, \dots, k-1$ de U, al igual que las columnas $1, 2, \dots, k-1$ de L. Haciendo i=j=k en la ecuación (54) obtenemos

$\begin{displaymath}a_{kk} = l_{kk}u_{kk} \sum_{s=1}^{k-1}l_{ks}u_{sk} \end{displaymath}$

(55)

Si especificamos un valor para l_kk (o para u_kk), a partir de la ecuación (55) es posible determinar un valor para el otro término. Conocidas u_kk y l_kk y a partir de la ecuación (54) podemos escribir las expresiones para la k-ésima fila (i=k) y para la k-ésima columna (j=k), respectivamente:

$\displaystyle a_{kj} = l_{kk}u_{kj} + \sum_{s=1}^{k-1} l_{ks}u_{sj}$		$\displaystyle (k+1 \leq j \leq n)$	(56)
$\displaystyle a_{ik} = l_{ik}u_{kk} + \sum_{s=1}^{k-1} l_{is}u_{sk}$		$\displaystyle (k+1 \leq i \leq n)$	(57)

Es decir, las ecuaciones (57) se pueden emplear para encontrar los elementos u_kj y l_ik.

El algoritmo basado en el análisis anterior se denomina factorización de Doolittle cuando se toman los términos l_ii = 1 para $1 \leq i \leq n$ (L triangular inferior unitaria) y factorización de Crout cuando se toman los términos u_ii=1 (U triangular superior unitaria).

Una implementación en pseudocódigo del algoritmo para llevar a cabo la factorización LU se muestra en la figura (11).

**Figure:** Implementación del algoritmo de la factorización LU.
$\begin{figure} \begin{center} \begin{tabular}{\vert l\vert} \hline \\ ~~~~~... ...$u_{ij}$ ) \\ ~ \\ \hline \end{tabular} \end{center} \protect\end{figure}$

Es interesante notar que los bucles que permiten el cómputo de la k-ésima fila de U y de la k-ésima columna de L se pueden llevar a cabo en paralelo, es decir, pueden evaluarse simultáneamente sobre dos procesadores, lo que redunda en un importante ahorro del tiempo de cálculo.

Ejemplo: Encuentre las factorizaciones de Doolittle y Crout de la matriz:

$\begin{displaymath}A = \left( \begin{array}{rrr} 60 & 30 & 20 \\ 30 & 20 & 15 \\ 20 & 15 & 12 \end{array}\right) \end{displaymath}$

La factorización de Doolittle es, a partir del algoritmo:

$\begin{displaymath}A = \begin{array}{ll} \left( \begin{array}{rrr} 1 & 0 & 0 ... ... \\ 0 & 0 & \frac{1}{3} \end{array} \right) \end{array}= LU \end{displaymath}$

En vez de calcular la factorización de Crout directamente, la podemos obtener a partir de la factorización de Doolittle que acabamos de ver. Efectivamente, si tenemos en cuenta que la matriz A es simétrica, es posible comprobar que se cumple la relación:

A = LU = U^TL^T

por lo que la factorización de Crout resulta ser:

$\begin{displaymath}A = \begin{array}{ll} \left( \begin{array}{rrr} 60 & 0 & 0... ... 1 \\ 0 & 0 & 1 \end{array} \right) \end{array}= U^{T}L^{T} \end{displaymath}$

Next: 6.1.3 Eliminación gaussiana básica Up: 6.1 Métodos de resolución Previous: 6.1.1 Sistemas fáciles de

Wladimiro Diaz Villanueva
1998-05-11