LG

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====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.

<WRAP center round info 60%>
TODO : à détailler.
</WRAP>

===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$