teorema de la descomposición LU

C´
alculo Num´erico II

Pr´
actica 1bis: Recordatorio de descomposiciones matriciales LU y Choleski

Descomposiciones matriciales LU y Choleski
Una matriz cuadrada A ∈ Mn×n (R) posee descomposici´on LU cuando existen matrices L, U ∈
Mn×n (R) triangular inferior (lower) y triangular superior (upper) respectivamente, tales que A = LU.
Tal descomposici´
on permite resolver de forma muy r´apidacualquier sistema compatible determinado
Ax = b a trav´es de dos algoritmos de bajada y subida:
LU x = b ⇔ [Lz = b & U x = z].
Los resultados conocidos de CNI respecto a la descomposici´on de tipo LU de una matriz cuadrada son:

Descomposici´
on LU
Teorema. Si los menores principales de una matriz A de dimensi´on n son no nulos entonces A admite
una descomposici´
on LU . Esta descomposici´on es u
´nicasi los elementos de la diagonal principal de L
son todos unos.
Una condici´
on suficiente para aplicar el resultado anterior es la siguiente:
Definici´
on. Sea A = (aij ) una matriz cuadrada n × n. Se dice que A es diagonalmente dominante en
sentido estricto si
n

|aii | >

|aij | para toda fila i = 1, ..., n.

(1)

j=1, j=i

Teorema. Sea A = (aij ) una matriz cuadrada n × n diagonalmentedominante en sentido estricto.
Entonces,
a) A es regular,
b) A admite una u
´nica factorizaci´
on LU de Doolittle.

C´
alculo efectivo LU
Para el c´
alculo efectivo de la factorizaci´on LU de una matriz dada, en la pr´actica se obtienen los
elementos de L y de U por identificaci´
on de forma recursiva, admitiendo que existe la factorizaci´
on.
As´ı, si
 a

a
...
a
a
11

 a21
 .
 .
 .

an−1,1
an11




=

l

l21
..
.

n−1,1

ln,1

0
1
..
.
ln−1,2
ln,2

...
...
...
...
...

12

a22
..
.
an−1,2
an2
0
0
..
.
1
ln,n−1

...

1,n−1

1n

a2,n−1
..
.

a2n
..
.

...
. . . an−1,n−1
...
an,n−1
u
0
11
0 0

.. 
 .
.   ..
0 0
1
0

u12
u22
..
.
0
0

an−1,n
an,n
...
...
...
...
...







u1,n−1
u2,n−1
..
.

u1n
u2n
..
.

un−1,n−1
0

un−1,n
un,n




,



identificando loselementos de la primera fila de A con los correspondientes de LU , y los de la primera
columna de A con los correspondientes de LU , obtenemos

 a1j = u1j , j = 1, ..., n,
a
 ai1 = li1 u11 ⇒ li1 = i1 , i = 2, ..., n.
u11
Dpto. Ecuaciones Diferenciales y An´
alisis Num´erico, Universidad de Sevilla

1

C´
alculo Num´erico II

Pr´
actica 1bis: Recordatorio de descomposiciones matriciales LU yCholeski

Identificando a continuaci´
on los elementos de la segunda fila de A con los correspondientes de LU , y
los de la segunda columna de A con los correspondientes de LU , obtenemos

 a2j = l21 u1j + u2j ⇒ u2j = a2j − l21 u1j , j = 2, ..., n,
 ai2 = li1 u12 + li2 u22 ⇒ li2 = 1 (ai2 − li1 u12 ), i = 3, ..., n.
u22
Y en general, si suponemos conocidas las k − 1 primeras filas de U y las k − 1primeras columnas de
L, entonces, identificando los elementos de la k-´esima fila de A con los correspondientes de LU , y los
de la k-´esima columna de A con los correspondientes de LU , obtenemos

akj = lk1 u1j + ... + lk,k−1 uk−1,j + ukj



k−1



 ⇒ ukj = akj −
lkr urj , j = k, ..., n,



r=1

aik = li1 u1k + ... + li,k−1 uk−1,k + lik ukk



k−1


1


lir urk , i = k + 1, ...,n.
a
−
⇒
l
=

ik
ik

ukk
r=1

Descomposici´
on de Choleski
Forzando un poco m´
as la factorizaci´on LU de una matriz, en casos especiales encontramos que
pueden elegirse L = U ∗ = B, es lo que se conoce como la factorizaci´on de Choleski para una matriz
cuadrada sim´etrica: A = BB ∗ . Que exista, a partir del Teorema de Doolittle, est´a intimamente relacionada con que en la expresi´
on A = LU =LDL∗ los elementos de la matriz diagonal D sean positivos,
lo que conduce a la siguiente definici´
on y siguientes resultados en CNI.
Definici´
on. Sea A = (aij ) una matriz n × n de coeficientes reales. Diremos que A es definida positiva
si
n

aij ui uj > 0,

para todo u ∈ Rn \ {0}.

(2)

i,j=1

Teorema. (Factorizaci´
on de Cholesky) Si A es una matriz n × n sim´etrica definida positiva, entonces...