Clase No.
7:
Matrices definidas positivas
Matrices simétricas
MAT–251 Dr. Alonso Ramírez Manzanares
Depto. de Matemáticas
Univ. de Guanajuato
e-mail: alram@ cimat.mx
web: http://www.cimat.mx/salram/met_num/
Dr. Joaquín Peña Acevedo
CIMAT A.C.
e-mail: joaquin@ cimat.mx
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 1 / 16
Matrices diagonalmente dominantes
Sea A = [aij ] ∈ Rn×n . Se dice que A es diagonalmente dominante si
n
X
|aii | ≥ |aij |.
j=1
j6=i
Además, se dice que es estrictamente diagonal dominante, si la desigualdad
se cumple de manera estricta.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 2 / 16
Matrices tridiagonales (I)
Ax = d
donde A ∈ Rn tal que
b1 c1 0 ··· 0 0 0
a2
b2 c2 ··· 0 0 0
0
a3 b3 ··· 0 0 0
. .. .. .. .. .. ..
A = .. ,
. . . . . .
0
0 0 ··· bn−2 cn−2 0
0 0 0 ··· an−1 bn−1 cn−1
0 0 0 ··· 0 an bn
Si definimos
ā1 = 0, ¯ 1 = b1 ,
b c̄1 = c1 , ¯ 1 = d1 ,
d
¯n = b
b ¯ n−1 bn − an c̄n−1 , ¯n = b
d ¯ n−1 dn − an d
¯ n−1 .
entonces
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 3 / 16
Matrices tridiagonales (II)
¯n
d
xn =
¯n
b
¯ i − c̄i xi+1
d
xi = i = n − 1, ..., 1
¯i
b
¯i
b = ¯ i−1 bi − ai c̄i−1
b
c̄i = ¯ i−1 ci
b
¯i
d = ¯ i−1 di − ai d
b ¯ i−1
¯ i es esencial.
La hipótesis de que podemos dividir entre b
Una condición suficiente es que la matriz sea estrictamente diagonal
dominante, es decir,
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 4 / 16
Matrices tridiagonales (III)
|b1 | > |c1 |, |bn | > |an |, |bi | > |ai | + |ci | i = 1, 2, ..., n,
¯ i 6= 0:
Esto garantiza que b
¯ 1 | = |b1 | > |c1 | ≥ 0. Supongamos que
Tenemos que |b
¯ i | > |c̄i | ≥ 0
|b para i = 1, ..., k < n.
Entonces
¯ k+1 |
|b = ¯ k bk+1 − ak+1 c̄k | ≥ |b
|b ¯ k | |bk+1 | − |ak+1 | |c̄k |
> ¯
|bk |(|ak+1 | + |ck+1 |) − |ak+1 | |c̄k | = |ak+1 |(|b¯ k | − |c̄k |) + |b
¯ k ||ck+1 |
= ¯ k | − |c̄k |) + |c̄k+1 | ≥ 0
|ak+1 |(|b
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 5 / 16
Matrices simétricas definidas positivas (I)
Sea A = [aij ] ∈ Rn×n .
La matriz A es simétrica si A = A> .
La matriz A es definida positiva si para todo x 6= 0 se tiene que
x > Ax > 0.
Notación: con A > 0 indicamos que la matriz es definida positiva.
Usamos s.d.p. para indicar que una matriz es simétrica y definida positiva.
Decimos que H es una submatriz principal de A si es una submatriz
cuadrada formada con las entradas alrededor de la diagonal principal:
H = A(j : k, j : k)
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 6 / 16
Matrices simétricas definidas positivas (II)
Proposición
Las siguientes proposiciones son equivalentes:
1 Sea X no singular. A es s.d.p. si y sólo si X > AX es s.d.p.
2 Si A es s.d.p. y H es cualquier submatriz principal de A, entonces H es
s.d.p.
3 A es s.d.p. si y sólo si A es simétrica y todos sus eigenvalores son
positivos.
4 Si A es s.d.p., entonces aii > 0 y maxij |aij | = maxi aii > 0.
5 A es s.d.p. si y sólo si existe una única matriz triangular inferior no
singular L, con entradas positivas en la diagonal, tal que A = LL> .
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 7 / 16
Matrices simétricas definidas positivas (III)
Para demostrar (1), considerar el vector Xx.
Para demostrar (2), empezar con H = A(1 : k, 1 : k).
Para demostrar (4), para la primera parte, tomar un vector canónico ei y
calcular ei> Aei . Para la segunda parte. Suponer que |aki | = maxij |aij | con
k 6= l y construir el vector x = ek − sgn(akl )el .
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 8 / 16
Factorización LDL>
Sea A una matriz no singular y simétrica.
Si A = LU, entonces,
LU = A = A> = (LU)> = U> L>
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 9 / 16
Factorización LDL>
Sea A una matriz no singular y simétrica.
Si A = LU, entonces,
LU = A = A> = (LU)> = U> L>
Como L y U son no singulares, tenemos
U(L> )−1 = L−1 U
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 9 / 16
Factorización LDL>
Sea A una matriz no singular y simétrica.
Si A = LU, entonces,
LU = A = A> = (LU)> = U> L>
Como L y U son no singulares, tenemos
U(L> )−1 = L−1 U
Como la matriz del miembro izquierdo es triangular superior y la del
miembro derecho es triangular inferior, se debe tener que la matriz es
diagonal. Digamos que U(L> )−1 = D, y
A = LU = LDL> .
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 9 / 16
Algoritmo para la factorización LDL> (I)
Sea L = [lij ] y D = diag(d1 , ..., dn ). Entonces
min{i,j}
X
aij = lik dk ljk .
k=1
Supongamos que j ≤ i, entonces
j
X j−1
X
aij = lik dk ljk = lik dk ljk + lij dj ljj
k=1 k=1
j−1
X
= lik dk ljk + lij dj .
k=1
En particular, para j = i.
i−1
X
aii = l2ik dk + di
k=1
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 10 / 16
Algoritmo para la factorización LDL> (II)
Esto es,
i−1
X
di = aii − l2ik dk
k=1
En particular, d1 = a11 .
Ahora, puesto que 1 ≤ j < i ≤ n,
j−1
X
aij = lik dk ljk + lij dj .
k=1
podemos obtener lij :
j−1
1 X
lij = aij − lik dk ljk
dj k=1
Para j = 1, tenemos
ai1
li1 = i = 2, ..., n.
d1
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 11 / 16
Algoritmo para la factorización LDL> (III)
Algoritmo LDL>
Dada A = [aij ] simétrica, calcular:
1: for j = 1, ..., n do
2: lii = 1;
j−1
X
3: dj = ajj − l2jk dk ;
k=1
4: for i = j + 1, ..., n do
5: lji = 0
j−1
1 X
6: lij = aij − lik dk ljk
dj k=1
7: end for
8: end for
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 12 / 16
Ejemplo de factorización LDL> (I)
4 3 2 1
3 3 2 1
A=
2
2 2 1
1 1 1 1
Esta matriz tiene la siguiente factorización LU:
1 0 0 0 4 3 2 1
3/ 4 1 0 0 0 3/ 4 1/ 2 1/ 4
A=
1/ 2 2/ 3 1 0 0 0 2/ 3 1/ 3
1/ 4 1/ 3 1/ 2 1 0 0 0 1/ 2
Determinar la factorización LDL> .
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 13 / 16
Factorización de Cholesky
La factorización de Cholesky es una consecuencia inmediata de lo anterior,
cuando la matriz A además de ser simétrica es definida positiva.
Proposición
Si A es una matriz real, simétrica y definida positiva, entonces tiene una
única factorización A = LL> , en la cual L es una matriz triangular inferior con
entradas positivas en la diagonal principal.
De lo anterior, tenemos que A = LDL> .
Podemos mostrar que D es definida positiva.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 14 / 16
Factorización de Cholesky
La factorización de Cholesky es una consecuencia inmediata de lo anterior,
cuando la matriz A además de ser simétrica es definida positiva.
Proposición
Si A es una matriz real, simétrica y definida positiva, entonces tiene una
única factorización A = LL> , en la cual L es una matriz triangular inferior con
entradas positivas en la diagonal principal.
De lo anterior, tenemos que A = LDL> .
Podemos mostrar que D es definida positiva.
Por tanto, las entradas en la diagonal de D son positivas, y podemos definir
p p
D1/ 2 = diag( d1 , ..., dn ).
Entonces D1/ 2 D1/ 2 = D y
>
A = LDL> = A = LD1/ 2 D1/ 2 L> = L
bLb con b = LD1/ 2 .
L
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 14 / 16
Algoritmo de la factorización de Cholesky
Algoritmo LL>
Dada A = [aij ] simétrica, calcular:
1: for j = 1, ..., n do
v
j−1
u
u X
2: l = ta −
jj jj l2 ; jk
k=1
3: for i = j + 1, ..., n do
j−1
1 X
4: lij = aij − lik ljk
ljj k=1
5: end for
6: end for
Puesto que ljj > 0, entonces
j−1
X
ajj > l2jk ≥ l2jk k≤j
k=1
p
Esto es, |ljk | ≤ ajj . Por tanto, todo elemento de L está acotado por la raíz
cuadrada del elemento correspondiente en la diagonal de A.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 15 / 16
Equivalencias
Proposición
Las siguientes proposiciones son equivalentes:
1 A es s.d.p.
2 El proceso de eliminación Gaussiana se puede realizar sin intercambiar
las filas del sistema Ax = b.
3 A se puede factorizar como LL> , donde L es triangular inferior con
entradas positivas en la diagonal.
4 A se puede factorizar como LDL> , donde L es triangular inferior con 1’s
en la diagonal y D > 0 diagonal.
Joaquín Peña (CIMAT) Métodos Numéricos (MAT–251) 29.08.2012 16 / 16
