LG

Outils pour utilisateurs

Outils du site

Piste : • reseau • poo • ihm • flann
math:matrices:propres

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentesRévision précédente
Prochaine révision		Révision précédente
math:matrices:propres [2019/02/28 22:51] – Ajout de "Itérative, algorithme élémentaire" rootmath:matrices:propres [2020/04/27 08:05] (Version actuelle) – Conversion de <note> vers <WRAP> root
Ligne 8: Ligne 8:
 Dans le cas d'une matrice diagonale, les valeurs propres sont sur la diagonale. Dans le cas d'une matrice diagonale, les valeurs propres sont sur la diagonale.
  
-===Itérative, algorithme élémentaire=== +====Itérative, algorithme élémentaire==== 
-Condition : $A$ matrice symétrique.+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$$ $$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\|}$$ $$X^n = \frac{X^{n+1/2}}{\left\|X^{n+1/2}\right\|}$$
Ligne 17: Ligne 31:
 $$R^n = (X^{n+1/2},X^n)$$ $$R^n = (X^{n+1/2},X^n)$$
  
-La valeur propre vaut $\frac{1}{R^{\infty}} + μ$ et le vecteur propre vaut $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$
math/matrices/propres.1551390712.txt.gz · Dernière modification : 2019/02/28 22:51 de root