😊
MÉTODO DOOLITTLE:
En álgebra lineal, se conoce por factorización LU de matrices al proceso que a
partir de una matriz cuadrada A halla dos matrices triangulares inferior y
superior, tal que A=LU, donde L es la matriz triangular inferior (L de lower) y U
es la matriz triangular superior (U de upper). Existen muchos métodos
numéricos para obtener estas matrices L y U, y su obtención tiene aplicaciones
en la resolución de sistemas lineales, cálculo de determinantes y en el cálculo
de matrices inversas.
Este método de Doolittle tiene la particularidad que hace que la diagonal de la
matriz L sea unitaria. Es un método denominado compacto, porque es sencillo
de programar y requiere poca memoria una vez implementado en el ordenador.
Existen muchos métodos compactos de factorización de matrices, y suelen
diferir en el tratamiento que hacen de los elementos de la diagonal de las
matrices L y/o U. En concreto, el método de Doolittle genera una matriz L que
tiene 1 en todos los elementos de la diagonal. Este método proporciona una
ventaja de cálculo en ordenadores modernos, que cuentan con memoria caché
además de la memoria principal. En este tipo de arquitecturas de ordenador, la
secuencia en la que se realizan los cálculos puede ser más importante que la
cantidad de cálculos que se realizan. El método de Doolittle tiene una
secuencia de operaciones óptima para ejecutarse en un ordenador con
memoria caché.
Los métodos de factorización LU se pueden usar para resolver sistemas
lineales, entre otras aplicaciones.
El resultado del método serán dos matrices triangulares tales que A=LU. La
matriz L será triangular inferior y de diagonal unitaria. La matriz U será
triangular superior. Al ser las matrices triangulares, podemos calcular cada
elemento de la matriz A mediante:
min ( ij )
a ij= ∑ l ik u kj
k=1
donde a, l y u se refieren a los elementos de las matrices A, L y U,
respectivamente. El límite superior de la suma se debe a que las matrices
triangulares tienen ceros en su mitad inferior o superior y, por tanto, el producto
matricial sumaría cero.
En el caso de que i ≤ j, es decir, el número de fila es más pequeño que el
número de la columna, en otras palabras, estamos por encima de la diagonal (o
en la diagonal), entonces min (i, j) = i y tendremos:
i−1
l ii uij =uij =aij −∑ l ik U kj
k=1
Ya que lii = 1. Es decir, hemos despejado del sumatorio el sumando cuando k
= i, y eso nos permite obtener una expresión genérica para calcular uij.
Si empezamos en i = 1 la ecuación anterior nos dice que u1j=a1j, por lo que ya
hemos calculado la primera fila de la matriz U.
Para seguir calculando filas de U es necesario conocer los valores de L. Si nos
movemos por debajo de la diagonal, j ≤ i, tendremos que min (i, j) = j, y
obtenemos:
j−1
aij −∑ l ik U kj
k=1
l ij =
u jj
Por tanto, podemos calcular li1 = ai / u11, es decir, hemos calculado ya la
primera columna de L. Al conocer la primera columna de L podemos intentar
calcular la siguiente fila de U. Al terminar una fila de U, ya conocemos los
elementos para calcular la siguiente columna de L. Aplicando sucesivamente
este método, obtendremos de manera completa las matrices L y U.
EJERCICIOS:
1. Obtener la factorización de Doolittle de la siguiente matriz, utilizando
pivotación parcial.
3 −4 5
(
−6 −8 −5
−5 −5 −7 )
Introducir el vector de permutaciones:
−6 −8 −5
(−1 /2 −8 5/2
5/6 −5/24 −37/16 )
Introducir el valor determinante:
( 2 13 )
Resolver el sistema lineal A x = b cundo b es el vector siguiente:
67
( )2
−31
( 1−6 8 )
Solución:
Factorización:
En cada etapa de la resolución se muestran los valores actuales de la matriz y
del vector de permutaciones de filas, en su caso.
3 −4 5
(−6 −8 −5
−5 −5 −7 )
Precalculando la sub columna 1.
Elementos a considerar: (3, -6, -5)
Máximo en fila 2 con valor = 6
Intercambio de filas 1 y 2.
−6 −8 −5
( )
[ 3 −4 5 , [ 2 ,1 , 3 ] ]
−5 −9 −7
Tratando la fila 1
Tratando la columna 1
−6 −8 −5
( 1 ∕ 2 −4 −5
5 ∕ 6 −5 −7 )
Precalculando la sub columna 2
Elementos a considerar: [-8, 5/3]
Máximo en fila 2 con valor = 8
−6 −8 −5
(
[ −1 ∕ 2 −8
)
5 ,[2 , 1 ,3 ]¿
5 ∕ 6 5 ∕ 3 −7
Tratando la fila 2
Tratando la columna 2
−6 −8 −5
(−1 ∕ 2 −8 5∕2
5 ∕ 6 −5 ∕ 24 −7 )
Tratando la fila 3
−6 −8 −5
(−1 ∕ 2 −8 5∕2
5 ∕ 6 −5 ∕ 24 −37 ∕ 16 )
La factorización final es la siguiente, en la siguiente, en la que aparecen las
matrices L y U, y el vector de permutaciones:
1 0 0 −6 1 8−5
[(
−1 /2 1
5/6 −5/24 1 0 )(
0 , 0 −8
)
5/2 , [ 2 , 1 ,3 ]
0 −37/16 ]
Determinante:
El valor del determinante viene dado por el productor de los elementos de la
diagonal principal, que es la principal de U, ya que |L| = 1. Además, hay que
considerar el numero realizado por permutaciones de filas 1, ya que el
determinante cambia de signo en cada una. Por tanto, es:
3
| A|=|L||U|=∏ U ii x (−1 ) =111
i=1
(-1) son los números de permutaciones.
Resolución del sistema:
Sabemos que P A = L U, siendo P la matriz que premultipicada por A produce
las permutaciones de filas en que se han realizado, si hay pivotación. Sin
pivotación, P seria la matriz identidad.
Queremos resolver A x = b P A x = P L U x = P b. Llamando y = U x, podemos
resolver el sistema en dos pasos:
- L y = P b, de donde se obtiene el vector y,
- U x = y, de donde ya se pude obtener el vector solución x.
P.b es el vector resultante de aplicar las permutaciones indicadas por el vector
pfilas = [2, 1, 3] al vector:
67
b= 2
( )
−31
O también se pude obtener premultipicando por la matriz P, que se puede
construir fácilmente a partir del vector de permutaciones:
0 1 0 2
( ) ( )
P= 1 0 0 P . b= 67
0 0 1 −31
Se resuelve el primer sistema triangular
1 0 ⅈ y1 2 y1 2
(
−1 ∕ 2 1 0
5 ∕ 6 −5 ∕ 24 1 )( ) ( )( ) ( )
y 2 = 63 y 2 = 68
y3 −31 y 3 −37/2
Por sustitución hacia adelante (y1 = y2 = y3). Se resuelve ahora
−6 −8 −5 x1 2 x1 1
(0 −8
0
5∕2 x 2 = 68
0 −37 ∕ 16 x 3 )( ) ( )( ) ( )
x 2 = −6
−37 ∕ 2 x 3 8
Por sustitución hacia atrás (x3 = x2 =x1), resultando el vector pedido.
2. Obtener la factorización de Doolittle de la siguiente matriz, sin utilizar
pivotación.
−2 29 0
(−4 2−5
3 −4−2
2 −4−2
0
4
9
)
Introducir el vector de permutaciones:
−2 2 9 0
( 2 −2
−3 ∕ 2 1 ∕ 2
−1 1
23
23
0
4
30/23 87 /23
)
Introducir el valor del determinante:
( 1 23 4 )
Resolver el sistema lineal A x = b cundo b es el vector siguiente:
−38
( )
20
−11
−40
(−1−2−4−6 )
Solución:
Factorización:
−2 2 9 0
(−4 2 −5
3 −4 −2
2 −4 −2
0
4
9
)
Tratando la fila 1
Tratando la columna 1
−2 2 9 0
( 2 2 −5
−3 ∕ 2 −4 −2
−1 −4 −2
0
4
9
)
Tratando la fila 2
Tratando la columna 2
−2 2 9 0
( 2 −2 −23
−3 ∕ 2 1/2 −2
−1 1 −2
0
4
9
)
Tratando la fila 3
Tratando la columna 3
−2 2 9 0
( 2 −2 −23 0
−3 ∕ 2 1/2
−1
23 4
1 30 /23 9
)
Tratando la fila 4
−2 2 9 0
( 2 −2 −23
−3 ∕ 2 1/2
−1
23
0
4
−4 30 /23 87 /23
)
La factorización final es el siguiente, en la que aparecen las matrices L y U, y el
vector de permutaciones:
1 0 9 0 −2 2 9 0
[
( 2
−1
1
−3 ∕ 2 1/2
0
1
1 −30 /23
0
9
)(
0 , 0 −2 −23
0
0
0
0
23
0
0
4
87 /23
)
,[1, 2, 3, 4]]
Determinante:
4
| A|=|L||U|=∏ U ii x (−1 ) =348
i=1
(-1) son los números de permutaciones.
Resolución del sistema:
- L y = P b, de donde se obtiene el vector y,
- U x = y, de donde ya se pude obtener el vector solución x.
1 0 0 0 −38
P= 0
0
0
( 1
0
0
0
1
0
0
1
) ( )
0 P .b= 20
−11
−40
Resolvemos entonces el primer sistema triangular:
−38
1 0 0 0 y1 y1
)( ) ( ) ( ) ( )
−38
( 2
−1
1
−3 /2 1/2
0
1
1 30/23
0 y 2 = 20
0 y3 11
1 y 4 −40
y2 =
y3
y4
96
−116
522
23
Por sustitución hacia adelante (y1 = y2 = y3 = y4). Resolvemos:
−2 2 9 0 −38
x 1 x1
( )( ) ( )( ) ( )
0 −2 −23 0 −1
96
0 0 23 4 x 2 = −116 x 2 = −2
87 x 3 x3 −4
522
0 0 0 x4 x4 −6
23 23
Por sustitución hacia atrás (x4 = x3 = x2 = x1), resultando el vector pedido.
REFERENCIAS:
LU decomposition (Wikipedia EN)
