Nada

Factorización directa de Crout
ETSII-UPM

ETSII-UPM
q

Factorización Directa de Matrices
Métodos de Crout y Choleski

Para una matriz cuadrada de rango r=n la eliminación de Gauss llega
al siguiente resultado:
 a11
a
 21
 a31

 a41


A = LU;

q

a12
a22
a32
a42

a14   1 0 0
a24  l 21 1 0
=
a34  l 31 l32 1

a44  l 41 l42 l 43


a13
a23
a33a43

0   u11 u12 u13
0   0 u 22 u 23

0  0
0 u 33

1  0
0
0


u14 
u 24 

u 34 

u 44 


A este mismo resultado se puede llegar por identificación directa
Ø

A partir de la primera fila de A

Matemáticas de la Especialidad (Mecánica-Máquinas)
Madrid, 21 de octubre de 2002

Ø

A partir de la primera columna de A

Javier García de Jalón

ØA partir de la segunda fila de A

u1 j = a1 j

j = 1,2,..., n

a j1 = l j1 u11 ;

ETSII - Departamento de Matemática Aplicada
a la Ingeniería Industrial

a 2 j = l 21 u1 j + 1⋅ u2 j;
Ø

u2 j = a2 j − l 21 u1 j = a2 j −

u1 u 1 j
2

A partir de la segunda columna de A
a j 2 = l j1u 2 + l j 2 u 2 ;
1
2

Factorización directa de Crout (2)

j = 2,3,...n

l j1 =a 1 / u11
jl j2 =

1
(a j 2 − l j 1u1 2 )
u 22

j = 2,...,n

u11

j = 3,..., n

Factorización directa de Crout (3)
ETSII-UPM

A = LU;

q

 a11
a
 21
 a31

 a41


a12
a22
a32

a13
a23
a33

a42

a43

a14   1 0 0
a24  l 21 1 0
=
a34  l 31 l32 1

a44  l 41 l42 l 43


ETSII-UPM
q

u14 
u 24 

u 34 

u 44 


Fórmulasgenerales para la factorización de Crout: A= LU

=

Para la tercera fila y columna de A
Ø

Elemento de la diagonal
a 33 = l 31 u13 + l 32 u 23 + 1⋅ u33

Ø

Ø

q

u 33 = a 33 − l 31 u13 − l 32 u23

Las zonas rayadas en L y U son las zonas ya calculadas
Ø

i −1

u34 = a34 − l 3 1 1 4 − l 32 u24
u

a 43 = l4 1u1 3 + l4 2u2 3 + l4 3u3 3

k =1

Ø

Elementos de la 3ª columna
l43 =

i −1
k =1

Ø

a ji = ∑ l jk u ki + l ji u i
i
k =1

Crout para matrices simétricas

k =1

i −1

ui j = a ij − ∑ li k u j
k

j = i + 1,..., n

k =1

A partir de aji (j=i+1, …, n) se calculan los elementos de la columna i de L
i −1

u44 = a 44 − l 41 u14 − l42 u24 − l 43 u34

i− 1

uii = ai i − ∑ lik u ki

A partir de aij (j=i+1, …, n) se calculan los elementosde la fila i de U
a ij = ∑ li k u j + u ij
k

1
( a43 − l4 1u1 3 − l4 2u2 3 )
u33

Para el último elemento de la diagonal
a 44 = l4 1u1 4 + l42 u24 + l 43 u34 + 1 ⋅ u44

A partir de aii se calcula el elemento de la diagonal uii
a ii = ∑ li k u i + ui i
k

Resto de los elementos de la 3ª fila
a 34 = l31 u14 + l32u 24 + u34

q

0   u11 u12 u13
0   0 u 22 u 23

0  0
0u 33

1  0
0
0


lji =

i −1
1

a ji − ∑ l j k uk i 
uii 

k =1


j = i +1,..., n

Crout para matrices simétricas (2)
ETSII-UPM

q

q
q

Si la matriz A es simétrica las expresiones de l ij y de uji coinciden,
excepto en que los elementos lij están divididos por los uii
Se puede escribir entonces A = LU = LDLT
Hay dos posibilidades para almacenar elresultado:
Ø
Ø

q

ETSII-UPM
q

Cálculo por filas
Ø
Ø

Almacenar U en su posición habitual incluyendo su diagonal, lo que permite
recuperar L fácilmente
Almacenar D en la diagonal de la matriz resultado y L T en la mitad superior.
En este caso, las filas de U se guardan ya divididas por el elemento de la
diagonal

La parte rayada está ya calculada
El cálculo de los elementos de lafila i recuerda al producto escalar de la
columna i por la columna j, excepto que cada sumando está dividido por el
elemento de la diagonal. Estas divisiones restan eficiencia a los cálculos
i −1
−1
i
i− 1 2
u
u
i
j
d ii = aii − ∑ lik uki = aii − ∑ ki uki =aii − ∑ ki
k =1
k =1ukk
k =1 ukk
i −1

i −1

k =1

k =1

uij = aij − ∑ l ik ukj = aij − ∑

uki ukj
ukk

j = i +...