autovalores-autovetores

Prévia do material em texto

Autovalores e Autovetores
Lucia Catabriga
Algoritmos Nume´ricos II
Computac¸a˜o Cient´ıfica
Universidade Federal do Esp´ırito Santo
10 de junho de 2014
Resumo
Este texto tem por objetivo introduzir os conceitos ba´sicos para o ca´lculo
aproximado de autovalores e autovetores dentro do contexto da disciplina
A;goritmos Nume´ricos II do Departamento de Informa´tica da Universidade
Federal do Esp´ırito Santo (DI/UFES). Na˜o e´ um texto completo, apenas
introduto´rio, detalhes devem ser consultados em ?? .
Cap´ıtulo 1
Introduc¸a˜o
Neste cap´ıtulo estudaremos me´todos nume´ricos para encontrar autovalores
e autovetores de matrizes com coeficientes reais. Os autovalores e corres-
pondentes autovetores de uma matriz satisfazem a propriedade:
Se multiplicarmos a matriz por um autovetor encontramos um multiplo
do pro´prio autovetor, com constante de multiplicidade conhecida por auto-
valor.
Seja
A =

 16 −24 183 −2 0
−9 18 −17


o vetor

 21
0

 satisfaz a

 16 −24 183 −2 0
−9 18 −17



 21
0

 = 4

 21
0


Portanto

 21
0

 e´ autovetor com autovalor correspondente igual a 4.
Como o autovetor foi pre´-multiplicado pela matriz e´ conhecido como
autovetor direito. A equac¸a˜o alge´brica para o autovalor λ e correspondente
autovetor direito q de uma matriz A e´:
Aq = λq
observe que esta equac¸a˜o so´ tem sentido para matrizes quadradas, portanto
somente tais matrizes possuem autovalores.
1
Um me´todo para encontrar os autovalores de uma matriz A pode ser
ilustrado atrave´s da matriz do exemplo anterior.
 16 −24 183 −2 0
−9 18 −17



 q1q2
q3

 = λ

 q1q2
q3


que pode ser escrito na forma
 (16− λ) −24 183 (−2− λ) 0
−9 18 (−17− λ)



 q1q2
q3

 = λ

 00
0


que e´ um sistema homogeˆneo. Este sistema so´ tem soluc¸a˜o na˜o-trivial (qi 6=
0) se a matriz for singular, ou seja se o determinante for nulo.
det

 (16− λ) −24 183 (−2− λ) 0
−9 18 (−17− λ)

 = 0⇔ λ3 + 3λ2 − 36λ+ 32 = 0
ou
(λ− 4)(λ− 1)(λ+ 8) = 0
que e´ denominada equac¸a˜o caracteristica. Os autovalores da matriz A sa˜o
λ = 4, λ = 1 e λ = −8.
Em geral a equac¸a˜o Aq = λq pode ser representada pelo sistema ho-
mogeˆneo (A−λI)q = 0. Se A e´ uma matriz de ordem n o sistema homogeˆneo
tem soluc¸a˜o na˜o-trivial se
det


(a11 − λ) a12 . . . a1n
a21 (a22 − λ) . . . a2n
...
...
. . .
...
an1 an2 . . . (ann − λ)

 = 0
A equac¸a˜o caracteristica tem a forma geral:
λn + cn−1λ
n−1 + . . .+ c1λ+ c0 = 0
O me´todo da equac¸a˜o caracter´ıstica na˜o e´ um bom processo nume´rico
para determinar os autovalores de uma matriz. O nu´mero de operac¸o˜es ne-
cessa´rias para obter os coeficientes da equac¸a˜o caracter´ıstica e´ muito grande.
Nos pro´ximos itens desenvolveremos processos mais eficientes para determi-
nar os autovalores.
Diversas aplicac¸o˜es recaem em problemas de autovalores, tais como:
• Flambagem de uma coluna
2
• Vibrac¸a˜o de estruturas
• Vibrac¸o˜es amortecidas
• Cadeias de Markov
No final deste cap´ıtulo desenvolveremos algumas aplicac¸o˜es citadas. Estas
aplicac¸o˜es nos levaram a determinar autovalores e autovetores de matrizes
que apresentam caracter´ısticas especiais, por exemplo matrizes tridiagonais.
Na pro´xima sec¸a˜o apresentamos algumas propriedades importantes de au-
tovalores e autovetores que sera˜o usadas no desenvolvimento nume´rico.
1.1 Algumas Propriedades de Autovalores
1. A equac¸a˜o caracter´ıstica pode ser fatorada na forma:
(λ− λ1)(λ− λ2) . . . (λ− λn) = 0
Esta equac¸a˜o mostra que uma matriz de ordem n tem n autovalores .
Pore´m os autovalores na˜o sa˜o necessariamente distintos (por exemplo,
podemos ter λ1 = λ2 = λn−1).
2. A soma dos elementos da diagonal principal da matriz e´ chamada
trac¸o. Sendo que:
tr(A) = a11 + a22 + . . .+ ann = −cn−1 = λ1 + λ2 + . . .+ λn
ou seja:
A soma dos autovalores de uma matriz e´ igual ao trac¸o da matriz
3. O produto dos autovalores da matriz e´ igual ao determinante da matriz
detA = (−1)nc0 = λ1λ2 . . . λn
Portanto se A e´ singular, existe pelo menos um autovalor λi = 0
4. A matriz A e sua transposta At tem os mesmos autovalores, pois o
detA = detAt.
5. O determinante de uma matriz triangular e´ igual ao produto dos ele-
mentos da diagonal. Enta˜o se A e´ triangular:
det(A− λI) = (a11 − λ)(a22 − λ) . . . (ann − λ)
Portanto os autovalores de uma matriz triangular sa˜o iguais aos ele-
mentos da diagonal.
3
6. Se as linhas e colunas correspondentes de uma matriz sa˜o trocadas os
autovalores permanecem os mesmos. Por exemplo:
 16 −24 183 −2 0
−9 18 −17



 q1q2
q3

 = λ

 q1q2
q3


Se trocarmos a linha 1 com a linha 2 e a coluna 1 com a coluna 2,
obtemos: 
 −2 3 0−24 16 18
18 −9 −17



 q2q1
q3

 = λ

 q2q1
q3


observe que os autovalores permanecem os mesmos, mas ao autovetores
tem a 1a. coordenada q1 trocada com a segunda coordenada q2.
7. Considere uma matriz A 4x4 e um autovalor λ. Multiplicando a se-
gunda linha de A por f, a segunda coluna de A por 1/f e a segunda
componente de q por f, obtemos:


a11 a12/f a13 a14
fa21 a22 fa23 fa24
a31 a32/f a33 a34
a41 a42/f a43 a44




q1
fq2
q3
q4

 = λ


q1
fq2
q3
q4


Portanto se uma linha de uma matriz e´ multiplicada por um escalar
e a coluna correpondente e´ multiplicada pelo inverso do escalar os
autovalores permanecem os mesmos.
O ca´lculo dos autovetores associados envolvem a soluc¸a˜o de um sistema
homogeˆneo. Para cada autovalor definimos um sistema de n equac¸o˜es e n
inco´gnitas
(A− λI)q = 0
Por exemplo:
A matriz
A =

 16 −24 183 −2 0
−9 18 −17


tem por autovalores λ1 = 4, λ2 = 1 e λ3 = −8. O autovetor associado a
λ1 = 1 e´ o vetor q tq (A− λI)q = 0, ou seja
 15 −24 183 −3 0
−9 18 −18



 q1q2
q3

 =

 00
0

 m21 = 0.2
m31 = −0.6
4
∼

 15 −24 180 1.8 −3.6
0 3.6 −7.2



 q1q2
q3

 =

 00
0

L3 = 2L2
Considerando somente L1 e L2, chegamos a:
q1 = q2 = 2q3
Portanto qualquer vetor que possui esta propriedade e´ autovetor associado
ao autovalor λ = 1.
Seja q =

 22
1

.
Para encontrar cada autovetor sa˜o necessa´rios n3/3 multiplicac¸o˜es se a
matriz dos coeficientes for cheia e na˜o sime´trica. Portanto a determinac¸a˜o
dos autovetores na˜o e´ considerado um processo nume´rico trivial, mesmo
quando os autovalores sa˜o conhecidos.
E´ poss´ıvel combinar a equac¸a˜o padra˜o dos autovalores com todos os
autovalores e correspondentes autovetores na forma:
A

 q1 q2 . . . qn

 =

 q1 q2 . . . qn




λ1
λ2
. . .
λn


isto e´,
AQ = QΛ
onde Λ e´ a matriz diagonal dos autovalores.
Q matriz quadrada contendo todos os autovetores.
5
Cap´ıtulo 2
Me´todos Iterativos Simples
2.1 Me´todo Das Poteˆncias
O objetivo do me´todo das poteˆncias e´ determinar o autovalor de maior
mo´dulo dentre todos os autovalores de uma matriz.
Seja A uma matriz de ordem n.
Sejam λ1, λ2, . . . , λn os autovalores de A e q1, q2, . . . , qn os autovetores
correspondentes.
Suponha que |λ1| > |λ2| ≥ . . . ≥ |λn|. Vamos desenvolver um processo
iterativo para determinar λ1.
Seja u(0) uma combinac¸a˜o linear dos autovetores correspondentes:
u(0) = c1q1 + c2q2 + . . .+ cnqn
Os autovetores sa˜o linearmente independentes.
u(1) = Au(0) = c1Aq1 + c2Aq2 + . . .+ cnAqn
= c1λ1q1 + c2λ2q2 + . . .+ cnλnqn
= λ1
[
c1q1 + c2
λ2
λ1
q2 + . . .+ cn
λn
λ1
qn
]
u(2) = A2u(0) = λ1
[
c1Aq1 + c2
λ2
λ1
Aq2 + . . .+ cn
λn
λ1Aqn
]
= λ21
[
c1q1 + c2
(
λ2
λ1
)2
q2 + . . .+ cn
(
λn
λ1
)2
qn
]
Se pre´-multiplicarmos a expressa˜o pela matriz A k-vezes obtemos:
u(k) = Aku(0) = λk1
[
c1q1 + c2
(
λ2
λ1
)k
q2 + . . .+ cn
(
λn
λ1
)k
qn
]
Como |λ1| > |λ2| ≥ . . . ≥ |λn|, temos que
∣∣∣ λiλ1 ∣∣∣ < 1, para i = 2, . . . , n.
Portanto quando k →∞
(
λi
λ1
)k
→ 0 para i = 2, . . . , n.
6
Enta˜o, o vetor[
c1q1 + c2
(
λ2
λ1
)k
q2 + . . .+ cn
(
λn
λ1
)k
qn
]
→ c1q1
que e´ um autovetor associado a λ1. Portanto podemos afirmar que para
valores grandes de k
u(k) ≃ λk1c1q1
u(k) tende a ser proporcional ao autovetor q1. Considerando que o autovetor
pode ter tamanho arbitra´rio (ou seja, um autovetor multiplicado por um
escalar tem o mesmo autovalor associado) e´ conveniente normalizar o vetor
que gera o processo iterativo depois de cada multiplicac¸a˜o. O algoritmo
iterativo para determinar q1 pode ser representado atrave´s das equac¸o˜es:

v(k) = Au(k)
u(k+1) = 1
α
v(k)
onde α = ± ‖ v(k) ‖
Exemplo: Considere a matriz
A =

 528.2 547.6 156.4273.8 312.8 98.0
78.2 98.0 39.0


Seja u(0) = (1 1 1)(t) e considere a norma do ma´ximo para obter o valor
de α.
• Iterac¸a˜o 1
 528.2 547.6 156.4273.8 312.8 98.0
78.2 98.0 39.0


︸ ︷︷ ︸
A

 11
1


︸ ︷︷ ︸
u(0)
=

 1232.1684.6
215.3


︸ ︷︷ ︸
v(0)
= 1232.1︸ ︷︷ ︸
α

 10.5556
0.1747


︸ ︷︷ ︸
u(1)
• Iterac¸a˜o 2
 A



 10.5556
0.1747


︸ ︷︷ ︸
u(1)
=

 859.7464.7
139.5


︸ ︷︷ ︸
v(1)
= 859.7︸ ︷︷ ︸
α

 10.5406
0.1622


︸ ︷︷ ︸
u(2)
• Iterac¸a˜o 3
 A



 10.5406
0.1622


︸ ︷︷ ︸
u(2)
=

 849.5458.8
137.3


︸ ︷︷ ︸
v(2)
= 849.5︸ ︷︷ ︸
α

 10.5400
0.1616


︸ ︷︷ ︸
u(3)
7
• Iterac¸a˜o 4
 A



 10.5400
0.1616


︸ ︷︷ ︸
u(3)
=

 849.1458.6
137.4


︸ ︷︷ ︸
v(3)
= 849.1︸ ︷︷ ︸
α

 10.5400
0.1619


︸ ︷︷ ︸
u(4)
O autovetor aproximado e´ u(4) ≃ q1 com erro inferior a 10
−3. O autovetor
correspondente e´ λ1 ≃ 849.1.
Quando a norma do ma´ximo e´ usada o sinal de α pode ser o mesmo do
maior elemento em mo´dulo. Neste caso α convergira´ para λ1 ate´ mesmo
quando ele for negativo, ale´m disso a sequeˆncia de vetores convergira´ nor-
malmente para q1.
Exemplo:
Encontre o maior autovalor da matriz
A =

 16 −24 183 −2 0
−9 18 −17


usando u(0) = (1 1 1)(t) e norma do ma´ximo para obter o valor de α. Fac¸a
algumas iterac¸o˜es.
Apo´s construir algumas iterac¸o˜es e´ possivel observar que a convergeˆncia
para o autovalor pode ser mais ra´pida que a convergeˆncia para o autovetor
associado.
Em geral, dependendo de cada aplicac¸a˜o, e´ poss´ıvel escolher uma apro-
ximac¸a˜o inicial para o autovetor associado ao autovalor de maior mo´dulo
atrave´s de algum crite´rio. Pore´m, quando na˜o existe alguma informac¸a˜o, e´
necessa´rio um cuidado especial para na˜o escolher u(0) tal que o coeficiente c1
seja nulo ou muito pequeno quando comparado com os outros coeficientes.
Para implementac¸o˜es computacionais do me´todo das poteˆncias, a deter-
minac¸a˜o do vetor inicial u(0) e´ feita atrave´s de procedimentos automa´ticos.
Um procedimento bastante usado consiste em gerar os elementos dos vetor
atrave´s de nu´meros randoˆmicos no intervalo −1 ≤ u
(0)
i ≤ 1. Quando este
processo e´ usado a probabilidade de ocorrer c1 = 0 e´ bem pequena.
2.1.1 Caracter´ısticas da Convergeˆncia do Me´todo das Poteˆncias
O autovetor u(k) pode ser expresso:
u(k) = q1 + e
(k)
onde
e(k) =
(
λ2
λ1
)k c2
c1
q2 + . . .+
(
λn
λ1
)k cn
c1
qn
8
Por hipo´tese temos que |λ1| > |λ2| ≥ . . . ≥ |λn|, portanto para valores
grande de k o erro pode ser aproximado por
‖ e(k) ‖∼
∣∣∣∣λ2λ1
∣∣∣∣(k) |c2||c1| ‖ q2 ‖
E´ possivel provar que |c2| ∼ |c1|.
Atrave´s desta aproximac¸a˜o e´ poss´ıvel estimar o nu´mero de iterac¸o˜es ne-
cessa´rias para atingir uma toleraˆncia pre´-fixada. Para exemplificar, suponha
que desejamos calcular os autovalores de uma matriz com toleraˆncia de 10−s.
Como ja´ foi mostrado o erro na iterac¸a˜o k depende do quociente
∣∣∣λ2λ1 ∣∣∣k, enta˜o:∣∣∣∣λ2λ1
∣∣∣∣k ≃ 10−s
k ≃
−sln10
ln|λ2/λ1|
Portanto se
∣∣∣λ2λ1 ∣∣∣ estiver pro´ximo de 1, o me´todo das poteˆncias converge
vagarosamente.
E´ poss´ıvel acelerar a convergeˆncia do me´todo das poteˆncias. Nota-se que
o uso da Norma Euclidiana no me´todo para normalizar os autovetores e
determinar os autovalores correspondentes aceleram a convergeˆncia, princi-
palmente no caso de matrizes sime´tricas. Pore´m este processo na˜o estabelece
um crite´rio simples para a escolha do sinal de α. Em geral, adota-se que o
sinal de α deve ser tal que as componentes do autovetor de uma iterac¸a˜o
a outra permanecam com o mesmo sinal. Outro processo similar a norma
euclidiana para matrizes sime´tricas em termos de precisa˜o e´ usar o Coefi-
ciente de Rayleigh para normalizar o vetor v(k):
α =
(u(k))tAu(k)
(u(k))tu(k)
=
(u(k))tv(k)
(u(k))tu(k)
Apesar da precisa˜o deste crite´rio ser similar a da norma euclidiana, na˜o
existe o incoveniente da escolha do sinal.
Portanto poderiamos definir o seguinte algoritmo:
9
Algoritmo 1: Me´todo da Iterac¸a˜o Inversa
1 Entrada: A,v(0),ǫ,kmax
2 Inicializar ρ (ρ = 1.0)
3 Inicializar λk (λk = 0.0)
4 while ρ > ǫ and k < kmax do
5 u = Av(k)
6 Resolva Uv = y
7 λk+1 =
v(k)
T
u
v(k)
T
v(k)
8 v(k+1) = u
λk+1
9 ρ =
|λk+1−λk|
|λk+1|
10 k = k + 1
11 end
12 Sa´ıda: λk+1, v
(k+1)
No entanto, podemos escalonar a sequeˆncia v(k), antes de calcular o λk.
Para isso, seja y(k) = u
(k)
‖u(k)‖
, enta˜o ‖y(k)‖ = 1.
Ay(k) ≈ λky
(k) λk =
y(k)
T
Ay(k)
y(k)
T
y(k)
= y(k)
T
u(k+1)
Exemplo:
Considere a Matriz sime´trica
A =


2 −1
−1 2 −1
−1 2 −1
−1 2


O autovalor de maior mo´dulo calculado pelo me´todo das poteˆncias e´
λ = 2.61803. A tabela abaixo mostra a toleraˆncia atingida para algumas
iterac¸o˜es, demonstrando que o uso da norma euclidiana e/ou do coeficiente
de Rayleigh acelera moderadamente a convergeˆncia. Para tal, Considere
u(0) = {1, 1, 1, 1} e crite´rio de parada ‖u
(k)−u(k−1)‖
‖u(k)‖
< ǫ.
4 iterac¸o˜es 6 iterac¸o˜es 8 iterac¸o˜es 10 iterac¸o˜es
N. Ma´ximo 1.538× 10−2 3.305× 10−4 7.035× 10−5 1.498× 10−7
N. Euclidiana 1.124× 10−2 2.391× 10−4 5.091× 10−6 1.083× 10−7
C. de Rayleigh 1.124× 10−2 2.391× 10−4 5.091× 10−6 1.083× 10−7
2.2 Me´todo da Poteˆncia Inversa
O me´todo da poteˆncia inversa e´ usado para determinar o autovalor de menor
valor absoluto e seu correspondente autovalor de uma matriz A. De forma
10
semelhante ao me´todo das poteˆncias, o me´todo e´ u´til para determinar o
menor autovalor em mo´dulo, desde que o mesmo esteja bem separado dos
demais, isto e´, seja menor que todos os outros e na˜o muito pro´ximo do
segundo menor. Considerando que |λ1| ≤ |λ2| ≤ . . . ≤ |λn−1| > |λn|,
desejamos calcular |λn|. Sabemos que se λ e´ autovalor de A, λ
−1 e´ autovalor
de A−1. Portanto se λn e´ o menor autovalor em mo´dulo de A, λ
−1
n e´ o maior
autovalor de A−1 em mo´dulo. Assim, dado
2.3 Me´todo da Sequeˆncia de Sturm
Em geral a soluc¸a˜o nume´rica de um problema de autovalor na˜o envolve a
determinac¸a˜o do polinoˆmio caracter´ıstico, pois o ca´culo do mesmo necessita
de muitas operac¸o˜es o que e´ envia´vel computacionalmente. Pore´m para
matrizes tridiagonais sime´tricas e´ poss´ıvel obter o polinoˆmio caracter´ıstico
atrave´s de um processo simplificado.
Seja A uma matriz tridiagonal de ordem n:
A =


α1 β1
β1 α2 β2
β2 α3 β2
. . .
. . .
. . .
βn−2 αn−1 βn−1
βn−1 αn

Considere a sequeˆncia formada por
fk(λ) = det


α1 β1
β1 α2 β2
. . .
. . .
. . .
βk−2 αk−1 βk−1
βk−1 αk


para 1 ≤ k ≤ n e f0(λ) ≡ 1.
Assim
f1(λ) = α1 − λ
f2(λ) = (α1 − λ)f1(λ)− β
2
1f0(λ)
...
fk(λ) = (αk − λ)fk−1(λ)− β
2
k−1fk−2(λ)
O processo descrito para obter o polinoˆmio caracter´ıstico fn(λ) requer
2n−3 multiplicac¸o˜es. Podemos enta˜o considerar qualquer me´todo nume´rico
para encontrar os zeros do polinoˆmio caracter´ıstico. Pore´m a sequeˆncia
{fk(λ), 1 ≤ k ≤ n} possui propriedades especiais e por isso e´ denominada
por sequeˆncia de Sturm. Tais propriedades nos levara˜o a isolar facilmente
os autovalores de A.
11
Propriedade da Sequeˆncia de Sturm: Seja a func¸a˜o de valores inteiros
s(λ) que guarda o nu´mero de trocas de sinal de membros consecutivos da
sequeˆncia {fk(λ)}. Dado um intervalo [a, b], o nu´mero de ra´ızes da equac¸a˜o
fn(λ) = 0 (ou o nu´mero de autovalores de A) no intervalo [a, b] e´ igual a
|s(a) − s(b)|. Se algum membro e´ nulo, ou seja, suponha que fj(λ) = 0.
Neste caso, observa-se a troca de sinal entre os membros fj−1(λ) e fj+1(λ),
pois se fj(λ) = 0 enta˜o fj−1(λ) 6= 0.
E´ possivel determinar o intervalo que contenha os autovalores de uma
matriz. Suponha uma matriz A de ordem n. Seja λ um autovalor e q um
autovetor correspondente, portanto
Aq = λq
suponha que o autovetor esta´ normalizado, ou seja, existe uma componente
qk = 1 e |qi| < 1 para i 6= k, assim:


× × . . . × . . . ×
× × . . . × . . . ×
ak1 ak2 . . . akk . . . akn
× × . . . × . . . ×




q1
q2
...
1
...
qn


= λ


q1
q2
...
1
...
qn


O produto da linha k com o vetor q gera a equac¸a˜o:
ak1q1 + ak2q2 + . . .+ akk + . . .+ akn = λ
Portanto
λ− akk =
∑
j 6=k
akjqj
como |qj | < 1
|λ− akk| ≤
∑
j 6=k
|akj |
O intervalo que conte´m todos os autovalores e´ formado pela unia˜o de
todos os intervalos definidos na expressa˜o anterior, ou seja para todo k.
Exemplo:
A Sequeˆncia de Sturm da matriz
A =

 2 −1−1 2 −1
−1 2


e´ dada por
12
f0(λ) = 1
f1(λ) = (2− λ)
f2(λ) = (2− λ)f1(λ)− 1
f3(λ) = (2− λ)f2(λ)− f1(λ)
O intervalo que conte´m todos os autovalores e´ dado pela unia˜o dos in-
tervalos:
|λ− 2| ≤ 1
|λ− 2| ≤ 2
|λ− 2| ≤ 1
Todos os autovalores de A esta˜o no intervalo [0,4]. Observe que f3(2) = 0,
portanto λ = 2 e´ autovalor da matriz A. Na tabela a seguir calculamos um
autovalor de A no intervalo (2,4), usando a propriedade de Sturm. O pro-
cesso consiste inicialmente em observar o nu´mero de trocas de sinal que
ocorre no intervalo [2,4], que e´ igual a 2 (sendo que λ = 2 e´ autovalor. Este
fato, significa que existe somente um autovalor no intervalo (2,4). O pro-
cesso iterativo deve continuar sempre particionando o intervalo que conte´m
o autovalor ao meio ate´ que uma determinada toleraˆncia pre´-fixada seja
atingida.
λ f0 f1 f2 f3 No. trocas de sinal
2 + 0 - 0 1
4 + - + - 4.0 3
3 + - 0 + 1.0 2
3.5 + - + - 0.375 3
3.25 + - + + 0.546875 2
3.375 + - + + 0.1503906 2
3.4375 + - + - 0.0954589 3
3.40625 + - + + 0.0315856 2
3.421875 + - + - 0.0621452 3
3.4140625 + - + + 0.0006041 2
3.4179688 + - + - 0.0150806 3
3.4142968 + - + - 0.0003333 3
2.4 Me´todo da Iterac¸a˜o Inversa
Seja Q a matriz que conte´m em cada coluna os autovetores de A e Λ a matriz
diagonal contendo os autovalores correspondentes:
AQ = QΛ
onde
13
Q =

 q1 q2 . . . qn

 e Λ =


λ1
λ2
. . .
λn


Em particular
Aqi = λiqi p/ i = 1, 2, . . . , n
Sem perda de generalidades, pode-se assumir que ‖ qi ‖∞= 1 ∀i.
Seja λ uma aproximac¸a˜o de um autovalor λk. Considere z
(0) um ve-
tor condic¸a˜o inicial para o ca´lculo do autovalor correspondente λ (ou λk).
Define-se duas sequeˆncias {w(m)} e {z(m)} tq
(A− λI)w(m+1) = z(m) e z(m+1) =
w(m+1)
‖ w(m+1) ‖∞
p/ m ≥ 0
O processo que acabamos de apresentar e´ essencialmente o Me´todo das
poteˆncias aplicado a matriz (A − λI)−1. Pore´m a matriz (A − λI) e´ mal-
condicionada, pois
det(A− λkI) = 0 sendo λ ≈ λk
O processo de obtenc¸a˜o do autovalor λ(≈ λk) causa o acu´mulo de erros
de arredondamento na matriz (A−λkI), o que leva a concluir que estes erros
equilibram a instabilidade. E´ possivel estudar com cautela este fato, pore´m
neste texto na˜o aprofundaremos esta discussa˜o. O vetor z(m) gerado pelas
sequeˆncias descritas converge para o autovetor correspondente de λk.
2.4.1 Implementac¸a˜o do Me´todo
A fatorac¸a˜o LU sera´ usada para decompor a matriz (A − λI) e resolver o
sistema (A− λI)w(m+1) = z(m). Portanto dado uma aproximac¸a˜o z(m):
LUw(m+1) = z(m)
⇓
Ly(m+1) = z(m)
Uz(m+1) = y(m+1)
⇒
w(m+1)
‖ w(m+1) ‖∞
p/ m ≥ 0
Como (A − λI) e´ quase singular, o u´ltimo elemento da diagonal de U
pode ser bem pequeno. Caso seja nulo, e´ poss´ıvel executar uma pequena
alterac¸a˜o no seu valor ou alterar o valor aproximado λ e recalcular L e U .
Este procedimento, em geral oferece bons resultados.
14
A condic¸a˜o inicial z(0), a princ´ıpio, poderia ser um vetor com nu´meros
randoˆmicos de -1 a 1. Pore´m demonstra-se que o seguinte procedimento leva
a melhores resultados:
z(0) = Le onde e =


1
1
...
1


Assim
y(1) = e ⇒ Uw(1) = e
z(m+1) =
w(m+1)
‖ w(m+1) ‖∞
onde
Ly(m+1) = z(m) e Uw(m+1) = y(m)
Exemplo 1:
A matriz
A =

 2 11 3 1
1 4

 tem por autovalor λ = 1.2679
A− 1.2679I =

 0.7321 11 1.7321 1
1 2.7321


LU =

 0.7321 1.01.3659 0.3662 1.0
2.7307 0.0014


z(0) = Le ⇒ y(1) =


1
1
...
1

 ⇒ w(1) =

 2661.9365−1947.8037
714.2857

⇒ z(1) =

 1.0−0.7317
0.2683


y(2) =

 1.0−2.0976
5.9962

 ⇒ w(2) =

 15984.869−11701.523
4283.000

 ⇒ z(2) =

 1.0−0.7320
0.2679


y(3) =

 1.0−2.0979
5.9966

 ⇒ w(3) =

 15986.031−11702.373
4283.3111

 ⇒ z(3) =

 1.0−0.7320
0.2679


Norma de ‖ z(3) − z(2) ‖= 0.
15