L'itération de puissance

Trouver la direction dominante par multiplications répétées

Résoudre un polynôme caractéristique est sans espoir pour une matrice $1000\times1000$, et l'on ne veut souvent que la plus grande paire propre, par exemple la première composante principale. L'itération de puissance la trouve avec de simples produits matrice-vecteur. Partez d'un vecteur quelconque $\mathbf x_0$ et répétez $\mathbf x_{k+1}=A\mathbf x_k/\lVert A\mathbf x_k\rVert$. Chaque multiplication étire la composante le long du vecteur propre dominant plus que toutes les autres, de sorte qu'après assez d'étapes le vecteur pointe dans cette direction.

Écrivons $\mathbf x_0=c_1\mathbf v_1+c_2\mathbf v_2+\cdots$ dans la base des vecteurs propres. Après $k$ étapes, les coefficients sont multipliés par $\lambda_i^k$, donc le rapport du deuxième au premier est $(\lambda_2/\lambda_1)^k$. La méthode converge si $|\lambda_1|>|\lambda_2|$ et si le vecteur de départ a une composante le long de $\mathbf v_1$ ; la vitesse dépend de $|\lambda_2/\lambda_1|$ : des valeurs propres proches donnent une convergence lente. La normalisation évite seulement le débordement ; seule la direction compte. L'estimation de la valeur propre est le quotient de Rayleigh. Pour la paire suivante, on retranche $\lambda_1\mathbf v_1\mathbf v_1^{T}$ d'une matrice symétrique $A$ et on recommence : c'est la déflation.

• Mise à jour : multiplier par $A$, diviser par la norme, recommencer ; chaque étape coûte un produit matrice-vecteur.
• Vitesse : l'erreur décroît comme $|\lambda_2/\lambda_1|^k$, donc des plus grandes valeurs propres proches convergent lentement.
• Conditions : un écart $|\lambda_1|>|\lambda_2|$ et un vecteur initial non orthogonal à $\mathbf v_1$.

Lab : ce qui est noté

• Vers quoi elle converge15 pts
• Un quotient de Rayleigh20 pts
• Le rapport de convergence10 pts
• Combien d'itérations15 pts
• L'algorithme dans l'ordre15 pts
• Quand elle est lente ou échoue15 pts
• Pourquoi normaliser10 pts