Aproximación valores y vectores propios
Catalina Domínguez,
Universidad del Norte
Doctorado en Ingeniería
Semestre II de 2014
Semana 10
Página 1 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de las potencias
Es adecuado para aproximar el valor propio extremo (en modulo) de una
matriz, junto con su vector propio asociado.
Sea A ∈ Rn×n una matriz diagonalizable y X la matriz de los vectores
propios (derecha). Supongamos
|λ1| > |λ2| ≥ |λ3| ≥ · · · |λn|
donde λ1 tiene multiplicidad 1.
Página 2 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias
Sea x0 ∈ Rn (cualquier vector), entonces x0 = c1v1 + c2v2 + · · · + cnvn
donde {v1,v2, . . . ,vn} es un conjunto de n vectores propios l.i.
entonces
Ax0 = c1Av1 + c2Av2 + · · ·+ cnAvn
= c1λ1v1 + c2λ2v2 + · · ·+ cnλnvn
AAx0 = c1λ21v1 + c2λ
22v2 + · · ·+ cnλ
2nvn
... =...
Amx0 = c1λm
1 v1 + c2λm
2 v2 + · · ·+ cnλm
n vn
Dividiendo entre λm1
Amx0
λm1
= c1v1 + c2λm2
λm1
v2 + · · ·+ cnλmn
λm1
vn
Cuandom → ∞
(λ2
λ1
)m
→ 0, . . . ,(λn
λ1
)m
→ 0
puesto que
|λ2/λ1| < 1, . . . , |λn/λ1| < 1.Entonces, sim → ∞
Amx0
λm1
→ c1v1
Página 3 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
continuación ...
Recuerde: se desea aproximar λ1 y v1
Página 4 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
continuación ...
Recuerde: se desea aproximar λ1 y v1
Sea y ∈ Rn cualquier vector con y 6= 0. Tenemos
Am+1x0
λm1
· y ≈ c1v1 · y,Amx0
λm1
· y ≈ c1v1 · y
entonces
Página 4 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
continuación ...
Recuerde: se desea aproximar λ1 y v1
Sea y ∈ Rn cualquier vector con y 6= 0. Tenemos
Am+1x0
λm1
· y ≈ c1v1 · y,Amx0
λm1
· y ≈ c1v1 · y
entonces
Am+1x0
λm+1
1
· y ≈Amx0
λm1
· y ⇒ λ1 =λm+1
1
λm1
=Am+1x0 · y
Amx0 · y
Página 4 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
continuación ...
Recuerde: se desea aproximar λ1 y v1
Sea y ∈ Rn cualquier vector con y 6= 0. Tenemos
Am+1x0
λm1
· y ≈ c1v1 · y,Amx0
λm1
· y ≈ c1v1 · y
entonces
Am+1x0
λm+1
1
· y ≈Amx0
λm1
· y ⇒ λ1 =λm+1
1
λm1
=Am+1x0 · y
Amx0 · y
Tomando y = Amx0
Página 4 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
continuación ...
Recuerde: se desea aproximar λ1 y v1
Sea y ∈ Rn cualquier vector con y 6= 0. Tenemos
Am+1x0
λm1
· y ≈ c1v1 · y,Amx0
λm1
· y ≈ c1v1 · y
entonces
Am+1x0
λm+1
1
· y ≈Amx0
λm1
· y ⇒ λ1 =λm+1
1
λm1
=Am+1x0 · y
Amx0 · y
Tomando y = Amx0
λ1 =Am+1x0 · y
Amx0 · y=
Am+1x0 ·Amx0
Amx0 · Amx0
=AAmx0 ·A
mx0
Amx0 · Amx0
Página 4 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
continuación ...
Recuerde: se desea aproximar λ1 y v1
Sea y ∈ Rn cualquier vector con y 6= 0. Tenemos
Am+1x0
λm1
· y ≈ c1v1 · y,Amx0
λm1
· y ≈ c1v1 · y
entonces
Am+1x0
λm+1
1
· y ≈Amx0
λm1
· y ⇒ λ1 =λm+1
1
λm1
=Am+1x0 · y
Amx0 · y
Tomando y = Amx0
λ1 =Am+1x0 · y
Amx0 · y=
Am+1x0 ·Amx0
Amx0 · Amx0
=AAmx0 ·A
mx0
Amx0 · Amx0
Cociente de Rayleigh
Si x es un vector propio, su
correspondiente valor propio es
λ =Ax · x
x · x
Página 4 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
continuación ...
Recuerde: se desea aproximar λ1 y v1
Sea y ∈ Rn cualquier vector con y 6= 0. Tenemos
Am+1x0
λm1
· y ≈ c1v1 · y,Amx0
λm1
· y ≈ c1v1 · y
entonces
Am+1x0
λm+1
1
· y ≈Amx0
λm1
· y ⇒ λ1 =λm+1
1
λm1
=Am+1x0 · y
Amx0 · y
Tomando y = Amx0
λ1 =Am+1x0 · y
Amx0 · y=
Am+1x0 ·Amx0
Amx0 · Amx0
=AAmx0 ·A
mx0
Amx0 · Amx0
v1 ≈ Amx0, λ1 ≈AAm
x0·Amx0
Amx0·Amx0
Cociente de Rayleigh
Si x es un vector propio, su
correspondiente valor propio es
λ =Ax · x
x · x
Página 4 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Así
λ1 ≈AAmx0 · A
mx0
Amx0 · Amx0
v1 ≈ Amx0 = qm
Página 5 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Así
λ1 ≈AAmx0 · A
mx0
Amx0 · Amx0
v1 ≈ Amx0 = qm
Si garantizamos ||qm|| = 1 es decir Amx0 ·Amx0 = 1 entonces
Página 5 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Así
λ1 ≈AAmx0 · A
mx0
Amx0 · Amx0
v1 ≈ Amx0 = qm
Si garantizamos ||qm|| = 1 es decir Amx0 ·Amx0 = 1 entonces
λ1 ≈ AAmx0 · Amx0, v1 ≈
Amx0
||Amx0||
Página 5 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Así
λ1 ≈AAmx0 · A
mx0
Amx0 · Amx0
v1 ≈ Amx0 = qm
Si garantizamos ||qm|| = 1 es decir Amx0 ·Amx0 = 1 entonces
λ1 ≈ AAmx0 · Amx0, v1 ≈
Amx0
||Amx0||
Algoritmo
Dado q0 ∈ Rn con ‖q0‖ = 1, calcular
Página 5 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Así
λ1 ≈AAmx0 · A
mx0
Amx0 · Amx0
v1 ≈ Amx0 = qm
Si garantizamos ||qm|| = 1 es decir Amx0 ·Amx0 = 1 entonces
λ1 ≈ AAmx0 · Amx0, v1 ≈
Amx0
||Amx0||
Algoritmo
Dado q0 ∈ Rn con ‖q0‖ = 1, calcular
1 zk = Aqk−1
Página 5 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Así
λ1 ≈AAmx0 · A
mx0
Amx0 · Amx0
v1 ≈ Amx0 = qm
Si garantizamos ||qm|| = 1 es decir Amx0 ·Amx0 = 1 entonces
λ1 ≈ AAmx0 · Amx0, v1 ≈
Amx0
||Amx0||
Algoritmo
Dado q0 ∈ Rn con ‖q0‖ = 1, calcular
1 zk = Aqk−1
2 qk = zk
‖zk‖(Normalización)
Página 5 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Así
λ1 ≈AAmx0 · A
mx0
Amx0 · Amx0
v1 ≈ Amx0 = qm
Si garantizamos ||qm|| = 1 es decir Amx0 ·Amx0 = 1 entonces
λ1 ≈ AAmx0 · Amx0, v1 ≈
Amx0
||Amx0||
Algoritmo
Dado q0 ∈ Rn con ‖q0‖ = 1, calcular
1 zk = Aqk−1
2 qk = zk
‖zk‖(Normalización)
3 λk = qTkAqk = (Aqk) · qk
Página 5 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de las potencias inversa
Aproxima un valor propio de una matriz A ∈ Cn×n más proximo a un
numero µ /∈ σ(A) dado.
Página 6 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de las potencias inversa
Aproxima un valor propio de una matriz A ∈ Cn×n más proximo a un
numero µ /∈ σ(A) dado. El método consiste en aplicar el método de
potencias a la matriz
(Mµ)−1 = (A− µI)−1
Página 6 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de las potencias inversa
Aproxima un valor propio de una matriz A ∈ Cn×n más proximo a un
numero µ /∈ σ(A) dado. El método consiste en aplicar el método de
potencias a la matriz
(Mµ)−1 = (A− µI)−1
• Los valores propios de Mµ son
κi = λi − µ
Página 6 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de las potencias inversa
Aproxima un valor propio de una matriz A ∈ Cn×n más proximo a un
numero µ /∈ σ(A) dado. El método consiste en aplicar el método de
potencias a la matriz
(Mµ)−1 = (A− µI)−1
• Los valores propios de Mµ son
κi = λi − µ
• Los valores propios de M−1µ son
ξi = (λi − µ)−1
Página 6 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de las potencias inversa
Aproxima un valor propio de una matriz A ∈ Cn×n más proximo a un
numero µ /∈ σ(A) dado. El método consiste en aplicar el método de
potencias a la matriz
(Mµ)−1 = (A− µI)−1
• Los valores propios de Mµ son
κi = λi − µ
• Los valores propios de M−1µ son
ξi = (λi − µ)−1
• Existe un m tal que
|λm − µ| < |λi − µ|
Página 6 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de las potencias inversa
Aproxima un valor propio de una matriz A ∈ Cn×n más proximo a un
numero µ /∈ σ(A) dado. El método consiste en aplicar el método de
potencias a la matriz
(Mµ)−1 = (A− µI)−1
• Los valores propios de Mµ son
κi = λi − µ
• Los valores propios de M−1µ son
ξi = (λi − µ)−1
• Existe un m tal que
|λm − µ| < |λi − µ|
Se requiere que λm tenga multiplicidad 1.
Página 6 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1.
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1
2 qk =z
‖zk‖
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1
2 qk =z
‖zk‖
3 λk = qTkAqk .
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1
2 qk =z
‖zk‖
3 λk = qTkAqk . Se calcula el valor propio asociado a A y no a
(A− µI)−1 mediante el cociente de Rayleigh
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1
2 qk =z
‖zk‖
3 λk = qTkAqk . Se calcula el valor propio asociado a A y no a
(A− µI)−1 mediante el cociente de Rayleigh
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1
2 qk =z
‖zk‖
3 λk = qTkAqk . Se calcula el valor propio asociado a A y no a
(A− µI)−1 mediante el cociente de Rayleigh
• Los vectores propios de M−1µ son los mismos vectores propios de A, sin
embargo los valores propios correspondientes son distintos.
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1
2 qk =z
‖zk‖
3 λk = qTkAqk . Se calcula el valor propio asociado a A y no a
(A− µI)−1 mediante el cociente de Rayleigh
• Los vectores propios de M−1µ son los mismos vectores propios de A, sin
embargo los valores propios correspondientes son distintos.
• Se debe solucionar el sistema (A− µI)zk = qk−1.
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método de potencias inversa: Algoritmo
Dado q0 de norma 1, calcular
1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1
2 qk =z
‖zk‖
3 λk = qTkAqk . Se calcula el valor propio asociado a A y no a
(A− µI)−1 mediante el cociente de Rayleigh
• Los vectores propios de M−1µ son los mismos vectores propios de A, sin
embargo los valores propios correspondientes son distintos.
• Se debe solucionar el sistema (A− µI)zk = qk−1.
• Si µ = 0, el método calcula el valor propio mas pequeño.
Página 7 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
function [lambda,q,iter,res] = InversePower(A,z0,mu,tol, nmax)
% Calcula el vector propio y valor propio mas cercano a MU de la
% matriz A
q = z0/norm(z0);
res = tol +1;
iter = 0;
M = A-mu*eye(size(A,1));
while res>tol && iter <= nmax
iter = iter +1;
z = M\q;
q = z/ norm(z); % aprox. vector propio de M^{-1}_mu
aux = A*q;
lambda = q’*aux; % aprox. valor propio de A
res = norm(aux-lambda*q);
end
end
Página 8 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Matrices simétricas: calculo de valores propios
Dado un par j < k y φ ∈ R la matriz
U =
Página 9 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Matrices simétricas: calculo de valores propios
Dado un par j < k y φ ∈ R la matriz
U =
1. . .
cos(φ) − sin(φ). . .
sin(φ) cos(φ). . .
1
Página 9 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Matrices simétricas: calculo de valores propios
Dado un par j < k y φ ∈ R la matriz
U =fila j
fila k
1. . .
cos(φ) − sin(φ). . .
sin(φ) cos(φ). . .
1
Página 9 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Matrices simétricas: calculo de valores propios
Dado un par j < k y φ ∈ R la matriz
U =fila j
fila k
columna j columna k
1. . .
cos(φ) − sin(φ). . .
sin(φ) cos(φ). . .
1
Página 9 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Matrices simétricas: calculo de valores propios
Dado un par j < k y φ ∈ R la matriz
U =fila j
fila k
columna j columna k
1. . .
cos(φ) − sin(φ). . .
sin(φ) cos(φ). . .
1
U describe la rotación en el plano xjxk, y además es unitaria UTU = Icoincide con la identidad excepto en ujj, ukk .
Página 9 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Teorema
Si A es simétrica y real, entonces B = UTAU es real y simétrica y
bjj = ajj cos2 φ+ ajk sin(2φ) + akk sin
2 φ,
bkk = ajj sin2 φ− ajk sin(2φ) + akk cos
2 φ,
bjk = bkj = ajk cos 2φ+1
2(akk − ajj) sin(2φ),
bij = bji = aij cosφ+ aik sinφ, i 6= j, k
bik = bki = −aij sinφ+ aik cosφ, i 6= j, k
bil = ail, i, l 6= j, k
es decir, B y A no coinciden en la filas y columnas j y k.
Página 10 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Teorema
Si A es simétrica y real, entonces B = UTAU es real y simétrica y
bjj = ajj cos2 φ+ ajk sin(2φ) + akk sin
2 φ,
bkk = ajj sin2 φ− ajk sin(2φ) + akk cos
2 φ,
bjk = bkj = ajk cos 2φ+1
2(akk − ajj) sin(2φ),
bij = bji = aij cosφ+ aik sinφ, i 6= j, k
bik = bki = −aij sinφ+ aik cosφ, i 6= j, k
bil = ail, i, l 6= j, k
es decir, B y A no coinciden en la filas y columnas j y k.
[
cos(φ) sin(φ)− sin(φ) cos(φ)
] [
ajj ajkakj akk
] [
cos(φ) − sin(φ)− sin(φ) cos(φ)
]
=
[
bjj bjkbkj bkk
]
Página 10 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Teorema
Para
tan(2φ) =2ajk
ajj − akk, ajj 6= akk
φ =π
4, ajj = akk
Página 11 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Teorema
Para
tan(2φ) =2ajk
ajj − akk, ajj 6= akk
φ =π
4, ajj = akk
las componentes
bjk = bkj = 0
N(B)2 = N(A)2 − 2a2jk
Página 11 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Teorema
Para
tan(2φ) =2ajk
ajj − akk, ajj 6= akk
φ =π
4, ajj = akk
las componentes
bjk = bkj = 0
N(B)2 = N(A)2 − 2a2jk
N(A) :=(
∑
j,k=1
j 6=k|aij|
2
)1/2
Página 11 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Teorema
Para
tan(2φ) =2ajk
ajj − akk, ajj 6= akk
φ =π
4, ajj = akk
las componentes
bjk = bkj = 0
N(B)2 = N(A)2 − 2a2jk
N(A) :=(
∑
j,k=1
j 6=k|aij|
2
)1/2es
una medida de la desviación de Ade la matriz diagonal.
Página 11 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Teorema
Para
tan(2φ) =2ajk
ajj − akk, ajj 6= akk
φ =π
4, ajj = akk
las componentes
bjk = bkj = 0
N(B)2 = N(A)2 − 2a2jk
N(A) :=(
∑
j,k=1
j 6=k|aij|
2
)1/2es
una medida de la desviación de Ade la matriz diagonal.
Para matrices normales
(A∗A = AA∗)
n∑
j=1
|λj |2 =
n∑
j=1
|ajj|+ (N(A))2
Página 11 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Teorema
Para
tan(2φ) =2ajk
ajj − akk, ajj 6= akk
φ =π
4, ajj = akk
las componentes
bjk = bkj = 0
N(B)2 = N(A)2 − 2a2jk
N(A) :=(
∑
j,k=1
j 6=k|aij|
2
)1/2es
una medida de la desviación de Ade la matriz diagonal.
Para matrices normales
(A∗A = AA∗)
n∑
j=1
|λj |2 =
n∑
j=1
|ajj|+ (N(A))2
Idea principal
EL método de Jacobi consiste en reducir N(A) sucesivamente mediante
matrices de rotación, de tal manera que su limite sea una matriz diagonal,
cuyos valores propios son las entradas de la diagonal.Página 11 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Am+1 = U∗
mAmUm
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Am+1 = U∗
mAmUm
= U∗
mU∗
m−1Am−1Um−1Um
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Am+1 = U∗
mAmUm
= U∗
mU∗
m−1Am−1Um−1Um
= U∗
mU∗
m−1 · · ·U0AU0 · · ·Um−1Um
= Q∗
mAQm
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Am+1 = U∗
mAmUm
= U∗
mU∗
m−1Am−1Um−1Um
= U∗
mU∗
m−1 · · ·U0AU0 · · ·Um−1Um
= Q∗
mAQm
En cada iteracion m
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Am+1 = U∗
mAmUm
= U∗
mU∗
m−1Am−1Um−1Um
= U∗
mU∗
m−1 · · ·U0AU0 · · ·Um−1Um
= Q∗
mAQm
En cada iteracion m
1 Am y A tienen los mismos valores
propios,
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Am+1 = U∗
mAmUm
= U∗
mU∗
m−1Am−1Um−1Um
= U∗
mU∗
m−1 · · ·U0AU0 · · ·Um−1Um
= Q∗
mAQm
En cada iteracion m
1 Am y A tienen los mismos valores
propios,
2 Cuandom → ∞, Am → D donde Des una matriz diagonal, cuyas
entradas son los valores propios de A.
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Am+1 = U∗
mAmUm
= U∗
mU∗
m−1Am−1Um−1Um
= U∗
mU∗
m−1 · · ·U0AU0 · · ·Um−1Um
= Q∗
mAQm
En cada iteracion m
1 Am y A tienen los mismos valores
propios,
2 Cuandom → ∞, Am → D donde Des una matriz diagonal, cuyas
entradas son los valores propios de A.
3 El par j, k corresponden a la posición
donde se encuentra la mayor
componente (en modulo) de la matriz
Am−1.
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Metodo de Jacobi: Idea principal
Consiste en reducir N(A) sucesivamente mediante matrices de rotación, de
tal manera que su limite sea una matriz diagonal, cuyos valores propios son
las entradas de la diagonal.
A0 = A
A1 = U∗
0A0U0
...
Am+1 = U∗
mAmUm
= U∗
mU∗
m−1Am−1Um−1Um
= U∗
mU∗
m−1 · · ·U0AU0 · · ·Um−1Um
= Q∗
mAQm
En cada iteracion m
1 Am y A tienen los mismos valores
propios,
2 Cuandom → ∞, Am → D donde Des una matriz diagonal, cuyas
entradas son los valores propios de A.
3 El par j, k corresponden a la posición
donde se encuentra la mayor
componente (en modulo) de la matriz
Am−1.
4 Las columnas Qm son una
aproximación de los vectores propios.
Página 12 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Convergencia
1
Página 13 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Convergencia
1
N(Am) ≤ qmN(A0),
Página 13 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Convergencia
1
N(Am) ≤ qmN(A0), q :=(
1−2
n(n− 1)
)1/2< 1,
Página 13 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Convergencia
1
N(Am) ≤ qmN(A0), q :=(
1−2
n(n− 1)
)1/2< 1,
por tanto,
N(Am) → cuandom → ∞
Página 13 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Convergencia
1
N(Am) ≤ qmN(A0), q :=(
1−2
n(n− 1)
)1/2< 1,
por tanto,
N(Am) → 0 cuandom → ∞
2 Cuando n es grande q ≈ 1, en decir la convergencia del método de
Jacobi es baja, sin embargo,
|λj − ajj,m| ≤ N(Am), j = 1, . . . , n
Página 13 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Convergencia
1
N(Am) ≤ qmN(A0), q :=(
1−2
n(n− 1)
)1/2< 1,
por tanto,
N(Am) → 0 cuandom → ∞
2 Cuando n es grande q ≈ 1, en decir la convergencia del método de
Jacobi es baja, sin embargo,
|λj − ajj,m| ≤ N(Am), j = 1, . . . , n
3 Método de Jacobi cíclico: las componentes no-diagonales son anuladas
siguiendo el orden
(1, 2), . . . , (1, n)(2, 3), . . . , (2, n), (3, 4) . . . , (n− 1, n)
Página 13 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Calculo de valores propios: Método QR
Idea principal
Reducir la matriz A mediante transformaciones, a una matriz cuyas calculo
de valores propios es mucho más fácil que usando la matriz A.
Página 14 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Calculo de valores propios: Método QR
Idea principal
Reducir la matriz A mediante transformaciones, a una matriz cuyas calculo
de valores propios es mucho más fácil que usando la matriz A.El problema se reduce a encontrar una matriz unitaria U (U∗U = I) tal que
T = U∗AU
siendo T una matriz triangular superior.
Página 14 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Calculo de valores propios: Método QR
Idea principal
Reducir la matriz A mediante transformaciones, a una matriz cuyas calculo
de valores propios es mucho más fácil que usando la matriz A.El problema se reduce a encontrar una matriz unitaria U (U∗U = I) tal que
T = U∗AU
siendo T una matriz triangular superior.
Principio teórico
Sea A ∈ Rn×n, dada una matriz ortogonal Q ∈ R
n×n, considere
T = QTAQ
Página 14 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Calculo de valores propios: Método QR
Idea principal
Reducir la matriz A mediante transformaciones, a una matriz cuyas calculo
de valores propios es mucho más fácil que usando la matriz A.El problema se reduce a encontrar una matriz unitaria U (U∗U = I) tal que
T = U∗AU
siendo T una matriz triangular superior.
Principio teórico
Sea A ∈ Rn×n, dada una matriz ortogonal Q ∈ R
n×n, considere
T = QTAQ entonces es posible descomponer T = Q̃R
Página 14 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Calculo de valores propios: Método QR
Idea principal
Reducir la matriz A mediante transformaciones, a una matriz cuyas calculo
de valores propios es mucho más fácil que usando la matriz A.El problema se reduce a encontrar una matriz unitaria U (U∗U = I) tal que
T = U∗AU
siendo T una matriz triangular superior.
Principio teórico
Sea A ∈ Rn×n, dada una matriz ortogonal Q ∈ R
n×n, considere
T = QTAQ entonces es posible descomponer T = Q̃R
donde R es una matriz triangular superior y Q̃ una matriz ortogonal.
Página 14 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk =
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk Tk−1 = QT
k−1Tk−2 Qk−1
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk Tk−1 = QT
k−1Tk−2 Qk−1
= QT
kQT
k−1Tk−2 Qk−1 Qk
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk Tk−1 = QT
k−1Tk−2 Qk−1
= QT
kQT
k−1Tk−2 Qk−1 Qk
...
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk Tk−1 = QT
k−1Tk−2 Qk−1
= QT
kQT
k−1Tk−2 Qk−1 Qk
...
= QT
kQT
k−1 · · ·QT
0 AQ0 · · · Qk−1 Qk
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk Tk−1 = QT
k−1Tk−2 Qk−1
= QT
kQT
k−1Tk−2 Qk−1 Qk
...
= QT
kQT
k−1 · · ·QT
0 AQ0 · · · Qk−1 Qk
= (Q0 · · · Qk−1 Qk)TAQ0 · · · Qk−1 Qk
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk Tk−1 = QT
k−1Tk−2 Qk−1
= QT
kQT
k−1Tk−2 Qk−1 Qk
...
= QT
kQT
k−1 · · ·QT
0 AQ0 · · · Qk−1 Qk
= (Q0 · · · Qk−1 Qk)TAQ0 · · · Qk−1 Qk
1 Tk y A son matrices semejantes, es
decir, tienen los mismos valores
propios.
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk Tk−1 = QT
k−1Tk−2 Qk−1
= QT
kQT
k−1Tk−2 Qk−1 Qk
...
= QT
kQT
k−1 · · ·QT
0 AQ0 · · · Qk−1 Qk
= (Q0 · · · Qk−1 Qk)TAQ0 · · · Qk−1 Qk
1 Tk y A son matrices semejantes, es
decir, tienen los mismos valores
propios.
2 Si A tiene valores propios reales (de
modulo distintos), Tk converge a una
matriz triangular superior.
Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Método Iterativo QR
Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R
n×n
1 se calcula
T0 = QT0 AQ0
2 Para k = 1, . . . , hasta la convergencia• Dada Tk−1, determinar Qk, Rk tal que QkRk = Tk−1
• tomamos Tk = RkQk
Observe
Tk = RkQk = Q−1
kTk−1 Qk
= QT
k Tk−1 Qk Tk−1 = QT
k−1Tk−2 Qk−1
= QT
kQT
k−1Tk−2 Qk−1 Qk
...
= QT
kQT
k−1 · · ·QT
0 AQ0 · · · Qk−1 Qk
= (Q0 · · · Qk−1 Qk)TAQ0 · · · Qk−1 Qk
1 Tk y A son matrices semejantes, es
decir, tienen los mismos valores
propios.
2 Si A tiene valores propios reales (de
modulo distintos), Tk converge a una
matriz triangular superior.
3 SiA tienes valores propios complejos,
Tk no converge a una matriz
triangular superior.Página 15 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
q2 = x2 − proyq1x2q1
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
q2 = x2 − proyq1x2q1
= x1 −q1 · x2
q1 · q1
q1
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
q2 = x2 − proyq1x2q1
= x1 −q1 · x2
q1 · q1
q1
qk+1 = xk+1 −k
∑
i=1
qi · xk+1
qi · qiqi
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
q2 = x2 − proyq1x2q1
= x1 −q1 · x2
q1 · q1
q1
qk+1 = xk+1 −k
∑
i=1
qi · xk+1
qi · qiqi
Denotando a a1, . . . ,an los vectores
columna de A, tomamos
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
q2 = x2 − proyq1x2q1
= x1 −q1 · x2
q1 · q1
q1
qk+1 = xk+1 −k
∑
i=1
qi · xk+1
qi · qiqi
Denotando a a1, . . . ,an los vectores
columna de A, tomamos
q̃1 =a1
‖a1‖,
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
q2 = x2 − proyq1x2q1
= x1 −q1 · x2
q1 · q1
q1
qk+1 = xk+1 −k
∑
i=1
qi · xk+1
qi · qiqi
Denotando a a1, . . . ,an los vectores
columna de A, tomamos
q̃1 =a1
‖a1‖,
q̃k+1 =qk+1
‖qk+1‖
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
q2 = x2 − proyq1x2q1
= x1 −q1 · x2
q1 · q1
q1
qk+1 = xk+1 −k
∑
i=1
qi · xk+1
qi · qiqi
Denotando a a1, . . . ,an los vectores
columna de A, tomamos
q̃1 =a1
‖a1‖,
q̃k+1 =qk+1
‖qk+1‖
qk+1 = ak+1 −k
∑
i=1
(q̃j ,ak+1)q̃j
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
Descomposición QR
Dado un conjunto de vectores l.i
x1, . . . ,xn se genera vectores
mutuamente ortogonales q1, . . . ,qn
mediante
q1 = x1
q2 = x2 − proyq1x2q1
= x1 −q1 · x2
q1 · q1
q1
qk+1 = xk+1 −k
∑
i=1
qi · xk+1
qi · qiqi
Denotando a a1, . . . ,an los vectores
columna de A, tomamos
q̃1 =a1
‖a1‖,
q̃k+1 =qk+1
‖qk+1‖
qk+1 = ak+1 −k
∑
i=1
(q̃j ,ak+1)q̃j
Debemos descomponer A como A = Q̃R̃. Puesto que Q̃−1 = Q̃T , la matriz
R puede calcularse fácilmente.
Página 16 Semana 10 23 de Octubre de 2014 Domínguez C., Prato
function [ EI,V,normT,i] = QRiteracion( A, nmax, tol)
% Realiza la iteracion QR para calculo de los vectores propios
% de una matriz A
T = A; % en este caso Q_0 = I
V = eye(size(A,1));
for i = 1: nmax
[Q,R] = qr(T);
T = R*Q;
V = V*Q;
normT = norm(T-triu(T),’fro’);
if normT <= tol
EI = diag(T);
return
end
end
EI = diag(T);
end
Página 17 Semana 10 23 de Octubre de 2014 Domínguez C., Prato