\documentclass[11pt,a4paper]{article}
\parindent=0cm
 
   \textheight=23,5cm
   \textwidth=15,7cm
\oddsidemargin=0cm

\usepackage[frenchb]{babel}
\usepackage[utf8]{inputenc}


\usepackage{url,amsmath,amssymb,amsthm,amsfonts,epsfig,eurosym,geometry}
\selectlanguage{french}

\def\var{\mathrm{var}}
\def\BB{\mathcal{B}}
\def\FF{\mathcal{F}}
\def\Pa{\mathcal{P}}
\def\M{\mathcal{M}}
\def\P{\mathcal{P}}
\def\T{\mathcal{T}}
\def\L{\mathcal{L}}

\def\AA{\mathfrak{A}}
\def\S{\mathfrak{S}}
\def\SS{\mathcal{S}}
\def\CC{\mathcal{C}}

\def\A{\mathbb{A}}
\def\B{\mathbb{B}}
\def\D{\mathbb{D}}
\def\U{\mathbb{U}}


\def\bq{\begin{quote}\begin{em}}
\def\eq{\end{em}\end{quote}}

\def\un{\mathbf{1}}
\def\dd{\mathrm{d}}
\def\ee{\mathrm{e}}
\def\ii{\mathrm{i}}
\def\eps{\varepsilon}

\def\hth{\widehat{\theta}}
\def\ovx{\overline{X}}
\def\ima{\mathrm{Im}}

\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}

\newcommand{\espmes }{(\Omega, {\cal F})}
\newcommand{\espprob}{(\Omega, {\cal F}, P)}
\newcommand{\va}{variable al\'eatoire }
\newcommand{\vas}{variables al\'eatoires }
\newcommand{\Vas}{Variables al\'eatoires }
\newcommand{\cov}{\hbox{cov}}
\newtheorem{theo}{Théorème}[section]
\newtheorem{coro}{Corollaire}[section]
\newtheorem{lemm}{Lemme}[section]
\newtheorem{defi}[theo]{Définition}
\newtheorem{prop}[theo]{Proposition}
\newtheorem{rque}[theo]{Remarque}
\newtheorem{exem}[theo]{Exemple}
\newtheorem{exer}[theo]{Exercice}
\def\card{\mathrm{card}\,}

\newcommand{\tran}[1]{\,{}^{t}\!#1}
\renewcommand\det{\mathop{\textrm{d\'et}}}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\def\demi{\frac{1}{2}}
\def\ds{\displaystyle}
\def\btheo{\begin{theo}}\def\etheo{\end{theo}}
\def\bcoro{\begin{coro}}\def\ecoro{\end{coro}}
\def\blemm{\begin{lemm}}\def\elemm{\end{lemm}}
\def\bdefi{\begin{defi}}\def\edefi{\end{defi}}
\def\bprop{\begin{prop}}\def\eprop{\end{prop}}
\def\brque{\begin{rque}}\def\erque{\end{rque}}
\def\bexem{\begin{exem}}\def\eexem{\end{exem}}

\def\bexer{\begin{exer}\begin{em}}\def\eexer{\end{em}\end{exer}}
\usepackage{graphics}
\usepackage{color}              % Need the color package
\usepackage{epsfig}
\def\F{{\cal F}}
\def\1{{\rm 1\kern-.8ex 1}}
\def\euro{\mbox{\raisebox{.25ex}{{\it =}}\hspace{-.5em}{\sf C}}} 
\newcommand{\bin}[2]{\left( \begin{array}{c} 
#1 \\#2\end{array}\right)}

\def\iif{{\bf I}}
\def\eef{{\bf E}}
\newcommand{\Com}{\mathbb{C}}

\begin{document}
\noindent M\'ethodes num\'eriques \hfill Feuille 7~: diagonalisation
\hfill {L3 2014/2015}\\

{\bf Exercice 1 : Domaine de Gershgorin}\\
Soit $A\in {\cal M}_n(\C)$.
On note, pour $1\leq i\leq n$, $D_i$ la boule fermée dans $\C$ de 
centre $a_{i,i}$ et de rayon $\ds\sum_{j\not= i}|a_{i,j}|$.
Le domaine de Gershgorin, qu'on notera ${\cal G}(A)$ est la réunion des 
disques $D_i$ pour $1\leq i\leq n$.
Montrer que le spectre de $A$ est inclus dans ${\cal G}(A)$.

{\bf Exercice 2  (Méthode de la puissance)}\\
Soit $A=\left(\begin{array}{ccc}99&1&0\\1&100&1\\0&1&98\end{array}\right)$.
\begin{enumerate}
 \item Montrer que $A$ est diagonalisable et en utilisant l'exercice 
précédent que ses valeurs propres appartiennent à $[97,102]$.
\item Déterminer par la méthode de la puissance
une approximation de la plus grande valeur propre de $A$.

Pour ceci, on écrira une fonction qui donnera une valeur approchée 
de la plus grande valeur propre, une valeur approchée d'un 
vecteur propre associé et le nombre d'itérations utilisées 
pour ce calcul. La fonction aura comme argument une matrice carrée, 
un nombre d'iterations maximales (pour un test d'arrêt) 
et epsilon mesurant une erreur maximale.

\item Expliquer pourquoi en appliquant la méthode de la puissance à $A-97I_3$, 
on accélere la convergence.


\item Que se passe t-il si on applique la méthode de la puissance à 
$A-\gamma I_3$ si $\gamma$ est la valeur trouvée à la question 2) ?
\end{enumerate}

{\bf Exercice 3  (élimination)}\\
Soit $A$ une matrice réelle de taille $n$.
On suppose que les valeurs propres de $A$ notées $\{\lambda_1,\ldots,\lambda_n\}$ sont deux à deux distinctes et vérifient :
\[|\lambda_1|<|\lambda_2|<\cdots <|\lambda_n|\]
On note $u_i$ un vecteur propre associé à $\lambda_i$, pour $1\leq i\leq n$.
\begin{enumerate}
 \item Montrer que $\{\lambda_1,\ldots,\lambda_n\}$ sont les valeurs 
propres de $\ ^tA$.
On note $v_i$ un vecteur propre de $\ ^tA$ associé à $\lambda_i$, pour $1\leq i\leq n$.
\item Montrer que si $i\not= j$, $\langle u_i,v_j\rangle =0$.
(On pourra calculer $\langle Au_i,v_j\rangle$ de deux manières).\\
Montrer que pour tout $1\leq i\leq n$, $\langle u_i,v_i\rangle\not=0$.

\item Soit $B=A-\lambda_n\frac{u_n\ ^tv_n}{\langle u_n,v_n\rangle}$.
Montrer que les valeurs propres de $B$ sont 
$\{0,\lambda_1,\ldots,\lambda_{n-1}\}$.

\item Donner une méthode utilisant la méthode de la puissance appliquée 
plusieurs fois pour trouver des valeurs approchées des valeurs propres 
de A et de ses vecteurs propres.

L'appliquer à la matrice de l'exercice précédent.
\end{enumerate}

{\bf Exercice 4 (valeurs propres conjuguées)}\\
Si $A$ est une matrice réelle, sa plus grande valeur propre en module n'est
pas forcément réelle, $A$ peut avoir un couple de valeurs propres
complexes conjuguées de module maximal. On peut appliquer la
méthode de la puissance à un shift de $A$ dans le complexe, par
exemple $A-iI$, on peut aussi rester dans le réel en cherchant
une relation de récurrence approchée $u_{n+2}+au_{n+1}+bu_n$
(où $u_{n+1}=Au_n$ et $u_0$ aléatoire). Programmer les deux
méthodes et comparer l'efficacité avec une matrice aléatoire
réelle de taille 4 (non symétrique).

{\bf Exercice 5 (itérations inverses)} \\
Lorsqu'on a effectué quelques itérations de la méthode de la puissance,
on a une première approximation $\lambda$ 
de la valeur propre de module maximal.
Il peut alors être intéressant d'effectuer la méthode de la puissance
sur la matrice $(A-\lambda I)^{-1}$. Programmer cette méthode
et discuter les avantages (vitesse de convergence) et inconvénients
(précision du calcul de l'inverse). Testez sur l'une des matrices
de la feuille.

{\bf Exercice 6}\\
Utiliser la méthode QR pour trouver des valeurs approchées 
des valeurs propres de 
 \[A=\left(\begin{array}{ccccc}
0&1&0&0&0\\1&1&1&0&0\\0&1&1&1&0\\0&0&1&1&1\\0&0&0&1&2
\end{array}\right)\]
Observer la forme des matrices intermédiaires.
Pour une matrice g\'en\'erale, on utilise la forme de Hessenberg avant
de faire la m\'ethode QR.

{\bf Exercice 7}\\
Utiliser la m\'ethode de la puissance pour d\'eterminer la norme
triple d'une matrice subordonn\'ee \`a la norme euclidienne.

{\bf Exercice 8}\\
Soit $P$ un polynôme à coefficients réels ou complexes. 
Appliquer la méthode de la
puissance à la matrice companion de $P$ pour déterminer une estimation
de la plus grande racine de $P$ en module.


\end{document}
