Método das potências

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 ira encontrar apenas um autovalor (aquele com o maior módulo) e poderá convergir lentamente.


O método[editar | editar código-fonte]

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

 b_{k+1} = \frac{Ab_k}{\|Ab_k\|}.

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 b_{0} tem um componente não-nulo na direção de um autovetor associado com o autovalor dominante.

Assim:

  • A sub-série \left( b_{k} \right) converge a um autovetor associado com o autovalor dominante.

Note que a série \left( b_{k} \right) não necessariamente converge. Pode ser mostrado que:
b_{k} = e^{i \phi_{k}} v_{1} + r_{k} onde: v_{1} é um autovetor associado ao autovalor dominante, e  \| r_{k} \| \rightarrow 0. A presença do termo e^{i \phi_{k}} implica que \left( b_{k} \right) não irá convergir a menos que e^{i \phi_{k}} = 1. Sob os dois pressupostos acima, a série \left( \mu_{k} \right) definida por: \mu_{k} = \frac{b_{k}^{*}Ab_{k}}{b_{k}^{*}b_{k}} 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:

 \frac{b_k^\top A b_k}{b_k^\top b_k} = \frac{b_{k+1}^\top b_k}{b_k^\top b_k}.


Análise[editar | editar código-fonte]

Decompondo A pela forma canônica de Jordan: A=VJV^{-1}, onde a primeira coluna de V é um autovetor de A correspondente ao autovalor dominante de \lambda_{1}. Como o autovalor dominante de A é único, o primeiro bloco de Jordan de J é a matriz 1x1 \begin{bmatrix} \lambda_{1} \end{bmatrix} , onde \lambda_{1} é o maior autovalor de A em magnitude. O vetor inicial b_{0} pode ser escrito como uma combinação linear das colunas de V:

b_{0} = c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n}.

Pela hipótese, b_{0} tem um componente não-nulo na direção do autovalor dominante , assim c_{1} \ne 0.

A útil relação de recorrência computacional para b_{k+1} pode ser reescrita como:

b_{k+1}=\frac{Ab_{k}}{\|Ab_{k}\|}=\frac{A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|},

onde a expressão:

\frac{A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}

é mais propícia a seguinte análise.


\displaystyle
\begin{array}{lcl}
b_{k} &=& \frac{A^{k}b_{0}}{\| A^{k} b_{0} \|} \\
      &=& \frac{\left( VJV^{-1} \right)^{k} b_{0}}{\|\left( VJV^{-1} \right)^{k}b_{0}\|} \\
      &=& \frac{ VJ^{k}V^{-1} b_{0}}{\| V J^{k} V^{-1} b_{0}\|} \\
      &=& \frac{ VJ^{k}V^{-1} \left( c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n} \right)}
               {\| V J^{k} V^{-1} \left( c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{n}v_{n} \right)\|} \\
      &=& \frac{ VJ^{k}\left( c_{1}e_{1} + c_{2}e_{2} + \cdots + c_{n}e_{n} \right)}
                {\| V J^{k} \left( c_{1}e_{1} + c_{2}e_{2} + \cdots + c_{n}e_{n} \right) \|} \\
      &=& \left( \frac{\lambda_{1}}{|\lambda_{1}|} \right)^{k} \frac{c_{1}}{|c_{1}|}
          \frac{ v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} 
                      \left( c_{2}e_{2} +  \cdots + c_{n}e_{n} \right)}
               {\| v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} 
                      \left( c_{2}e_{2} +  \cdots + c_{n}e_{n} \right) \| }
           
\end{array}

A expressão acima simplifica como k \rightarrow \infty k \rightarrow \infty

\left( \frac{1}{\lambda_{1}} J \right)^{k} = 
\begin{bmatrix}
[1] & & & & \\
& \left( \frac{1}{\lambda_{1}} J_{2} \right)^{k}& & & \\
& & \ddots & \\
& & & \left( \frac{1}{\lambda_{1}} J_{m} \right)^{k} \\
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & & & & \\
& 0 & & & \\
& & \ddots & \\
& & & 0 \\
\end{bmatrix}

enquanto  k \rightarrow \infty .


O limite vem do fato de que o autovalor de  \frac{1}{\lambda_{1}} J_{i} ser menor que 1 em magnitude, então


\left( \frac{1}{\lambda_{1}} J_{i} \right)^{k} \rightarrow 0
enquanto  k \rightarrow \infty
.

Segue que:

\frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} 
\left( c_{2}e_{2} +  \cdots + c_{n}e_{n} \right)
\rightarrow 0
enquanto 
k \rightarrow \infty


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

\begin{matrix}
b_{k} &=& \left( \frac{\lambda_{1}}{|\lambda_{1}|} \right)^{k} \frac{c_{1}}{|c_{1}|}
          \frac{ v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} 
                      \left( c_{2}e_{2} +  \cdots + c_{n}e_{n} \right)}
               {\| v_{1} + \frac{1}{c_{1}} V \left( \frac{1}{\lambda_1} J \right)^{k} 
                      \left( c_{2}e_{2} +  \cdots + c_{n}e_{n} \right) \| }
      &=& e^{i \phi_{k}} \frac{c_{1}}{|c_{1}|} v_{1} + r_{k}
\end{matrix}

onde  e^{i \phi_{k}} = \left( \lambda_{1} / |\lambda_{1}| \right)^{k} e  \| r_{k} \| \rightarrow 0 enquanto k \rightarrow \infty


A série  \left( b_{k} \right) é 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 \left(b_{k}\right) possa não convergir, b_{k} é 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 \lambda_1 é o autovalor dominante, assim |\lambda_1| > |\lambda_j| para j>1.

O vetor inicial b_0 pode ser escrito como:

b_0 = c_{1}v_{1} + c_{2}v_{2} + \cdots + c_{m}v_{m}.

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

\begin{array}{lcl}A^{k}b_0 & = & c_{1}A^{k}v_{1} + c_{2}A^{k}v_{2} + \cdots + c_{m}A^{k}v_{m} \\
& = & c_{1}\lambda_{1}^{k}v_{1} + c_{2}\lambda_{2}^{k}v_{2} + \cdots + c_{m}\lambda_{m}^{k}v_{m} \\
& = & c_{1}\lambda_{1}^{k} \left( v_{1} + \frac{c_{2}}{c_{1}}\left(\frac{\lambda_{2}}{\lambda_{1}}\right)^{k}v_{2} + \cdots + \frac{c_{m}}{c_{1}}\left(\frac{\lambda_{m}}{\lambda_{1}}\right)^{k}v_{m}\right). \end{array}

A expressão entre parênteses converge para v_1 por causa que | \lambda_j/\lambda_1| < 1 para j>1. Por outro lado, nós temos

 b_k = \frac{A^kb_0}{\|A^kb_0\|}.

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

 \left| \frac{\lambda_2}{\lambda_1} \right|,

onde \lambda_2 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 | editar código-fonte]

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 A^{-1}. Outros algoritmos olham para todo o sub-espaço gerado pelos vetores b_k.. 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  \left| \lambda_{n+1} / \lambda_1\right|, , é "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).

Referencia[editar | editar código-fonte]

  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). "[1]".

Links Externos[editar | editar código-fonte]

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