Algoritmo de descomposición

A partir de la matriz

hemos obtenido por transformaciones elementales la nueva matriz trapezoidal superior.

( La letra U, se asocia con la palabra inglesa UPPER ).

La relación entre A y U, siguiendo la secuencia de transformaciones elementales

es:

E_{3 - ( 10/ 3 ) 2} E_{3 - ( 6 ) 1} E_{2 - ( 4 ) 1} A = U

Luego

A = ( E_{3 - ( 10/3 ) 2 .} E_{3 - ( 6 ) 1 .} E_{2 - ( 4 ) 1} ) ^-1 U

por lo tanto

A = ( E_{2 - ( 4 ) 1}^-1 _. E_{3 - ( 6 ) 1} ^-1_. E_{3 - ( 10/ 3 ) 2}^-1 U

De donde

A = E_{2 + ( 4 ) 1 .} E_{3 + ( 6 ) 1 .} E_{3 + ( 10/ 3 ) 2} U

que es similar a la expresión (4.49).

Desarrollemos el producto

E_{2 + ( 4 ) 1 .} E_{3 + ( 6 ) 1 .} E_{3 + ( 10/ 3 ) 2} =

Si la matriz A fuese cuadrada entonces la matriz U sería una matriz triángular superior.

La matriz L es una matriz no singular, por ser un producto de matrices elementales (no singulares).

Si la matriz A fuese no singular, la matriz U también lo sería.

Las siguientes relaciones, a partir del ejemplo anterior, nos permitirán ilustrar un procedimiento práctico para hallar la descomposición LU de una matriz A.

Secuencia de premultiplicaciones por matrices elementales Matriz U obtenida

Secuencia de operaciones para obtener L (las inversas) Matriz L obtenida

La matriz L y la matriz U se pueden construir simultáneamente a medida que se efectuan las operaciones elementales en el proceso progresivo de obtención de ceros, por operaciones elementales sobre las filas de A, siempre y cuando no se intercambien filas, sin necesidad de escribir explícitamente las matrices elementales E_i.

A partir de la observación cuidadosa de las operaciones elementales sobre las filas de A, señaladas por los pasos (1), (2) y (3) en (*), concluimos:

Primer paso (1): Resultado: LU sobreescrita

Al terminar exitosamente la descomposición LU con sobreescritura concluimos que

Observaciones:

· Los 1 en la diagonal de L se completan al final, ya que han sido sobreescritos por los elementos de la diagonal de U.

· La matriz L es en todos los casos una matriz triangular inferior.

· La matriz U es una matriz trapezoidal superior.

· La razón por la cual los números 4 y 6 de A parecen no cambiar en L se debe a que el pivote utilizado en los pasos (1) y (2) fué 1. Este no es siempre el caso, como se puede observar al resolver otros ejercicios.

· Los elementos que aparecen sucesivamente en L, los l_ik, en el paso (i,k)(lograr 0 en posición (i,k) de A), se podrían calcular por la fórmula u_ik/u_ii, i < k, donde u_ik es el elemento a eliminar en U (será 0 al terminar el paso i) y u_ii es el pivote que ya es un elemento de U calculado en el paso anterior. Por ejemplo, en el paso (2,1), u₂₁ = a₂₁ =4 y u₁₁ = a₁₁ = 1, luego l₂₁ = a₂₁/a₁₁ = 4/1 = 4. La operación elemental utilizada fue fila 2 – 4 (fila 1), es decir (fila 2) – ( a₂₁/a₁₁ ) x (fila 1). Por ello es que l₃₁ = a₃₁/a₁₁ = 6, y l₃₂ = u₃₂/u₂₂ = (-10/-3) = 10/3. Este tipo de razonamiento sobre los subíndices lo utilizan quienes desarrollan métodos numéricos. Por ello los lenguajes de programación incorporan estructuras especiales para manejar los subíndices y para “sobreescribir” (sustituir) valores a medida que progresan los cálculos.

La matriz L ( de lower ) es una matriz TRIANGULAR INFERIOR ( ya que L_{i j} = 0 para todo i > j ) y como L es un producto de matrices elementales, además es no singular . ( posee inversa ).

Esta descomposición de una matriz A en un producto LU se puede lograr siempre que las operaciones elementales no involucren cambio de filas y que además todas las operaciones elementales involucrando matrices de tipo E_{p + ( c ) q} , c ¹ 0, cumplan la condición q< p o sea que para obtener ceros hacia abajo se utilicen las filas superiores.