Table des matières
Définitions
Soit $\lambda$ valeur propre et $\omega$ vecteur propre, alors $A \omega = \lambda \omega$
Détermination
Scolaire
Il faut résoudre $det(A-I_n x) = 0$ avec les solutions de $x$ toutes les valeurs propres.
Dans le cas d'une matrice diagonale, les valeurs propres sont sur la diagonale.
Itérative, algorithme élémentaire
Condition : $A$ diagonalisable, valeurs propres distinctes.
Si une valeur propre est double, il faudra itérer non pas sur un vecteur mais sur un sous espèce (plusieurs vecteurs) et obtenir ainsi une matrice de covariance.
TODO : à détailler.
Méthode basique
$$X^{n+1/2} = (A - μ I)^{-1} X^n$$
avec $μ$ une valeur proche de la valeur propre à trouver et $X^0$ une valeur approchée du vecteur propre et $(X^0, \omega)$.
L'algorithme convergera vers $min |\lambda_i - μ|$.
Généralement, on prend $μ$ à 0 pour la recherche de la première valeur propre.
$$X^n = \frac{X^{n+1/2}}{\left\|X^{n+1/2}\right\|}$$
$$R^n = (X^{n+1/2},X^n)$$
La valeur propre vaut $\lambda = \frac{1}{R^{\infty}} + μ$ et le vecteur propre vaut $\omega = X^n$.
En prenant $(A - μ I)^{-1}$, on va trouver le $\lambda$ le plus petit.
Il est aussi possible de prendre $(A - μ I)$. Dans ce cas, on va trouver le $\lambda$ le plus grand avec $\lambda = R^{\infty} + μ$ et $\omega = X^n$.
Exemple :
$$A = \begin{pmatrix} 3 & 1 & 1 \\ 1 & 4 & 2 \\ 1 & 2 & 4 \\ \end{pmatrix}$$
On pose $μ = 1$.
$$(A - μ I)^{-1} = \begin{pmatrix} 0.625 & -0.125 & -0.125 \\ -0.125 & 0.625 & -0.375 \\ -0.125 & -0.375 & 0.625 \\ \end{pmatrix}$$
On pose $$\omega = \begin{pmatrix} 1 \\ 2 \\ 4 \\ \end{pmatrix}$$
$$X^{1/2} = \begin{pmatrix} -0.125 \\ -0.375 \\ 1.625 \\ \end{pmatrix}$$
$$X^1 = \begin{pmatrix} -0.074744 \\ -0.224231 \\ 0.971666 \\ \end{pmatrix}$$
$$X^5 = \begin{pmatrix} -0.067514 \\ -0.685836 \\ 0.724618 \\ \end{pmatrix}$$
$$X^{40} = \lambda = \begin{pmatrix} 0 \\ -0.707107 \\ 0.707107 \\ \end{pmatrix}$$
$$R^{40} = 1$$
$$\lambda = \frac{1}{1} + 1 = 2$$
Accélération
On peut accélérer la convergence :
$$X^{n+1/2} = (A - μ I)^{-1} \left( 1 + \frac{1}{R^n} \right) X^n$$
Exemple :
$$A = \begin{pmatrix} 3 & 1 & 1 \\ 1 & 4 & 2 \\ 1 & 2 & 4 \\ \end{pmatrix}$$
On pose $μ = 1$.
$$(A - μ I)^{-1} = \begin{pmatrix} 0.625 & -0.125 & -0.125 \\ -0.125 & 0.625 & -0.375 \\ -0.125 & -0.375 & 0.625 \\ \end{pmatrix}$$
On pose $$\omega = \begin{pmatrix} 1 \\ 2 \\ 4 \\ \end{pmatrix}$$
On norme $\omega$.
$$X^{0} = \begin{pmatrix} 0.218218 \\ 0.436436 \\ 0.872872 \\ \end{pmatrix}$$
$$X^{1/2} = \begin{pmatrix} -0.027277 \\ -0.081832 \\ 0.354604 \\ \end{pmatrix}$$
$$R^1 = 0.267857$$
On ne connait pas $R^0$.
$$X^1 = \begin{pmatrix} -0.074744 \\ -0.224231 \\ 0.971666 \\ \end{pmatrix}$$
$$X^{1+1/2} = \begin{pmatrix} -0.663349 \\ -2.34393 \\ 3.31674 \\ \end{pmatrix}$$
$$R^{2} = 3.79791$$
$$X^{2} = \begin{pmatrix} -0.161197 \\ -0.569563 \\ 0.805986 \\ \end{pmatrix}$$
$$R^{3} = 1.23655$$
$$X^{3} = \begin{pmatrix} -0.132438 \\ -0.648537 \\ 0.749573 \\ \end{pmatrix}$$
$$R^{5} = 1.55162$$
$$X^{5} = \begin{pmatrix} -0.067514 \\ -0.685836 \\ 0.724618 \\ \end{pmatrix}$$
On converge légèrement plus vite en 35 itérations.
Recherche de la valeur propre suivante et supérieure
$$X^{n+1/4} = (A - μ I)^{-1} X^n$$
$$X^{n+1/2} = X^{n+1/4} - (X^{n+1/4}, \omega) \omega$$
Exemple :
$$A = \begin{pmatrix} 3 & 1 & 1 \\ 1 & 4 & 2 \\ 1 & 2 & 4 \\ \end{pmatrix}$$
On pose $μ = 1$.
$$(A - μ I)^{-1} = \begin{pmatrix} 0.625 & -0.125 & -0.125 \\ -0.125 & 0.625 & -0.375 \\ -0.125 & -0.375 & 0.625 \\ \end{pmatrix}$$
$$\omega = \begin{pmatrix} 0 \\ -0.707107 \\ 0.707107 \\ \end{pmatrix}$$
$$X^{0} = \begin{pmatrix} 0.218218 \\ 0.436436 \\ 0.872872 \\ \end{pmatrix}$$
$$X^{0+1/4} = \begin{pmatrix} -0.027277 \\ -0.081832 \\ 0.354604 \\ \end{pmatrix}$$
$$X^{0+1/2} = \begin{pmatrix} -0.085728 \\ -0.198734 \\ 0.120799 \\ \end{pmatrix}$$
$$X^{1} = \begin{pmatrix} -0.345867 \\ -0.801784 \\ 0.487359 \\ \end{pmatrix}$$
$$X^{5} = \begin{pmatrix} -0.931698 \\ -0.256854 \\ 0.256854 \\ \end{pmatrix}$$
$$X^{13} = \begin{pmatrix} -0.92941 \\ -0.260956 \\ 0.260956 \\ \end{pmatrix}$$
$$R^{13} = 0.695194$$
Soit $\lambda_2 = 2.43845$