Método das potências

Em matemática, o método das potências é um algoritmo para calcular autovalores: dada uma matriz A, o algoritmo irá produzir um número λ (o autovalor) e um vetor v não nulo (o autovetor), tal que Av = λv. O algoritmo também é conhecido como a iteração de Von Mises.[1]

O método da potência é um algoritmo muito simples. Ele não computa a decomposição matricial, e portanto pode ser usada quando A é uma grande matriz esparsa. No entanto, ele irá encontrar apenas um autovalor (aquele com o maior módulo) e poderá convergir lentamente.

O método

editar

O método da potência inicia com um vetor b0, que pode ser uma aproximação para o autovalor dominante ou um vetor aleatório. O método é descrito pela iteração

 

Assim, a cada iteração, o vetor bk é multiplicado pela matriz A e normalizado.

De acordo com as premissas:

  • A tem um autovalor que é estritamente maior em magnitude que os outros autovalores;
  • O vetor inicial   tem um componente não-nulo na direção de um autovetor associado com o autovalor dominante.

Assim:

  • A sub-série   converge a um autovetor associado com o autovalor dominante.

Note que a série   não necessariamente converge. Pode ser mostrado que:
  onde:   é um autovetor associado ao autovalor dominante, e  . A presença do termo   implica que   não irá convergir a menos que  . Sob os dois pressupostos acima, a série   definida por:   converge para o autovalor dominante.

Isso pode ser executado como uma simulação com o seguinte algoritmo:

for each(''simulation'') {
    // calcular o produto de matriz-por-vetor Ab
    for(i=0; i<n; i++) {
         tmp[i] = 0;
         for (j=0; j<n; j++)
              tmp[i] += A[i][j] * b[j]; // produto escalar de col(A) com b
    }

    // calcular o comprimento do vetor resultante
    norm_sq=0;
    for (k=0; k<n; k++)
         norm_sq += tmp[k]*tmp[k]; 
    norm = sqrt(norm_sq);

    // normalizar b para um vetor unitário para a próxima iteração
    b = tmp/norm;
}

O valor da norma converge para o autovalor dominante, e o vetor b para o autovetor associado.

(Nota: O código acima assume A e b real. Para lidar com valores complexos; A[i][j] se torna conj(A[i][j]), e tmp[k]*tmp[k] se torna conj(tmp[k])*tmp[k])

Esse algoritmo é utilizado para calcular coisas tais como o Google en:PageRank.

O método também pode ser usado para calcular o raio espectral da matriz pelo cálculo do quociente de Rayleigh:

 

Análise

editar

Decompondo   pela forma canônica de Jordan:  , onde a primeira coluna de   é um autovetor de   correspondente ao autovalor dominante de  . Como o autovalor dominante de   é único, o primeiro bloco de Jordan de   é a matriz 1x1  , onde   é o maior autovalor de A em magnitude. O vetor inicial   pode ser escrito como uma combinação linear das colunas de V:

 .

Pela hipótese,   tem um componente não-nulo na direção do autovalor dominante , assim  .

A útil relação de recorrência computacional para   pode ser reescrita como:

 ,

onde a expressão:

 

é mais propícia a seguinte análise.


 

A expressão acima simplifica como    
 

enquanto  .

O limite vem do fato de que o autovalor de   ser menor que 1 em magnitude, então

  enquanto  
.

Segue que:
  enquanto  

Usando esse fato,   pode ser escrito numa forma de enfatizar sua relação com   quando k é grande:
 

onde   e   enquanto  

A série   é delimitada, para que contenha uma sub-série convergente. Note que o autovetor correspondente ao autovalor dominante só é único até um escalar, assim, embora a série   possa não convergir,   é quase um autovetor de A para grandes k.

Alternativamente, se A é uma matriz diagonalizável, então o seguinte prova o mesmo resultado: Seja λ1, λ2, …, λm os m autovalores de A e seja v1, v2, …, vm os correspondentes autovetores. Suponha que   é o autovalor dominante, assim   para  .

O vetor inicial   pode ser escrito como:

 

Se   é escolhido aleatoriamente (com probabilidade uniforme), então c1 ≠ 0 com probabilidade 1. Agora,

 

A expressão entre parênteses converge para   porque   para  . Por outro lado, nós temos

 

Por tanto,   converge para (um múltiplo de) o autovetor  . A convergência é geométrica com taxa

 

onde   indica o segundo autovalor dominante. Assim, o método converge lentamente, se houver um autovalor próximo em magnitude ao autovalor dominante.

Aplicações

editar

Apesar do método das potências aproximar apenas um autovalor de uma matriz, continua sento usado para certos problemas computacionais. Por exemplo, a Google o usa para calcular o rank da página de documentos do seu sistema de pesquisa.[2] Para matrizes que são bem condicionadas e esparsas como the Web matrix, o método das potências pode ser mais eficiente do que outros métodos para encontrar autovetores dominantes.

Alguns dos mais avançados algoritmos para autovalores pode ser entendido como variações do método das potências. Por exemplo, o método da potência inverso aplica a iteração a matriz  . Outros algoritmos olham para todo o sub-espaço gerado pelos vetores  .. Esse subespaço é conhecido como the en:Krylov subspace. Pode ser computado pela iteração de Arnoldi ou a iteração de Lanczos. Outra variação do método de potências que simultaneamente nos fornece n autovalores e autofunções, bem como acelera a convergência para  , é "Multiple extremal eigenpairs by the power method" no Journal of Computational Physics Volume 227 Issue 19, October, 2008, Pages 8508-8522 (Também veja o pdf abaixo para Los Alamos National Laboratory report LA-UR-07-4046).

Referências

  1. R. von Mises and H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
  2. Ipsen, Ilse, and Rebecca M. Wills (5–8 de maio de 2005). «Analysis and Computation of Google's PageRank» (PDF). Fields Institute, Toronto, Canada  Parâmetro desconhecido |book= ignorado (ajuda)

Ligações externas

editar
  • Power method, part of lecture notes on numerical linear algebra by E. Bruce Pitman, State University of New York.
  • Module for the Power Method
  • [1] Los Alamos report LA-UR-07-4046 ""Multiple extremal eigenpairs by the power method"