Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Quociente de Rayleigh
Escalar importante relacionado com os valores próprios, definido,
para qualquer x 6= 0, por
R(x) =
Análise Numérica II - Valores e vetores próprios
(Ax, x)
kxk22
=
xH Ax
xH x
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Algumas propriedades.
i) Se A é hermitiana, então o quociente de Rayleigh é real
ii) Se u∗ é um vetor próprio, então o valor próprio λ∗ associado a u∗ é
dado por
λ∗ = R(u∗ )
iii) Para qualquer x ∈ Cn \ {0} e qualquer α ∈ C, temos
R(λx) = R(x)
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Teorema de Rayleigh-Ritz. Seja A ∈ Cn×n hermitiana e assume que
os seus valores próprios satisfazem λ1 ≥ λ2 ≥ · · · ≥ λn . Então
λ1 = max R(x),
x6=0
λn = min R(x)
x6=0
Demonstração. Uma vez que o espectro
σ(λ1 I − A) = λ1 − σ(A)
vem que
σ(λ1 I − A) = {0, λ1 − λ2 , · · · , λ1 − λn }
e portanto a matriz λ1 I − A é semi-definida positiva.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Assim
((λ1 I − A) x, x) ≥ 0 ∀ x 6= 0
⇐⇒
λ1 ≥ R(x)
∀ x 6= 0
⇐⇒
λ1 ≥ max R(x).
x6=0
Por outro lado, e tendo em conta a propriedade ii), temos
λ1 = R(u1 ) ≤ max R(x)
x6=0
onde u1 é o vetor próprio associado a λ1 . Por conseguinte, conclui-se
que
λ1 = max R(x).
x6=0
A demonstração da segunda expressão é análoga.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Localização géometrica dos valores próprios
Alguns métodos de cálculo de valores próprios requerem um
conhecimento prévio da localização destes valores. Tendo em conta a
relação entre o raio espectral e as normas (consistentes), temos uma
primeira estimativa:
ρ(A) ≤ kAk
⇐⇒
|λ| ≤ kAk
∀λ ∈ σ(A)
pelo que todos os valores próprios estão contidos no disco centrado
em 0 e de raio kAk.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Observação. Para efeito de localização de valores próprios, interessa
utilizar normas fáceis de calcular. Assim, temos (por exemplo)
ρ(A) ≤ kAk1
ρ(A) ≤ kAk∞
p
ρ(A) ≤ kAk1 kAk∞
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
O próximo teorema proporciana resultados ainda mais estritos
Teorema 1. (Teorema dos círculos de Gershgorin) Seja A ∈ Cn×n e
seja σ(A) o seu espectro. Então
σ(A) ⊂ SR = ∪nk=1 Rk
onde Rk , chamado círculo de Gershgorin, é definido por
n
o
n
X
|Aki |
Rk = z ∈ C | |z − Akk | ≤
i=1
i6=k
Análise Numérica II - Valores e vetores próprios
(1)
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Demonstração. Seja λ um valor próprio e A e seja u um vetor próprio
associado tal que kuk∞ = 1. Seja k o índice para o qual o máximo é
atingido, i.e.
|uk | = max |ui | = kuk∞ .
1≤i≤n
Então
(Au)k = (λu)k
⇐⇒
⇐⇒
Análise Numérica II - Valores e vetores próprios
n
X
i=1
n
X
i=1
i6=k
Aki ui = λuk
Aki ui = (λ − Akk ) uk .
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Uma vez que |ui | ≤ |uk | = 1, temos
|λ − Akk | = |λ − Akk | |uk | = |(λ − Akk ) uk |
n
n
X
X
|Aki ui |
Aki ui ≤
=
i=1
i6=k
≤
n
X
i=1
i6=k
i=1
i6=k
|Aki | |uk | =
n
X
i=1
i6=k
|Aki | .
Existe então um círculo Rk tal que
λ ⊂ Rk ⊂ ∪ki=1 Rk
pelo que todos os valores próprios estão contidos em ∪ki=1 Rk .
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Recordendo que A e AT têm o mesmo espectro, o Teorema 1 implica
que
σ(A) ⊂ SC = ∪nk=1 Ck
(2)
onde Ck é definido por
n
Ck = z ∈ C | |z − Akk | ≤
n
X
i=1
i6=k
|Aik |
o
Os circlos Rk no plano complexo são chamados círculos linha,
enquanto os circlos Ck são chamados círculos coluna.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Resumindo, temos
Primeiro teorema de Gershgorin. Seja A ∈ Cn×n e seja σ(A) o seu
espectro. Então
σ(A) ⊂ SR ∩ SC
(3)
Observação. Este teorema não permite descobrir em qual dos
círculos de Gershgorin está situado um dado valor próprio, e não
exclui a existência de um círculo que não contem valores próprios, a
menos que este círculo seja isolado dos outros:
Segundo teorema de Gershgorin. Se k círculos de Gershgorin forem
disjuntos dos restantes, então existem exatamente k valores próprios
na sua união.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Método das potências diretas
Para fixar as idéias, consideraremos que os valores próprios de
A ∈ Cn×n estão ordenados de modo a que
|λ1 | ≥ |λ2 | ≥ · · · ≥ |λn |.
O método das potências é um método eficiente para a aproximação
dos valores próprios extremos λ1 e λn .
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Teorema 4. Seja A ∈ Cn×n uma matriz diagonalizável e sejam u1 , u2 ,
· · · , un os seus vetores próprios. Assume que os valores próprios
associados λ1 , · · · , λn satisfazem
|λ1 | > |λ2 | ≥ · · · ≥ |λn |.
P
Se q(0) = ni=1 αi ui é um vetor arbitrário em Cn com α1 6= 0, então a
sucessão definida por
q(k) = Aq(k−1)
k = 1, 2, · · ·
satisfaz a estimativa
(k)
q
−
u
α λk
1 ≤
1 1
Análise Numérica II - Valores e vetores próprios
2
n X
αi α1 kui k2
i=2
!
k
λ2 λ1 Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Demonstração. A matriz A sendo diagonalizável, possui n vetores
próprios u1 , u2 , · · · , un que constituem uma base de Cn . Seja q(0) um
vetor arbitrário, e seja
n
X
(0)
αi ui
q =
i=1
a sua respresentação na base (ui )i=1,··· ,n . Então
q(1) = Aq(0) =
n
X
αi Aui =
αi λi ui
i=1
i=1
= α1 λ1 u1 +
n
X
n
X
i=2
αi λi
α1 λ1 ui
!
se α1 6= 0.
A multiplicação de um vetor por A produz um vetor mais alinhado
com a direção do vetor u1 associado ao valor próprio dominante λ1 .
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
De modo similar, construimos uma sucessão de vetores por meio da
fórmula
q(k) = Aq(k−1) ,
k = 1, 2, · · · .
concluindo facilmente que
q(k) = Ak q(0) = α1 λk1
u1 +
n
X
αi
α1
i=2
k
λi
λ1
e portanto
q(k)
α1 λk1
Análise Numérica II - Valores e vetores próprios
− u1 =
n
X
i=2
αi
α1
k
λi
λ1
ui .
ui
!
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Aplicando normas a ambos os membros desta igualdade, obtemos
n
X k (k)
q
αi
λi
ui α λk − u1 = α1 λ1
1 1
2
i=2
2
n X
α λ k i
i
≤
α1 λ1 ui ≤
≤
Análise Numérica II - Valores e vetores próprios
i=2
n X
i=2
2
αi λi k
α1 λ1 kui k2
n X
αi α1 kui k2
i=2
!
k
λ2 λ1 .
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Do Teorema 4, vem que
q(k)
k
α
k→+∞ 1 λ1
lim
= u1
Tendo em conta as propriedade ii) e iii) do quociente de Rayleigh R,
deduzimos que
(k) lim R q(k) = lim R αq λk = R(u1 ) = λ1
k→+∞
k→+∞
1 1
Assim a sucessão (λ(k) ) converge para λ1 .
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
O método das potências é ainda mais interessante, porque permite de
gerir simultaneamente uma sucessão (λ(k) , q(k) ) que converge para
(λ1 , v1 ) onde v1 é um vetor próprio normalizado. De facto, considere
X (k) =
q(k)
q
k (k) k2
=
Aq(k−1)
Aq
k (k−1) k2
É fácil ver que
lim R X (k) = lim R q(k) = λ1
k→+∞
Análise Numérica II - Valores e vetores próprios
k→+∞
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Além disso
X (k) =
=
=
≡
Ak q(0)
A
k k q(0) k2
Pn
αi λki ui
Pni=1
k i=1 αi λki ui k2
k
P
λ
α
u1 + ni=2 α i λ i ui
α1 λk1
1
1
|α1 λk1 | u1 +Pn αi λi k ui i=2 α1 λ1
+w(k)
µk uu1+w
k 1 (k) k2
2
com |µk | = 1
e
lim w(k) = 0
k
O algoritmo
seguinte
gera uma sucessão (λ(k) , X (k) ) que converge
para λ1 , kuu11k2 .
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Inicialização :
escolher X (0) tal que kX (0) k2 = 1 e λ(0)
fixar uma tolerância ε
q(1) = AX (0)
Para k = 1, 2, · · · fazer :
X (k) =
q(k)
kq(k) k2
q(k+1) = AX (k)
λ(k+1) = q(k+1) , X (k)
fim do ciclo k : Terminar quando λ(k+1) − λ(k) < ε λ(k) .
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Observações.
1. Este algoritmo pressupõe que |λ1 | > |λ2 | condição geralmente
difícil de verificar a priori.
2. Idem com the condição α1 6= 0. Contudo, isso não constitui em
geral um obstáculo do momento que na prática é pouco provável que
este vetor tenha uma componente segundo u1 exatamente nula.
3. A convergência
deste algoritmo é tanto mais rápida quanto mais
pequeno for λλ12 .
4. Se A for hermitiana, a convergência é mais rápida
2k
R(q(k) ) − λ1 ≤ C λλ12 onde C é uma constante independente de k.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Método das potências inversas
Idéia. Aplicar o método das potências a matriz inversa A−1 para o
cálculo do valor próprio de A com menor módulo, ou a (A − µI)−1
para o cálculo do valor próprio mais próximo de µ.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Procura do valor próprio de menor módulo
O valor próprio de maior módulo de A−1 é igual ao inverso do valor
próprio de menor módulo de A, uma vez que
1
max λ1i =
= |λ1n |
min |λi |
1≤i≤n
1≤i≤n
Daí
Aplicar o método das potências diretas a A−1
=⇒ v.p. dominante de A−1
=⇒ Inverter este valor para obter o v.p. de menor módulo de A
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Inicialização :
escolher q(0) tal que kq(0) k2 = 1 e α1 6= 0
fixar uma tolerância ε
q(1) = A−1 X (0)
Para k = 1, 2, · · · fazer :
X (k) =
q(k)
kq(k) k2
q(k+1) = A−1 X (k)
λ(k) = q(k+1) , X (k)
fim do ciclo k : Terminar quando λ(k+1) − λ(k) < ε λ(k) .
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Observação. Na realização prática deste método não se deve calcular
A−1 , mas resolver o sistema
Aq(k+1) = X (k)
por um método apropriado.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Procura do valor próprio mais próximo de um dado escalar
Seja µ ∈
/ σ(A) um dado escalar e assume que existe m ∈ N tal que
|λm − µ| < |λi − µ|
∀ i = 1, · · · , n
e i 6= m
Esta condição garante que o valor próprio λm é o mais próximo de µ e
tem multiplicidade igual a 1. Garante ainda que
ηm =
1
λm −µ
é o valor próprio de (A − µI)−1 com maior módulo.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Aplicando o algoritmo das potências inversas a A − µI, obtemos uma
aproximação ηapr de ηm :
ηapr ≈ ηm =
1
λm −µ
⇐⇒
λm ≈
1
ηapr
+µ
Portanto se µ for uma boa aproximação de um valor próprio λm , é de
esperar que se produza em poucas iterações um valor bastante preciso
para λm .
Observação. Se existir um grupo de valores próprios próximos uns
dos outros, podemos ter problemas de convergência.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Método de Jacobi
Os métodos das potências permitem obter um par próprio de cada vez
e deixam de ser eficientes se houver necessidade de calcular todos os
pares próprios. O método de Jacobi permite de obter simultaneamente
todos os pares próprios de uma matriz simétrica.
Princípio. A matriz A sendo simétrica é diagonizável. Existe então
uma matriz ortogonal R tal que
RT AR = diag(λ1 , λ2 , · · · , λn ),
onde os λi são os valores próprios da matriz A.
Dificuldade. Reside na construção da matriz ortogonal R.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Rotações planas in R2
Pista possível: Considere uma matriz A ∈ R2×2 simétrica, escrita na
forma
!
A11 A12
.
A=
A12 A22
A matriz
R=
c s
−s c
!
com
(
c = cos θ
s = sin θ
efectua uma rotação de um ângulo θ de todos os vetores de R2 .
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Simples cálclulos mostram que para tornar a matriz
!
!
!
c s
A11 A12
c −s
T
R AR =
−s c
A12 A22
s
c
numa matriz diagonal, basta escolher uma rotação tal que
(c2 − s2 )A12 + (A11 − A22 )sc = 0.
Portanto, o ângulo θ é completamente determinado por
(
θ = π4
se A11 = A22
tan(2θ) =
2A12
A22 −A11
Análise Numérica II - Valores e vetores próprios
e |θ| < π4 ,
se A11 6= A22 .
(4)
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Pondo
η=
A22 −A11
2A12
= cot(2θ)
e
t = tan θ
vem que
t2 + 2ηt − 1 = 0
(5)
e daqui obtemos
t = −η ±
p
1 + η2 .
Uma vez que |t| < 1 para |θ| < π4 e que o produto das raizes de (5) é
igual a −1, vamos reter apenas a solução de menor valor absoluto, i.e.
correspondente ao menor ângulo de rotação possível. Assim

1

se η ≥ 0
 η+√1+η2
t=
−1

√
senão

2
−η+
Análise Numérica II - Valores e vetores próprios
1+η
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Podemos então calcular os parâmetros c e s
c=
√1
1+t2
e
s = ct.
Assim, tendo em conta (4), obtemos
(RT AR)11 = A11 c2 + A22 s2 − 2A12 sc
=
A11 +A22 t2 −2A12 t
1+t2
= A11 +
e do mesmo modo
(A11 −A22 )t2 −2A12 t
1+t2
= A11 − A12 t
(RT AR)22 = A22 + A12 t.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Resumindo: sejam
η=
t=
c=
A22 −A11
2A12 ,





η+
√1
se η ≥ 0,
1+η2
−1
√
−η+ 1+η2
√1 ,
1+t2
senão,
s = ct,
então, a matriz A pode ser reduzida à forma
D = RT AR =
A11 − A12 t
0
0
A22 + A12 t
e logo σ(A) = {A11 − A12 t, A22 − A12 t}.
Análise Numérica II - Valores e vetores próprios
!
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Rotações planas in Rn
Definição. Sejam p, q ∈ N tal que 1 ≤ p < q ≤ n. Seja θ ∈ R,
c = cos θ e s = sin θ. A matriz definida por
p
↓

q
↓

1






R(p, q, θ) = 





..
.
c
..
.
···
1
−s · · ·
s
..
.
c
..
diz-se rotação plana de ângulo θ no plano (p, q).
Análise Numérica II - Valores e vetores próprios
.
1












←p
←q
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Teorema 5. Seja A ∈ Rn×n uma matriz simétrica e seja R(p, q, θ) a
rotação plana de ângulo θ no plano (p, q). Então, a matriz
B = R(p, q, θ)T AR(p, q, θ) é simétrica e os seus coeficientes são
dados por

Bij = Aij
i 6= p, q, j 6= p, q






Bpj = cApj − sAqj
j 6= p, q





 Biq = sAip + cAiq
i 6= p, q
Bpp = c2 App + s2 Aqq − 2scApq






Bqq = s2 App + c2 Aqq + 2scApq





 Bpq = (c2 − s2 )Apq + sc(App − Aqq )
Além disso, temos
n
X
i,j=1
Análise Numérica II - Valores e vetores próprios
(Bij )2 =
n
X
i,j=1
(Aij )2
(6)
(7)
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Demonstração. É fácil ver que B é simétrica se A é simétrica, e que
os coeficientes Bij são dados por (6). Tendo en conta o facto que
R ≡ R(p, q, θ) é ortogonal, obtemos
n
X
(Bij )2 =
n
X
Bij BTji
i,j=1
i,j=1
=
n
X
i
BBT
ii
= tr(BBT )
= tr RT ARRT AT R = tr RT AAT R
= tr AT RRT A = tr AAT
n
n
X
X
(Aij )2 .
Aij ATji =
=
i,j=1
Análise Numérica II - Valores e vetores próprios
i=1
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Teorema 6. Sejam p, q ∈ N tal que 1 ≤ p < q ≤ n e seja θ ∈ R. Seja
R(p, q, θ) a rotação plana de ângulo θ no plano (p, q). Se Apq 6= 0,
então existe um único θ determinado por
(
θ=
π
4
se App = Aqq
tan(2θ) =
2Apq
Aqq −App
e |θ| < π4 ,
se App 6= Aqq
(8)
e tal que
Bpq = 0.
Além disso, temos
n
X
i=1
Análise Numérica II - Valores e vetores próprios
(Bii )2 =
n
X
i=1
(Aii )2 + 2 (Apq )2
(9)
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Demonstração. Observe que
c −s
Bpp Bpq
c s
App Apq
=
.
Bpq Bqq
s
c
Apq Aqq
−s c
c −s
Ora, sendo
uma matriz ortogonal, o mesmo raciocínio
s
c
usado na prova de (7) nos permite concluir que
B2pp + B2qq + 2B2pq = A2pp + A2qq + 2A2pq .
Por outro lado, usando (6), temos
Bpq = Bqp = (c2 − s2 )Apq + sc(App − Aqq ).
Análise Numérica II - Valores e vetores próprios
(10)
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Se Apq 6= 0 e se escolhemos θ tal que (8) esteja satisfeita, então
Bpq = 0. Finalmente, para provar (9) observe que
Bii = Aii
i 6= p e i 6= q.
Tendo en conta (10), vem que
n
X
(Bii )
2
=
n
X
(Bii )2 + (Bpp )2 + (Bqq )2
i=1
i6=p,q
i=1
=
n
X
(Aii )2 + (App )2 + (Aqq )2 + 2 (Apq )2
i=1
i6=p,q
=
n
X
i=1
Análise Numérica II - Valores e vetores próprios
(Aii )2 + 2 (Apq )2 .
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Observação. Do mesmo modo que no caso de uma matriz de
dimensão 2, para determinar os coeficientes de B precisamos de
calcular t, c e s. Pondo
η=
t=
c=
Aqq −App
2Apq ,





√1
1+η2
−1
√
−η+ 1+η2
√1 ,
1+t2
s = ct
Análise Numérica II - Valores e vetores próprios
η+
se η ≥ 0,
senão,
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
vem que as fórmulas (6) são reduzidas a

Bij = Aij






Bpj = cApj − sAqj





 Biq = sAip + cAiq
Bpp = App − tApq






Bqq = Aqq + tApq





 Bpq = 0
Análise Numérica II - Valores e vetores próprios
i 6= p, q
e j 6= p, q
j 6= p, q
i 6= p, q
(11)
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Princípio do método de Jacobi. Partindo da matriz inicial A(0) = A,
construir de uma sucessão de matrizes ortogonais (R(k) )k de modo
que as matrices definidas por
A(k) = R(k)
T
A(k−1) R(k)
sejam ainda simétricas e convergem para uma matriz diagonal D com
os mesmos valores próprios que a matriz A.
Idéia. Consiste em tirar partido das matrizes de rotação plana para,
em operações sucessivas, anular os elementos não diagonais de A.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
O princípio de cada transformação
A(k) −→ A(k+1) = R(k+1)
T
A(k) R(k+1)
é de anular um coeficiente não diagonal de A(k) (de facto são dois).
Pondo
(k)
(k)
A −A
η = qq (k)pp ,
2Apq
t=
c=





√1
1+η2
−1
√
−η+ 1+η2
√1 ,
1+t2
s = ct
Análise Numérica II - Valores e vetores próprios
η+
se η ≥ 0,
senão,
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
vem que as fórmulas (11) escrevam-se

(k+1)
(k)

= Aij
i 6= p, q

 Aij



(k+1)
(k)
(k)


Apj
= cApj − sAqj
j 6= p, q





(k)
(k)

 A(k+1)
= sAip + cAiq
i 6= p, q
iq
(k+1)
(k)
(k)

App
= App − tApq





(k+1)
(k)
(k)


Aqq
= Aqq + tApq





(k+1)

=0
 Apq
Análise Numérica II - Valores e vetores próprios
e j 6= p, q
(12)
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Método de Jacobi clássico
O método de Jacobi clássico consiste em escolher, a cada iteração k, p
(k)
e q (p < q) tal que Apq seja o coeficiente de maior módulo da matriz
A(k) , i.e.
(k) (k) Apq = max Aij 1≤i<j≤n
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Algoritmo.
Inicialização :
A(0) = A
Fixar uma tolerância ε
Para k = 0, 1, 2, · · · :
determinar o maior elemento em valor obsoluto de A(k)
aplicar uma rotação de Jacobi para anular este elemento
calcular os elementos de A(k+1) usando (12)
Fim do ciclo k : Terminar quando os elementos de A(k+1)
satisfazem o critério de paragem.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Convergência do método de Jacobi clássico
Para estudar a convergência do método, consideramos a
decomposição
A(k) = D(k) + E(k)
com D(k) = diagA(k)
e comparemos a evolução de D(k) k e E(k) k . A norma mais
adequada para esta análise é a norma de Frobenius k · kF definida por
kCk2F
Análise Numérica II - Valores e vetores próprios
T
= tr C C =
n
X
i,j=1
|Cij |2 .
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Teorema 7. A matriz E(k) = A(k) − diag A(k) satisfaz
lim E(k) = ORn×n
k→+∞
Demonstração. Primeiro, observamos que
n n X
X
(k) 2
(k) 2
(k) 2
Aij
Eij
.
=
E =
F
i,j=1
i,j=1
i6=j
Por conseguite, tendo em conta (7) e (9), temos
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
n n n X
X
X
(k+1) 2
(k+1) 2
(k+1) 2
(k+1) 2
Aii
Aij
Aij
−
=
E
=
F
i=1
i,j=1
i,j=1
i6=j
n n X
X
(k) 2
(k+1) 2
=
Aij
Aii
−
=
i,j=1
n X
(k)
Aij
i,j=1
i6=j
2
+
i=1
n X
(k) 2
Aii
i=1
−
n n X
X
(k) 2
(k) 2
Aii
Aij
−
+
=
i=1
i,j=1
i6=j
2
(k) 2
= E(k) − 2 Apq .
F
Análise Numérica II - Valores e vetores próprios
n X
(k+1) 2
Aii
i=1
n X
(k) 2
(k) 2
Aii
+ 2 Apq
i=1
(13)
!
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Por outro lado, uma vez que
(k) (k) (k) Aij ≤ Apq = max Aij ∀ i, j
1≤i<j≤n
vem que
n X
(k) 2
(k) 2
(k) 2
Aij
≤ n(n − 1) Apq .
E =
F
Deduzimos de (13) e (14) que
(k+1) 2
≤ 1−
E
F
≤ 1−
2
n(n−1)
E(k) 2
F
k+1 2
E(0) 2 ,
n(n−1)
F
e portanto, as matrizes E(k) convergem para a matriz nula.
Análise Numérica II - Valores e vetores próprios
(14)
i,j=1
i6=j
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Teorema 8. Seja Sn o conjunto das permutações de {1, 2, · · · , n}.
Então existe τ ∈ Sn tal que
lim D(k) = diag λτ (1) , λτ (2) , · · · , λτ (n)
k→+∞
Antes de provar este teorema, enunciamos um resultado que será útil.
Lema 1. Seja (X, k · kX ) um espaço normado de dimensão finita. Seja
(uk )k∈N uma sucessão limitada em X e com um número finito de
pontos de acumulação. Se lim kuk+1 − uk kX = 0, então a sucessão
k→+∞
(uk )k∈N é convergente.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Demonstração do Teorema 8. 1) Uma vez que
(k) 2
D F
=
n X
(k) 2
Dij
2
i,j=1
≤
n
X
i,j=1
(k)
Aij
concluimos que a sucessão D(k)
=
n X
i=1
(k) 2
Dii
n X
(k) 2
Aii
=
i=1
2
= A(k) = kAk2F
F
k
é limitada em (Rn×n , k · kF ).
2) Mostramos agora que esta sucessão admite um número finito de
pontos de acumulação. Seja D um ponto de acumulação de D(k) k e
′
seja D(k ) ′ uma sub-sucessão que converge para D.
k
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Temos
′
′
′
det D(k ) + E(k ) − λI = det A(k ) − λI = · · · = det(A − λI)
e tendo em conta o Teorema 7, deduzimos que
′
(k )
(k′ )
lim
det
D
+
E
−
λI
= det(D − λI) = det(A − λI).
′
k →+∞
A matriz D é, portanto, uma matriz diagonal que tem os mesmos
valores próprios que A. Existe então τ ∈ Sn tal que
D = diag λτ (1) , λτ (2) , · · · , λτ (n) .
Concluimos ainda que a sucessão (D(k) )k admite, no máximo, n!
pontos de acumulação.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
3) Usando (12), obtemos
(k+1)
Dii
(k)
(k+1)
− Dii = Aii
(k)
− Aii

0



(k)
−tk Apq
=



(k)
tk Apq
Uma vez que |tk | ≤ 1, deduzimos que
(k) (k+1)
(k) max Dii
− Dii ≤ Apq −→ 0
e portanto
lim D(k+1) − D(k) = 0.
Análise Numérica II - Valores e vetores próprios
se i = p,
se i = q.
quando k → +∞,
1≤i≤n
k→+∞
se i 6= p e i 6= q,
F
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
4) Usando as alíneas 1), 2), 3) e o Lema 1, concluimos que existe
τ ∈ Sn tal que
lim D(k) = diag λτ (1) , λτ (2) , · · · , λτ (n)
k→+∞
o que prove o resultado.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Teorema 9. Seja A ∈ Rn×n uma matriz simétrica. O método de
(k)
Jacobi clássico é convergente, i.e. cada elemento diagonal Aii
converge para um valor próprio de A e cada elemento não diagonal
(k)
Aij (i 6= j) converge para zero.
Demonstração. É uma consequência direta do Teorema 7 e do
Teorema 8.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Observação.
1. O método de Jacobi clássico permite obter todos os valores
próprios de uma matriz simétrica.
2. O método de Jacobi clássico impõe que em cada iteração se procure
o elemento não diagonal da matriz A(k) de maior valor absoluto para
ser, em seguida, anulado. Como os elementos anulados numa iteração
não permanecem nulos nas iterações seguintes, esta pesquisa pode
sobrecargar excessivamente o algoritmo. Esta característica restringe
a sua aplicação a matrizes de dimensão moderada.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Variantes do método de Jacobi
Método de Jacobi cíclico
(k) (k)
Em vez de escolher (pk , qk ) tal que Apk qk = maxi6=j Aij , fazemos
variar (pk , qk ) de modo mais sistematico, escolhindo por exemplo a
ordem sequencial de linhas
(1, 2); (1, 3); (1, 4); · · · ; (1, n)
(2, 3); (2, 4); · · · ; (2, n);
(3, 4); · · ·
Quando chegamos a (n − 1, n) recomeçamos o cíclo.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Observação.
1. Mesmo se a convergência é garantida, onúmero
de iterações pode
ser muito importante porque a quantidade E(k) F diminui
ligeiramente a cada iteração.
2. Uma outra desvantagem deste método é a que os elementos são
sistematicamente anulados, mesmo aqueles cujo valor é muito
pequeno.
Análise Numérica II - Valores e vetores próprios
Quociente de Rayleigh Localização géometrica dos valores próprios Método das potências diretas Método das potências inversas Método de Ja
Método de Jacobi com patamar
Para remediar ao inconveniente acabado de referir, podemos
establecer um critério de anulamento mais selectivo, i.e., só anular os
elementos cujo valor absoluto estiver acima de um certo patamar.
Fixamos ε e escolhemos (pk , qk ) efectuando uma exploração
sistématica como no caso do método precedente, mas aplicando a
rotação só se
(k) A
pk qk ≥ ε.
Quando todos os elementos são inferiores a ε, repetimos o processo
para um novo valor de ε inferior ao precedente. O processo é
interrompido quando o patamar é da ordem da precisão desejada.
Análise Numérica II - Valores e vetores próprios