Eclats de vers : Matemat 10 : Optimisation - 5

Index des Grimoires

Retour à l’accueil

Table des matières

\( \newcommand{\parentheses}[1]{\left(#1\right)} \newcommand{\crochets}[1]{\left[#1\right]} \newcommand{\accolades}[1]{\left\{#1\right\}} \newcommand{\ensemble}[1]{\left\{#1\right\}} \newcommand{\identite}{\mathrm{Id}} \newcommand{\indicatrice}{\boldsymbol{\delta}} \newcommand{\dirac}{\delta} \newcommand{\moinsun}{{-1}} \newcommand{\inverse}{\ddagger} \newcommand{\pinverse}{\dagger} \newcommand{\topologie}{\mathfrak{T}} \newcommand{\ferme}{\mathfrak{F}} \newcommand{\img}{\mathbf{i}} \newcommand{\binome}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\canonique}{\mathfrak{c}} \newcommand{\tenseuridentite}{\boldsymbol{\mathcal{I}}} \newcommand{\permutation}{\boldsymbol{\epsilon}} \newcommand{\matriceZero}{\mathfrak{0}} \newcommand{\matriceUn}{\mathfrak{1}} \newcommand{\christoffel}[2]{ \left\{ \begin{array}{c} #1 \\ #2 \\ \end{array} \right\} } \newcommand{\lagrangien}{\mathfrak{L}} \newcommand{\sousens}{\mathfrak{P}} \newcommand{\partition}{\mathrm{Partition}} \newcommand{\tribu}{\mathrm{Tribu}} \newcommand{\topologies}{\mathrm{Topo}} \newcommand{\setB}{\mathbb{B}} \newcommand{\setN}{\mathbb{N}} \newcommand{\setZ}{\mathbb{Z}} \newcommand{\setQ}{\mathbb{Q}} \newcommand{\setR}{\mathbb{R}} \newcommand{\setC}{\mathbb{C}} \newcommand{\corps}{\mathbb{K}} \newcommand{\boule}{\mathfrak{B}} \newcommand{\intervalleouvert}[2]{\relax \ ] #1 , #2 [ \ \relax} \newcommand{\intervallesemiouvertgauche}[2]{\relax \ ] #1 , #2 ]} \newcommand{\intervallesemiouvertdroite}[2]{[ #1 , #2 [ \ \relax} \newcommand{\fonction}{\mathbb{F}} \newcommand{\bijection}{\mathrm{Bij}} \newcommand{\polynome}{\mathrm{Poly}} \newcommand{\lineaire}{\mathrm{Lin}} \newcommand{\continue}{\mathrm{Cont}} \newcommand{\homeomorphisme}{\mathrm{Hom}} \newcommand{\etagee}{\mathrm{Etagee}} \newcommand{\lebesgue}{\mathrm{Leb}} \newcommand{\lipschitz}{\mathrm{Lip}} \newcommand{\suitek}{\mathrm{Suite}} \newcommand{\matrice}{\mathbb{M}} \newcommand{\krylov}{\mathrm{Krylov}} \newcommand{\tenseur}{\mathbb{T}} \newcommand{\essentiel}{\mathfrak{E}} \newcommand{\relation}{\mathrm{Rel}} \newcommand{\strictinferieur}{\ < \ } \newcommand{\strictsuperieur}{\ > \ } \newcommand{\ensinferieur}{\eqslantless} \newcommand{\enssuperieur}{\eqslantgtr} \newcommand{\esssuperieur}{\gtrsim} \newcommand{\essinferieur}{\lesssim} \newcommand{\essegal}{\eqsim} \newcommand{\union}{\ \cup \ } \newcommand{\intersection}{\ \cap \ } \newcommand{\opera}{\divideontimes} \newcommand{\autreaddition}{\boxplus} \newcommand{\autremultiplication}{\circledast} \newcommand{\commutateur}[2]{\left[ #1 , #2 \right]} \newcommand{\convolution}{\circledcirc} \newcommand{\correlation}{\ \natural \ } \newcommand{\diventiere}{\div} \newcommand{\modulo}{\bmod} \newcommand{\pgcd}{pgcd} \newcommand{\ppcm}{ppcm} \newcommand{\produitscalaire}[2]{\left\langle #1 \left|\right\relax #2 \right\rangle} \newcommand{\scalaire}[2]{\left\langle #1 \| #2 \right\rangle} \newcommand{\braket}[3]{\left\langle #1 \right| #2 \left| #3 \right\rangle} \newcommand{\orthogonal}{\bot} \newcommand{\forme}[2]{\left\langle #1 , #2 \right\rangle} \newcommand{\biforme}[3]{\left\langle #1 , #2 , #3 \right\rangle} \newcommand{\contraction}[3]{\left\langle #1 \odot #3 \right\rangle_{#2}} \newcommand{\dblecont}[5]{\left\langle #1 \right| #3 \left| #5 \right\rangle_{#2,#4}} \newcommand{\major}{major} \newcommand{\minor}{minor} \newcommand{\maxim}{maxim} \newcommand{\minim}{minim} \newcommand{\argument}{arg} \newcommand{\argmin}{arg\ min} \newcommand{\argmax}{arg\ max} \newcommand{\supessentiel}{ess\ sup} \newcommand{\infessentiel}{ess\ inf} \newcommand{\dual}{\star} \newcommand{\distance}{\mathfrak{dist}} \newcommand{\norme}[1]{\left\| #1 \right\|} \newcommand{\normetrois}[1]{\left|\left\| #1 \right\|\right|} \newcommand{\adh}{adh} \newcommand{\interieur}{int} \newcommand{\frontiere}{\partial} \newcommand{\image}{im} \newcommand{\domaine}{dom} \newcommand{\noyau}{ker} \newcommand{\support}{supp} \newcommand{\signe}{sign} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\unsur}[1]{\frac{1}{#1}} \newcommand{\arrondisup}[1]{\lceil #1 \rceil} \newcommand{\arrondiinf}[1]{\lfloor #1 \rfloor} \newcommand{\conjugue}{conj} \newcommand{\conjaccent}[1]{\overline{#1}} \newcommand{\division}{division} \newcommand{\difference}{\boldsymbol{\Delta}} \newcommand{\differentielle}[2]{\mathfrak{D}^{#1}_{#2}} \newcommand{\OD}[2]{\frac{d #1}{d #2}} \newcommand{\OOD}[2]{\frac{d^2 #1}{d #2^2}} \newcommand{\NOD}[3]{\frac{d^{#3} #1}{d #2^{#3}}} \newcommand{\deriveepartielle}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\dblederiveepartielle}[2]{\frac{\partial^2 #1}{\partial #2 \partial #2}} \newcommand{\dfdxdy}[3]{\frac{\partial^2 #1}{\partial #2 \partial #3}} \newcommand{\dfdxdx}[2]{\frac{\partial^2 #1}{\partial #2^2}} \newcommand{\gradient}{\mathbf{\nabla}} \newcommand{\combilin}[1]{\mathrm{span}\{ #1 \}} \newcommand{\trace}{tr} \newcommand{\proba}{\mathbb{P}} \newcommand{\probaof}[1]{\mathbb{P}\left[#1\right]} \newcommand{\esperof}[1]{\mathbb{E}\left[#1\right]} \newcommand{\cov}[2]{\mathrm{cov} \left( #1 , #2 \right) } \newcommand{\var}[1]{\mathrm{var} \left( #1 \right) } \newcommand{\rand}{\mathrm{rand}} \newcommand{\variation}[1]{\left\langle #1 \right\rangle} \newcommand{\composante}{comp} \newcommand{\bloc}{bloc} \newcommand{\ligne}{ligne} \newcommand{\colonne}{colonne} \newcommand{\diagonale}{diag} \newcommand{\matelementaire}{\mathrm{Elem}} \newcommand{\matpermutation}{permut} \newcommand{\matunitaire}{\mathrm{Unitaire}} \newcommand{\gaussjordan}{\mathrm{GaussJordan}} \newcommand{\householder}{\mathrm{Householder}} \newcommand{\rang}{rang} \newcommand{\schur}{\mathrm{Schur}} \newcommand{\singuliere}{\mathrm{DVS}} \newcommand{\convexe}{\mathrm{Convexe}} \newcommand{\petito}[1]{o\left(#1\right)} \newcommand{\grando}[1]{O\left(#1\right)} \)

1 Valeurs propres

1.1 Minimisation d'une forme quadratique avec norme contrainte

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 :

\( \partial_x \lagrangien(x,\lambda) = 2 H \cdot x - 2 \lambda \cdot x = 0 \\ \partial_\lambda \lagrangien(x,\lambda) = R^2 - x^\dual \cdot x = 0 \)

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.

1.1.1 Norme unité

Un cas particulier souvent utilisé est celui où \(R = 1\).

1.2 Application linéaire

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\).

1.2.1 Rapport de Rayleigh

En prenant le produit scalaire de \(u\) avec la relation \(A(u) = \lambda \cdot u\), on obtient :

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

d'où l'on tire :

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

Une telle expression est appelée rapport de Rayleigh. Par extension, on définit :

\[R(v) = \frac{ \scalaire{v}{A(v)} }{ \scalaire{v}{v} }\]

pou tout vecteur non nul \(v \in E\).

1.2.2 Définie positive

Si \(A\) est définie positive, toute valeur propre \(\lambda = R(u) \ge 0\) est un réel positif.

1.2.3 Formulation équivalente

On voit qu'il est équivalent de chercher un scalaire \(\lambda\) et un vecteur \(u \ne 0\) tel que :

\[(A - \lambda \cdot \identite)(u) = A(u) - \lambda \cdot u = 0\]

1.3 Opérateurs auto-adjoints

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.

1.3.1 Orthonormalité

Soit la suite de vecteurs propres \(u_i \in \Omega\) et de valeurs propres \(\lambda_i \in \setR\). On a :

\[\scalaire{u_i}{A(u_j)} = \lambda_j \cdot \scalaire{u_i}{u_j}\]

ainsi que :

\[\scalaire{u_i}{A(u_j)} = \scalaire{A(u_i)}{u_j} = \lambda_i \cdot \scalaire{u_i}{u_j}\]

En soustrayant ces deux équations, on obtient :

\[(\lambda_j - \lambda_i) \cdot \scalaire{u_i}{u_j} = 0\]

Le produit scalaire doit s'annuler lorsque les valeurs propres diffèrent. Si toutes les valeurs propres sont distinctes, les vecteurs propres forment une suite orthonormée :

\[\scalaire{u_i}{u_j} = \indicatrice_{ij}\]

1.3.2 Orthogonalité par rapport à l'application linéaire

Si les vecteurs propres \(u_i \in \Omega\) sont orthonormés, on a :

\[\scalaire{u_i}{A(u_j)} = \lambda_j \cdot \scalaire{u_i}{u_j} = \lambda_j \cdot \indicatrice_{ij}\]

1.4 Représentation tensorielle

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}\]

1.5 Inverse

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\]

1.6 Représentation matricielle

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\]

1.6.1 Formulation équivalente

On voit qu'il est équivalent de chercher un scalaire \(\lambda\) et un vecteur \(u \ne 0\) tel que :

\[(A - \lambda \cdot I) \cdot u = 0\]

1.6.2 Rapport de Rayleigh

On peut évaluer \(\lambda\) à partir de \(u\) en multipliant l'équation ci-dessus à gauche par \(u^\dual\). On obtient alors :

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

et le rapport de Rayleigh en \(u\) s'en suit :

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

1.7 Invariance

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.

1.8 Matrices triangulaires

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)\) :

\( T =

\begin{Matrix}{cc} T^{(n-1)} & z \\ 0 & \lambda_n \end{Matrix}

\)

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

\( T(n-1) =

\begin{Matrix}{ccc} \lambda_1 & \hdots & \hdots \\ 0 & \ddots & \hdots \\ 0 & 0 & \lambda_{n-1} \\ \end{Matrix}

\)

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 :

\( u =

\begin{Matrix}{c} v \\ \mu \end{Matrix}

\)

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 :

\( A =

\begin{Matrix}{cccc} \lambda_1 - \lambda_n & \hdots & \hdots & \hdots \\ 0 & \ddots & \hdots & \hdots \\ 0 & 0 & \lambda_{n-1} - \lambda_n & \hdots \end{Matrix}

\)

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

\( (T - λn ⋅ I) ⋅ u =

\begin{Matrix}{c} A \\ 0 \end{Matrix}

⋅ u =

\begin{Matrix}{c} A \cdot u \\ 0 \end{Matrix}

= 0 \)

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\).

1.9 Forme de Schur

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 :

\( U1^\dual ⋅ A ⋅ U1 =

\begin{Matrix}{cc} \lambda_1 & \hdots \\ 0 & A^{(n - 1)} \end{Matrix}

\)

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 :

\( U2 =

\begin{Matrix}{cc} 1 & 0 \\ 0 & U^{(n - 1)} \end{Matrix}

\)

On obtient :

\( U2^\dual ⋅ U1^\dual ⋅ A ⋅ U1 ⋅ U2 =

\begin{Matrix}{ccc} \lambda_1 & \hdots & \hdots \\ 0 & \lambda_2 & \hdots \\ 0 & 0 & A^{(n - 2)} \end{Matrix}

\)

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

\( Uk + 1 =

\begin{Matrix}{cc} I_k & 0 \\ 0 & U^{(n-k)} \end{Matrix}

\)

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 :

\( U^\dual ⋅ A ⋅ U = T =

\begin{Matrix}{ccc} \lambda_1 & \hdots & \hdots \\ 0 & \ddots & \hdots \\ 0 & 0 & \lambda_n \end{Matrix}

\)

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)\]

1.9.1 Valeurs propres

La matrice \(T\) étant triangulaire supérieure, ses éléments diagonaux sont des valeurs propres de \(T\). Par invariance sous transformation, on voit aussi que les valeurs propres de :

\[A = U \cdot T \cdot U^\dual = U \cdot T \cdot U^{-1}\]

sont égales aux valeurs propres de \(T\). La décomposition de Schur d'une matrice \(A\) nous permet donc de connaître les valeurs propres en examinant la matrice triangulaire obtenue.

1.9.2 Ordre

Nous allons montrer par récurrence sur la taille de \(A\) que les valeurs propres sont triées par ordre décroissant. Si \(n = 1\), il n'y a rien à montrer. Supposons à présent que le résultat soit vrai pour \(n - 1\). Soit :

\[(R,V) = \schur(A^{(n - 1)})\]

Par l'hypothèse de récurrence, \(R\) contient sur sa diagonale les valeurs propres de \(A^{(n - 1)}\) triées par ordre décroissant :

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

Mais on a aussi :

\(

\begin{Matrix}{cc} 1 & 0 \\ 0 & V^\dual \end{Matrix}

⋅ U1^\dual ⋅ A ⋅ U1

\begin{Matrix}{cc} 1 & 0 \\ 0 & V \end{Matrix}

=

\begin{Matrix}{cc} \lambda_1 & \hdots \\ 0 & R \end{Matrix}

\)

Les valeurs propres de \(A^{(n - 1)}\) sont donc également les valeurs propres de \(A\). Par construction de l'algorithme, \(\lambda_1\) est la plus grande valeur propre et on a \(\lambda_1 \ge \max\{\lambda_2,...,\lambda_n\}\). On en conclut finalement que :

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

1.10 Algorithme \(Q R\)

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 :

\( \lim_{p \to \infty} \mathcal{U}_p = U \\ \lim_{p \to \infty} R_p = R \)

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.

1.11 Matrices hermitiennes

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}\]

1.12 Théorème de Courant-Fisher

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\]

1.12.1 Propriétés extrémales

Nous allons analyser les extrema du rapport de Rayleigh sur les ensembles :

\begin{align} \mathcal{P}_m &= \combilin{u_1,u_2,...,u_m} \setminus \{0\} \\ \mathcal{Q}_m &= \mathcal{P}_{m - 1}^\orthogonal \setminus \{0\} \end{align}
  • Si \(x \in \mathcal{P}_m\), les seules coordonnées non nulles sont \(a_1,...,a_m\). Il en va donc de même des \(w_i\) et :

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

On voit aussi que :

\begin{align} 1 = \sum_{i = 1}^n w_i &= \sum_{i = 1}^m w_i + \sum_{i = m + 1}^n w_i \\ &= \sum_{i = 1}^m w_i + 0 \\ &= \sum_{i = 1}^m w_i \end{align}

Les valeurs propres étant ordonnées par ordre décroissant, on a donc :

\[R(x) \ge \lambda_m \sum_{i = 1}^m w_i = \lambda_m\]

Cette borne inférieure est atteinte en \(u_m \in \mathcal{P}_m\) :

\[R(u_m) = \lambda_m\]

On en conclut que \(\lambda_m\) est le minimum de \(R\) sur l'espace \(\mathcal{P}_m\) :

\[\lambda_m = \min_{x \in \mathcal{P}_m} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

et que \(u_m\) est solution du problème de minimisation :

\[u_m \in \arg\min_{x \in \mathcal{P}_m} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

  • Si \(x \in \mathcal{Q}_m\), on doit avoir \(\scalaire{z}{x} = 0\) pour tout \(z \in \mathcal{P}_{m - 1}\), et en particulier :

\[a_k = \scalaire{u_k}{x} = 0\]

pour tout \(k \in \{1, ..., m - 1\}\). Les \(m - 1\) premières coordonnées sont nulles. Les \(m - 1\) premiers \(w_i\) le sont donc aussi et :

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

La somme des \(w_i\) se simplifie alors en :

\[\sum_{i = m}^n w_i = 1\]

Les valeurs propres étant ordonnées par ordre décroissant, on a donc :

\[R(x) \le \lambda_m \sum_{i = m}^n w_i = \lambda_m\]

Cette borne supérieure est atteinte en \(u_m \in \mathcal{Q}_m\) :

\[R(u_m) = \lambda_m\]

On en conclut que \(\lambda_m\) est le maximum de \(R\) sur l'espace \(\mathcal{Q}_m\) :

\[\lambda_m = \max_{x \in \mathcal{Q}_m} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

et que \(u_m\) est solution du problème de maximisation :

\[u_m \in \arg\max_{x \in \mathcal{Q}_m} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

1.12.2 Minimax

Soit \(m \in \setN\) et la collection d'espaces vectoriels de dimension \(m\) générés par des bases orthonormées :

\[\mathcal{D}_m = \{ \combilin{v_1,...,v_m} : v_i \in \setC^n, \ \scalaire{v_i}{v_j} = \delta_{ij} \text{ pour tout } i,j \in \{1,...,m\} \}\]

On définit des collections associées par :

\begin{align} \mathcal{V}_m &= \{ X \setminus \{0\} : X \in \mathcal{D}_m \} \\ \mathcal{W}_m &= \{ X^\orthogonal \setminus \{0\} : X \in \mathcal{D}_{m - 1} \} \end{align}
  • Soit \(X \in \mathcal{V}_m\) et la suite \((v_1,...,v_m)\) formant une base orthonormée de \(X\). Il est équivalent d'imposer la contrainte \(x \in X \cap \mathcal{Q}_m\), ou d'imposer simultanément que \(x \ne 0\) s'écrive :

\[x = \sum_{j = 1}^m a_j \cdot v_j\]

et que \(x\) soit orthogonal à \(u_1,...,u_{m - 1}\) :

\[\scalaire{u_i}{x} = \sum_{j = 1}^m \scalaire{u_i}{v_j} \cdot a_j = 0\]

pour tout \(i \in \{1,...,m - 1\}\). Soit la matrice \(C \in \matrice(\setC, m - 1, m)\) de composantes :

\[\composante_{ij} C = \scalaire{u_i}{v_j}\]

et le vecteur \(a = [a_1 \ ... \ a_m]^\dual\). On doit alors avoir \(C \cdot a = 0\). Cette matrice étant strictement longue, il existe une infinité de solution dans l'espace :

\[S = \{ a \in \setC^m : C \cdot a = 0 \}\]

On peut donc choisir \(a \ne 0\) dans \(S\) correspondant à un \(x \ne 0\) appartenant à \(X \cap \mathcal{Q}_m\). On a alors :

\[\min_{z \in X} R(z) \le R(x) \le \max_{z \in \mathcal{Q}_m} R(z) = \lambda_m\]

L'espace \(X\) produit donc un minimum inférieur ou égal à \(\lambda_m\). Le cas particulier \(X = \mathcal{P}_m \in \mathcal{V}_m\) atteignant la borne, on en déduit que :

\[\lambda_m = \max_{X \in \mathcal{V}_m} \min_{x \in X} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

  • Soit \(Y \in \mathcal{W}_m\). On peut alors trouver un \(X \in \mathcal{D}_{m - 1}\) tel que \(Y = X^\orthogonal \setminus \{0\}\). Soit la suite \((v_1,...,v_{m - 1})\) formant une base orthonormée de \(X\). Il est équivalent d'imposer la contrainte \(x \in Y \cap \mathcal{P}_m\), ou d'imposer simultanément que \(x \ne 0\) s'écrive :

\[x = \sum_{j = 1}^m a_j \cdot u_j\]

et que \(x\) soit orthogonal à \(v_1,...,v_{m - 1}\) :

\[\scalaire{v_i}{x} = \sum_{j = 1}^m \scalaire{v_i}{u_j} \cdot a_j = 0\]

pour tout \(i \in \{1,...,m - 1\}\). Soit la matrice \(C \in \matrice(\setC, m - 1, m)\) de composantes :

\[\composante_{ij} C = \scalaire{v_i}{u_j}\]

et le vecteur \(a = [a_1 \ ... \ a_m]^\dual\). On doit alors avoir \(C \cdot a = 0\). Cette matrice étant strictement longue, il existe une infinité de solution dans l'espace :

\[S = \{ a \in \setC^m : C \cdot a = 0 \}\]

On peut donc choisir \(a \ne 0\) dans \(S\) correspondant à un \(x \ne 0\) appartenant à \(Y \cap \mathcal{P}_m\). On a alors :

\[\lambda_m = \min_{z \in \mathcal{P}_m} R(z) \le R(x) \le \max_{z \in Y} R(z)\]

L'espace \(Y\) produit donc un maximum supérieur ou égal à \(\lambda_m\). Le cas particulier \(Y = \mathcal{Q}_m \in \mathcal{V}_m\) atteignant la borne, on en déduit que :

\[\lambda_m = \min_{Y \in \mathcal{W}_m} \max_{x \in Y} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

1.12.3 Remarque

Si les valeurs propres étaient ordonnées par ordre croissant :

\[\lambda_1 \le \lambda_2 \le \lambda_3 \le ...\]

on aurait bien entendu :

\[\lambda_m = \min_{X \in \mathcal{V}_m} \max_{x \in X} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x} = \max_{Y \in \mathcal{W}_m} \min_{x \in Y} \frac{x^\dual \cdot A \cdot x}{x^\dual \cdot x}\]

1.12.4 Résolution numérique

Les propriétés extrémales nous offrent un moyen d'obtenir numériquement des approximations des valeurs et vecteurs propres d'une matrice hermitienne.

1.12.4.1 Valeur propre maximale

Nous allons nous servir d'un algorithme d'optimisation pour obtenir le maximum \(\lambda_1\) de \(R\) sur \(\mathcal{Q}_1 = \setR^n\). A titre d'exemple, nous choisissons « la plus grande montée », qui n'est rien d'autre que l'opposé de la plus grande descente. On part d'un vecteur \(x \ne 0\) et on considère l'itération \(k\) :

\[x_{k + 1} = x_k + \alpha_k \cdot \delta_k\]

où \(\alpha_k \in \setR\) et \(\delta_k \in \setR^n\). Soit \(J_k = (\partial R(x_k))^\dual\) et le développement :

\[R(x_{k + 1}) \approx R(x_k) + \alpha_k \cdot J_k^\dual \cdot \delta_k\]

On a vu que pour maximiser \(J_k^\dual \cdot \delta_k = \scalaire{J_k}{\delta_k}\) sur \(\boule(0,\norme{J_k})\), il suffit de choisir \(\delta_k = J_k\). On pose donc :

\[x_{k + 1} = x_k + \alpha_k \cdot J_k\]

Si \(H_k = \partial^2 R(x_k)\), la valeur optimale de \(\alpha_k\) s'écrit :

\[\alpha_k = \frac{J_k^\dual \cdot J_k}{J_k^\dual \cdot H_k \cdot J_k}\]

On peut aussi utiliser un autre algorithme de minimisation libre pour construire une suite \(x_k\) dont on espère que \(\lim_{k \to \infty} x_k = u_1\) et \(\lim_{k \to \infty} R(x_k) = \lambda_1\).

1.12.4.2 Autres valeurs propres

Supposons que l'on ait déjà obtenu une bonne approximation de \((\lambda_1,...,\lambda_{m - 1})\) et de \((u_1,...,u_{m - 1})\). Si on veut que \(x \in \mathcal{Q}_m\), il faut et il suffit d'imposer que :

\[\scalaire{u_1}{x} = ... = \scalaire{u_{m - 1}}{x} = 0\]

On est donc amenés à construire le complémentaire orthogonal \((v_m,...,v_n)\) de \((u_1,...,u_{m - 1})\) et à poser :

\[V = [v_m \ v_{m + 1} \ ... \ v_n]\]

On a alors \(\combilin{v_m,...,v_n} = \mathcal{Q}_m\). Pour tout \(x \in \mathcal{Q}_m\), on peut donc trouver \(z = [z_m \ ... \ z_n]^\dual \in \setR^{n - m + 1}\) tel que :

\[x = \sum_{i = m}^n z_i \cdot v_i = V \cdot z\]

On pose donc :

\[\varrho(z) = R(V \cdot z) = \frac{z^\dual \cdot V^\dual \cdot A \cdot V \cdot z}{z^\dual \cdot V^\dual \cdot V \cdot z}\]

Par orthonormalité, on a \(V^\dual \cdot V = I\). On est donc finalement amené à maximiser :

\[\varrho(z) = \frac{z^\dual \cdot V^\dual \cdot A \cdot V \cdot z}{z^\dual \cdot z}\]

sur \(\setR^{n - m + 1}\). Pour cela, on part de \(z_0 \ne 0\) et on itère :

\[z_{k + 1} = z_k + \alpha_k \cdot \partial \varrho(z_k)\]

où :

\[\alpha_k = \frac{\partial \varrho(z_k)^\dual \cdot \partial \varrho(z_k)}{\partial \varrho(z_k)^\dual \cdot \partial^2 \varrho(z_k) \cdot \partial \varrho(z_k)}\]

Auteur: chimay

Created: 2019-10-01 mar 12:32

Validate