Upload
jaime-salguerro
View
217
Download
0
Embed Size (px)
DESCRIPTION
Gracias.
Citation preview
Calculo de valores y vectores propios
Catalina Domínguez,
Universidad del Norte
Maestría en matemáticas
Semestre II de 2015
Semana 15
Página 1 Semana 15 11 de Noviembre de 2015 Domínguez
Reducción a una matriz de Hessenberg
Dada una matriz A ∈ Rn×n, reducir A a una matriz de Hessenberg
mediante el producto de matrices de Householder P(1)P(2) . . . P(n−2).
En paso k-ésimo consiste en calcular P(k), la cual anula las componentes
k + 2, . . . , n de la k-esima columna de A
Si n = 5 el proceso de reducción consiste en
• • • • •
• • • • •
• • • • •
• • • • •
• • • • •
−−→
P(1)
• • • • •
• • • • •
0 • • • •
0 • • • •
0 • • • •
−−→
P(2)
• • • • •
• • • • •
0 • • • •
0 0 • • •
0 0 • • •
−−→
P(3)
• • • • •
• • • • •
0 • • • •
0 0 • • •
0 0 0 • •
Página 2 Semana 15 11 de Noviembre de 2015 Domínguez
Método de Householder
Dada A ∈ Rn×n
1 A(0) := A
2 Para k = 1, . . . , n − 2• A(k) = PT
(k)A(k−1)P(k) donde
P(k) =
[Ik 00 R(n−k)
]
, R(n−k) = In−k − 2w
(k)w
(k)T
‖w(k)‖2,
w(k) = x(n−k)±‖x(n−k)‖ e
(n−k)1 , x : k-esimo vector columna de A(k−1).
Observaciones
1 Al realizar el producto P T(k)A(k−1), las primeras k filas no varían.
2 Al realizar el producto P T(k)A(k−1)P(k), las primeras k columnas
no varían.
3 Si A ∈ Rn×n es simétrica, entonces A(k) = P T
(k)A(k−1)P(k)
también lo es, y por tantoH debe ser tridiagonal.Página 3 Semana 15 11 de Noviembre de 2015 Domínguez
Ejemplo
A =
4 2 2 12 −3 1 12 1 3 11 1 1 2
Matrices reducción
w(1) =
−121
, P1 =
1 0 0 00 0.6 0.6 0.30 0.6 −0.3 −0.60 0.3 −0.6 0.6
A1 =
4 3 0 03 2 −3 −10 −3 −1 −10 −1.8 −1 1
, A2 =
4 3 0 03 2 3.16 0.00 3.16 −1.4 0.20 0 0.2 1.4
Página 4 Semana 15 11 de Noviembre de 2015 Domínguez
function [H,Q] = RedHouseholder(A)
% Dada una matriz A, determina la reduccion de A
% a una matriz de Hessenberg superior H, usando
% matrices de Householder.
n = size(A,1);
Q = eye(n);
for k=1:n-2
P = zeros(n,n);
P(1:k,1:k) = eye(k);
x = A(k+1:end,k);
w = x-norm(x)*eye(n-k,1);
W = w*w’;
P(k+1:end,k+1:end) = eye(n-k)- 2/norm(w)^2*W;
H = P’*A*P;
A = H;
Q = Q*P;
end
end
Página 5 Semana 15 11 de Noviembre de 2015 Domínguez
Fact. QR de una matriz de Hessenberg usando matrices de rotación
Dada una matriz A ∈ Rn es posible factorizar A mediante
H = QTAQ, Q = P(1)P(2) . . . P(n−2)
donde P(k) es una matriz de Householder, y H es una matriz de
Hessenberg superior.
• Tenemos que A y H son matrices semejantes, es decir, éstas
poseen los mismos valores propios.
• Encontrar los valores propios de H es más fácil de hallar que los
de A. Al obtener H es posible aplicar distintos métodos para
encontrar los valores propios, entre ellos, descomposición QR
mediante matrices de rotación.
Página 6 Semana 15 11 de Noviembre de 2015 Domínguez
Descomposición QR matrices de Hessenberg: Matrices de Rotación
• G(j, k, θ)TH anula la componente hk,j de H .
G(j, k, θ) =fila j
fila k
columna j columna k
1. . .
cos(θ) − sin(θ). . .
sin(θ) cos(θ). . .
1
Si hk,j = 0 ⇒ cos(θ) = 1, sin θ = 0;
Si |hk,j | > |hj,j | ⇒
τ =hj,j
hk,j
sin(θ) = 1√
1+τ2
cos θ = τ sin(θ);
|hj,j | > |hk,j | ⇒
τ =hk,j
hj,j
cos(θ) = 1√
1+τ2
sin(θ) = τ cos(θ);
Página 7 Semana 15 11 de Noviembre de 2015 Domínguez
Fact. QR mediante matrices de rotación
Objetivo: Para una matriz de Hessenberg H , encontrar una matriz
triangular superior R, tal que
H = QR, siendo Q una matriz ortogonal.
Estrategia: Anular las componentes (j+1, j) deH mediante el pro-
ducto de matrices de rotación G(j, j +1, θ) hasta obtener una matriz
triangular superior R,
GT(n−1) · · ·G
T(2)G
T(1)
︸ ︷︷ ︸
QT
H = R
donde
G(m) = G(m,m+ 1, θ).
Página 8 Semana 15 11 de Noviembre de 2015 Domínguez
Ejemplo: H =
1 2 −1 1
2 −3 1 0
0 1 −2 0
0 0 −3 1
G(1) =
0.44 −0.89 0 00.89 0.44 0 00 0 1 00 0 0 1
, G(1)TH =
2.23 −1.78 0.44 0.440 −3.13 1.34 −0.890 1 −2 00 0 −3 1
G(2) =
1 0 0 00 0.95 0.30 00 −0.30 0.95 00 0 0 1
, GT
(2)GT
(1)H =
2.23 −1.78 0.44 0.440 −3.28 1.88 −0.850 0 −1.49 −0.270 0 −3 1
G(3) =
1 0 0 00 1 0 00 0 0.44 −0.890 0 0.89 0.44
, GT
(3)GT
(2)GT
(1)H =
2.23 −1.78 0.44 0.440 −3.28 1.88 −0.850 0 −3.35 0.770 0 0 0.69
︸ ︷︷ ︸
R
Q = G(1)G(2)G(3), QT = GT
(3)GT
(2)GT
(3)
Observe que el calculo deG(m) anula la componente (m+1,m) de lamatriz G(m−1)H
Página 9 Semana 15 11 de Noviembre de 2015 Domínguez
Algoritmo método QR usando matrices de rotación y de Hessenberg
Dada una matriz A ∈ Rn×n
1 Se calcula una matriz de Hessenberg superiorH usando
matrices de Householder
H = QTAQ, donde Q = P(1)P(2) · · ·P(n−2)
2 Se realiza descomposición QR usando matrices de rotación:
1 DadoH(0) = H
2 Para k = 1 hasta nmax
1 Calcular Q(k) y R(k) tal que H(k−1) = Q(k)R(k) usando
matrices de rotación.
2 H(k) = R(k)Q(k)
3 parar si
{
H(k) es triangular superior
óH(k) es de bloque triangular superior.
Página 10 Semana 15 11 de Noviembre de 2015 Domínguez
function G = MatrizRotacion(A,j,n)
% Calcula una matriz de rotacion para anular la componente
% (j+1,j) de una matriz de Hessenberg A
G = eye(n);
xj = A(j,j);
xk = A(j+1,j);
if abs(xk)<=eps
c=1;
s=0;
elseif abs(xk) >= abs(xj)
t = xj/xk;
s= 1/sqrt(1+t^2);
c = s*t;
elseif abs(xj) > abs(xk)
t = xk/xj;
c = 1/sqrt(1+t^2);
s = c*t;
end
G(j:j+1,j:j+1) =[c -s; s c];
end
Página 11 Semana 15 11 de Noviembre de 2015 Domínguez
function [EI,H, R] = QRRotacion(H,nmax,tol)
% Determina la descomposicion Schur usando
% matrices de Hessenberg. En la descomposicion QR utiliza
% matrices de rotacion.
n = size(H,1);
[H,Q] = RedHouseholder(H); % Reduccion matriz de Hessenberg
iter =0;
while normH< tol && iter <=nmax
% Desc. QR con matrices de rotacion
Q = eye(n);
for j=1: n-1
G = MatrizRotacion(H,j,j+1,n);
H = G’*H
Q = Q*G;
end
R = H;
H = R*Q;
% Metodo QR para calculo EIG
iter = iter +1;
normH = norm(tril(H,-1),’fro’);
end
EI = diag(H,-1);
end
Página 12 Semana 15 11 de Noviembre de 2015 Domínguez