\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{hyperref}
\usepackage{amscd}
\usepackage{amsthm}
\usepackage[frenchb]{babel}
\usepackage{fontenc}
\usepackage[pdftex]{graphicx}
\usepackage{xcolor}
\usepackage{fullpage}
\usepackage{mathrsfs}
\usepackage{dsfont}
\newtheorem*{thm}{Théorème}
\newcommand{\scal}[2]{\left\langle #1 , #2 \right \rangle}
\newcommand{\cond}{\operatorname{Cond}}
\newtheorem*{lem}{Lemme}
\date{}
\title{Méthode du gradient à pas optimal}
\begin{document}
 \maketitle
Ce développement est extrait du \emph{Cours de mathématiques pures et appliquées, volume 1} de Ramis, Warusfel et Moulin. La preuve de l'inégalité de Kantorovitch se trouve dans les oraux X-ENS. \\
Soit $A$ une matrice symétrique définie positive. On utilise sans démonstration le résultat suivant : $\overline x$ est la solution du système $Ax=b$ si et seulement s'il minimise la fonction $f: x \mapsto \frac{1}{2} \scal{Ax}{x}-\scal{b}{x}$. Il s'agit d'appliquer l'algorithme de minimisation du gradient à pas optimal à la fonction $f$ : on construit la suite $(x_n)$ en posant 
$$x_{n+1}=x_n+\alpha_{n+1} r_n$$ où $r_n=-\nabla f(x_n)=b-Ax_n$ (direction de plus grande pente) et $\alpha_{n+1}$ est le pas optimal, c'est-à-dire que
$$f(x_n+\alpha_{n+1}r_n)=\min_{\alpha > 0} f(x_n+\alpha r_n).$$ On vérifie que $\alpha_{n+1}=\frac{\Vert r_n \Vert^2}{\scal{Ar_n}{r_n}},$ défini tant que $x_n \neq \overline x$. \\
On rappelle l'algorithme : \\
\begin{center}
\begin{minipage}{0.7\textwidth}
Soit $x_0$ donné et $r_0=b-Ax_0$. On se fixe un seuil de tolérance $TOL$. \\
Tant que $\frac{\Vert r_n\Vert}{\Vert r_0 \Vert} \geqslant TOL$, faire \\
\begin{align}
 \alpha_{n+1} = \frac{\Vert r_n\Vert^2}{\scal{Ar_n}{r_n}} \\
 x_{n+1}=x_n+\alpha_{n+1} r_n \\
 r_{n+1}=b-Ax_{n+1}.
\end{align}

\end{minipage}
\end{center}
\begin{thm}
 L'algorithme du gradient converge vers la solution $\overline x$ du système $Ax=b$ et, pour tout $n \in \mathbb N$
$$\Vert x_n - \overline x \Vert \leqslant \left( \frac{\cond(A)-1}{\cond(A)+1}\right)^n \sqrt{\cond(A)} \Vert x_0-\overline x\Vert.$$
\end{thm}
\begin{proof}
 \begin{lem}{Inégalité de Kantorovitch}
Soit $A \in \mathcal M_N(\mathbb R)$ symétique définie positive, de valeurs propres minimale et maximale $\lambda_m$ et $\lambda_M$. Alors
$$\forall x \in \mathbb R, \quad \frac{\Vert x \Vert^4}{\Vert x \Vert_{A^{-1}}^2 \Vert x \Vert_A^2}\geqslant 4\frac{\lambda_m \lambda_M}{(\lambda_M+\lambda_m)^2}$$
où $\Vert x \Vert_A=\sqrt{\scal{Ax}{x}}$.
 \end{lem}
\begin{proof}
Il suffit de montrer cette inégalité pour $x$ de norme 1, ce qu'on supposera dans la suite. $A$ est symétrique donc il existe une base $(e_1,\cdots,e_n)$ orthonormale de vecteurs propres de $A$. On note $x=\sum x_i e_i$ et $0<\lambda_1 \leqslant \cdots \leqslant \lambda_n$ les valeurs propres de $A$.
\begin{align*}
 \scal{Ax}{x} \scal{A^{-1}x}{x} &= \sum_{i=1}^n \lambda_i x_i^2 \sum_{i=1}^n \frac{1}{\lambda_i} x_i^2  
= \frac{\lambda_1}{\lambda_n} \sum_{i=1}^n \frac{\lambda_i}{\lambda_n} x_i^2 \sum_{i=1}^n \frac{\lambda_1}{\lambda_i} x_i^2  \\ & \leqslant \frac{\lambda_1}{4\lambda_n} \left( \sum_{i=1}^n \left( \frac{\lambda_i}{\lambda_n}+\frac{\lambda_1}{\lambda_i} \right) x_i^2 \right)^2.
\end{align*}
Après étude de la fonction $x \mapsto x+\frac{1}{x}$ qui atteint son maximum $1+\frac{\lambda_n}{\lambda_1}$ en $\lambda_1$ et en $\lambda_n$, on en déduit que
$$\scal{Ax}{x} \scal{A^{-1}x}{x} \leqslant \frac{\lambda_1}{4\lambda_n}   \left( \left( 1+\frac{\lambda_n}{\lambda_1} \right) \sum_{i=1}^n x_i^2 \right)^2
=\leqslant \frac{\lambda_1}{4\lambda_n}   \left( 1+\frac{\lambda_n}{\lambda_1} \right)^2=\frac{(\lambda_1+\lambda_n)^2}{4\lambda_1\lambda_n}.$$
Il suffit d'inverser cette formule pour obtenir l'inégalité escomptée.

\end{proof}
Pour la preuve générale, remarquons que 
$$f(x)=\frac{1}{2}\scal{Ax}{x}-\scal{b}{x}=\frac{1}{2}\scal{Ax}{x}-\scal{A\overline x}{x} = \frac{1}{2}\scal{A(x-\overline x)}{x-\overline x} - \frac{1}{2}\scal{A\overline x}{\overline x},$$
c'est-à-dire $f(x)=\frac{1}{2} \Vert x-\overline x \Vert_A - \frac{1}{2}\scal{A\overline x}{\overline x}$. L'algorithme garantit la décroissance de $f$ à chaque itération. Reste à voir qu'on a en fait une contractance de $f$ :
\begin{align}
 \frac{\Vert x_{n+1}-\overline x\Vert_A^2}{\Vert x_n-\overline x \Vert_A^2} & =\frac{\Vert x_{n}+\alpha_{n+1}r_n-\overline x\Vert_A^2}{\Vert x_n-\overline x \Vert_A^2} = \frac{\Vert x_{n}-\overline x\Vert_A^2+ \alpha_{n+1}^2\Vert r_n \Vert_A^2+2\scal{A(x_n-\overline x)}{\alpha_{n+1} r_n}}{\Vert x_n-\overline x \Vert_A^2} \\
&=1+ \frac{\Vert r_n \Vert ^4/\Vert r_n \Vert_A^2+2\alpha_{n+1} \scal{Ax_n-b}{ b-Ax_n}}{\Vert x_n-\overline x \Vert_A^2} \\
&= 1 - \frac{\Vert r_n \Vert ^4/\Vert r_n \Vert_A^2}{\Vert x_n-\overline x \Vert_A^2} = 1 - \frac{\Vert r_n \Vert ^4}{\Vert r_n \Vert_A^2 \Vert A^{-1}r_n \Vert_A^2} = 1 - \frac{\Vert r_n \Vert ^4}{\scal{Ar_n}{r_n}\scal{A^{-1}r_n}{r_n}}.
\end{align}
On peut alors appliquer l'inégalité de Kantorovitch qui donne
\begin{align}
\Vert x_{n+1}-\overline x\Vert_A^2 & \leqslant \left( 1-  4 \frac{\lambda_1 \lambda_n}{(\lambda_1+\lambda_n)^2} \right)\Vert x_n-\overline x \Vert_A^2 \\
& \leqslant \left( \frac{\lambda_1-\lambda_n}{\lambda_1+\lambda_n}\right)^2 \Vert x_n-\overline x \Vert_A^2. \\
& \leqslant \left( \frac{1-\cond(A)}{1+\cond(A)}\right)^2 \Vert x_n-\overline x \Vert_A^2. 
\end{align}
Ceci montre la convergence linéaire de $(x_n)$ vers $\overline x$ pour $\Vert \cdot \Vert_A$. \\
Or, pour tout $x$, $\leqslant \lambda_1 \Vert x \Vert^2 \scal{Ax}{x} = \Vert x \Vert_A^2 \leqslant \lambda_n \Vert x \Vert^2$, c'est-à-dire
$$\Vert x_n-\overline x \Vert \leqslant \left( \frac{1-\cond(A)}{1+\cond(A)}\right)^n \sqrt{\lambda_n/\lambda_1}\Vert x_0-\overline x \Vert=\left( \frac{1-\cond(A)}{1+\cond(A)}\right)^n \sqrt{\cond(A)}\Vert x_0-\overline x \Vert,$$ ce qu'il fallait montrer.
\end{proof}

\end{document}