Autovalores e Autovetores Lucia Catabriga Algoritmos Numéricos II Computação Cientı́fica Universidade Federal do Espı́rito Santo 10 de junho de 2014 Resumo Este texto tem por objetivo introduzir os conceitos básicos para o cálculo aproximado de autovalores e autovetores dentro do contexto da disciplina A;goritmos Numéricos II do Departamento de Informática da Universidade Federal do Espı́rito Santo (DI/UFES). Não é um texto completo, apenas introdutório, detalhes devem ser consultados em ?? . Capı́tulo 1 Introdução Neste capı́tulo estudaremos métodos numéricos para encontrar autovalores e autovetores de matrizes com coeficientes reais. Os autovalores e correspondentes autovetores de uma matriz satisfazem a propriedade: Se multiplicarmos a matriz por um autovetor encontramos um multiplo do próprio autovetor, com constante de multiplicidade conhecida por autovalor. Seja 16 −24 18 0 A = 3 −2 −9 18 −17 2 o vetor 1 satisfaz a 0 2 2 16 −24 18 3 −2 0 1 = 4 1 0 0 −9 18 −17 2 Portanto 1 é autovetor com autovalor correspondente igual a 4. 0 Como o autovetor foi pré-multiplicado pela matriz é conhecido como autovetor direito. A equação algébrica para o autovalor λ e correspondente autovetor direito q de uma matriz A é: Aq = λq observe que esta equação só tem sentido para matrizes quadradas, portanto somente tais matrizes possuem autovalores. 1 Um método para encontrar os autovalores de uma matriz A pode ser ilustrado através da matriz do exemplo anterior. q1 q1 16 −24 18 3 −2 0 q2 = λ q2 q3 q3 −9 18 −17 que pode ser escrito na forma q1 0 (16 − λ) −24 18 3 (−2 − λ) 0 q2 = λ 0 q3 0 −9 18 (−17 − λ) que é um sistema homogêneo. Este sistema só tem solução não-trivial (qi 6= 0) se a matriz for singular, ou seja se o determinante for nulo. (16 − λ) −24 18 3 (−2 − λ) 0 = 0 ⇔ λ3 + 3λ2 − 36λ + 32 = 0 det −9 18 (−17 − λ) ou (λ − 4)(λ − 1)(λ + 8) = 0 que é denominada equação caracteristica. Os autovalores da matriz A são λ = 4, λ = 1 e λ = −8. Em geral a equação Aq = λq pode ser representada pelo sistema homogêneo (A−λI)q = 0. Se A é uma matriz de ordem n o sistema homogêneo tem solução não-trivial se (a11 − λ) a12 . . . a1n a21 (a22 − λ) . . . a2n det .. .. = 0 .. . . . . . . an1 an2 . . . (ann − λ) A equação caracteristica tem a forma geral: λn + cn−1 λn−1 + . . . + c1 λ + c0 = 0 O método da equação caracterı́stica não é um bom processo numérico para determinar os autovalores de uma matriz. O número de operações necessárias para obter os coeficientes da equação caracterı́stica é muito grande. Nos próximos itens desenvolveremos processos mais eficientes para determinar os autovalores. Diversas aplicações recaem em problemas de autovalores, tais como: • Flambagem de uma coluna 2 • Vibração de estruturas • Vibrações amortecidas • Cadeias de Markov No final deste capı́tulo desenvolveremos algumas aplicações citadas. Estas aplicações nos levaram a determinar autovalores e autovetores de matrizes que apresentam caracterı́sticas especiais, por exemplo matrizes tridiagonais. Na próxima seção apresentamos algumas propriedades importantes de autovalores e autovetores que serão usadas no desenvolvimento numérico. 1.1 Algumas Propriedades de Autovalores 1. A equação caracterı́stica pode ser fatorada na forma: (λ − λ1 )(λ − λ2 ) . . . (λ − λn ) = 0 Esta equação mostra que uma matriz de ordem n tem n autovalores . Porém os autovalores não são necessariamente distintos (por exemplo, podemos ter λ1 = λ2 = λn−1 ). 2. A soma dos elementos da diagonal principal da matriz é chamada traço. Sendo que: tr(A) = a11 + a22 + . . . + ann = −cn−1 = λ1 + λ2 + . . . + λn ou seja: A soma dos autovalores de uma matriz é igual ao traço da matriz 3. O produto dos autovalores da matriz é igual ao determinante da matriz detA = (−1)n c0 = λ1 λ2 . . . λn Portanto se A é 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 é igual ao produto dos elementos da diagonal. Então se A é triangular: det(A − λI) = (a11 − λ)(a22 − λ) . . . (ann − λ) Portanto os autovalores de uma matriz triangular são iguais aos elementos da diagonal. 3 6. Se as linhas e colunas correspondentes de uma matriz são trocadas os autovalores permanecem os mesmos. Por exemplo: q1 q1 16 −24 18 3 −2 0 q2 = λ q2 q3 q3 −9 18 −17 Se trocarmos a linha 1 com a linha 2 e a coluna 1 com a coluna 2, obtemos: q2 q2 −2 3 0 −24 16 18 q1 = λ q1 q3 q3 18 −9 −17 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 segunda linha de A por f, a segunda coluna de A por 1/f e a segunda componente de q por f, obtemos: q1 a11 a12 /f a13 a14 f a21 a22 f a23 f a24 f q2 a31 a32 /f a33 a34 q3 q4 a41 a42 /f a43 a44 q1 = λ f q2 q3 q4 Portanto se uma linha de uma matriz é multiplicada por um escalar e a coluna correpondente é multiplicada pelo inverso do escalar os autovalores permanecem os mesmos. O cálculo dos autovetores associados envolvem a solução de um sistema homogêneo. Para cada autovalor definimos um sistema de n equações e n incógnitas (A − λI)q = 0 Por exemplo: A matriz 16 −24 18 0 A = 3 −2 −9 18 −17 tem por autovalores λ1 = 4, λ2 = 1 e λ3 = λ1 = 1 é o vetor q tq (A − λI)q = 0, ou seja q1 15 −24 18 3 −3 0 q2 = q3 −9 18 −18 4 −8. O autovetor associado a 0 0 m21 = 0.2 m31 = −0.6 0 0 q1 15 −24 18 ∼ 0 1.8 −3.6 q2 = 0 L3 = 2L2 q3 0 0 3.6 −7.2 Considerando somente L1 e L2 , chegamos a: q1 = q2 = 2q3 Portanto qualquer vetor que possui esta propriedade é autovetor associado ao autovalor λ= 1. 2 Seja q = 2 . 1 Para encontrar cada autovetor são necessários n3 /3 multiplicações se a matriz dos coeficientes for cheia e não simétrica. Portanto a determinação dos autovetores não é considerado um processo numérico trivial, mesmo quando os autovalores são conhecidos. É possı́vel combinar a equação padrão dos autovalores com todos os autovalores e correspondentes autovetores na forma: λ 1 λ2 q1 q2 . . . qn q1 q2 . . . qn = A .. . λn isto é, AQ = QΛ onde Λ é a matriz diagonal dos autovalores. Q matriz quadrada contendo todos os autovetores. 5 Capı́tulo 2 Métodos Iterativos Simples 2.1 Método Das Potências O objetivo do método das potências é determinar o autovalor de maior mó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 combinação linear dos autovetores correspondentes: u(0) = c1 q1 + c2 q2 + . . . + cn qn Os autovetores são linearmente independentes. u(1) = Au(0) u(2) = A2 u(0) = c1 Aq1 + c2 Aq2 + . . . + cn Aqn = c1 λh1 q1 + c2 λ2 q2 + . . . + cn λn qn i = λ1 c1 q1 + c2 λλ21 q2 + . . . + cn λλn1 qn i h = λ1 c1 Aq1 + c2 λλ12 Aq2 + . . . + cn λλn1 Aqn 2 2 λ2 2 = λ1 c1 q1 + c2 λ1 q2 + . . . + cn λλn1 qn Se pré-multiplicarmos a expressão pela matriz A k-vezes obtemos: " u(k) = Ak u(0) = λk1 c1 q1 + c2 λ2 λ1 k q2 + . . . + c n λn λ1 k qn # Como |λ1 | > |λ2 | ≥ . . . ≥ |λn |, temos que λλ1i < 1, para i = 2, . . . , n. k Portanto quando k → ∞ λλ1i → 0 para i = 2, . . . , n. 6 Então, o vetor " c 1 q1 + c 2 λ2 λ1 k q2 + . . . + c n λn λ1 k # qn → c 1 q1 que é um autovetor associado a λ1 . Portanto podemos afirmar que para valores grandes de k u(k) ≃ λk1 c1 q1 u(k) tende a ser proporcional ao autovetor q1 . Considerando que o autovetor pode ter tamanho arbitrário (ou seja, um autovetor multiplicado por um escalar tem o mesmo autovalor associado) é conveniente normalizar o vetor que gera o processo iterativo depois de cada multiplicação. O algoritmo iterativo para determinar q1 pode ser representado através das equações: (k) v = Au(k) u(k+1) = α1 v (k) onde α = ± k v (k) k Exemplo: Considere a matriz 528.2 547.6 156.4 A = 273.8 312.8 98.0 78.2 98.0 39.0 Seja u(0) = (1 1 1)(t) e considere a norma do máximo para obter o valor de α. • Iteração 1 1 1232.1 1 528.2 547.6 156.4 273.8 312.8 98.0 1 = 684.6 = 1232.1 0.5556 | {z } 0.1747 215.3 1 78.2 98.0 39.0 α | | {z } | {z } | {z } {z } A • Iteração 2 • Iteração 3 A u(0) v (0) 859.7 1 1 0.5556 = 464.7 = 859.7 0.5406 | {z } 139.5 0.1747 0.1622 α {z } | {z } {z } | | u(1) A u(1) v (1) u(2) 1 1 849.5 0.5406 = 458.8 = 849.5 0.5400 | {z } 0.1622 0.1616 137.3 α | | {z } | {z } {z } u(2) v (2) 7 u(3) • Iteração 4 849.1 1 1 0.5400 = 458.6 = 849.1 0.5400 | {z } 137.4 0.1616 0.1619 α {z } | {z } {z } | | A u(3) v (3) u(4) O autovetor aproximado é u(4) ≃ q1 com erro inferior a 10−3 . O autovetor correspondente é λ1 ≃ 849.1. Quando a norma do máximo é usada o sinal de α pode ser o mesmo do maior elemento em módulo. Neste caso α convergirá para λ1 até mesmo quando ele for negativo, além disso a sequência de vetores convergirá normalmente para q1 . Exemplo: Encontre o maior autovalor da matriz 16 −24 18 0 A = 3 −2 −9 18 −17 usando u(0) = (1 1 1)(t) e norma do máximo para obter o valor de α. Faça algumas iterações. Após construir algumas iterações é possivel observar que a convergência para o autovalor pode ser mais rápida que a convergência para o autovetor associado. Em geral, dependendo de cada aplicação, é possı́vel escolher uma aproximação inicial para o autovetor associado ao autovalor de maior módulo através de algum critério. Porém, quando não existe alguma informação, é necessário um cuidado especial para não escolher u(0) tal que o coeficiente c1 seja nulo ou muito pequeno quando comparado com os outros coeficientes. Para implementações computacionais do método das potências, a determinação do vetor inicial u(0) é feita através de procedimentos automáticos. Um procedimento bastante usado consiste em gerar os elementos dos vetor (0) através de números randômicos no intervalo −1 ≤ ui ≤ 1. Quando este processo é usado a probabilidade de ocorrer c1 = 0 é bem pequena. 2.1.1 Caracterı́sticas da Convergência do Método das Potências O autovetor u(k) pode ser expresso: u(k) = q1 + e(k) onde e (k) = λ2 λ1 k c2 q2 + . . . + c1 8 λn λ1 k cn qn c1 Por hipótese temos que |λ1 | > |λ2 | ≥ . . . ≥ |λn |, portanto para valores grande de k o erro pode ser aproximado por ke (k) (k) λ2 |c2 | k q2 k k∼ λ1 |c1 | É possivel provar que |c2 | ∼ |c1 |. Através desta aproximação é possı́vel estimar o número de iterações necessárias para atingir uma tolerância pré-fixada. Para exemplificar, suponha que desejamos calcular os autovalores de uma matriz com tolerância de 10−s . k Como já foi mostrado o erro na iteração k depende do quociente λλ12 , então: k λ2 ≃ 10−s λ1 k≃ −sln10 ln|λ2 /λ1 | Portanto se λλ21 estiver próximo de 1, o método das potências converge vagarosamente. É possı́vel acelerar a convergência do método das potências. Nota-se que o uso da Norma Euclidiana no método para normalizar os autovetores e determinar os autovalores correspondentes aceleram a convergência, principalmente no caso de matrizes simétricas. Porém este processo não estabelece um crité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 iteração a outra permanecam com o mesmo sinal. Outro processo similar a norma euclidiana para matrizes simétricas em termos de precisão é usar o Coeficiente de Rayleigh para normalizar o vetor v (k) : α= (u(k) )t Au(k) (u(k) )t v (k) = (u(k) )t u(k) (u(k) )t u(k) Apesar da precisão deste critério ser similar a da norma euclidiana, não existe o incoveniente da escolha do sinal. Portanto poderiamos definir o seguinte algoritmo: 9 Algoritmo 1: Método da Iteração Inversa 1 2 3 4 5 6 Entrada: A,v (0) ,ǫ,kmax Inicializar ρ (ρ = 1.0) Inicializar λk (λk = 0.0) while ρ > ǫ and k < kmax do u = Av (k) Resolva U v = y T v (k) u 7 λk+1 = 8 v (k+1) = 9 ρ= 10 11 12 T v (k) v (k) u λk+1 |λk+1 −λk | |λk+1 | k =k+1 end Saı́da: λk+1 , v (k+1) No entanto, podemos escalonar a sequência v (k) , antes de calcular o λk . (k) Para isso, seja y (k) = kuu(k) k , então ky (k) k = 1. T Ay (k) ≈ λk y (k) λk = y (k) Ay (k) T y (k) y (k) T = y (k) u(k+1) Exemplo: Considere a Matriz simétrica 2 −1 −1 2 −1 A= −1 2 −1 −1 2 O autovalor de maior módulo calculado pelo método das potências é λ = 2.61803. A tabela abaixo mostra a tolerância atingida para algumas iterações, demonstrando que o uso da norma euclidiana e/ou do coeficiente de Rayleigh acelera moderadamente a convergência. Para tal, Considere (k) (k−1) k u(0) = {1, 1, 1, 1} e critério de parada ku ku−u < ǫ. (k) k N. Máximo N. Euclidiana C. de Rayleigh 2.2 4 iterações 1.538 × 10−2 1.124 × 10−2 1.124 × 10−2 6 iterações 3.305 × 10−4 2.391 × 10−4 2.391 × 10−4 8 iterações 7.035 × 10−5 5.091 × 10−6 5.091 × 10−6 10 iterações 1.498 × 10−7 1.083 × 10−7 1.083 × 10−7 Método da Potência Inversa O método da potência inversa é usado para determinar o autovalor de menor valor absoluto e seu correspondente autovalor de uma matriz A. De forma 10 semelhante ao método das potências, o método é útil para determinar o menor autovalor em módulo, desde que o mesmo esteja bem separado dos demais, isto é, seja menor que todos os outros e não muito próximo do segundo menor. Considerando que |λ1 | ≤ |λ2 | ≤ . . . ≤ |λn−1 | > |λn |, desejamos calcular |λn |. Sabemos que se λ é autovalor de A, λ−1 é autovalor de A−1 . Portanto se λn é o menor autovalor em módulo de A, λ−1 n é o maior autovalor de A−1 em módulo. Assim, dado 2.3 Método da Sequência de Sturm Em geral a solução numérica de um problema de autovalor não envolve a determinação do polinômio caracterı́stico, pois o cáculo do mesmo necessita de muitas operações o que é enviável computacionalmente. Porém para matrizes tridiagonais simétricas é possı́vel obter o polinômio caracterı́stico através de um processo simplificado. Seja A uma matriz tridiagonal de ordem n: α1 β 1 β 1 α2 β 2 β 2 α3 β2 A= .. .. .. . . . βn−2 αn−1 βn−1 βn−1 αn Considere a sequência formada por α1 β 1 β 1 α2 β2 . . .. .. .. fk (λ) = det . βk−2 αk−1 βk−1 βk−1 αk para 1 ≤ k ≤ n e f0 (λ) ≡ 1. Assim f1 (λ) = α1 − λ f2 (λ) = (α1 − λ)f1 (λ) − β12 f0 (λ) .. . 2 f fk (λ) = (αk − λ)fk−1 (λ) − βk−1 k−2 (λ) O processo descrito para obter o polinômio caracterı́stico fn (λ) requer 2n − 3 multiplicações. Podemos então considerar qualquer método numérico para encontrar os zeros do polinômio caracterı́stico. Porém a sequência {fk (λ), 1 ≤ k ≤ n} possui propriedades especiais e por isso é denominada por sequência de Sturm. Tais propriedades nos levarão a isolar facilmente os autovalores de A. 11 Propriedade da Sequência de Sturm: Seja a função de valores inteiros s(λ) que guarda o número de trocas de sinal de membros consecutivos da sequência {fk (λ)}. Dado um intervalo [a, b], o número de raı́zes da equação fn (λ) = 0 (ou o número de autovalores de A) no intervalo [a, b] é igual a |s(a) − s(b)|. Se algum membro é 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 então fj−1 (λ) 6= 0. É 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 está normalizado, ou seja, existe uma componente qk = 1 e |qi | < 1 para i 6= k, assim: q1 q1 × × ... × ... × q2 q2 × × ... × ... × .. .. . . ak1 ak2 . . . akk . . . akn 1 = λ 1 .. .. . . × × ... × ... × qn qn O produto da linha k com o vetor q gera a equação: ak1 q1 + ak2 q2 + . . . + akk + . . . + akn = λ Portanto λ − akk = X akj qj j6=k como |qj | < 1 |λ − akk | ≤ X |akj | j6=k O intervalo que contém todos os autovalores é formado pela união de todos os intervalos definidos na expressão anterior, ou seja para todo k. Exemplo: A Sequência de Sturm da matriz 2 −1 2 −1 A = −1 −1 2 é dada por 12 f0 (λ) = 1 f1 (λ) = (2 − λ) f2 (λ) = (2 − λ)f1 (λ) − 1 f3 (λ) = (2 − λ)f2 (λ) − f1 (λ) O intervalo que contém todos os autovalores é dado pela união dos intervalos: |λ − 2| ≤ 1 |λ − 2| ≤ 2 |λ − 2| ≤ 1 Todos os autovalores de A estão no intervalo [0,4]. Observe que f3 (2) = 0, portanto λ = 2 é autovalor da matriz A. Na tabela a seguir calculamos um autovalor de A no intervalo (2,4), usando a propriedade de Sturm. O processo consiste inicialmente em observar o número de trocas de sinal que ocorre no intervalo [2,4], que é igual a 2 (sendo que λ = 2 é autovalor. Este fato, significa que existe somente um autovalor no intervalo (2,4). O processo iterativo deve continuar sempre particionando o intervalo que contém o autovalor ao meio até que uma determinada tolerância pré-fixada seja atingida. λ 2 4 3 3.5 3.25 3.375 3.4375 3.40625 3.421875 3.4140625 3.4179688 3.4142968 2.4 f0 + + + + + + + + + + + + f1 0 - f2 + 0 + + + + + + + + + f3 0 - 4.0 + 1.0 - 0.375 + 0.546875 + 0.1503906 - 0.0954589 + 0.0315856 - 0.0621452 + 0.0006041 - 0.0150806 - 0.0003333 No. trocas de sinal 1 3 2 3 2 2 3 2 3 2 3 3 Método da Iteração Inversa Seja Q a matriz que contém em cada coluna os autovetores de A e Λ a matriz diagonal contendo os autovalores correspondentes: AQ = QΛ onde 13 q1 q2 . . . qn Q= e Em particular Aqi = λi qi λ1 Λ= λ2 .. . λn p/ i = 1, 2, . . . , n Sem perda de generalidades, pode-se assumir que k qi k∞ = 1 ∀i. Seja λ uma aproximação de um autovalor λk . Considere z (0) um vetor condição inicial para o cálculo do autovalor correspondente λ (ou λk ). Define-se duas sequências {w(m) } e {z (m) } tq (A − λI)w(m+1) = z (m) e z (m+1) = w(m+1) p/ m ≥ 0 k w(m+1) k∞ O processo que acabamos de apresentar é essencialmente o Método das potências aplicado a matriz (A − λI)−1 . Porém a matriz (A − λI) é malcondicionada, pois det(A − λk I) = 0 sendo λ ≈ λk O processo de obtenção do autovalor λ(≈ λk ) causa o acúmulo de erros de arredondamento na matriz (A−λk I), o que leva a concluir que estes erros equilibram a instabilidade. É possivel estudar com cautela este fato, porém neste texto não aprofundaremos esta discussão. O vetor z (m) gerado pelas sequências descritas converge para o autovetor correspondente de λk . 2.4.1 Implementação do Método A fatoração LU será usada para decompor a matriz (A − λI) e resolver o sistema (A − λI)w(m+1) = z (m) . Portanto dado uma aproximação z (m) : LU w(m+1) = z (m) w(m+1) ⇓ ⇒ p/ m ≥ 0 (m+1) (m) Ly = z k w(m+1) k∞ U z (m+1) = y (m+1) Como (A − λI) é quase singular, o último elemento da diagonal de U pode ser bem pequeno. Caso seja nulo, é possı́vel executar uma pequena alteração no seu valor ou alterar o valor aproximado λ e recalcular L e U . Este procedimento, em geral oferece bons resultados. 14 A condição inicial z (0) , a princı́pio, poderia ser um vetor com números randômicos de -1 a 1. Porém demonstra-se que o seguinte procedimento leva a melhores resultados: 1 1 z (0) = Le onde e = . .. 1 Assim y (1) = e ⇒ U w(1) = e z (m+1) = w(m+1) k w(m+1) k∞ onde Ly (m+1) = z (m) e U w(m+1) = y (m) Exemplo 1: A matriz 2 1 A = 1 3 1 tem por autovalor λ = 1.2679 1 4 0.7321 1 1 1.7321 1 A − 1.2679I = 1 2.7321 0.7321 1.0 1.0 LU = 1.3659 0.3662 2.7307 0.0014 z (0) = Le ⇒ y (1) y (2) y (3) = 1 1 .. . 1 1.0 2661.9365 ⇒ w(1) = −1947.8037 ⇒ z (1) = −0.7317 0.2683 714.2857 1.0 15984.869 1.0 = −2.0976 ⇒ w(2) = −11701.523 ⇒ z (2) = −0.7320 0.2679 4283.000 5.9962 1.0 15986.031 1.0 = −2.0979 ⇒ w(3) = −11702.373 ⇒ z (3) = −0.7320 0.2679 4283.3111 5.9966 Norma de k z (3) − z (2) k= 0. 15