Factorizaci´on LU Departamento de Matem´aticas, CCIR/ITESM 9 de febrero de 2011

´Indice 26.1. Introducci´on . . . . . . . . . . . . . . 26.2. Factorizaci´ on LU . . . . . . . . . . . 26.3. Uso de la factorizaci´ on LU . . . . . . 26.4. Obtenci´on de la factorizaci´ on LU con 26.5. Factorizaci´ on LU: ejemplo clave . . . 26.6. Complejidad . . . . . . . . . . . . . . 26.7. Factorizaci´ on de P A = L U . . . . . 26.8. Notas generales . . . . . . . . . . . .

26.1.

. . . . . . . . . . . . . . . . . . . . . elementales . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

1 1 2 3 4 5 5 13

Introducci´ on

La factorizaci´on LU de una matriz es una factorizaci´on que resume el proceso de eliminaci´on gaussiana aplicado a la matriz y que es conveniente en terminos del n´ umero total de operaciones de punto flotante cuando se desea calcular la inversa de una matriz o cuando se resolver´a una serie de sistemas de ecuaciones con una misma matriz de coeficientes. En la lectura, primeramente consideraremos la factorizaci´on LU sin intercambio basada en matrices elementales y que es conocida como de Doolittle y posteriormente veremos el algoritmo que da la factorizaci´ on PA = LU.

26.2.

Factorizaci´ on LU

Suponga que la matriz A es una matriz m × n se puede escribir como el producto de dos matrices: A = LU donde L es una matriz triangular inferior m × m y U es una matriz escalonada m × n. Entonces para resolver el sistema: A x = b, escribimos A x = (L U) x = L (U x) . Una posible estrategia de soluci´ on consiste en tomar y = U x y resolver para y: L y = b. Como la matriz L es triangular superior este sistema puede resolverse mediante sustituci´on hacia abajo, lo cual se hace f´acilmente en m2 FLOPS. Una vez con los valores encontrados de y, las inc´ognitas al sistema inicial se resuelve despejando x de U x = y.

Nuevamente, como U es escalonada, este sistema puede resolverse en caso de tener souci´on mediante sustituci´on hacia atr´as, lo cual es sencillo. Estas observaciones nos dan la pauta para ver la conveniencia de una factorizaci´on como la anterior, es decir factorizar A como el producto de una matriz L triangular superior, por otra U la cual es escalonada. Esta factorizaci´ on se llama usualmente Descomposici´ on LU.

26.3.

Uso de la factorizaci´ on LU

Ejemplo 26.1 Use la factorizaci´on LU de A: 

    4 −2 1 1 0 0 4 −2 1 3 7  = LU A =  20 −7 12  =  5 1 0   0 −8 13 17 −2 3 1 0 0 −2

para despejar x del sistema: 

 11 A x =  70  = b 17 Soluci´ on Sea y = (y1 , y2 , y3 ) un nuevo vector de inc´ ognitas. Primero resolveremos el sistema triangular inferior L y = b:     1 0 0 11  5 1 0  y =  70  −2 3 1 17 Este sistema escrito en su forma de ecuaciones queda: y1 = 11 5 y1 + y2 = 70 −2 y1 + 3 y2 + y3 = 17 Por eliminaci´on directa de la: primera ecuaci´ on: y1 = 11, segunda ecuaci´ on: y2 = 70 − 5 y1 = 70 − 5 (11) = 15, y de la tercera: y3 = 17 + 2y1 − 3 y2 = 17 + 2 (11) − 3 (15) = −6. Ahora el sistema U x = y: 

   4 −2 1 11  0 3 7  x =  15  0 0 −2 −6 El cual escrito en su forma de ecuaciones queda: 4 x1 − 2 x2 + x3 = 11 3 x2 + 7 x3 = 15 − 2 x3 = −6 El cual al ser resuelto por sustituci´ on hacia atr´as queda: 2

de la u ´ltima ecuaci´ on: x3 = 3, segunda ecuaci´ on: x2 = 5 − 7/3 x3 = 5 − 7/3 (3) = −2, y de la primera: x1 = 11/4 + 1/2x2 − 1/4 x3 = 11/4 + 1/2 (−2) − 1/4 (−3) = 1 

26.4.

Obtenci´ on de la factorizaci´ on LU con elementales

Ejemplo 26.2 Determine una factorizaci´ on LU de la matriz: 

 2 3 −1  −6 −6 5   A=  4 18 6  −2 −9 −3 Soluci´ on La idea del m´etodo es ir acumulando las inversas de las operaciones hechas sobre los renglones la matriz para irla trasnformando en una matriz escalonada. Y m´as que propiamente las inversas de las operaciones sobre los renglones, las matrices elementales involucradas. As´ı por ejemplo el primer c´alculo que se realiza es hacer un cero debajo de el elemento (1, 1) que es el elemento 2, para ello debemos realizar la operaci´on R2 ← R2 + 3R1 , esta operaci´on tiene como matriz elemental la matriz:   1 0 0 0  3 1 0 0   E1 =   0 0 1 0  0 0 0 1 As´ı la situaci´on est´a:



 2 3 −1  0 3 3   = B1 E1 A =   4 18 6  −2 −9 −3

En el siguiente paso del proceso de eliminaci´ on es R3 ← R3 −2R1 , esta operaci´on tiene como matriz elemental la matriz:   1 0 0 0  0 1 0 0   E2 =   −2 0 1 0  0 0 0 1 As´ı la situaci´on est´a:



 2 3 −1  0 3 2   = B2 E2 E1 A =   0 12 8  −2 −9 −3

En el siguiente paso del proceso de eliminaci´ on es R4 ← R4 + R1 , esta operaci´on tiene como matriz elemental la matriz:   1 0 0 0  0 1 0 0   E3 =   0 0 1 0  1 0 0 1 3

As´ı la situaci´on est´a:

 2 3 −1  0 3 2   = B3 E 3 E 2 E1 A =   0 12 8  0 −6 −4 

Observamos que el hipot´etico caso de que en E3 E2 E1 A = B3 La matriz B3 ya fuera escalonada, es decir la U buscada, entonces: A = E1 −1 E2 −1 E3 −1 U Lo cual indica que lo que debemos acumular son las inversas de las matrices elementales utilizadas. La forma sistem´atica de ir acumulando las inversas de las Ei s es ir contruyendo la matriz L:   1 0 0 0  −3 1 0 0   L=  2 ? 1 0  −1 ? ? 1 As´ı, en el avance de la conversi´ on a escalonada de A:   2 3 −1  0 3 2  , A ∼   0 12 8  0 −6 −4 

2  0 ∼   0 0



1  −3 L=  2 −1

0 1 ? ?

  1 0 3 −1   −3 1 3 2  = U, L =   2 4 0 0  −1 −2 0 0

0 0 1 ? 0 0 1 ?

 0 0   0  1  0 0   0  1

En este caso la matriz U est´ a en la forma escalonada y por consiguiente el proceso se detiene haciendo cero aquellos valores desconocidos. Por consiguiente una factorizaci´on de A ser´a:    1 0 0 0 2 3 −1  −3  1 0 0  2   0 3  A = LU =   2   4 1 0 0 0 0  −1 −2 0 1 0 0 0

26.5.

Factorizaci´ on LU: ejemplo clave

Ejemplo 26.3 Determine una factorizaci´ on LU de la matriz: 

 2 3 −1  −6 −6 5   A=  4 18 6  −2 −9 −3 Soluci´ on El m´etodo procede as´ı. 4

La matriz L inicialmente es la matriz identidad con el mismo n´ umero de renglones de A. Si se utiliz´ o la operaci´on Ri → Ri + c Rj entonces en la posici´on (i, j) de L se coloca −c. La matriz U es la matriz que queda en al escalonar A. Si hubo necesidad de intercambiar renglones para escalonar, A NO admite una factorizaci´on L U. Digamos que con las operaciones siguientes 1. R2 → R2 + 3 R1 2. R3 → R3 − 2 R1 3. R4 → R4 + 1 R1 4. R3 → R3 − 4 R2 5. R4 → R4 + 2 R2 la matriz A se escalona y que queda: 

2  0 A −→   0 0 Entonces



1 0 0  −(3) 1 0 L=  −(−2) −(−4) 1 −(1) −(2) 0

26.6.

 3 −1 3 2   0 0  0 0

  0 1 0   0   −3 1 = 0   2 4 1 −1 −2

0 0 1 0

  0  0   y U=   0 1

2 0 0 0

 3 −1 3 2   0 0  0 0

Complejidad

Observe que para la obtenci´ on de la factorizaci´on LU se realiza la fase 1 del m´etodo de eliminaci´on gaussiana. Por consiguiente, la complejidad del algoritmo de factorizaci´on LU ser´a O(2/3 n3 ). Teniendo la factorizaci´ on 2 LU, la aplicaci´on de la sustici´ on hacia atr´ as o hacia adelante toman cada uno n . Por ello es que para resolver un solo sistema de ecuaciones no hay ventaja en utilizar la factorizaci´on LU. La ventaja aparece cuando se desean resolver varios sistemas de ecuaciones con la misma matriz de coeficientes. En la primera soluci´ on se determina la factorizaci´ on LU, y en las siguientes bastar´a sustituci´on hacia adelante y hacia atr´as. O sea que cada siguiente soluci´ on tomar´ a s´ olo 2 n2 FLOPs contrario a los 2/3 n3 de eliminaci´on gaussiana.

26.7.

Factorizaci´ on de P A = L U

Frecuentemente, no es posible escalonar una matriz s´olo con operaciones de eliminaci´on. En estos casos se requiere realizar intercambio de renglones. Para este tipo de matrices no existe la factorizaci´on LU. Lo que aplica es la factorizaci´ on P A = L U. Donde la matriz P es una matriz de permutaci´on. Estas matrices de permutaci´on se obtienen de la matriz identidad intercambiando renglones. La factorizaci´on P A = L U se obtiene de forma an´ aloga a la factorizaci´ on LU pero se lleva un registro de los renglones que se intercambian y se efectuan los intercambios en una matriz que registra los inversos de las operaciones de eliminaci´ on. Algoritmo de P A = L U Entrada: Matriz A n × m 5

Salida: P matriz de permutaci´ on n × n, L matriz triangular superior unitaria n × n (lii = 1), U matriz escalonada n × m que cumplen: PA = LU 1. Tome P = In , L = 0, y U = A. 2. Mientras que U no sea escalonada hacer 2.1. Aplicar una operaci´ on R de eliminaci´on o de intercambio a U. 2.2. Si R es de la forma Ri ↔ Rj , entonces aplicar R a P y a L. 2.3. Si R es de la forma Ri ← Ri − a Rj ,entonces modificar L haciendo lij = a. 3. Tome L = L + In . Ejemplo 26.4 Determine una factorizaci´ on P A = L U de la matriz  1 2 −2 1  4 5 −7 6 A=  5 25 −15 −3 6 −12 −6 22

   

Soluci´ on Tomemos U0 = A, P0 = I4 y L0 = 0. 1. Si aplicamos sobre U0 las operaciones de eliminaci´on R2 → R2 − 4 R1 ,R3 → R3 − 5 R1 y R4 → R4 − 6 R1 se obtiene a la nueva matriz U1 :   1 2 −2 1  0 −3 1 2   U1 =   0 15 −5 −8  0 −24 6 16 Estos cambios se registran en L1 y hasta el momento  0 0  4 0 L1 =   5 0 6 0

se tiene:  0 0 0 0  ,P = I 0 0  0 0

2. Si aplicamos sobre U1 las operaciones de eliminaci´on R3 → R3 + 5 R2 y R4 → R4 − 8 R2 se obtiene a la nueva matriz U2 :   1 2 −2 1  0 −3 1 2   U2 =   0 0 0 2  0 0 −2 0

6

Estos cambios se registran en L1 y hasta el momento  0 0  4 0 L2 =   5 −5 6 8

se tiene:  0 0 0 0   , P = P1 0 0  2 0 0

3. Si aplicamos sobre U2 la operaci´ on de intercambio R3 ↔ R4 se obtiene la nueva matriz U3 :   1 2 −2 1  0 −3 1 2   U3 =   0 0 −2 0  0 0 0 2 Aplicando la operaci´ on de intercambio a L2 y  0 0  4 0 L3 =   6 8 5 −5

a P2 , se tiene:   0 0  0 0   , P3 =    0 0 0 0

1 0 0 0

0 1 0 0

0 0 0 1

4. Puesto que la matriz U3 ya es escalonada, el procedimiento termina y se tiene:    1 2 −2 1 1 0  0 −3   1 2  4 1 U = U3 =  ,L =   0  6 0 −2 0  8 0 0 0 2 5 −5   1 0 0 0  0 1 0 0   P = P3 =   0 0 0 1  0 0 1 0 Como ejercicio, compruebe que P A = L U  Ejemplo 26.5 Determine una factorizaci´ on P A = L U de la matriz  0 −3 1 2 2  0 0 0 0 2   2 −2 1 1 A= 1  4 2 −8 8 9 5 1 −5 13 11 Soluci´ on Tomemos U0 = A, P0 = I5 y L0 = 0. 1. Si aplicamos sobre U la operaci´ on de intercambio R1 ↔ R3 se  1 2 −2 1  0 0 0 0   1 2 U1 =  0 −3  4 2 −8 8 5 1 −5 13

7

 0 0   1  0 finalizamos haciendo L = L3 + I y  0 0 0 0   1 0  0 1

     

obtiene la nueva matriz U:  1 2   2   9  11

Aplicando la operaci´ on de intercambio  0  0  L1 =   0  0 0

a L0 y a P0 , se tiene:   0 0 0 0  0 0 0 0     0 0 0 0  , P1 =    0 0 0 0  0 0 0 0

2. Si aplicamos sobre U1 las operaciones de eliminaci´on R4 nueva matriz U2 :  1 2 −2  0 0 0   1 U2 =  0 −3  0 −6 0 0 −9 5

0 0 1 0 0

0 1 0 0 0

1 0 0 0 0

0 0 0 1 0

0 0 0 0 1

     

→ R4 − 4 R1 y R5 → R5 − 5 R1 se obtiene a la 1 0 2 4 8

Estos cambios se registran en L1 y hasta el momento se tiene:    0 0 0 0 0  0 0 0 0 0        L2 =  0 0 0 0 0  , P2 =    4 0 0 0 0   5 0 0 0 0

1 2 2 5 6

0 0 1 0 0

     

0 1 0 0 0

1 0 0 0 0

0 0 0 1 0

0 0 0 0 1

     

3. Si aplicamos sobre U2 la operaci´ on de intercambio R2 ↔ R3 se obtiene la nueva matriz U3 :   1 2 −2 1 1  0 −3 1 2 2    0 0 0 2  U3   0   0 −6 0 4 5  0 −9 5 8 6 Aplicando la operaci´ on de intercambio  0  0  L3 =   0  4 5

a L2 y a P2 , se tiene:   0 0 0 0  0 0 0 0     0 0 0 0   , P3 =    0 0 0 0 0 0 0 0

0 1 0 0 0

0 0 1 0 0

1 0 0 0 0

0 0 0 1 0

0 0 0 0 1

     

Si aplicamos sobre U3 las operaciones de eliminaci´on R4 → R4 − 2 R2 y R5 → R5 − 3 R2 se obtiene a la nueva matriz U4 :   1 2 −2 1 1  0 −3 1 2 2     0 0 0 2  U4 =  0   0 0 −2 0 1  0 0 2 2 0 Estos cambios se registran en L3 y hasta el momento se tiene:    0 0 0 0 0  0 0 0 0 0        L4 =  0 0 0 0 0  , P4 =    4 2 0 0 0   5 3 0 0 0 8

0 1 0 0 0

0 0 1 0 0

1 0 0 0 0

0 0 0 1 0

0 0 0 0 1

     

5. Si aplicamos sobre U4 la operaci´ on de intercambio R2 ↔ R3  1 2 −2 1  0 −3 1 2   0 −2 0 U5 =  0  0 0 0 0 0 0 2 2 Estos cambios se registran en L4 y hasta el momento se tiene:    0 0 0 0 0  0 0 0 0 0        L5 =  4 2 0 0 0  , P5 =    0 0 0 0 0   5 3 0 0 0

se obtiene la nueva matriz U5 :  1 2   1   2  0

0 1 0 0 0

0 0 0 1 0

1 0 0 0 0

0 0 1 0 0

0 0 0 0 1

     

6. Si aplicamos sobre U5 la operaci´ on de eliminaci´on R5 → R5 + 1 R3 se obtiene a la nueva matriz U6 :   1 2 −2 1 1  0 −3 1 2 2     0 −2 0 1  U6 =  0   0 0 0 0 2  0 0 0 2 1 Estos cambios se registran en L6 y hasta el momento se tiene:    0 0 0 0 0  0 0  0 0 0       0 0 0  , P6 =  L6 =  4 2   0 0  0 0 0  5 3 −1 0 0 7. Si aplicamos sobre U6 la operaci´ on de intercambio R4 ↔ R5  1 2 −2 1  0 −3 1 2  0 0 −2 0 U7 =    0 0 0 2 0 0 0 0 Estos cambios se registran en L6 y hasta el momento se tiene:    0 0 0 0 0   0 0 0 0 0       0 0 0  , P7 =  L7 =  4 2    5 3 −1 0 0  0 0 0 0 0

0 1 0 0 0

0 0 0 1 0

1 0 0 0 0

0 0 1 0 0

0 0 0 0 1

     

se obtiene la nueva matriz U7 :  1 2   1   1  2

0 1 0 0 0

0 0 0 0 1

1 0 0 0 0

0 0 1 0 0

0 0 0 1 0

     

8. Puesto que la matriz U7 ya es escalonada, el procedimiento termina y finalizamos haciendo L = L7 + I y se tiene:     1 0 0 0 0 1 2 −2 1 1  0 −3  0 1 1 2 2  0 0 0         0 −2 0 1  , L =  4 2 1 0 0  U = U7 =  0   0  5 3 −1 1 0  0 0 2 1  0 0 0 0 2 0 0 0 0 1 9

   P = P7 =   

0 1 0 0 0

0 0 0 0 1

1 0 0 0 0

0 0 1 0 0



0 0 0 1 0

    

Como ejercicio, compruebe que P A = L U  Ejemplo 26.6 Determine una factorizaci´ on P A = L U de la matriz  0 −18 0 14 16 7  8 16 −18 8 9 −16   9 3 −13 21 20 −14 A=  1 2 −2 1 1 −2   0 −3 1 2 2 1 10 −1 −21 28 32 −12 Soluci´ on Tomemos U0 = A, P0 = I5 y L0 = 0. 1. Si aplicamos sobre U la operaci´ on de intercambio  1 2  8 16   9 3 U1 =   0 −18   0 −3 10 −1 Aplicando la operaci´ on de intercambio  0 0  0 0   0 0 L1 =   0 0   0 0 0 0

       

R1 ↔ R4 se obtiene la nueva matriz U:  −2 1 1 −2 −18 8 9 −16   −13 21 20 −14   0 14 16 7   1 2 2 1  −21 28 32 −12

a L0 y a P0 , se tiene:   0 0 0 0  0 0 0 0      0 0 0 0   , P = 1  0 0 0 0      0 0 0 0 0 0 0

0 0 0 1 0 0

0 1 0 0 0 0

0 0 1 0 0 0

1 0 0 0 0 0

0 0 0 0 1 0

0 0 0 0 0 1

       

2. Si aplicamos sobre U1 las operaciones de eliminaci´on R2 → R2 − 8 R1 , R3 → R3 − 9 R1 y R6 → R6 − 10 R1 se obtiene a la nueva matriz U2 :   1 2 −2 1 1 −2  0 0 −2 0 1 0      0 −15 5 12 11 4   U2 =   0 −18 0 14 16 7    0 −3 1 2 2 1  0 −21 −1 18 22 8 Estos cambios se registran en L1 y hasta el  0 0 0  8 0 0   9 0 0 L2 =   0 0 0   0 0 0 10 0 0

momento se tiene:   0 0 0  0 0 0      0 0 0  , P2 =    0 0 0    0 0 0  0 0 0 10

0 0 0 1 0 0

0 1 0 0 0 0

0 0 1 0 0 0

1 0 0 0 0 0

0 0 0 0 1 0

0 0 0 0 0 1

       

3. Si aplicamos sobre U2 la operaci´ on de intercambio R2  1 2 −2  0 −3 1   0 −15 5 U3 =   0 −18 0   0 0 −2 0 −21 −1 Aplicando la operaci´ on de intercambio a L2 y  0 0 0 0  0 0 0 0   9 0 0 0 L3 =   0 0 0 0   8 0 0 0 10 0 0 0

↔ R5 se obtiene la nueva matriz U3 :  1 1 −2 2 2 1   12 11 4   14 16 7   0 1 0  18 22

a P2 , se tiene:   0 0  0 0     0 0   , P3 =    0 0     0 0 0 0

0 0 0 1 0 0

8

0 0 0 0 1 0

0 0 1 0 0 0

1 0 0 0 0 0

0 1 0 0 0 0

0 0 0 0 0 1

       

4. Si aplicamos sobre U3 las operaciones de eliminaci´on R3 → R3 − 5 R2 , R4 → R4 − 6 R2 y R6 → R6 − 7 R2 se obtiene a la nueva matriz U4 :   1 2 −2 1 1 −2  0 −3 1 2 2 1      0 0 0 2 1 −1   U4 =   0 0 −6 2 4 1    0 0 −2 0 1 0  0 0 −8 4 8 1 Estos cambios se registran en L3 y hasta el  0 0 0  0 0 0   9 5 0 L4 =   0 6 0   8 0 0 10 7 0

momento se tiene:   0 0 0  0 0 0      0 0 0   , P = 4   0 0 0    0 0 0  0 0 0

0 0 0 1 0 0

0 0 0 0 1 0

0 0 1 0 0 0

1 0 0 0 0 0

0 1 0 0 0 0

0 0 0 0 0 1

       

5. Si aplicamos sobre U4 la operaci´ on de intercambio R3 ↔ R5 se obtiene la nueva matriz U5 :   1 2 −2 1 1 −2  0 −3 1 2 2 1     0 0 −2 0 1 0    U5 =  0 −6 2 4 1    0  0 0 0 2 1 −1  0 0 −8 4 8 1 Aplicando la operaci´ on de intercambio a L4 y  0 0 0 0  0 0 0 0   8 0 0 0 L5 =   0 6 0 0   9 5 0 0 10 7 0 0

a P4 , se tiene:   0 0  0 0      0 0  , P5 =    0 0    0 0  0 0 11

0 0 0 1 0 0

0 0 1 0 0 0

0 0 0 0 1 0

1 0 0 0 0 0

0 1 0 0 0 0

0 0 0 0 0 1

       

6. Si aplicamos sobre U5 las operaciones de eliminaci´on R4 nueva matriz U6 :  1 2 −2 1  0 −3 1 2   0 0 −2 0 U6 =   0 0 0 2   0 0 0 2 0 0 0 4 Estos cambios se registran en L6 y hasta el  0 0 0  0 0 0   8 0 0 L6 =   0 6 3   9 5 0 10 7 4

 1 −2 2 1   1 0   1 1   1 −1  4 1

momento se tiene:   0 0 0  0 0 0     0 0 0   , P6 =    0 0 0     0 0 0 0 0 0

7. Si aplicamos sobre U6 las operaciones de eliminaci´on R5 nueva matriz U7 :  1 2 −2 1  0 −3 1 2   0 0 −2 0 U7 =   0 0 0 2   0 0 0 0 0 0 0 0 Estos cambios se registran en L7 y hasta el  0 0 0  0 0 0   8 0 0 L7 =   0 6 3   9 5 0 10 7 4

→ R4 − 3 R3 y R6 → R6 − 3 R3 se obtiene a la

0 0 0 1 0 0

0 0 1 0 0 0

0 0 0 0 1 0

1 0 0 0 0 0

0 1 0 0 0 0

0 0 0 0 0 1

       

→ R5 − 1 R4 y R6 → R6 − 2 R4 se obtiene a la  1 −2 2 1   1 0   1 1   0 −2  2 −1

momento se tiene:   0 0 0  0 0 0      0 0 0  , P7 =    0 0 0    1 0 0  2 0 0

0 0 0 1 0 0

0 0 1 0 0 0

0 0 0 0 1 0

1 0 0 0 0 0

0 1 0 0 0 0

0 0 0 0 0 1

       

8. Si aplicamos sobre U7 la operaci´ on de intercambio R5 ↔ R6 se obtiene la nueva matriz U8 :   1 2 −2 1 1 −2  0 −3 1 2 2 1     0 0 −2 0 1 0    U8 =  0 0 2 1 1   0   0 0 0 0 2 −1  0 0 0 0 0 −2 Aplicando la operaci´ on de intercambio a L7 y  0 0 0 0  0 0 0 0   8 0 0 0 L8 =   0 6 3 0   10 7 4 2 9 5 0 1

a P7 , se tiene:   0 0  0 0      0 0  , P8 =    0 0    0 0  0 0 12

0 0 0 1 0 0

0 0 1 0 0 0

0 0 0 0 0 1

1 0 0 0 0 0

0 1 0 0 0 0

0 0 0 0 1 0

       

9. Puesto que la matriz U8 ya es escalonada, se tiene:  1 2 −2  0 −3 1   0 0 −2 U = U8 =   0 0 0   0 0 0 0 0 0

el procedimiento termina y   1 1 −2 1 0  0 1 2 2 1     0 1 0  ,L =  8 0   0 6 2 1 1     10 7 0 2 −1 0 0 −2 9 5   0 0 0 1 0 0  0 0 0 0 1 0     0 1 0 0 0 0    P = P8 =   1 0 0 0 0 0    0 0 0 0 0 1  0 0 1 0 0 0

finalizamos haciendo L = L8 + I y  0 0 0 0 0 0 0 0   1 0 0 0   3 1 0 0   4 2 1 0  0 1 0 1

Como ejercicio, compruebe que P A = L U 

26.8.

Notas generales

A continuaci´on hacermos algunos comentarios generales sobre la factorizaci´on LU y su uso. Nota 1 Existen maneras de programar el algoritmo anterior de forma tal que la matriz U y la matriz L queden en una misma matriz cuadrada. Un truco radica en que siendo todos los elementos de la diagonal de U unos, no se requiere el espacio para almacenarlos. Tambi´en hay forma de programar el algoritmo para que la matriz de permutaciones P se represente por un s´ olo vector con n valores, con n´ umeros de 1 al n, que indican c´ omo deben permutarse los renglones de la identidad. Esto es muy conveniente pues la matriz P es tal que de sus n2 valores todos son cero excepto n que son 1. Usando estas ideas el almacenamiento requerido por el algoritmo de factorizaci´on LU puede reducirse de 3 n2 a n2 + n n´ umeros de punto flotante. Significando un ahorro de espacio aproximandamente 66 %. Nota 2 Si se posee una factorizaci´ on A = L U de una matriz cuadrada invertible, entonces la inversa de A puede calcularse mediante A−1 = U−1 L−1 El costo de invertir una matriz triangular es de n3 FLOPs lo cual es m´as econ´omico que invertir una matriz n × n cualquiera que es de 38 n3 FLOPs. Adem´ as de los costos para calcular L−1 y U−1 , habr´ıa que calcular el 3 producto el cual tiene un costo de n FLOPs. Esto nos hace llegar a la conclusi´on de que el c´ alculo u ´ nico de 8 3 −1 3 A haciendo uso de la factorizaci´ on LU toma 3 n FLOPs que es m´as grande que los 3 n FLOPs que toma el procedimiento tradicional. Por ello es que no es conveniente esta estrategia de c´alculo. Nota 3 Si se desea calcular A−1 B y se posee una factorizaci´on LU de A entonces puede aplicarse eliminaci´on gaussiana en la reducci´on [L|B] → [I|D] aqu´ı D = L−1 B lo cual tiene un costo computacional de n3 FLOPs utilizando que L es triangular. Seguido de esto, se aplica tambi´en eliminaci´on gaussiana en la reducci´ on [U|D] → [I|E] aqu´ı E = U−1 D = U−1 L−1 B = A−1 B lo cual tiene un costo computacional de n3 FLOPs utilizando que U es triangular. Esto da como resultado un proceso de c´alculo para A−1 B con un costo 2 n3 FLOPs teniendo disponible una factorizaci´on LU. 13

Nota 4 Las matrices de permutaci´ on P son f´ acilmente invertibles al cumplir la relaci´on: P−1 = PT Adem´as, normalmente no es conveniente realizar el producto P B que tiene un costo de n3 FLOPs sino m´ as bien realizar el movimiento de renglones correspondiente. Y m´as que realizar el movimiento de renglones, se hacen trucos de programaci´ on para evitar tales movimientos teniendo un vector que refiere a los renglones de diferentes posiciones.

14