Semana 14 Am

Calculo de calores propios

Métodos iterativos

Catalina Domínguez,

Universidad del Norte

Doctorado en Ingeniería

Semestre II de 2015

Semana 14

Página 1 Semana 15 03 de Noviembre de 2015 Domínguez

Modificación Factorización QR: Hessenberg Matrices

Transformar A ∈ Cn×n en una matriz de Hessenberg

B = QHAQ

donde Q = Hn−2 · · ·H1 yHi son matrices de Householder.

Para matriz de Hessenberg, el polinomio característico y su respectiva

derivada en un punto c ∈ C puede calcularse fácilmente si calcular los

coeficientes del polinomio.


Matrices de Householder

Para v = x± ‖x‖2em definamos P = I −2vvT

‖v‖2,

1 Dado x ∈ Rn, y = Px es la reflexión de x con respecto al hiperplano

π = span{v}⊥ .2 P transforma x a un vector nulo excepto en una m-esima componente

Ejemplo

Para x = [−1, 1,−1, 1]T y m = 3

v =

−1111

, P =

1

2

1 1 −1 11 1 1 −1−1 1 1 11 −1 1 1

, Px =

0020


Matrices de Householder

Dado x ∈ Rn, tenemos

P(k) =

[Ik 00 R(n−k)

]

, R(n−k) = In−k − 2w

(k)w

(k)T

‖w‖2,

• w(k) = x(n−k) ± ‖x(n−k)‖ e

(n−k)1 , donde x

(n−k) ∈ Rn−k es el vector

formado por las ultimas n− k componentes de x.

• e(n−k)1 es el primer vector unitario de Rn−k

•

y = P(k)x, con yj =

xj si j = 1, . . . , k

±‖x(n−k)‖ si j = k

0 si j = k + 2, . . . , n.

k = 2, x =

−12−134

, P(2) =

1 0 0 0 00 1 0 0 00 0 0.1961 −0.5883 −0.78450 0 −0.5883 0.5694 −0.57410 0 −0.7845 −0.5741 0.2345

, y =

−12

−√26

00


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 • •


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‖2,

w(k) = x(n−k)±‖x(n−k)‖ e

(n−k)1 , x : k-esimo vector columna de A(k).

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 6 Semana 15 03 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 −1 1

, A2 =

4 3 0 03 2 3.1622 0.00 3.1622 −1.4 0.20 0 0.2 1.4


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


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.


• 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(θ);


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, j +1) 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, θ).


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


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.


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 xk==0

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


function [EI,H, R] = QRRotacion(H,nmax,tol)

% Determina la descomposicion Schur usando

% matrices de Hessenberg. Pra 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


Calculo de valores propios matrices de Hessenberg

Método de Hyme

Calculo de raíces del polinomio característico


Documents

Semana 14 Am