Autovalores e Autovetores

Prévia do material em texto

Caṕıtulo 6
Autovalores e Autovetores
6.1 Introdução
Neste caṕıtulo, apresentaremos alguns dos métodos utilizados para a solução do problema do
autovalor, i.e., o sistema de n equações lineares
Ax = λx (6.1)
para o qual procuramos um vetor solução x tal que xi �= 0 para pelo menos algum i, ou seja, uma
solução não-trivial. Para que tal seja posśıvel, é necessário que
det(A− λI) = 0 (6.2)
a qual é uma equação polinomial de grau n na variável λ, chamada de equação caracteŕıstica de
A; o polinômio det(A− λI) é chamado de polinômio caracteŕıstico de A.
As n ráızes de (6.2) são chamadas de autovalores, ráızes latentes ou valores caracteŕısticos de
A. A cada raiz λ corresponde um vetor x ∈ ICn �= 0 que satisfaz a equação (6.1), o qual é chamado
de autovetor, vetor latente ou vetor caracteŕıstico de A. Note que, se x é um autovetor de A, então
kx, onde k ∈ IR, também é, pois
Akx = kAx = λkx = kλx.
Costumeiramente os autovetores são normalizados, i.e. ||x || = 1 em alguma norma escolhida (o
que pode ser feito pela relação acima).
Se todas as ráızes de (6.2) são distintas entre si, então isso implica em que a matriz A apresenta
um conjunto completo de autovetores linearmente independentes (L.I.). No entanto, mesmo para
casos em que os autovalores não são todos distintos, podemos encontrar um conjunto completo de
autovetores L.I.
Podemos também calcular os autovalores da matriz inversa de A, A−1, a partir dos autovalores
de A. Se multiplicarmos a equação (6.1) à esquerda por A−1, temos
x = λA−1x
ou
A−1x =
1
λ
x. (6.3)
Essa última equação nos diz que 1λ é autovalor de A
−1, onde λ é um autovalor de A, com o
autovetor x correspondente.
Problemas envolvendo autovalores e autovetores surgem em inúmeras aplicações, como pode-
mos ver nos exemplos que seguem, conforme apresentados em [6].
110
Introdução ao Cálculo Numérico Autovalores e Autovetores
Exemplo 6.1 O estudo das vibrações de sistemas dinâmicos e de estruturas requer a solução de
problemas de autovalores e autovetores. Considere, apenas para fins de explanação, o problema
de se determinar as vibrações de pequenas part́ıculas presas por um fio uniforme, sem peso, ao
qual é aplicada uma força −→F nas extremidades (cf. a figura 6.1) e no qual desconsidera-se a ação
da gravidade. As part́ıculas encontram-se a distâncias iguais entre si e as vibrações das mesmas
são consideradas pequenas e perpendiculares à posição de descanso do fio. Escrevendo as equações
Figura 6.1: O problema das vibrações.
diferenciais para as forças atuantes em cada part́ıcula, temos:
m1
d2x1
dt2
= −F x1
h
+ F
x2 − x1
h
m2
d2x2
dt2
= −F x2 − x1
h
+ F
x3 − x2
h
m3
d2x3
dt2
= −F x3 − x2
h
− F x3 − x4
h
m4
d2x4
dt2
= +F
x3 − x4
h
− F x4
h
Introduzindo a notação
x = (x1, x2, x3, x4)T
di =
mih
F
, i = 1, 2, 3, 4
podemos escrever o sistema de equações diferenciais acima na forma matricial
D
d2x
dt2
= Tx (6.4)
onde D é a matriz diagonal
D =


d1
d2
d3
d4


e T é a matriz tridiagonal
T =


−2 1 0 0
1 −2 1 0
0 1 −2 1
0 0 1 −2

 .
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 111
Introdução ao Cálculo Numérico Autovalores e Autovetores
Quando as part́ıculas vibram em fase ou em direções opostas, i.e., em modo normal, então a
condição
d2x
dt2
= −w2x, w ∈ IR (6.5)
é satisfeita. Substituindo a equação (6.5) em (6.4), obtemos o problema de autovalor
Dw2i xi = −Txi, i = 1, 2, 3, 4 (6.6)
para as freqüências de vibração w1, w2, w3 e w4 e os modos normais correspondentes, i.e., os
autovetores x1, x2, x3 e x4.
Aparentemente, se isolarmos x no lado direito da equação (6.6), obteŕıamos o que se chama
de problema generalizado do autovalor, cuja forma geral é
(A− λB)x = 0
onde A e B são matrizes de ordem n. Porém, se introduzirmos o vetor
y = D1/2x
o que é posśıvel, já que os elementos da diagonal de D são positivos, por definição, então podemos
escrever (6.6) como
D−1/2TD−1/2yi = −w2i yi
o qual recai na forma 6.1.
Exemplo 6.2 A teoria de Leontief sobre a compra e a venda de produtos é muito utilizada no
campo de estudo da macroeconomia; como exemplo, consideramos as vendas e compras de produtos
num setor industrial.
Seja bij as vendas da indústria i para a indústria j; bii representa os bens produzidos pela
indústria i e retidos por ela própria. As vendas de bens da indústria i para o mercado é denotada
por yi e o total de bens produzidos por xi. Então,
xi = yi +
∑
j
bij (6.7)
A fim de definirmos bij, assume-se que as vendas da indústria i para a j estão em proporção
constante à produção da indústria j, i.e.
bij = aijxj
onde aij são ditos coeficientes de entrada. Em uma situação estática, podemos escrever, a partir
de (6.7),
x = y + Ax (6.8)
onde x = (x1, x2, . . . , xn)T e y = (y1, y2, . . . , yn)T e A é matriz de ordem n cujos elementos (i, j)
são os coeficientes de entrada aij. Ora, a equação (6.8) pode ser reescrita como
(I −A)x = y (6.9)
onde I − A é chamada de matriz de Leontief. A equação (6.9) pode ser resolvida calculando-
se os autovalores e autovetores de A. Sua utilidade reside no fato de que, com ela, é posśıvel
determinar-se a quantidade de bens produzidos (x) necessários para satisfazer a uma demanda
final (y), pré-estabelecida.
Se a produção e a demanda não se encontram em equiĺıbrio, então devemos considerar um
modelo dinâmico, que leve em consideração a taxa de variação da produção. Nesse caso, usual-
mente considera-se que a produção em cada indústria varia a uma taxa proporcional à diferença
entre os ńıveis de venda e de produção. Dáı,
dx(t)
dt
= D ((A− I)x(t) + y(t)) (6.10)
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 112
Introdução ao Cálculo Numérico Autovalores e Autovetores
onde D é uma matriz diagonal de ordem n, cujos elementos dii representam os coeficientes de
reação das indústrias.
A equação (6.10) substitui nesse caso a equação (6.8) e representa o comportamento dinâmico
do sistema econômico em estudo. Uma das questões a serem estudadas, nesse caso, é se o sistema
é estável, determinando-se os autovalores e autovetores da matriz D(A − I). Particularmente,
procura-se determinar se esses autovalores tem parte real positiva pois, como as soluções do
sistema de equações diferenciais (6.10) são da forma eλit, isso indicaria uma instabilidade, já
que a demanda x(t) cresceria exponencialmente com o tempo.
A seguir, apresentaremos dois importantes teoremas, os quais nos permitirão desenvolver
técnicas de determinação de autovalores e autovetores para um tipo espećıfico de matrizes.
6.2 Teoremas de limites sobre autovalores
Teorema 6.2.1 Discos de Gerschgorin: Seja A uma matriz de ordem n, e di, i = 1, 2, . . . , n
os discos cujos centros são os elementos aii e cujos raios ri são dados por
ri =
n∑
j=1
j �=i
|aij |, i = 1, 2, . . . , n.
Seja D a união de todos os discos di. Então, todos os autovalores de A encontram-se contidos em
D.
Prova: Seja λ um autovalor de A e x um autovetor correspondente, tal que maxi |xi | = 1. Então,
λx = Ax
de onde
(λ− aii)xi =
n∑
j=1
j �=i
aijxj , i = 1, 2, . . . n
Supondo que |xk | = 1, então
|λ− akk | ≤
n∑
j=1
j �=i
| akj ||xj |
≤
n∑
j=1
j �=i
| akj | = rk
i.e., o autovalor λ está contido no disco dk e, como λ é arbitrário, então todos os autovalores de A
devem estar contidos na união de todos os discos, D. ♦
O exemplo a seguir apresenta uma aplicação do teorema 6.2.1.
Exemplo 6.3 A matriz
A =

 −1 0 −1−1 4 −1
−1 −2 10


tem como seus autovalores λ1 = 10, 3863, λ2 = 3, 8037 e λ3 = 0, 8100. Calculando os discos de
Gerschgorin, temos:
d1 = |z − 1| < |0|+ | − 1| = 1
d2 = |z − 4| < | − 1|+ | − 1| = 2
d3 = |z − 10| < | − 1|+ | − 2| = 3
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 113
Introdução ao Cálculo Numérico Autovalores e Autovetores
Como todos os autovaloresde A são reais, e observando (veja a figura 6.2) que em cada disco
devemos ter um autovalor, podemos dizer que:
• existe um autovalor, λ1, que está dentro do disco centrado em 10 e raio 3 e, de fato, 7 <
10, 3863 < 13;
• existe um autovalor, λ2, que está dentro do disco centrado em 4 e raio 2 e, realmente,
2 < 3, 8037 < 6;
• existe um autovalor, λ3, que está dentro do disco centrado em 1 e raio 1 e, com efeito,
0 < 0, 81 < 2;
A figura 6.2 ilustra esse resultado.
Figura 6.2: Discos de Gerschgorin
Uma conseqüência do teorema de Gerschgorin é a determinação do maior disco que contém
todos os autovalores de A. Podemos obter, a partir dos discos, os extremos ao longo do eixo dos
números reais, i.e. o intervalo [α, ω] tal que
α = min
i
{aii − ri}, ω = max
i
{aii + ri}, i = 1, 2, . . . , n (6.11)
e o maior disco é justamente aquele com centro (α+ω)/2 e raio (α+ω)/2. No caso em que todos
os autovalores são reais, basta então considerar o intervalo [α, ω].
Teorema 6.2.2 Maior e menor autovalor: Seja A uma matriz real simétrica de ordem n, e
x ∈ IC um vetor arbitrário. Então,
λ1 = max
x �=0
xTAx
xTx
, λn = min
x �=0
xTAx
xTx
onde os autovalores são ordenados tais que λ1 ≥ λ2 ≥ . . . ≥ λn.
A razão
xTAx
xTx
, x �= 0 (6.12)
é chamada de quociente de Rayleigh correspondente a x e, juntamente com o teorema 6.2.2, nos
permitirá estimar de forma bastante rápida um autovalor de uma matriz simétrica, conforme
veremos na seção 6.5.
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 114
Introdução ao Cálculo Numérico Autovalores e Autovetores
6.3 Cálculo de autovalores e autovetores via determinantes
Já vimos que, por definição, os autovalores de uma matriz A são as ráızes do polinômio caracte-
ŕıstico de A. Evidentemente, para matrizes de ordem n > 4, não é aconselhável que se utilize a
equação (6.2) para se obter o polinômio caracteŕıstico, por duas razões:
1. o cálculo de determinantes de ordem superior a 4 envolve considerável custo computacional;
2. o polinômio caracteŕıstico de uma matriz grande pode ser instável numericamente.
No entanto, algumas aplicações de engenharia, f́ısica e outros campos do conhecimento envolvem
a determinação de autovalores de matrizes de ordem n = 2 ou n = 3 e, nesse caso, é posśıvel obter-
se os autovalores extraindo as ráızes do polinômio caracteŕıstico, conforme mostra o exemplo a
seguir.
Exemplo 6.4 Seja a matriz [
2 5
3 −4
]
.
O seu polinômio caracteŕıstico é
p(λ) = det(A− λI) =
∣∣∣∣ 2− λ 53 −4− λ
∣∣∣∣ = (2 − λ)(−4− λ)− 15
ou p(λ) = λ2 + 2λ− 23, cujas ráızes são λ1 = 3, 8990 e λ2 = −5, 8990.
Para se determinar os autovetores, utiliza-se a equação (6.1) para cada autovalor λi, na forma
(A− λiI)xi = 0, como segue:
Exemplo 6.5 Calcule os autovetores do exemplo 6.4.
Solução: Para o autovalor λ1 = 3, 8990, escrevemos
(A− 3, 8990I)x1 = 0[
7, 8990 5
3 1, 8990
] [
(x1)1
(x1)2
]
=
[
0
0
]
de onde obtemos
x1 =
[
k
−1, 5798k
]
, k �= 0
O autovetor correspondente a λ2 = −5, 8990 é obtido de forma similar:
(A + 5, 8990I)x1 = 0[ −1, 8990 5
3 −7, 8990
] [
(x2)1
(x2)2
]
=
[
0
0
]
de onde obtemos
x2 =
[
k
0, 3798k
]
, k �= 0
Computacionalmente, no entanto, podemos estimar o autovetor correspondente a um autovalor
utilizando os métodos da potência com translação da origem (seção 6.5.2) ou da iteração inversa
com translação da origem (seção 6.5.3).
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 115
Introdução ao Cálculo Numérico Autovalores e Autovetores
6.4 Autovalores de uma matriz tridiagonal simétrica
Em muitas aplicações surgem matrizes tridiagonais simétricas, das quais necessitamos extrair
autovalores e/ou autovetores. Por exemplo, ao aproximarmos a equação diferencial parcial
∂u
∂t
=
∂2u
∂x2
por diferenças finitas, obtemos uma matriz

−2 1 0 0
1 −2 1 0
0 1 −2 1
0 0 1 −2


a qual apresenta aquela caracteŕıstica.
De forma geral, consideramos uma matriz T de ordem n,
T =


a1 b1 0 . . . 0
b1 a2
. . . . . .
...
0
. . .
. . .
. . . 0
...
. . . . . . . . . bn−1
0 . . . 0 bn−1 an


(6.13)
e chamamos de Tr a matriz principal de ordem r de T , i.e.
T1 =
[
a1
]
, T2 =
[
a1 b1
b1 a2
]
, T3 =

 a1 b1 0b1 a2 b2
0 b2 a3

 , . . .
Escrevendo as equações caracteŕısticas p1(λ), p2(λ) e p3(λ) das matrizes T1, T2 e T3, obtemos:
p1(λ) = det(T1 − λI) = a1 − λ (6.14)
p2(λ) = det(T2 − λI) = (a2 − λ)(a1 − λ)− b21 = (a2 − λ)p1(λ)− b21 (6.15)
p3(λ) = det(T3 − λI) = (a3 − λ)
(
(a2 − λ)(a1 − λ)− b21(a3 − λ)
)− b22(a1 − λ) =
= (a3 − λ)p2(λ) − b22p1(λ) (6.16)
de onde podemos escrever, generalizando para r,
pr(λ) = (ar − λ)pr−1(λ)− b2r−1pr−2(λ), r = 2, 3, . . . , n, p0(λ) = 1, (6.17)
A equação (6.17) nos permite avaliar o polinômio caracteŕıstico da matriz T de forma bastante
eficiente; no entanto, estamos preocupados em obter os autovalores de T , ou as ráızes de pn. O
teorema a seguir nos permitirá escrever um algoritmo bastante eficiente para se extrair alguns ou
todos os autovalores de T .
Teorema 6.4.1 Seqüência de Sturm: Se a matriz tridiagonal (6.13) é não-reduźıvel 1, então
os r − 1 autovalores µ da matriz Tr−1 separam estritamente os r autovalores λ da matriz Tr:
λr < µr−1 < λr−1 < µr−2 < · · · < λ2 < µ1 < λ1.
Mais ainda, se s(λ) representa o número de trocas de sinal na seqüência
{p0(λ), p1(λ), . . . , pn(λ)}
então s(λ) é igual ao número de autovalores de T menores do que λ, onde pr(λ) é dado por (6.17)
e assume-se que pr(λ) tem o sinal oposto de pr−1(λ) se pr(λ) = 0.
1Uma matriz A é dita não-reduźıvel se os elementos da diagonal da matriz triangular superior R, resultante de
sua fatoração no produto QR, são todos não-nulos, onde Q é uma matriz ortogonal (i.e. QT Q = I).
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 116
Introdução ao Cálculo Numérico Autovalores e Autovetores
O teorema 6.4.1 é extremamente importante: ele nos diz que, se tivermos os n autovalores µ
de uma matriz triadiagonal Tn (de ordem n), então entre cada par de autovalores consecutivos
µ (com exceção do menor e do maior), existe um e apenas um autovalor λ da matriz tridiagonal
Tn+1 (de ordem n + 1), obtida acrescentando-se uma linha e uma coluna à matriz Tn. Devido à
essa caracteŕıstica, podemos utilizar o algoritmo da bissecção (ver algoritmo 2.2.1), juntamente
com a equação (6.17), para obtermos rapidamente, e com segurança, um autovalor de Tn+1, à
partir de um intervalo que é um par de autovalores consecutivos de Tn.
Para obter-se o menor e o maior autovalores de Tn+1, utilizamos o teorema de Gerschgorin -
mais especificamente, calculamos o maior intervalo que engloba todos os autovalores, com a equa-
ção (6.11). Assim, o menor autovalor é calculado usando-se como estimativa inicial para o método
da bissecção o intervalo [α, µr−1]; para o maior autovalor, utiliza-se o intervalo [µ1, ω].
Os algoritmos 6.4.1, 6.4.2 e 6.4.3 combinam as idéias apresentadas acima. Da maneira como o
algoritmo 6.4.3 é apresentado, todos os autovalores são obtidos; no entanto, simples modificações
do mesmo nos permitem obter apenas alguns autovalores (por exemplo, o maior e o menor, ou os
dois maiores, etc.).
O exemplo 6.6 demonstra uma situação t́ıpica, resolvido utilizando-se esses algoritmos.
Algoritmo 6.4.1 Avalia polinômio caracteŕıstico de uma matriz
tridiagonal simétrica
function pol carac trid(input: x, a, b; output: p)
% a e b são os vetores contendo os elementos da
% diagonal e subdiagonal, respectivamente,
% da matriz tridiagonal
p0 ← 1
p1 ← a1 − x
p← p1
for r← 2, 3, . . . , n do
p← (ar − x)p1 − b2r−1p0
p0 ← p1
p1 ← p
endfor
endfunction
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 117
Introdução ao Cálculo Numérico Autovalores e Autovetores
Algoritmo 6.4.2 Método da bissecção com polinômio caracte-
ŕıstico
proc bissecção trid(input: a, b, α, β, kmax, δ, &; output: χ)
% a e b são os vetores contendoos elementos da
% diagonal e subdiagonal, respectivamente,
% da matriz tridiagonal
u← pol carac trid(α, a, b)
v ← pol carac trid(β, a, b)
e← β − α
if (sign(u) = sign(v)) then
“não pode proceder”
else
k ← 1
w ← 1
while ((k ≤ kmax) AND (| e | ≥ δ) AND (|w | ≥ &))
e← e/2
χ← α + e
w ← pol carac trid(χ, a, b)
if (sign(w) �= sign(u)) then
β ← χ
v ← w
else
α← χ
u← w
endif
k ← k + 1
endwhile
endif
endproc
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 118
Introdução ao Cálculo Numérico Autovalores e Autovetores
Algoritmo 6.4.3 Autovalores de uma matriz tridiagonal
simétrica
proc autovalores tridiagonal(input: a, b, n; output: λ)
% Calcula os raios dos discos de Gerschgorin, cada qual com centro a(i)
r1 ← | b1 |
for i← 2, 3, . . . , n− 1 do
ri ← | bi−1 |+ | bi |
endfor
rn ← | bn−1 |
% Calcula o intervalo [α, ω] na reta dos reais
% contendo os autovalores
α← minni=1(ai − ri)
ω ← maxni=1(ai + ri)
% Calcula os autovalores, iniciando com o autovalor
% de T1 = [a1], µ = a1
µ1 = a1
for i← 2, 3, . . . , n do
% Calcula os autovalores de Ti
% a. entre α e µ1
call bissecção trid(a, b, α, µ1, kmax, δ, &, λ1)
% b. autovalores entre µ1 e µi−1
for j ← 1, 2, . . . , i− 2 do
call bissecção trid(a, b, µj , µj+1, kmax, δ, &, λj+1)
endfor
% c. entre µi−1 e ω
call bissecção trid(a, b, µi−1, ω, kmax, δ, &, λ1)
µ← λ
endfor
λ← µ
endproc
Exemplo 6.6 Seja a matriz tridiagonal
T =


2 −1
−1 2 −1
−1 2 −1
−1 2


a qual pode ser representada de forma compacta através dos vetores
a = (2, 2, 2, 2)T e b = (−1,−1,−1)T
Para se obter os autovalores de T , iniciamos com a matriz
T1 =
[
a1
]
=
[
2
]
a qual tem como seu único autovalor µ1 = a1 = 2. Além disso, calculamos os extremos do intervalo
de Gerschgorin, α = 0 e ω = 6, através da equação (6.11).
Agora, precisamos calcular os dois autovalores λ da matriz
T2 =
[
a1 b1
b1 a2
]
=
[
2 −1
−1 2
]
os quais, pelos teoremas de Gerschgorin e 6.4.1, satisfazem
α < λ2 < µ1 < λ1 < ω
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 119
Introdução ao Cálculo Numérico Autovalores e Autovetores
Estipulando-se como tolerâncias de convergência para o método da bisseção δ = & =
√
ε e um
máximo de 200 iterações, λ2 é obtido em 2 iterações utilizando-se como intervalo de busca [α, µ1] =
[0, 2], resultando no valor λ2 = 1. O autovalor λ1 também é obtido em 2 iterações, usando-se como
intervalo de busca [µ1, β] = [2, 6], com o qual obtém-se λ1 = 3.
Antes de procedermos ao cálculo dos autovalores de T3, fazemos uma cópia dos λ, armazenando-
os em µ; assim, temos µ1 = 3 e µ2 = 1.
Procedemos, então, com o cálculo dos autovalores λ de T3; para tanto, utilizamos os intervalos
de busca
• [α, µ2] = [0, 1] para calcular o autovalor λ3;
• [µ2, µ1] = [1, 3] para calcular o autovalor λ2;
• [µ1, ω] = [3, 6] para calcular o autovalor λ1.
Os autovalores λ3, λ2 e λ1 são então obtidos com o método da bissecção, utilizando-se as mesmas
tolerâncias especificadas anteriormente, resultando em λ3 = 0, 5858, λ2 = 2 e λ1 = 3, 4142, obtidos
em 27, 2 e 27 iterações respectivamente.
Finalmente, basta calcularmos os autovalores de T4. Procedendo de forma similar, fazemos
µ3 = 0, 5858, µ2 = 2 e µ1 = 3, 4142 e estipulamos os intervalos de busca
• [α, µ3] = [0, 0, 5858] para calcular o autovalor λ4;
• [µ3, µ2] = [0, 5858, 2] para calcular o autovalor λ3;
• [µ2, µ1] = [2, 3, 4142] para calcular o autovalor λ2;
• [µ1, ω] = [3, 4142, 6] para calcular o autovalor λ1.
de onde, após aplicarmos o algoritmo da bissecção a cada um desses intervalos, obtemos os
autovalores de T4 ≡ T , λ4 = 0, 3820, λ3 = 1, 3820, λ2 = 2, 6180 e λ1 = 3, 6180, após 27 iterações
(para todos os intervalos de busca).
Note que não se obtém, com essa técnica, os autovetores correspondentes aos autovalores. Os
métodos apresentados na seção a seguir podem ser utilizados para se obter esses autovetores.
6.5 Métodos para aproximação de autovalores e autovetores
Em muitas aplicações, não é necessário obter-se todos os autovalores; é comum desejar-se, por
exemplo, obter apenas o maior autovalor e seu correspondente autovetor. Os métodos apresentados
nessa seção são indicados para o caso em que apenas um dos autovalores (e seu autovetor) necessita
ser calculado. Particularmente, tais métodos são iterativos e apresentam boa eficiência quando a
matriz em estudo é grande, esparsa e apresenta uma grande separação relativa entre o autovalor
desejado e os demais autovalores.
6.5.1 Método da potência
Seja A uma matriz de ordem n com autovalores λi tais que
|λ1| = |λ2| = . . . = |λr| > |λr+1| ≥ . . . ≥ |λn| (6.18)
Nesse caso, diz-se que A apresenta r autovalores dominantes. Por hipótese, assumimos que existem
n autovetores linearmente independentes xi, de onde qualquer vetor arbitrário z0 pode ser expresso
como combinação linear desses autovetores, i.e.
z0 =
n∑
i=1
αixi (6.19)
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 120
Introdução ao Cálculo Numérico Autovalores e Autovetores
Considere agora o método de aproximação sucessiva
zk = Azk−1, k = 1, 2, . . . (6.20)
onde z0 é um valor inicial, dado. Usando as equações (6.1), (6.19) e escrevendo (6.20) em termos
de z0, temos
zk = Azk−1 = A2zk−2 = . . . = Akz0
=
n∑
i=1
αiλ
k
i xi (6.21)
Se pelo menos um dos α1, α2, . . ., αr não é nulo, então os termos correspondentes a eles, i.e.∑r
i=1 αiλ
k
i xi irão dominar o somatório da equação (6.21).
Suponha, por exemplo, que temos um autovalor dominante, λ1, de A. Considerando que
α1 �= 0, podemos reescrever (6.21) como
zk = λk1
(
α1x1 +
n∑
i=1
αi
(
λi
λ1
)k
xi
)
Note agora que, como λ1 > λ2 ≥ . . . ≥ λn, por hipótese, então os termos(
λi
λ1
)k
tendem a zero à medida que k cresce. Dáı, podemos escrever
zk = λk1(α1x1 + &k) (6.22)
onde &k é um vetor com elementos próximos a zero. O vetor zk tende, então, a aproximar o
autovetor não-normalizado x1. Essa equação nos permite escrever o assim chamado método da
potência.
Da equação (6.22), podemos escrever
zk+1 = λk+11 (α1x1 + &k+1)
e, dividindo a i-ésima componente da equação acima pela componente correspondente de (6.22),
obtemos
(zk+1)i
(zk)i
= λ1
(
α1x1 + &k+1
α1x1 + &k
)
→ λ1, quando k →∞, i = 1, 2, . . . , n (6.23)
onde (zk)i indica o elemento i do vetor zk. A equação (6.23) nos diz que a taxa de convergência
do método depende não só das constantes αi, mas principalmente das frações∣∣∣∣λ2λ1
∣∣∣∣ ,
∣∣∣∣λ3λ1
∣∣∣∣ , . . . ,
∣∣∣∣λnλ1
∣∣∣∣ .
Quanto menores forem esses frações, mais rápida é a convergência; por isso diz-se que o método
da potência é eficiente – converge rapidamente para um autovalor – desde que este autovalor seja
dominante, i.e., relativamente distante dos demais.
De posse das equações (6.20) e (6.23), podemos escrever um algoritmo para o método da
potência. Uma questão que se coloca é: quais valores iniciais, λ0 e z0, devemos utilizar para o
autovalor dominante e seu autovetor? Para z0, consideraremos um vetor arbitrário, o qual será
normalizado antes de se iniciar as iterações. Com essa escolha, valemo-nos da equação (6.1) e
escrevemos
Az0 = λ0z0 ... || z0 || = 1 ...
zT0 Az0 = z
T
0 λ0z0 = λ0(z
T
0 z0) = λ0
Aplica-se, então, repetidamente a equação (6.20), normalizando o vetor zk a cada iteração, conforme
mostrado no algoritmo 6.5.1. O exemplo 6.7 mostra o funcionamento do método.
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 121
Introdução ao Cálculo Numérico Autovalores e Autovetores
Algoritmo 6.5.1 Método da potência
proc potencia(input: A, z0, &, kmax; output: λk, zk)
z0 ← z0/|| z0 ||
λ0 ← zT0 Az0
for k = 1, 2, . . . , kmax do
q ← Azk−1
zk ← q/|| q ||
λk ← zTk Azk
if |λk − λk−1 | < & then
break
endif
endfor
endproc
Exemplo 6.7 Seja a matriz
A =

 8 1 2−1 5 1
0 1 90

 ,
a qual tem como autovalores e respectivos autovetores,
λ1 = 90, 0115, λ2 = 7, 6308, λ3 = 5, 3577
x1 =

 0, 02450, 0115
0, 9996

, x2 =

 −0, 93530, 3539
−0, 0043

 , x3 =

 −0, 0043−0, 0111
0, 9996

 .
Utilizando-se o método da potência com um vetor com três elementos escolhidos arbitrariamente
e normalizado, z0 = (0, 4394, 0, 6415, 0, 6287)T, obtém-se a seguinte seqüência de valores, com uma
tolerância para convergência de 10−5:
k zk λk
0 (0, 4394, 0, 6415, 0, 6287)T 40, 5408
1 (0, 0940, 0, 0590, 0, 9938)T 89, 2834
2 (0, 0313, 0, 0133, 0, 9994)T 89, 9939
3 (0, 0251, 0, 0115, 0, 9996)T 90, 0102
4 (0, 0246, 0, 0115, 0, 9996)T 90, 0114
5 (0, 0245, 0, 0115, 0, 9996)T 90, 0115
6 (0, 0245, 0, 0115, 0, 9996)T 90, 0115
onde pode-se verificar que z6 é uma boa aproximação para x1, sujeita àquela tolerância.
Caso a matriz tenha autovalores dominantes repetidos, i.e.
λ1 = λ2 = . . . = λr
o método da potência irá obter apenas um autovetor, o qual será combinação linear dos autovetores
correspondentes a λ1.
O método da potência diverge se A tiver autovalores diferentes, porém de mesmo valor absoluto
como, por exemplo, um par conjugado de autovalores dominantes complexos, λ2 = λ1; o exemplo
a seguir ilustra tal situação:
Exemplo 6.8 Seja a matriz
A =

 1 10 2−1 1 10
10 1 −13

 ,
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 122
Introdução ao Cálculo Numérico Autovalores e Autovetores
a qual tem como autovalores e respectivos autovetores,
λ1 = −9, 4515 + 3, 8807i, λ2 = −9, 4515− 3, 8807i, λ3 = 7, 9030
x1 =

 0, 0307− 0, 4143i0, 2160 + 0, 5518i
−0, 4368− 0, 5343i

 , x2 =

 0, 0307 + 0, 4143i0, 2160− 0, 5518i
−0, 4368 + 0, 5343i

 , x3 =

 0, 78970, 4651
0, 4000

 .
Utilizando-se o método da potência com um vetor com três elementos escolhidos arbitrariamente
e normalizado, z0 = (0, 4857, 0, 0197, 0, 8739)T, obtém-se a seguinte seqüência de valores, com uma
tolerância para convergência de 10−5:
k zk λk
0 (0, 4857, 0, 0197, 0, 8739)T −4, 3241
1 (0, 2253, 0, 7668,−0, 6010)T −9, 1975
2 (0, 4829,−0, 3946, 0, 7817)T −8, 1345
3 (−0, 2066, 0, 7546,−0, 6229)T −9, 4601
4 (0, 5786,−0, 5001, 0, 6443)T −6, 4876
5 (−0, 4517, 0, 7731,−0, 4454)T −6, 2931
6 (0, 8581,−0, 4338, 0, 2749)T −1, 8886
a qual apresenta um comportamento não convergente.
6.5.2 O método da potência com translação da origem
Como vimos na seção anterior, a convergência do método da potência depende de |λ2/λ1 |, para
o caso de existir apenas um autovalor dominante. Se essa razão for muito próxima de 1, então a
convergência é muito lenta.
No entanto, podemos obter a solução de forma mais rápida se procedermos a uma modificação
do método da potência. Essa modificação baseia-se no fato de que, se λ é um autovalor de uma
matriz A, então λ− σ é o autovalor correspondente da matriz A− σI. Dessa forma, se aplicarmos
o método da potência a uma matriz A− σI, tal que λ1 − σ ainda seja dominante, a convergência
do método dependerá de ∣∣∣∣ λ2 − σλ1 − σ
∣∣∣∣
o que, para um valor adequado de σ, poderá ser menor do que |λ2/λ1 |. A esse processo, dá-se
o nome de translação da origem – é como se os autovalores estivessem distribúıdos em um novo
sistema de referência cuja origem é σ, e não mais zero – e pode ser bastante eficaz, desde que a
escolha de σ seja criteriosa.
Obviamente, podeŕıamos calcular explicitamente a matriz A− σI e utilizar o algoritmo 6.5.1;
no entanto, pequenas modificações naquele algoritmo nos permitem utilizar o processo de trans-
lação da origem de forma mais eficiente. Novamente, z0 é considerado um vetor unitário, de onde
podemos obter a seguinte estimativa para λ0:
(A− σI)z0 = λ0z0; pré-multiplicando por zT0 ,
zT0 Az0 − σzT0 z0 = λ0(zT0 z0) ... || z0 || = 1 ...
λ0 = zT0 Az0 − σ
e, por analogia, escrevemos
λk = zTk Azk − σ
Além disso, ao invés de calcularmos q = Azk, devemos calcular q = Azk − σzk. Ao final do
processo, devemos corrigir λk, adicionando a ele σ. Essas idéias são apresentadas no algoritmo
6.5.2.
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 123
Introdução ao Cálculo Numérico Autovalores e Autovetores
Algoritmo 6.5.2 Método da potência (com translação)
proc potencia translação(input: A, z0, σ, &, kmax; output: λk, zk)
z0 ← z0/|| z0 ||
λ0 ← zT0 Az0 − σ
for k = 1, 2, . . . , kmax do
q ← Azk−1 − σzk−1
zk ← q/|| q ||
λk ← zTk Azk − σ
if |λk − λk−1 | < & then
break
endif
endfor
λk ← λk + σ
endproc
O exemplo a seguir ilustra o uso do método da potência com translação de origem.
Exemplo 6.9 Seja a matriz
A =

 2 −1 0−1 2 −1
0 −1 2

 ,
a qual tem como autovalores e respectivos autovetores,
λ1 = 3, 4142, λ2 = 2, λ3 = 0, 5858
x1 =

 0, 5000−0, 7071
0, 5000

 , x2 =

 0, 70710, 0000
−0, 7071

 , x3 =

 0, 50000, 7071
0, 5000

 .
Note que |λ2/λ1 | = 0, 5858. Se utilizarmos o método da potência, a uma tolerância de 10−5 e
vetor inicial z0 = (1, 0, 0)T , necessitaremos de 13 iterações para obter a aproximação 3, 4142 para
o autovalor λ1.
No entanto, se usarmos o translação da origem, com σ = 1, necessitamos apenas de 9 iterações
para obter a mesma aproximação; veja que∣∣∣∣ λ2 − 1λ1 − 1
∣∣∣∣ =
∣∣∣∣ 12, 4142
∣∣∣∣ = 0, 4142 < 0, 5858 =
∣∣∣∣ λ2λ1
∣∣∣∣
o que sugere o menor número de iterações.
6.5.3 Método da iteração inversa
Como vimos, o método da potência nos permite aproximar o autovalor dominante de A; suponha,
agora, que desejamos aproximar o menor autovalor (e seu correspondente autovetor) de A. Re-
lembrando que os autovalores de A−1 são o inverso dos autovalores de A (equação (6.3)), então,
se utilizarmos o método da potência sobre a matriz A−1, aproximaremos o menor autovalor de
A pois ele é o maior autovalor de A−1. A essa modificação do método da potência chamamos de
método da iteração inversa.
O método da iteração inversa procede, basicamente, com o cálculo sucessivo de vetores zk
dados por
zk = A−1zk−1, k = 1, 2, . . .
mas já vimos (caṕıtulo 4) que, computacionalmente, devemos evitar, se posśıvel, calcular a inversa
de uma matriz. Nesse caso, é aconselhado que se resolva o sistema
Azk = zk−1, k = 1, 2, . . .
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 124
Introdução ao Cálculo Numérico Autovalores e Autovetores
através da fatoração LU de A (seção 4.3.2), uma vez que várias iterações serão necessárias para
se aproximar o menor autovalor e respectivo autovetor.
Além disso, o método da iteração inversa é, normalmente, combinado com a translação de
origem, o que resulta na fatoração LU da matriz A − σI. O algoritmo 6.5.3 apresenta o método
da iteração inversa, incorporando translação de origem.
Algoritmo 6.5.3 Método da iteração inversa (com translação)
proc iteração inversa translação(input: A, z0, σ, &, kmax;
output: λk, zk)
Fatore A− σI no produto LU
z0 ← z0/|| z0 ||
λ0 ← zT0 Az0 − σ
for k = 0, 1, . . . , kmax do
Resolva o sistema Ly = zk
Resolva o sistema Uq = y
zk ← q/|| q ||
λk ← zTk Azk − σ
if |λk − λk−1 | < & then
break
endif
endfor
λk ← λk + σ
endproc
Exemplo 6.10 Seja a matriz do exemplo 6.9,
A =

 2 −1 0−1 2 −1
0 −1 2

 ,
cujo menor autovalor é λ3 = 0, 5858 e o seu correspondente autvetor é x3 = (0, 5000, 0, 7071, 0, 5000)T .
Se utilizarmos o algoritmo 6.5.3 com σ = 0, i.e. sem translação da origem, a uma tolerância
de 10−5 e vetor inicial z0 = (1, 0, 0)T , necessitaremos de 7 iterações para obter a aproximação
0, 5858 para o autovalor λ3 e (0, 5002, 0, 7071, 0, 4998)T para o correspondente autovetor.
No entanto, se usarmos o translação da origem, com σ = 0, 5, necessitamos apenas de 4
iterações para obter a mesma aproximação; veja que∣∣∣∣ λ−12 − 0, 5λ−13 − 0, 5
∣∣∣∣ =
∣∣∣∣ 00, 0858
∣∣∣∣ = 0 < 0, 2929 =
∣∣∣∣ λ−12λ−13
∣∣∣∣
o que sugere o menor número de iterações; na verdade, σ = 0, 5 é a melhor escolha posśıvel, nesse
caso.
Outro exemplo mostra como usar o método da iteração inversa em conjunto com o teorema de
Gerschgorin, a fim de se determinar um autovalor espećıfico.
Exemplo6.11 Seja a matriz
A =

 5 2 12 3 1
1 1 1


Os discos de Gerschgorin são:
d1 : c1 = 5, r1 = 3
d2 : c2 = 3, r2 = 3
d3 : c3 = 1, r3 = 2
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 125
Introdução ao Cálculo Numérico Autovalores e Autovetores
Suponha que desejamos aproximar o menor autovalor; como o disco d3 é aquele que se encontra
mais à esquerda em comparação aos demais, podemos utilizar o seu centro como fator de transla-
ção. Então, utilizamos o método da iteração inversa com σ = 1, vetor inicial z0 =
√
3
−1
(1, 1, 1)T
e tolerância 10−5 e obtemos λ = 0, 5764 e z = (−0, 0597,−0, 3380, 0, 9393)T após 10 iterações.
Por outro lado, se tivéssemos utilizado σ = c3 + r3, a convergência para o mesmo autovalor seria
obtida em apenas 4 iterações.
6.5.4 O método da iteração inversa e o quociente de Rayleigh
Como visto no teorema 6.2.2, o valor do autovalor dominante λ1 de uma matriz real simétrica
é o máximo do quociente de Rayleigh, dentre todos os vetores x �= 0. Isso nos permite utilizar
a expressão (6.12) juntamente com o método da iteração inversa, conforme mostra o algoritmo
6.5.4.
Algoritmo 6.5.4 Método da iteração inversa com translação via
quociente de Rayleigh)
proc iteração inversa translação(input: A, z0, &, kmax;
output: λk, zk)
z0 ← z0/|| z0 ||
for k = 0, 1, . . . , kmax do
λk =
zTk Azk
zT
k
zk
Resolva o sistema (A− λkI)q = zk
zk ← q/|| q ||
if || zk − zk−1 || < & then
break
endif
endfor
endproc
Note que, no algoritmo 6.5.4, um sistema de equações diferente é resolvido a cada iteração, já
que uma nova estimativa λk é utilizada a cada iteração. É posśıvel, no entanto, que o sistema
A− λkI seja singular e, nesse caso, o processo deve ser terminado.
6.6 Exerćıcios
Exerćıcio 6.1 Determine os autovalores e autovetores correspondentes da matriz
 1 −1 −10 2 5
0 0 −1

 .
Exerćıcio 6.2 Calcule o autovalor dominante de
 10 9 83 5 6
7 2 −1

 .
Exerćıcio 6.3 Calcule o autovalor dominante e o autovetor correspondente da matriz
 6 2 12 3 1
1 1 1

 ,
usando o método da potência, com z0 = (1, 1, 1)T e tolerância 10−5.
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 126
Introdução ao Cálculo Numérico Autovalores e Autovetores
Exerćıcio 6.4 Calcule o autovalor dominante e o autovetor correspondente da matriz
 0 1 1−1 0 1
−1 −1 0

 ,
usando o método da potência, com z0 = (1, 1, 1)T e tolerância 10−5.
Exerćıcio 6.5 Explique o que acontece com o método da potência para a matriz
 2 1 −11 2 −1
1 −1 2

 ,
com z0 = (1, 1, 1)T e tolerância 10−5, sabendo que os seus autovalores são 1, 2 e 3. Repita para
z0 = (1, 0, 10−6)T .
Exerćıcio 6.6 Utilize o método da iteração inversa para calcular o menor autovalor da matriz
 2 1 −11 2 −1
1 −1 2

 ,
com z0 = (1, 1, 1)T e tolerância 10−5.
Exerćıcio 6.7 Seja a matriz
A =

 5 2 12 3 1
1 1 1


Explique o que ocorre com o método da iteração inversa utilizado com σ = 3, z0 = (1, 0, 0)T e
tolerância 10−5. Generalize a sua resposta.
A.L. de Bortoli, C. Cardoso, M.P.G. Fachin, R.D. da Cunha 127