Semana 10

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.


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


continuación ...

Recuerde: se desea aproximar λ1 y v1


continuación ...


Sea y ∈ Rn cualquier vector con y 6= 0. Tenemos

Am+1x0

λm1

· y ≈ c1v1 · y,Amx0

λm1

· y ≈ c1v1 · y

entonces


continuación ...



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


continuación ...



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


continuación ...



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


continuación ...



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


continuación ...



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


Así

λ1 ≈AAmx0 · A

mx0

Amx0 · Amx0

v1 ≈ Amx0 = qm


Así

λ1 ≈AAmx0 · A

mx0

Amx0 · Amx0

v1 ≈ Amx0 = qm

Si garantizamos ||qm|| = 1 es decir Amx0 ·Amx0 = 1 entonces


Así

λ1 ≈AAmx0 · A

mx0

Amx0 · Amx0

v1 ≈ Amx0 = qm


λ1 ≈ AAmx0 · Amx0, v1 ≈

Amx0

||Amx0||


Así

λ1 ≈AAmx0 · A

mx0

Amx0 · Amx0

v1 ≈ Amx0 = qm


λ1 ≈ AAmx0 · Amx0, v1 ≈

Amx0

||Amx0||

Algoritmo

Dado q0 ∈ Rn con ‖q0‖ = 1, calcular


Así

λ1 ≈AAmx0 · A

mx0

Amx0 · Amx0

v1 ≈ Amx0 = qm


λ1 ≈ AAmx0 · Amx0, v1 ≈

Amx0

||Amx0||

Algoritmo


1 zk = Aqk−1


Así

λ1 ≈AAmx0 · A

mx0

Amx0 · Amx0

v1 ≈ Amx0 = qm


λ1 ≈ AAmx0 · Amx0, v1 ≈

Amx0

||Amx0||

Algoritmo


1 zk = Aqk−1

2 qk = zk

‖zk‖(Normalización)


Así

λ1 ≈AAmx0 · A

mx0

Amx0 · Amx0

v1 ≈ Amx0 = qm


λ1 ≈ AAmx0 · Amx0, v1 ≈

Amx0

||Amx0||

Algoritmo


1 zk = Aqk−1

2 qk = zk

‖zk‖(Normalización)

3 λk = qTkAqk = (Aqk) · qk


Método de las potencias inversa

Aproxima un valor propio de una matriz A ∈ Cn×n más proximo a un

numero µ /∈ σ(A) dado.




numero µ /∈ σ(A) dado. El método consiste en aplicar el método de

potencias a la matriz

(Mµ)−1 = (A− µI)−1






(Mµ)−1 = (A− µI)−1

• Los valores propios de Mµ son

κi = λi − µ






(Mµ)−1 = (A− µI)−1


κi = λi − µ

• Los valores propios de M−1µ son

ξi = (λi − µ)−1






(Mµ)−1 = (A− µI)−1


κi = λi − µ


ξi = (λi − µ)−1

• Existe un m tal que

|λm − µ| < |λi − µ|






(Mµ)−1 = (A− µI)−1


κi = λi − µ


ξi = (λi − µ)−1

• Existe un m tal que

|λm − µ| < |λi − µ|

Se requiere que λm tenga multiplicidad 1.


Método de potencias inversa: Algoritmo



Dado q0 de norma 1, calcular




1 zk = (A− µI)−1qk−1.




1 zk = (A− µI)−1qk−1. Realmente se resuelve (A− µI)zk = qk−1





2 qk =z

‖zk‖





2 qk =z

‖zk‖

3 λk = qTkAqk .





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





2 qk =z

‖zk‖







2 qk =z

‖zk‖



• Los vectores propios de M−1µ son los mismos vectores propios de A, sin

embargo los valores propios correspondientes son distintos.





2 qk =z

‖zk‖





• Se debe solucionar el sistema (A− µI)zk = qk−1.





2 qk =z

‖zk‖





• Se debe solucionar el sistema (A− µI)zk = qk−1.

• Si µ = 0, el método calcula el valor propio mas pequeño.


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


Matrices simétricas: calculo de valores propios

Dado un par j < k y φ ∈ R la matriz

U =




U =

1. . .

cos(φ) − sin(φ). . .

sin(φ) cos(φ). . .

1




U =fila j

fila k

1. . .



1




U =fila j

fila k

columna j columna k

1. . .



1




U =fila j

fila k

columna j columna k

1. . .



1

U describe la rotación en el plano xjxk, y además es unitaria UTU = Icoincide con la identidad excepto en ujj, ukk .


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.


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

]


Teorema

Para

tan(2φ) =2ajk

ajj − akk, ajj 6= akk

φ =π

4, ajj = akk


Teorema

Para

tan(2φ) =2ajk


φ =π

4, ajj = akk

las componentes

bjk = bkj = 0

N(B)2 = N(A)2 − 2a2jk


Teorema

Para

tan(2φ) =2ajk


φ =π

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


Teorema

Para

tan(2φ) =2ajk


φ =π

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.


Teorema

Para

tan(2φ) =2ajk


φ =π

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


Para matrices normales

(A∗A = AA∗)

n∑

j=1

|λj |2 =

n∑

j=1

|ajj|+ (N(A))2


Teorema

Para

tan(2φ) =2ajk


φ =π

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


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.






A0 = A






A0 = A

A1 = U∗

0A0U0






A0 = A

A1 = U∗

0A0U0

...






A0 = A

A1 = U∗

0A0U0

...

Am+1 = U∗

mAmUm






A0 = A

A1 = U∗

0A0U0

...

Am+1 = U∗

mAmUm

= U∗

mU∗

m−1Am−1Um−1Um






A0 = A

A1 = U∗

0A0U0

...

Am+1 = U∗

mAmUm

= U∗

mU∗

m−1Am−1Um−1Um

= U∗

mU∗

m−1 · · ·U0AU0 · · ·Um−1Um

= Q∗

mAQm






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






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,






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


propios,

2 Cuandom → ∞, Am → D donde Des una matriz diagonal, cuyas

entradas son los valores propios de A.






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


propios,



3 El par j, k corresponden a la posición

donde se encuentra la mayor

componente (en modulo) de la matriz

Am−1.






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


propios,



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.


Convergencia

1


Convergencia

1

N(Am) ≤ qmN(A0),


Convergencia

1

N(Am) ≤ qmN(A0), q :=(

1−2

n(n− 1)

)1/2< 1,


Convergencia

1

N(Am) ≤ qmN(A0), q :=(

1−2

n(n− 1)

)1/2< 1,

por tanto,

N(Am) → cuandom → ∞


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


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)


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.



Idea principal


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.



Idea principal



T = U∗AU


Principio teórico

Sea A ∈ Rn×n, dada una matriz ortogonal Q ∈ R

n×n, considere

T = QTAQ



Idea principal



T = U∗AU


Principio teórico


n×n, considere

T = QTAQ entonces es posible descomponer T = Q̃R



Idea principal



T = U∗AU


Principio teórico


n×n, considere

T = QTAQ entonces es posible descomponer T = Q̃R

donde R es una matriz triangular superior y Q̃ una matriz ortogonal.


Método Iterativo QR

Sea A ∈ Rn×n, dada una matriz ortogonal Q0 ∈ R

n×n




n×n

1 se calcula

T0 = QT0 AQ0




n×n

1 se calcula

T0 = QT0 AQ0

2 Para k = 1, . . . , hasta la convergencia




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




n×n

1 se calcula

T0 = QT0 AQ0


• tomamos Tk = RkQk

Observe




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk =




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT

k Tk−1 Qk




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT

k Tk−1 Qk Tk−1 = QT

k−1Tk−2 Qk−1




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT


k−1Tk−2 Qk−1

= QT

kQT

k−1Tk−2 Qk−1 Qk




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT


k−1Tk−2 Qk−1

= QT

kQT


...




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT


k−1Tk−2 Qk−1

= QT

kQT


...

= QT

kQT

k−1 · · ·QT

0 AQ0 · · · Qk−1 Qk




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT


k−1Tk−2 Qk−1

= QT

kQT


...

= QT

kQT

k−1 · · ·QT

0 AQ0 · · · Qk−1 Qk

= (Q0 · · · Qk−1 Qk)TAQ0 · · · Qk−1 Qk




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT


k−1Tk−2 Qk−1

= QT

kQT


...

= 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.




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT


k−1Tk−2 Qk−1

= QT

kQT


...

= QT

kQT

k−1 · · ·QT

0 AQ0 · · · Qk−1 Qk

= (Q0 · · · Qk−1 Qk)TAQ0 · · · Qk−1 Qk



propios.

2 Si A tiene valores propios reales (de

modulo distintos), Tk converge a una

matriz triangular superior.




n×n

1 se calcula

T0 = QT0 AQ0



Observe

Tk = RkQk = Q−1

kTk−1 Qk

= QT


k−1Tk−2 Qk−1

= QT

kQT


...

= QT

kQT

k−1 · · ·QT

0 AQ0 · · · Qk−1 Qk

= (Q0 · · · Qk−1 Qk)TAQ0 · · · Qk−1 Qk



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


Descomposición QR




mediante

q1 = x1


Descomposición QR




mediante

q1 = x1

q2 = x2 − proyq1x2q1


Descomposición QR




mediante

q1 = x1


= x1 −q1 · x2

q1 · q1

q1


Descomposición QR




mediante

q1 = x1


= x1 −q1 · x2

q1 · q1

q1

qk+1 = xk+1 −k

∑

i=1

qi · xk+1

qi · qiqi


Descomposición QR




mediante

q1 = x1


= 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


Descomposición QR




mediante

q1 = x1


= x1 −q1 · x2

q1 · q1

q1

qk+1 = xk+1 −k

∑

i=1

qi · xk+1

qi · qiqi



q̃1 =a1

‖a1‖,


Descomposición QR




mediante

q1 = x1


= x1 −q1 · x2

q1 · q1

q1

qk+1 = xk+1 −k

∑

i=1

qi · xk+1

qi · qiqi



q̃1 =a1

‖a1‖,

q̃k+1 =qk+1

‖qk+1‖


Descomposición QR




mediante

q1 = x1


= x1 −q1 · x2

q1 · q1

q1

qk+1 = xk+1 −k

∑

i=1

qi · xk+1

qi · qiqi



q̃1 =a1

‖a1‖,

q̃k+1 =qk+1

‖qk+1‖

qk+1 = ak+1 −k

∑

i=1

(q̃j ,ak+1)q̃j


Descomposición QR




mediante

q1 = x1


= x1 −q1 · x2

q1 · q1

q1

qk+1 = xk+1 −k

∑

i=1

qi · xk+1

qi · qiqi



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.


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


Documents

Semana 10