\documentclass[10pt,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}{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)}
\begin{document}

\noindent M\'ethodes num\'eriques \hfill Feuille 3: Conditionnement \hfill {L3 2013/2014}\\


% \bexer{\bf Décomposition QR}
% 
% 
% On munit $\C^n$ du produit scalaire hermitien standard:
% $$ \langle Z,Z'\rangle =\sum_{i=1}^n \bar{Z_i}Z'_i .
% $$
% Soit $A$ une matrice $n\times n$ \`a coefficients complexes inversible. 
% 
% 1) En utilisant la décomposition de Choleski pour la matrice $A^*A$, montrer qu'il existe un unique 
%  couple de matrices $(Q,R)$ tel que $Q$ est unitaire, $R$ triangulaire sup\'erieure à coefficients sur la diagonale strictement positifs et $A=QR$.\\
% 2) Soit $Q_k\in \C^n$ le k-i\`eme vecteur colonne de $Q$ (resp. $A_k\in \C^n$ le k-i\`eme vecteur colonne de $A$).
% Montrer que $Q_k$ appartient au sous espace vectoriel de $\C^n$ engendr\'e par  $\{ A_1, \ldots, A_k \}$. \\
% 3) Montrer que $(Q_1, \ldots, Q_n)$ est l'unique base de $\C^n$ telle que:
% \begin{enumerate}
%  \item $\langle Q_i,Q_j\rangle=\delta_{ij}$,
% \item Pour tout $k$, $Q_k$ appartient au sous espace vectoriel de $\C^n$ engendr\'e par  $\{ A_1, \ldots, A_k \}$,
% \item $\langle Q_k,A_k\rangle\in \R^{+*}$.
% \end{enumerate}
% Ainsi $(Q_1, \ldots, Q_n)$ est l'orthonormalis\'ee de Gram-Schmidt de la base des colonnes de $A$
%  relativement au produit scalaire hermitien standard.\\
% 4) Donner un algorithme pour effectuer la factorisation $QR$ d'une matrice inversible.
% \eexer
% 
% 
% \paragraph{Conditionnement}

Pour r\'esoudre le syst\`eme $Ax=b$, il faut conna\^\i tre $b$. En g\'en\'eral, celui-ci n'est pas connu avec une pr\'ecision infinie car il peut y avoir des erreurs de mesures et car la pr\'ecision des instruments et de l'ordinateur n'est pas infinie. On s'int\'eresse donc \`a l'erreur qui peut \^etre commise sur $x$ \`a cause des impr\'ecisions sur $b$. La valeur pertinente est l'erreur relative $\|\Delta x\|/\|x\|$.

\bexer On souhaite r\'esoudre le syst\`eme lin\'eaire $Ax=b$ avec
$$A=\left(\begin{array}{cc} 1001&1000\\1000&1001\end{array}\right)~.$$
\begin{enumerate}
\item Montrer que $A$ admet une base orthonormale de vecteurs propres dont on donnera les valeurs propres.
\item Expliciter la r\'esolution de l'\'equation $Ax=b$ en fonction des \'el\'ements propres.
\item R\'esoudre le syst\`eme $Ax=b$ avec $b=(1,1)$. On a en fait une
  petite erreur sur $b$ qui est donn\'e par $\Delta b$ avec $\|\Delta
  b\|/\|b\|$ de l'ordre de $0,01$. On a donc une erreur $\Delta x$ sur
  $x$ donn\'ee par $A(x+\Delta x)=b+\Delta b$. Montrer que l'erreur
  relative $\|\Delta x\|/\|x\|$ peut être de l'ordre de 20.
\end{enumerate}
\eexer

\vspace{.2cm}

\bexer On consid\`ere le syst\`eme $Ax=b$ avec $A\in GL_n(\R)$. Les donn\'ees $A$ et $b$ sont impr\'ecises. On a donc en r\'ealit\'e le syst\`eme lin\'eaire
$$(A+\Delta A)(x+\Delta x)=b+\Delta b~.$$
Etant donn\'ee une norme subordonnée (par exemple $L^2$), 
on d\'efinit le conditionnement de la matrice $A$ par
$\kappa(A)=|||A|||.|||A^{-1}|||$.
\begin{enumerate}
\item Montrer que si $\frac{|||\Delta A|||}{|||A|||}< \frac 1 {\kappa(A)}$, on a 
$$\frac {\|\Delta x\|}{\|x\|}\leq
\frac{\kappa(A)}{1-\kappa(A)\frac{|||\Delta A|||}{|||A|||}}
\left(\frac{\|\Delta b\|}{\|b\|}+\frac{|||\Delta A|||}{|||A|||}
\right) $$
Indication~:$(A+\Delta A)^{-1}=(A(I+A^{-1} \Delta A))^{-1}$ et
utiliser le d\'eveloppement en s\'eries enti\`eres de $(1+x)^{-1}$
pour $|x|<1$.
\item Montrer que le conditionnement de $A$ est minor\'e par le rapport $|\lambda_n/\lambda_1|$, o\`u $\lambda_n$ et $\lambda_1$ sont respectivement la plus grande et la plus petite valeur propre en module. Expliquer l'exercice pr\'ec\'edent du point de vue du conditionnement.
\item Montrer que le conditionnement d'une matrice unitaire est $1$
  pour la norme $L^2$.
\end{enumerate}

\eexer


\bexer On cherche \`a r\'esoudre le syst\`eme $Ax=b$ avec 
$$
A=\left(
\begin{array}{cccc}
 10 & 7 & 8 & 7 \\
7 & 5 & 6 & 5 \\
8 & 6 & 10 & 9 \\
7 & 5 & 9 & 10
\end{array}
 \right) \ \ b=\left(
\begin{array}{c}
32\\
23 \\
33 \\
31
\end{array}
 \right) .
$$

1) Calculer la solution exacte du syst\`eme. 
Quelle diff\'erence y-a-t-il entre 
\verb|linsolve(A,b)| et $\texttt{inv}(A)*b$? \\

2) Calculer la solution $y$ du syst\`eme perturb\'e
$(A+\Delta A)y=b$ avec
$$
\Delta A=\left(
\begin{array}{cccc}
 0 & 0 & 0.1 & 0.2 \\
0.08 & 0.04 & 0 & 0 \\
0 & -0.02 & -0.11 & 0 \\
-0.01 & -0.01 & 0 & -0.02
\end{array}
 \right)
$$
On note $\Delta x= y-x$. 
D\'eterminer le coefficient d'amplification d'erreur:
$$\frac{\|\Delta x \|_2}{\| x+\Delta x\|_2}
\times \frac{|||A|||_2}{|||\Delta A |||_2}. 
$$
Dans cette expression la norme $\|u \|_2$ d'un vecteur $u\in\R^n$ 
est d\'efinie par $\|u \|_2^2=\sum_{i=1}^n u_i^2$ et celle d'une 
matrice $A$ correspond \`a celle de l'application lin\'eaire associ\'ee.
Elles se calculent par la commande \textbf{l2norm()} pour un vecteur
et avec {\tt SVL} pour une matrice.\\
3) Calculer la solution du syst\`eme perturb\'e $Az=b+\Delta b$ avec
$$
\Delta b=\left(
\begin{array}{c}
0.01\\
-0.01 \\
0.01 \\
-0.01
\end{array}
 \right) .
$$ 
On note $\Delta x= z-x$. 
D\'eterminer le coefficient d'amplification d'erreur:
$$\frac{\|\Delta x \|_2}{\| x\|_2}
\times \frac{\|b\|_2}{\|\Delta b \|_2}. 
$$


Que remarquez vous?\\
4) Calculer le conditionnement
en norme $\| \ \  \|_2$ de la matrice $A$: $\kappa_2(A)=||| | A ||| |_2 .||||A^{-1}||| |_2$.
Retrouver ce r\'esultat avec la commande $\texttt{COND(.,2)}$. Comparer
conditionnement et erreurs relatives. Montrer que 
\[\frac{\|\Delta x \|_2}{\| x+\Delta x\|_2}
\times \frac{|||A|||_2}{|||\Delta A |||_2}\leq \kappa_2(A)\ \ \mbox{et}\ \ \frac{\|\Delta x \|_2}{\| x\|_2}
\times \frac{\|b\|_2}{\|\Delta b \|_2}\leq \kappa_2(A)\]
 \\
5) Calculer les valeurs propres de $A$ avec la commande $\texttt{egvl}$.
Calculer le rapport $\lambda_{max}/\lambda_{min}$ des valeurs propres de 
$A$.\\
6) Montrer que le conditionnement d'une matrice normale est le rapport 
entre sa plus grande et sa plus petite valeur propre (en valeur absolue).\\
7) Refaire les calculs ci-dessus avec une autre norme, par exemple $L^1$.
\eexer
% \bexer Ecrire un programme donnant la d\'ecomposition $QR$ d'une matrice. Le transformer en un programme calculant l'inverse d'une matrice.
% \eexer

\pagebreak

{\bf Devoir \`a rendre au plus tard le 27/2~:} 
exercice 7 de la feuille 1 (expliquez pourquoi les estimations sont
ou ne sont pas raisonnables) et exercice 4 ci-dessous.
\bexer
Soit $P$ une matrice transpos\'ee d'une matrice stochastique,
c'est-\`a-dire une matrice carr\'ee de taille $N$ dont les coefficients v\'erifient
$$ a_{ij} \in [0,1], \quad \sum_{i=1}^N a_{ij} =1 $$
la somme des coefficients d'une colonne donn\'ee vaut 1.\\
L'algorithme PageRank de Google construit une telle matrice \`a partir
du graphe connectant les pages web entre elles en posant
$a_{ij}=\frac{1}{n_j}$ si la page $j$ pointe vers la page $i$ et 0
sinon, avec $n_j$ le nombre de liens \'emis par la page $j$ (chaque lien
repr\'esente en quelque sorte un vote, dont le poids est pond\'er\'e
par le nombre de liens). Par
exemple
\[ P= \left(\begin{array}{ccccc}
0 & 0 & \frac{1}{4} & 0 & 0 \\
0 & 0 & \frac{1}{4} & 0 & 0 \\
\frac{1}{2} & 1 & 0 & \frac{1}{2} & 0 \\
0 & 0 & \frac{1}{4} & 0 & 0 \\
\frac{1}{2} & 0 & \frac{1}{4} & \frac{1}{2} & 1
\end{array}\right) \]
correspondrait \`a un web jouet de 5 pages
 o\`u la page 1 pointe vers les pages 3
et 5, la page 2 vers la page 3, la page 3 vers 1, 2, 4, 5, 
la page 4
vers les pages 3 et 5 et la page 5 vers elle-m\^eme.

On s'int\'eresse \`a la solution de 
\[ (I-\alpha P) r =\frac1N (1,...,1), \quad \alpha \in ]0,1[ \]
Dans PageRank $\alpha=0.15$ et
$r_j$ donne le rang de classement de la page $j$ (mais on ne
le calcule pas en r\'esolvant cd syst\`eme lin\'eaire)
\begin{enumerate}
\item D\'eterminer la norme de $P$ comme application lin\'eaire
de $\R^N$ dans $\R^N$ subordonn\'ee \`a la norme $L^1$ dans $\R^N$
$$ |||P|||_1 = \mbox{max}_{\{r/\|r\|_1=1\}} \|Pr\|_1, \quad \|r\|_1=\sum_{j=1}^N |r_j| $$
\item En d\'eduire que si $\alpha \in ]0,1[$ alors $I-\alpha P$ est inversible, d'inverse
\[ \sum_{j=0}^\infty \alpha^j P^j \]
%Montrer que~:
%$$ ||| I-\alpha P |||_1 \leq 1+\alpha, \quad ||| (I-\alpha P)^{-1}|||_1 \leq \frac{1}{1-\alpha} $$
Donner une majoration du nombre de condition de $I-\alpha P$.
V\'erifiez avec la matrice donn\'ee en exemple.
\item Que peut-on dire de la pr\'ecision de la solution $r$ renvoy\'ee
en fonction de $\alpha$ (par exemple pour $\alpha=0.15$, pour $\alpha$
proche de 1)~?
\end{enumerate}
\eexer

\end{document}
