Autovalores e Autovetores

Lucia Catabriga

Algoritmos Numericos II

Computacao Cientfica

Universidade Federal do Esprito Santo

10 de junho de 2014

Resumo

Este texto tem por objetivo introduzir os conceitos basicos para o calculoaproximado de autovalores e autovetores dentro do contexto da disciplinaA;goritmos Numericos II do Departamento de Informatica da UniversidadeFederal do Esprito Santo (DI/UFES). Nao e um texto completo, apenasintrodutorio, detalhes devem ser consultados em ?? .

Captulo 1

Introducao

Neste captulo estudaremos metodos numericos para encontrar autovalorese 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 proprio autovetor, com constante de multiplicidade conhecida por auto-

valor.

Seja

A =

16 24 183 2 09 18 17

o vetor

21

0

satisfaz a

16 24 183 2 09 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 comoautovetor direito. A equacao algebrica para o autovalor e correspondenteautovetor direito q de uma matriz A e:

Aq = q

observe que esta equacao so tem sentido para matrizes quadradas, portantosomente tais matrizes possuem autovalores.

1

Um metodo para encontrar os autovalores de uma matriz A pode serilustrado atraves da matriz do exemplo anterior.

16 24 183 2 09 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 homogeneo. Este sistema so tem solucao nao-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 + 32 36+ 32 = 0

ou( 4)( 1)(+ 8) = 0

que e denominada equacao caracteristica. Os autovalores da matriz A sao = 4, = 1 e = 8.

Em geral a equacao Aq = q pode ser representada pelo sistema ho-mogeneo (AI)q = 0. Se A e uma matriz de ordem n o sistema homogeneotem solucao nao-trivial se

det

(a11 ) a12 . . . a1na21 (a22 ) . . . a2n

......

. . ....

an1 an2 . . . (ann )

= 0

A equacao caracteristica tem a forma geral:

n + cn1n1 + . . .+ c1+ c0 = 0

O metodo da equacao caracterstica nao e um bom processo numericopara determinar os autovalores de uma matriz. O numero de operacoes ne-cessarias para obter os coeficientes da equacao caracterstica e muito grande.Nos proximos itens desenvolveremos processos mais eficientes para determi-nar os autovalores.

Diversas aplicacoes recaem em problemas de autovalores, tais como:

Flambagem de uma coluna

2

Vibracao de estruturas

Vibracoes amortecidas

Cadeias de Markov

No final deste captulo desenvolveremos algumas aplicacoes citadas. Estasaplicacoes nos levaram a determinar autovalores e autovetores de matrizesque apresentam caractersticas especiais, por exemplo matrizes tridiagonais.Na proxima secao apresentamos algumas propriedades importantes de au-tovalores e autovetores que serao usadas no desenvolvimento numerico.

1.1 Algumas Propriedades de Autovalores

1. A equacao caracterstica pode ser fatorada na forma:

( 1)( 2) . . . ( n) = 0

Esta equacao mostra que uma matriz de ordem n tem n autovalores .Porem os autovalores nao sao necessariamente distintos (por exemplo,podemos ter 1 = 2 = n1).

2. A soma dos elementos da diagonal principal da matriz e chamadatraco. Sendo que:

tr(A) = a11 + a22 + . . .+ ann = cn1 = 1 + 2 + . . .+ n

ou seja:

A soma dos autovalores de uma matriz e igual ao traco da matriz

3. O produto dos autovalores da matriz e igual ao determinante da matriz

detA = (1)nc0 = 12 . . . 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 odetA = detAt.

5. O determinante de uma matriz triangular e igual ao produto dos ele-mentos da diagonal. Entao se A e triangular:

det(A I) = (a11 )(a22 ) . . . (ann )

Portanto os autovalores de uma matriz triangular sao iguais aos ele-mentos da diagonal.

3

6. Se as linhas e colunas correspondentes de uma matriz sao trocadas osautovalores permanecem os mesmos. Por exemplo:

16 24 183 2 09 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 024 16 1818 9 17

q2q1

q3

=

q2q1

q3

observe que os autovalores permanecem os mesmos, mas ao autovetorestem 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 segundacomponente de q por f, obtemos:

a11 a12/f a13 a14fa21 a22 fa23 fa24a31 a32/f a33 a34a41 a42/f a43 a44

q1fq2q3q4

=

q1fq2q3q4

Portanto se uma linha de uma matriz e multiplicada por um escalare a coluna correpondente e multiplicada pelo inverso do escalar osautovalores permanecem os mesmos.

O calculo dos autovetores associados envolvem a solucao de um sistemahomogeneo. Para cada autovalor definimos um sistema de n equacoes e nincognitas

(A I)q = 0

Por exemplo:A matriz

A =

16 24 183 2 09 18 17

tem por autovalores 1 = 4, 2 = 1 e 3 = 8. O autovetor associado a1 = 1 e o vetor q tq (A I)q = 0, ou seja

15 24 183 3 09 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 associadoao autovalor = 1.

Seja q =

22

1

.

Para encontrar cada autovetor sao necessarios n3/3 multiplicacoes se amatriz dos coeficientes for cheia e nao simetrica. Portanto a determinacaodos autovetores nao e considerado um processo numerico trivial, mesmoquando os autovalores sao conhecidos.

E possvel combinar a equacao padrao dos autovalores com todos osautovalores e correspondentes autovetores na forma:

A

q1 q2 . . . qn

=

q1 q2 . . . qn

12

. . .

n

isto e,AQ = Q

onde e a matriz diagonal dos autovalores.Q matriz quadrada contendo todos os autovetores.

5

Captulo 2

Metodos Iterativos Simples

2.1 Metodo Das Potencias

O objetivo do metodo das potencias e determinar o autovalor de maiormodulo 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 combinacao linear dos autovetores correspondentes:

u(0) = c1q1 + c2q2 + . . .+ cnqn

Os autovetores sao linearmente independentes.

u(1) = Au(0) = c1Aq1 + c2Aq2 + . . .+ cnAqn= c11q1 + c22q2 + . . .+ cnnqn

= 1

[c1q1 + c2

21q2 + . . .+ cn

n1qn

]u(2) = A2u(0) = 1

[c1Aq1 + c2

21Aq2 + . . .+ cn

n1Aqn

]= 21

[c1q1 + c2

(21

)2q2 + . . .+ cn

(n1

)2qn

]

Se pre-multiplicarmos a expressao pela matriz A k-vezes obtemos:

u(k) = Aku(0) = k1

[c1q1 + c2

(21

)kq2 + . . .+ cn

(n1

)kqn

]

Como |1| > |2| . . . |n|, temos que i1 < 1, para i = 2, . . . , n.

Portanto quando k (i1

)k 0 para i = 2, . . . , n.

6

Entao, o vetor[c1q1 + c2

(21

)kq2 + . . .+ cn

(n1

)kqn

] c1q1

que e um autovetor associado a 1. Portanto podemos afirmar que paravalores grandes de k

u(k) k1c1q1

u(k) tende a ser proporcional ao autovetor q1. Considerando que o autovetorpode ter tamanho arbitrario (ou seja, um autovetor multiplicado por umescalar tem o mesmo autovalor associado) e conveniente normalizar o vetorque gera o processo iterativo depois de cada multiplicacao. O algoritmoiterativo para determinar q1 pode ser representado atraves das equacoes:

v(k) = Au(k)

u(k+1) = 1v(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 maximo para obter o valorde .

Iteracao 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)

Iteracao 2 A

10.5556

0.1747

u(1)

=

859.7464.7

139.5

v(1)

= 859.7

10.5406

0.1622

u(2)

Iteracao 3 A

10.5406

0.1622

u(2)

=

849.5458.8

137.3

v(2)

= 849.5

10.5400

0.1616

u(3)

7

Iteracao 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 103. O autovetor

correspondente e 1 849.1.Quando a norma do maximo e usada o sinal de pode ser o mesmo do

maior elemento em modulo. Neste caso convergira para 1 ate mesmoquando ele for negativo, alem disso a sequencia de vetores convergira nor-malmente para q1.Exemplo:

Encontre o maior autovalor da matriz

A =

16 24 183 2 09 18 17

usando u(0) = (1 1 1)(t) e norma do maximo para obter o valor de . Facaalgumas iteracoes.

Apos construir algumas iteracoes e possivel observar que a convergenciapara o autovalor pode ser mais rapida que a convergencia para o autovetorassociado.

Em geral, dependendo de cada aplicacao, e possvel escolher uma apro-ximacao inicial para o autovetor associado ao autovalor de maior moduloatraves de algum criterio. Porem, quando nao existe alguma informacao, enecessario um cuidado especial para nao escolher u(0) tal que o coeficiente c1seja nulo ou muito pequeno quando comparado com os outros coeficientes.

Para implementacoes computacionais do metodo das potencias, a deter-minacao do vetor inicial u(0) e feita atraves de procedimentos automaticos.Um procedimento bastante usado consiste em gerar os elementos dos vetor

atraves de numeros randomicos no intervalo 1 u(0)i 1. Quando este

processo e usado a probabilidade de ocorrer c1 = 0 e bem pequena.

2.1.1 Caractersticas da Convergencia do Metodo das Potencias

O autovetor u(k) pode ser expresso:

u(k) = q1 + e(k)

onde

e(k) =

(21

)k c2c1q2 + . . .+

(n1

)k cnc1qn

8

Por hipotese temos que |1| > |2| . . . |n|, portanto para valoresgrande de k o erro pode ser aproximado por

e(k)

21(k) |c2||c1| q2

E possivel provar que |c2| |c1|.Atraves desta aproximacao e possvel estimar o numero de iteracoes ne-

cessarias para atingir uma tolerancia pre-fixada. Para exemplificar, suponhaque desejamos calcular os autovalores de uma matriz com tolerancia de 10s.

Como ja foi mostrado o erro na iteracao k depende do quociente21 k, entao:21

k 10sk

sln10

ln|2/1|

Portanto se21 estiver proximo de 1, o metodo das potencias converge

vagarosamente.E possvel acelerar a convergencia do metodo das potencias. Nota-se que

o uso da Norma Euclidiana no metodo para normalizar os autovetores edeterminar os autovalores correspondentes aceleram a convergencia, princi-palmente no caso de matrizes simetricas. Porem este processo nao estabeleceum criterio simples para a escolha do sinal de . Em geral, adota-se que osinal de deve ser tal que as componentes do autovetor de uma iteracaoa outra permanecam com o mesmo sinal. Outro processo similar a normaeuclidiana para matrizes simetricas em termos de precisao 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 precisao deste criterio ser similar a da norma euclidiana, naoexiste o incoveniente da escolha do sinal.

Portanto poderiamos definir o seguinte algoritmo:

9

Algoritmo 1: Metodo da Iteracao Inversa

1 Entrada: A,v(0),,kmax2 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)

Tu

v(k)Tv(k)

8 v(k+1) = uk+1

9 =|k+1k||k+1|

10 k = k + 1

11 end

12 Sada: k+1, v(k+1)

No entanto, podemos escalonar a sequencia v(k), antes de calcular o k.

Para isso, seja y(k) = u(k)

u(k), entao y(k) = 1.

Ay(k) ky(k) k =

y(k)TAy(k)

y(k)Ty(k)

= y(k)Tu(k+1)

Exemplo:Considere a Matriz simetrica

A =

2 11 2 1

1 2 11 2

O autovalor de maior modulo calculado pelo metodo das potencias e = 2.61803. A tabela abaixo mostra a tolerancia atingida para algumasiteracoes, demonstrando que o uso da norma euclidiana e/ou do coeficientede Rayleigh acelera moderadamente a convergencia. Para tal, Considere

u(0) = {1, 1, 1, 1} e criterio de parada u(k)u(k1)

u(k)< .

4 iteracoes 6 iteracoes 8 iteracoes 10 iteracoes

N. Maximo 1.538 102 3.305 104 7.035 105 1.498 107

N. Euclidiana 1.124 102 2.391 104 5.091 106 1.083 107

C. de Rayleigh 1.124 102 2.391 104 5.091 106 1.083 107

2.2 Metodo da Potencia Inversa

O metodo da potencia inversa e usado para determinar o autovalor de menorvalor absoluto e seu correspondente autovalor de uma matriz A. De forma

10

semelhante ao metodo das potencias, o metodo e util para determinar omenor autovalor em modulo, desde que o mesmo esteja bem separado dosdemais, isto e, seja menor que todos os outros e nao muito proximo dosegundo menor. Considerando que |1| |2| . . . |n1| > |n|,desejamos calcular |n|. Sabemos que se e autovalor de A,

1 e autovalorde A1. Portanto se n e o menor autovalor em modulo de A,

1n e o maior

autovalor de A1 em modulo. Assim, dado

2.3 Metodo da Sequencia de Sturm

Em geral a solucao numerica de um problema de autovalor nao envolve adeterminacao do polinomio caracterstico, pois o caculo do mesmo necessitade muitas operacoes o que e enviavel computacionalmente. Porem paramatrizes tridiagonais simetricas e possvel obter o polinomio caractersticoatraves de um processo simplificado.

Seja A uma matriz tridiagonal de ordem n:

A =

1 11 2 2

2 3 2. . .

. . .. . .

n2 n1 n1n1 n

Considere a sequencia formada por

fk() = det

1 11 2 2

. . .. . .

. . .

k2 k1 k1k1 k

para 1 k n e f0() 1.Assim

f1() = 1 f2() = (1 )f1()

21f0()

...fk() = (k )fk1()

2k1fk2()

O processo descrito para obter o polinomio caracterstico fn() requer2n3 multiplicacoes. Podemos entao considerar qualquer metodo numericopara encontrar os zeros do polinomio caracterstico. Porem a sequencia{fk(), 1 k n} possui propriedades especiais e por isso e denominadapor sequencia de Sturm. Tais propriedades nos levarao a isolar facilmenteos autovalores de A.

11

Propriedade da Sequencia de Sturm: Seja a funcao de valores inteiross() que guarda o numero de trocas de sinal de membros consecutivos dasequencia {fk()}. Dado um intervalo [a, b], o numero de razes da equacaofn() = 0 (ou o numero 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 fj1() e fj+1(),pois se fj() = 0 entao fj1() 6= 0.

E possivel determinar o intervalo que contenha os autovalores de umamatriz. Suponha uma matriz A de ordem n. Seja um autovalor e q umautovetor correspondente, portanto

Aq = q

suponha que o autovetor esta normalizado, ou seja, existe uma componenteqk = 1 e |qi| < 1 para i 6= k, assim:

. . . . . . . . . . . .

ak1 ak2 . . . akk . . . akn

. . . . . .

q1q2...1...qn

=

q1q2...1...qn

O produto da linha k com o vetor q gera a equacao:

ak1q1 + ak2q2 + . . .+ akk + . . .+ akn =

Portanto akk =

j 6=k

akjqj

como |qj | < 1

| akk| j 6=k

|akj |

O intervalo que contem todos os autovalores e formado pela uniao detodos os intervalos definidos na expressao anterior, ou seja para todo k.Exemplo:A Sequencia de Sturm da matriz

A =

2 11 2 1

1 2

e dada por

12

f0() = 1f1() = (2 )f2() = (2 )f1() 1f3() = (2 )f2() f1()

O intervalo que contem todos os autovalores e dado pela uniao dos in-tervalos:

| 2| 1| 2| 2| 2| 1

Todos os autovalores de A estao no intervalo [0,4]. Observe que f3(2) = 0,portanto = 2 e autovalor da matriz A. Na tabela a seguir calculamos umautovalor de A no intervalo (2,4), usando a propriedade de Sturm. O pro-cesso consiste inicialmente em observar o numero de trocas de sinal queocorre no intervalo [2,4], que e igual a 2 (sendo que = 2 e autovalor. Estefato, significa que existe somente um autovalor no intervalo (2,4). O pro-cesso iterativo deve continuar sempre particionando o intervalo que contemo autovalor ao meio ate que uma determinada tolerancia pre-fixada sejaatingida.

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 Metodo da Iteracao Inversa

Seja Q a matriz que contem em cada coluna os autovetores de A e a matrizdiagonal contendo os autovalores correspondentes:

AQ = Q

onde

13

Q =

q1 q2 . . . qn

e =

12

. . .

n

Em particularAqi = iqi p/ i = 1, 2, . . . , n

Sem perda de generalidades, pode-se assumir que qi = 1 i.Seja uma aproximacao de um autovalor k. Considere z

(0) um ve-tor condicao inicial para o calculo do autovalor correspondente (ou k).Define-se duas sequencias {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 Metodo daspotencias aplicado a matriz (A I)1. Porem a matriz (A I) e mal-condicionada, pois

det(A kI) = 0 sendo k

O processo de obtencao do autovalor ( k) causa o acumulo de errosde arredondamento na matriz (AkI), o que leva a concluir que estes errosequilibram a instabilidade. E possivel estudar com cautela este fato, poremneste texto nao aprofundaremos esta discussao. O vetor z(m) gerado pelassequencias descritas converge para o autovetor correspondente de k.

2.4.1 Implementacao do Metodo

A fatoracao LU sera usada para decompor a matriz (A I) e resolver osistema (A I)w(m+1) = z(m). Portanto dado uma aproximacao 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 ultimo elemento da diagonal de Upode ser bem pequeno. Caso seja nulo, e possvel executar uma pequenaalteracao no seu valor ou alterar o valor aproximado e recalcular L e U .Este procedimento, em geral oferece bons resultados.

14

A condicao inicial z(0), a princpio, poderia ser um vetor com numerosrandomicos de -1 a 1. Porem demonstra-se que o seguinte procedimento levaa melhores resultados:

z(0) = Le onde e =

11...1

Assimy(1) = e Uw(1) = e

z(m+1) =w(m+1)

w(m+1)

ondeLy(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) =

11...1

w(1) =

2661.93651947.8037

714.2857

z(1) =

1.00.7317

0.2683

y(2) =

1.02.0976

5.9962

w(2) =

15984.86911701.523

4283.000

z(2) =

1.00.7320

0.2679

y(3) =

1.02.0979

5.9966

w(3) =

15986.03111702.373

4283.3111

z(3) =

1.00.7320

0.2679

Norma de z(3) z(2) = 0.

15