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.

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

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

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

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

Página 4 Semana 15 03 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 5 Semana 15 03 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‖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

Página 7 Semana 15 03 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 8 Semana 15 03 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 9 Semana 15 03 de Noviembre de 2015 Domínguez

• 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 10 Semana 15 03 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, 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, θ).

Página 11 Semana 15 03 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 12 Semana 15 03 de Noviembre de 2015 Domínguez

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 13 Semana 15 03 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 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

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

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

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

Calculo de valores propios matrices de Hessenberg

Método de Hyme

Calculo de raíces del polinomio característico

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