A iteração de potência

Achar a direção dominante por multiplicações repetidas

Resolver um polinômio característico é inviável para uma matriz $1000\times1000$, e muitas vezes só se quer o maior par próprio, por exemplo o primeiro componente principal. A iteração de potência o encontra apenas com produtos matriz-vetor. Parta de qualquer vetor $\mathbf x_0$ e repita $\mathbf x_{k+1}=A\mathbf x_k/\lVert A\mathbf x_k\rVert$. Cada multiplicação estica a componente ao longo do autovetor dominante mais que todas as outras, de modo que, após passos suficientes, o vetor aponta nessa direção.

Escreva $\mathbf x_0=c_1\mathbf v_1+c_2\mathbf v_2+\cdots$ em autovetores. Após $k$ passos os coeficientes são multiplicados por $\lambda_i^k$, então a razão do segundo para o primeiro é $(\lambda_2/\lambda_1)^k$. O método converge quando $|\lambda_1|>|\lambda_2|$ e o vetor inicial tem alguma componente ao longo de $\mathbf v_1$, e a velocidade depende de $|\lambda_2/\lambda_1|$: autovalores próximos significam convergência lenta. A normalização apenas evita o estouro numérico; o que importa é a direção. A estimativa do autovalor é o quociente de Rayleigh. Para o próximo par, subtrai-se $\lambda_1\mathbf v_1\mathbf v_1^{T}$ de uma matriz simétrica $A$ e repete-se, o que se chama deflação.

• Atualização: multiplicar por $A$, dividir pela norma e repetir; cada passo custa um produto matriz-vetor.
• Velocidade: o erro cai como $|\lambda_2/\lambda_1|^k$, então autovalores maiores próximos convergem devagar.
• Requisitos: uma folga $|\lambda_1|>|\lambda_2|$ e um vetor inicial não ortogonal a $\mathbf v_1$.

Lab: o que é avaliado

• A que converge15 pts
• Um quociente de Rayleigh20 pts
• A razão de convergência10 pts
• Quantas iterações15 pts
• O algoritmo em ordem15 pts
• Quando é lenta ou falha15 pts
• Por que normalizar10 pts