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.

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

O método da potência inicia com um vetor b₀, 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 b_k é 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 }Ab_{k}}{b_{k}^{\top }b_{k}}}={\frac {b_{k+1}^{\top }b_{k}}{b_{k}^{\top }b_{k}}}.$

Análise

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}\neq 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}}{\|VJ^{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)}{\|VJ^{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)}{\|VJ^{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 λ₁, λ₂, …, λ_m os m autovalores de A e seja v₁, v₂, …, v_m 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 c₁ ≠ 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}$ porque $|\lambda _{j}/\lambda _{1}|<1$ para $j>1$. Por outro lado, nós temos

$b_{k}={\frac {A^{k}b_{0}}{\|A^{k}b_{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

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

Ligações externas

• 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"