Eclats de vers : Matemat 10 : Optimisation - 5

Soit un réel \(R \ne 0\), la matrice \(H \in \matrice(\setR,m,n)\) hermitienne et définie positive, et l'ensemble :

\[\Omega = \{ x \in \corps^n : \norme{x} = \sqrt{x^\dual \cdot x} = R \}\]

On peut reformuler \(\Omega\) de manière équivalente par :

\[\Omega = \{ x \in \corps^n : x^\dual \cdot x = R^2 \}\]

Soit l'objectif \(\varphi : \corps^n \mapsto \corps\) défini par :

\[\varphi(x) = x^\dual \cdot H \cdot x\]

pour tout \(x \in \corps^n\). On veut trouver le \(x \in \Omega\) qui minimise \(\varphi\) sur \(\Omega\). Définissons le lagrangien :

\[\lagrangien(x,\lambda) = x^\dual \cdot H \cdot x + \lambda \cdot (R^2 - x^\dual \cdot x)\]

où \(\lambda \in \setR\). On impose les conditions de Kuhn-Tucker :

Toute solution optimale \(x \in \Omega\) vérifie donc l'équation :

\[H \cdot x = \lambda \cdot x\]

pour un certain \(\lambda \in \setR\). Nous allons généraliser cette propriété aux applications linéaires.

Soit l'espace vectoriel \(E\) sur \(\corps\) et une application linéaire \(A : E \mapsto E\). Si le couple \((u,\lambda) \in (E \setminus \{0\}) \times \corps\) vérifie :

\[A(u) = \lambda \cdot u\]

On dit que \(u\) est vecteur propre de \(A\) correspondant à la valeur propre \(\lambda\).

Si l'application linéaire \(A\) est auto-adjointe (\(A^\dual = A\)), ses valeurs et vecteurs propres possèdent d'importantes propriétés. Soit \(u \in E\) et \(\lambda \in \setC\) tels que \(A(u) = \lambda \cdot u\) et \(\scalaire{u}{u} = 1\). On a alors :

\[\lambda = \scalaire{u}{A(u)} = \scalaire{A(u)}{u} = \conjugue \scalaire{u}{A(u)} = \bar{\lambda}\]

La valeur propre doit donc être réelle.

Supposons que la suite de vecteurs propres \((u_1,...,u_n)\) soit orthonormée. Pour tout \(x \in \combilin{u_1,...,u_n}\), on a alors :

\[x = \sum_i \scalaire{u_i}{x} \cdot u_i\]

et :

\begin{align} A(x) &= \sum_i \scalaire{u_i}{x} \cdot A(u_i) \\ &= \sum_i \lambda_i \cdot \scalaire{u_i}{x} \cdot u_i \end{align}

On peut donc représenter \(A\) sur \(\combilin{u_1,...,u_n}\) par le tenseur associé :

\[\mathcal{A} = \sum_i \lambda_i \cdot u_i \otimes u_i\]

de sorte que :

\[A(x) = \mathcal{A} \cdot x = \contraction{ \mathcal{A} }{1}{x}\]

Supposons que les vecteurs propres \(u_i\) forment une base orthonormée de \(E\), et que les valeurs propres correspondantes \(\lambda_i\) soient non nulles. Si \(x,y \in E\) sont tels que \(A(x) = \mathcal{A} \cdot x = y\), on a :

\[y = \sum_i \scalaire{u_i}{y} \cdot u_i = \mathcal{A} \cdot x = \sum_i \lambda_i \cdot u_i \cdot \scalaire{u_i}{x}\]

On en déduit en comparant les coefficients de chaque vecteur \(u_i\) que \(\lambda_i \cdot \scalaire{u_i}{x} = \scalaire{u_i}{y}\), d'où :

\[\scalaire{u_i}{x} = \unsur{\lambda_i} \cdot \scalaire{u_i}{y}\]

Mais ces produits scalaires sont les coordonnées de \(x\) par rapport aux \(u_i\) :

\[x = \sum_i \scalaire{u_i}{x} \cdot u_i = \sum_i \unsur{\lambda_i} \cdot \scalaire{u_i}{y} \cdot u_i\]

Donc, si on pose :

\[\mathcal{A}^{-1} = \sum_i \unsur{\lambda_i} \cdot u_i \otimes u_i\]

on a :

\[x = \mathcal{A}^{-1} \cdot y\]

On dit que \(\lambda \in \corps\) est la valeur propre de la matrice \(A \in \matrice(\corps,n,n)\) correspondant au vecteur propre non nul \(u \in \corps^n\) si ils sont valeurs et vecteurs propres de l'application linéaire sous-jacente :

\[A \cdot u = \lambda \cdot u\]

Soit la valeur propre \(\lambda\) de \(A\) et le vecteur propre correspondant \(u \ne 0\). On a :

\[A \cdot u = \lambda \cdot u\]

Multiplions cette équation à gauche par une matrice inversible \(Q\) :

\[Q \cdot A \cdot u = \lambda \cdot Q \cdot u\]

Posons à présent \(v = Q \cdot u\). On a alors \(u = Q^{-1} \cdot v\) et :

\[Q \cdot A \cdot Q^{-1} \cdot v = \lambda \cdot v\]

On constate aussi que \(v \ne 0\), car sinon :

\[0 \ne u = Q^{-1} \cdot v = Q^{-1} \cdot 0 = 0\]

ce qui est impossible. On en conclut que \(\lambda\) est aussi une valeur propre de la matrice :

\[B = Q \cdot A \cdot Q^{-1}\]

On dit que les valeurs propres sont des invariants sous transformation linéaire réversible.

Nous allons démontrer par récurrence sur la taille \(n\) d'une matrice triangulaire supérieure \(T\) que les composantes diagonales sont des valeurs propres de \(T\).

• Si \(n = 1\), soit les uniques composantes \(\lambda = \composante_{11}(T)\) et \(\mu = \composante_1(u)\). On a :

\[T \cdot u = [\lambda] \cdot [\mu] = \lambda \cdot [1] \cdot [\mu] = \lambda \cdot u\]

ce qui montre que la composante diagonale \(\lambda\) est une valeur propre de \(T\).

• Supposons que le résultat soit vrai pour \(n - 1\). Partitionnons à part la dernière ligne et la dernière colonne d'une matrice \(T \in \matrice(\corps,n,n)\) :

Donc, \(T^{(n-1)}\) est une matrice triangulaire de la forme :

où les composantes diagonales \(\lambda_1,...,\lambda_{n-1}\) vérifient :

\[T^{(n-1)} \cdot u_i^{(n-1)} = \lambda_i \cdot u_i^{(n-1)}\]

pour certains vecteurs propres \(u_i^{(n-1)} \ne 0\). Nous allons chercher les vecteurs propres \(u \in \corps^n\) de \(T\) sous la forme :

où \(v \in \corps^{n - 1}\) et \(\mu \in \setC\). Si on choisit \(v = u_i^{(n-1)}\) pour \(i \in \{1,2,...,n-1\}\) et \(\mu = 0\), on a :

\begin{align} T \cdot u &= \begin{Matrix}{cc} T^{(n-1)} & z \\ 0 & \lambda_n \end{Matrix} \cdot \begin{Matrix}{c} u_i^{(n-1)} \\ 0 \end{Matrix} \\ &= \begin{Matrix}{c} T^{(n-1)} \cdot u_i^{(n-1)} \\ 0 \end{Matrix} = \begin{Matrix}{c} \lambda_i \cdot u_i^{(n-1)} \\ 0 \end{Matrix} \\ &= \lambda_i \cdot \begin{Matrix}{c} u_i \\ 0 \end{Matrix} = \lambda_i \cdot u \end{align}

Les valeurs propres de \(T^{(n-1)}\) sont donc également valeurs propres de \(T\). Il nous reste à examiner le cas de \(\lambda_n\). Posons :

On doit donc trouver un vecteur \(u \in \corps^n\) non nul tel que :

Il suffit donc que \(u \ne 0\) vérifie \(A \cdot u = 0\). Mais comme \(A\) est de taille \((n - 1, n)\), le rang \(r\) vérifie \(r \le n - 1 \strictinferieur n\). Le système admet donc une infinité de solutions non nulles et \(\lambda_n\) est également une valeur propre de \(T\).

Soit une matrice carrée \(A\) de taille \((n,n)\). On choisit la valeur propre \(\lambda_1\) la plus grande de \(A\) et on évaluer un vecteur propre non nul correspondant \(u_1\) en résolvant le système :

\[(A - \lambda_1 \cdot I) \cdot u_1 = 0\]

On construit alors le complément orthogonal \((u_2, ..., u_n)\) tel que \((u_1,...,u_n)\) forme une suite orthonormée. On a donc \(u_j^\dual \cdot u_i = \indicatrice_{ij}\). Soit la matrice \(U\) de taille \((n,n)\) définie par :

\[U_1 = [u_1 \ u_2 \ ... \ u_n]\]

On a bien sur \(U_1^{-1} = U_1^\dual\) et :

\begin{align} A \cdot U_1 &= \begin{Matrix}{cccc} A \cdot u_1 & A \cdot u_2 & \hdots & A \cdot u_n \end{Matrix} \\ &= \begin{Matrix}{cccc} \lambda_1 \cdot u_1 & A \cdot u_2 & \hdots & A \cdot u_n \end{Matrix} \end{align}

En multipliant à gauche par la duale, on obtient :

\begin{align} U_1^\dual \cdot A \cdot U_1 &= \begin{Matrix}{cccc} (\lambda_1 \cdot u_1^\dual \cdot u_1) & (u_1^\dual \cdot A \cdot u_2) & \hdots & (u_1^\dual \cdot A \cdot u_n) \\ (\lambda_1 \cdot u_2^\dual \cdot u_1) & (u_2^\dual \cdot A \cdot u_2) & \hdots & (u_2^\dual \cdot A \cdot u_n) \\ \vdots & \vdots & \vdots & \vdots \\ (\lambda_1 \cdot u_n^\dual \cdot u_1) & (u_n^\dual \cdot A \cdot u_2) & \hdots & (u_n^\dual \cdot A \cdot u_n) \end{Matrix} \\ &= \begin{Matrix}{cccc} \lambda_1 & (u_1^\dual \cdot A \cdot u_2) & \hdots & (u_1^\dual \cdot A \cdot u_n) \\ 0 & (u_2^\dual \cdot A \cdot u_2) & \hdots & (u_2^\dual \cdot A \cdot u_n) \\ \vdots & \vdots & \vdots & \vdots \\ 0 & (u_n^\dual \cdot A \cdot u_2) & \hdots & (u_n^\dual \cdot A \cdot u_n) \end{Matrix} \\ \end{align}

ou, plus schématiquement :

On peut réitérer le même raisonnement en utilisant la plus grande valeur propre de \(A^{(n - 1)}\) et une matrice unitaire correspondante \(U^{(n - 1)}\). Posons :

On obtient :

On continue ainsi, en utilisant à l'étape \(k + 1\) la plus grande valeur propre de \(A^{(n - k)}\) et :

On s'arrête évidemment lorsque \(k + 1 = n\). Posons :

\[U = U_1 \cdot ... \cdot U_n\]

On obtient à la fin du processus une matrice triangulaire :

Comme :

\[U^{-1} = U_n^\dual \cdot ... \cdot U_1^\dual = U^\dual\]

on obtient, en multipliant la relation précédente à gauche par \(U\) et à droite par \(U^\dual\) la décomposition :

\[A = U \cdot T \cdot U^\dual\]

On appelle cette décomposition la forme de Schur et on la note :

\[(T,U) = \schur(A)\]

Le but est d'évaluer les valeurs propres d'une matrice \(A\). Pour cela, on tente d'obtenir une approximation de la forme de Schur. Il s'agit d'un algorithme itératif qui part de :

\[A_0 = A\]

A chaque itération \(k\), on décompose la matrice \(A_k\) obtenue à l'itération précédente en utilisant l'algorithme de Householder :

\[(Q_k, R_k) = \householder(A_k)\]

On a alors \(A_k = Q_k \cdot R_k\), avec \(Q_k^\dual = Q_k^{-1}\). On construit ensuite une nouvelle matrice \(A_{k+1}\) par :

\[A_{k + 1} = Q_k^\dual \cdot A_k \cdot Q_k = Q_k^\dual \cdot Q_k \cdot R_k \cdot Q_k = R_k \cdot Q_k\]

Au bout de \(p\) itérations, la matrice \(A_p\) produite par l'algorithme vérifie :

\[A_p = Q_p^\dual \cdot ... \cdot Q_0^\dual \cdot A \cdot Q_0 \cdot ... \cdot Q_p\]

En inversant cette relation, on obtient :

\[A = Q_0 \cdot ... \cdot Q_p \cdot A_p \cdot Q_p^\dual \cdot ... \cdot Q_0^\dual\]

En injectant l'identité \(A_p \cdot Q_p^\dual = R_p\), on arrive à :

\[A = Q_0 \cdot ... Q_p \cdot R_p \cdot Q_{p - 1}^\dual \cdot ... \cdot Q_0^\dual\]

Si les suites :

\[\mathcal{U}_p = Q_0 \cdot ... Q_p\]

et \(R_p\) convergent :

on a bien évidemment :

\[\lim_{p \to \infty} \mathcal{U}_{p - 1}^\dual = U^\dual\]

On en déduit la forme approximative :

\[A = U \cdot R \cdot U^\dual \approx \mathcal{U}_N \cdot R_N \cdot \mathcal{U}_N^\dual\]

pour \(N\) suffisamment grand. Par invariance sous transformation réversible, les estimations des valeurs propres de \(A\) sont sur la diagonale de la matrice triangulaire supérieure \(R_N \approx R\). On peut se servir de ces estimations pour appliquer l'algorithme de Schur et construire une matrice triangulaire où les valeurs propres sont triées par ordre décroissant sur la diagonale.

Si \(A\) est hermitienne (\(A = A^\dual)\), la forme de Schur \((T,U) = \schur(A)\) implique que :

\[A = U \cdot T \cdot U^\dual = A^\dual = U \cdot T^\dual \cdot U^\dual\]

On en déduit en multipliant à gauche par \(U^\dual\) et à droite par \(U\) que \(T = T^\dual\). Mais comme \(T\) est triangulaire supérieure, on a \(t_{ij} = \composante_{ij}(T) = 0\) si \(i \strictsuperieur j\). De l'autre coté de la diagonale, on a \(t_{ji} = \conjaccent{t}_{ij} = 0\). On en conclut que les seuls éléments potentiellement non nuls doivent se trouver sur la diagonale (\(i = j\)). La matrice \(T\) se réduit donc à une matrice diagonale formée à partir des valeurs propres \(\lambda_i\) (non nécessairement distinctes) de \(A\) :

\[T = \Lambda = \diagonale_n(\lambda_1,...,\lambda_n)\]

En multipliant \(A = U \cdot \Lambda \cdot U^\dual\) à droite par \(U\), on a :

\[A \cdot U = \Lambda \cdot U\]

Donc, si \(u_i = \colonne_i U\), on a :

\[A \cdot u_i = \lambda_i \cdot u_i\]

Les vecteurs propres sont donc donnés par les colonnes de \(U\). Comme \(U^\dual \cdot U = I\), on a la propriété d'orthonormalité :

\[u_i^\dual \cdot u_j = \indicatrice_{ij}\]

Soit une matrice hermitienne \(A\) et sa forme de Schur :

\[A = U \cdot \Lambda \cdot U^\dual\]

Nous posons :

\begin{align} \lambda_i &= \composante_{ii} \Lambda \\ u_i &= \colonne_i U \end{align}

pour les valeurs propres et vecteurs propres correspondants. Les valeurs propres étant triées par ordre décroissant, on a :

\[\lambda_1 \ge \lambda_2 \ge \lambda_3 \ge ...\]

On considère le rapport de Rayleigh défini par :

\[R(x) = \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

pour tout \(x \in \setC^n \setminus \{0\}\). Choisissons un tel \(x\). Comme les \(u_i\) forment une base orthonormée, on a :

\[x = \sum_{i = 1}^n a_i \cdot u_i\]

où \(a_i = \scalaire{u_i}{x}\) par orthonormalité. Le rapport s'écrit alors :

\begin{align} R(x) &= \frac{ \sum_{i,j = 1}^n \conjaccent{a}_i \cdot a_j \cdot u_i^\dual \cdot A \cdot u_j }{ \sum_{i,j = 1}^n \conjaccent{a}_i \cdot a_j \cdot u_i^\dual \cdot u_j} \\ \\ &= \frac{ \sum_{i = 1}^n \abs{a_i}^2 \cdot \lambda_i }{ \sum_{j = 1}^n \abs{a_j}^2 } \end{align}

Posons :

\[w_i = \frac{\abs{a_i}^2}{\sum_{j = 1}^n \abs{a_j}^2}\]

Il est clair que les \(w_i\) sont des réels positifs et que :

\[\sum_{i = 1}^n w_i = \frac{\sum_{i = 1}^n \abs{a_i}^2}{\sum_{j = 1}^n \abs{a_j}^2} = 1\]

On a alors :

\[R(x) = \sum_{i = 1}^n w_i \cdot \lambda_i\]