\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 Intro. mod. num\'erique \hfill Syst\`emes, conditionnement \hfill {L3 2016}\\

\bexer Appliquer la m\'ethode de Gauss pour r\'esoudre le syst\`eme
$Ax=b$ o\`u
$$
A=\left(
  \begin{array}{cc}
    \varepsilon & 1\\
    1 & 1
  \end{array}
\right)
\qquad 
b=\left(
  \begin{array}{l} 
    1 \\ 
    2 
  \end{array}
\right)
$$
\begin{enumerate}
\item
Cette m\'ethode para\^it-elle judicieuse quand $\varepsilon$ est
petit?
Que se passe-t-il si l'on effectue cette m\'ethode avec une machine qui
travaille avec une pr\'ecision de $\varepsilon$? 
\item Comparer avec
le syst\`eme obtenu en intervertissant les deux \'equations du syst\`eme.
\end{enumerate}
\eexer

\bexer Soit
$$A=\left(\begin{array}{cc} 1&4\\
    -1&2 \end{array}\right)~~~~B=\left(\begin{array}{ccc} -2& 3&0\\
    1&0&-4\\ 2&0&5 \end{array}\right)~.$$
\begin{enumerate}
\item D\'etailler \'etape par \'etape le calcul de la d\'ecomposition
  $LU$ des matrices $A$ et $B$
\item
Calculer le d\'eterminant de $B$ \`a l'aide de cette d\'ecomposition.
\item R\'esoudre $Bx=(1,2,3)$ en utilisant la d\'ecomposition $LU$.
\item Calculer l'inverse de $B$ en r\'esolvant 3 syst\`emes lin\'eaires avec
la d\'ecomposition $LU$.
\end{enumerate}
\eexer

\bexer 
Soit $\alpha$ un param\`etre r\'eel.
On consid\`ere la matrice 
$$
A(\alpha)=
\left(
\begin{array}{ccc}
 \alpha & 1 \\
1&2 
\end{array}
\right)
.$$
\begin{enumerate}
\item Pour quels $\alpha$ la matrice $A(\alpha)$ admet-elle une
  factorisation $LU$? 
\item D\'eterminer la factorisation $LU$ de $A(1)$ \`a l'aide de la commande Xcas \texttt{lu}.
Interpr\'eter le r\'esultat de la commande \texttt{lu}
  appliqu\'ee \`a $A(0)$.
\end{enumerate}
\eexer

\bexer 
\begin{enumerate}
\item Entrer une matrice al\'eatoire $A$ de taille 5x5 et un vecteur al\'eatoire $b$ de taille 5x1
 (pr\'eciser la loi des coefficients de $A$ et $b$, commandes
 \verb|ranm| et \verb|ranv|) 
\item Calculer le carr\'e de A. 
Calculer aussi le produit de Hadamard de $A$ avec $A$, 
c'est \`a dire la matrice dont le coefficient $(i,j)$ est $A_{i,j}^2$.
\item Inverser num\'eriquement $A$. 
\item Trouver et ex\'ecuter la commande Xcas pour r\'esoudre le syst\`eme lin\'eaire $Ax=b$. On notera $c$ le r\'esultat num\'erique. 
\item Calculer la norme $L_2$ de $\|Ac-b\|$. 
\end{enumerate}
\eexer

\bexer 
Mesurer le temps de calcul par Xcas de la factorisation LU d'une
matrice al\'eatoire \`a coefficients approch\'es 10x10, 100x100, 200 x 200, etc.... 
Comparer avec le r\'esultat th\'eorique du cours. 
\eexer

% \bexer L'exercice pr\'ec\'edent sugg\`ere la strat\'egie suivante
% (appel\'ee m\'ethode de Gauss avec pivot partiel): \`a l'\'etape $k$,
% avant d'introduire des z\'eros sous la diagonale dans la $k$-\`eme
% colonne, on commence par intervertir la $k$-\`eme ligne avec une ligne
% d'indice $l\geq k$, de fa\c{c}on \`{a} utiliser un pivot le plus grand
% possible en valeur absolue.

% Le but de cet exercice est de donner une interpr\'etation matricielle
% de la m\'ethode de Gauss avec pivot partiel. On notera $e_1,\dots,e_n$
% la base standard de $\Com^n$. Une matrice de permutation est par
% d\'efinition la matrice d'une transformation lin\'eaire qui permute
% ces $n$ vecteurs.
% \begin{enumerate}
% \item Montrer que chaque \'etape revient \`a multiplier \`a gauche par
%   $L^{(k)}P^{k}$, o\`u $P^{(k)}$ est une matrice de permutation qui
%   correspond \`a \'echanger $e_k$ avec $e_l$, pour un $l\geq k$, et
%   $L^{(k)}=I-B^{(k)}$ avec $B^{(k)}$ une matrice $n\times n$ qui est nulle sauf
% \'eventuellement dans la $k$-\`eme colonne, strictement sous la
% diagonale. En d'autres termes, $B^{(k)}_{ij}=0$ si $j\neq k$ ou si
% $i\leq j$.
% \item Montrer qu'avec les notations du point pr\'ec\'edent, on a pour
%   $l>k$
% $$
% P^{(l)}L^{(k)} = \tilde{L}^{(k)} P^{(l)}
% $$
% o\`u $\tilde{L}^{(k)}$ est obtenue \`a partir de $L^{(k)}$ en
% interchangeant deux \'el\'ements sous la diagonale.
% \item En d\'eduire que pour toute matrice inversible $A$, il existe une
%   matrice de permutation $P$, une matrice triangulaire inf\'erieure
%   \`a diagonale unit\'e $L$ et une matrice triangulaire sup\'erieure
%   $U$ telles que $A=PLU$. Cette \'ecriture est-elle unique?
% \end{enumerate}


% \bexer Dans cet exercice, on fixe $n\in\Nm^*$ et, pour $1\leq k
% \leq n$ on note $B^{(k)}$ une matrice $n\times n$ qui est nulle sauf
% \'eventuellement dans la $k$-\`eme colonne, strictement sous la
% diagonale. En d'autres termes, $B^{(k)}_{ij}=0$ si $j\neq k$ ou si
% $i\leq j$.
% 
% \begin{enumerate}
% \item D\'ecrire l'effet sur un matrice $A\in M_n(\Com)$ de la
%   multiplication \`a gauche par $(I-B^{(k)})$, et expliquer le lien
%   avec la m\'ethode de Gauss et la factorisation $LU$.
% \item Montrer que $B^{(k)}B^{(l)}=0$ si $k\leq l$.
% \item Montrer que $I-B^{(k)}$ est inversible, et que $(I-B^{(k)})^{-1}
%   = I+B^{(k)}$.
% \item Montrer que $(I+B^{(k)})(I+B^{(l)})=I+B^{(k)}+B^{(l)}$ si $k\leq
%   l$. Interpr\'eter ceci en termes de la factorisation $LU$.
% \end{enumerate}



%\bexer Soit $A\in M_n(\Com)$ une matrice hermitienne d\'efinie
%positive. Montrer que $A$ admet une unique d\'ecomposition $LU$.

%Indication: On pourra montrer que $A$ ainsi que toutes les
%sous-matrices principales $(A_{ij})_{1\leq i,j\leq k}$, $k=1,\dots, n$
%sont inversibles.



\bexer Donner l'ordre de grandeur du nombre d'op\'erations
n\'ecessaires pour calculer le d\'eterminant et l'inverse d'une
matrice A de taille $n\times n$ gr\^ace aux formules
$$\det(A)=\sum_{\sigma\in\Sigma_n}  \varepsilon(\sigma) a_{1\sigma(1)}a_{2\sigma(2)}...a_{n\sigma(n)}~~\text{ et }~~A^{-1}=\frac 1{\det(A)}~^t\text{com}(A)~.$$
M\^eme question mais en utilisant la d\'ecomposition $A=LU$ (m\'ethode de Gauss).\\
Un ordinateur standard effectue de l'ordre de $10^{10}$ op\'erations
par secondes (10 gigaflops). Comparer les temps n\'ecessaires dans le
cas d'une matrice $100\times 100$.
\eexer


\bexer Calculer le d\'eterminant de la matrice de Hilbert de taille 50 puis 100
de mani\`ere num\'erique et de mani\`ere exacte. Comparer les
r\'esultats et temps de calcul.\\
Pour quelques matrices $M$ al\'eatoires de taille 100, 200, 300, calculez le
d\'eterminant de $M$, comparez avec la borne de Hadamard de $M$
(produit des normes des vecteurs colonnes). Qu'observe-t-on~? 
\eexer

% La librairie d'alg\`ebre lin\'eaire num\'erique LAPACK ne propose aucune
% instruction pour calculer le d\'eterminant d'une matrice...
%(cf. \verb|http://www.netlib.org/lapack/lug/node72.html|)

%\bexer {\bf D\'ecomposition QR.}\\
%On munit $\Com^n$ du produit hermitien canonique $<x|y>=\sum x_i \overline y_i$.\\
%1) Soient $a_1,...,a_n$ des vecteurs formant une base de
%$\Com^n$. Montrer qu'il existe une base orthonorm\'ee $q_1,...,q_n$ et
%des nombres complexes $r_{ij}$ ($i\leq j$) tels que $r_{ii}$ est un
%r\'eel positif pour tout $i$ et
%$$\left\{\begin{array}{l}a_1=r_{11}q_1\\ a_2=r_{12}q_1+r_{22}q_2\\ ~~\vdots\\ a_n=r_{1n}q_1+\hdots+r_{nn}q_n \end{array}\right. $$ 
%2) En d\'eduire que toute matrice inversible $A$ peut s'\'ecrire $A=QR$ o\`u $Q$ est unitaire et $R$ est triangulaire sup\'erieure \`a \'el\'ements diagonaux r\'eels et positifs et que cette d\'ecomposition est unique.\\
%3) Comment utiliser cette d\'ecomposition pour r\'esoudre facilement le syst\`eme $Ax=b$ ?\\
%4) Soit $A\in GL_n(\Com)$, montrer que $^t\overline A A$ est
%hermitienne d\'efinie positive. Quel est le lien entre la
%d\'ecomposition de Choleski et la d\'ecomposition $QR$ ?

\bexer {\bf D\'ecomposition de Cholesky.}\\
Soit $A$ une matrice hermitienne d\'efinie positive. Il existe une unique matrice triangulaire sup\'erieure $C$ qui a des \'el\'ements diagonaux strictement positifs telle que $A=C^*C$ (d\'ecomposition de Cholesky).\\
1) Donner l'algorithme qui permet de calculer $C$. L'appliquer \`a la
matrice
$$A= \left(\begin{array}{ccc} 1& 2&1\\ 2&13&-1\\ 1&-1&3 \end{array}\right)~.$$
Cet algorithme est-il appliquable \`a des matrices non hermitiennes ?\\
2) Expliquer comment utiliser la d\'ecomposition de Cholesky pour r\'esoudre le syst\`eme $Ax=b$ et donner le nombre d'op\'erations.\\
3) Une matrice $A=(a_{ij})$ est appel\'ee $p-$bande si $a_{ij}=0$ d\`es que $|i-j|\geq p$.\\
$~~~~$a) Donner des exemples de matrices $p-$bandes.\\
$~~~~$b) Montrer que si $A$ est une matrice hermitienne d\'efinie positive $p-$bande, alors $C$ est\\ $~~~~~~~$aussi $p-$bande.

Pour $p=1$, compter le nombre d'op\'erations n\'ecessaires pour trouver $C$.
\eexer

%\bigskip

% \bexer {\bf D\'ecomposition QR}
% On munit $\Com^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 Cholesky 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 \Com^n$ le k-i\`eme vecteur colonne de $Q$ (resp. $A_k\in \Com^n$ le k-i\`eme vecteur colonne de $A$).
% Montrer que $Q_k$ appartient au sous espace vectoriel de $\Com^n$ engendr\'e par  $\{ A_1, \ldots, A_k \}$. \\
% 3) Montrer que $(Q_1, \ldots, Q_n)$ est l'unique base de $\Com^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 $\Com^n$ engendr\'e par  $\{ A_1, \ldots, A_k \}$,
% \item $\langle Q_k,A_k\rangle\in \Rm^{+*}$.
% \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.



% \bexer Ecrire un programme donnant la d\'ecomposition $QR$ d'une
% matrice. Le transformer en un programme calculant l'inverse d'une
% matrice.
%\eexer

\bexer Ecrire un programme calculant l'inverse d'une matrice en
utilisant l'une des d\'ecompositions.
\eexer


\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~: on a 
$$ \Delta x=A^{-1}(\Delta A (x+\Delta x)+\Delta b)$$
\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$.
 C'est pour cette raison que l'on utilise des
  matrices unitaires dans des algorithmes it\'eratifs, on garantit
  ainsi la stabilit\'e num\'erique.
\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) .
$$
\begin{enumerate}
\item Calculer la solution exacte $x$ du syst\`eme. 
Quelle diff\'erence y-a-t-il entre 
\verb|linsolve(A,b)| et $\texttt{inv}(A)*b$? 

\item 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 \left( \frac{|||\Delta A|||_2}{|||A |||_2} \right)^{-1} 
$$
et de m\^eme en \'echangeant le r\^ole de $x$ et $y$ et de $A$ et $A+\Delta A$.
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 {\tt l2norm()} pour un vecteur
et avec {\tt matrix\_norm()} pour une matrice.
\item
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 \left( \frac{\|\Delta b\|_2}{\| b \|_2} \right)^{-1} 
$$
Que remarquez vous? On pourra calculer la solution exacte du syst\`eme
perturb\'e pour \'eliminer tout risque d'erreur d'arrondi.
\item Faire la r\'esolution du syst\`eme approch\'e en utilisant la
d\'ecomposition $QR$ de $A$.
\item
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)\]
 \item
 Calculer les valeurs propres de $A$ avec la commande $\texttt{egvl}$.
Calculer le rapport $\lambda_{max}/\lambda_{min}$ des valeurs propres de 
$A$.
\item Montrer que le conditionnement d'une matrice normale est le rapport 
entre sa plus grande et sa plus petite valeur propre (en valeur absolue).
\item Refaire les calculs ci-dessus avec une autre norme, par exemple
  $L^1$.
\end{enumerate}
\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

\bexer
M\'ethode $QR$ et Cholesky. Soit $A=QR$ est la d\'ecomposition $QR$ de
$A$ o\`u $R$ est normalis\'e pour avoir tous ses coefficients
diagonaux positifs. Calculer $A^*A$, en d\'eduire sa d\'ecomposition
de Cholesky. Appliquer ce r\'esultat pour d\'eterminer la
d\'ecomposition $QR$ de la matrice
$$A=\left(\begin{array}{cc} 1001&1000\\1000&1001\end{array}\right)~.$$
en prenant $A$ \`a coefficients flottants, puis calculer
$QQ^*$. Comparer avec la m\'ethode de Givens. Conclusion~?
\eexer

\end{document}

\pagebreak

\noindent M\'ethodes num\'eriques \hfill Devoir pour le 27/2 
\hfill {L3 2014/2015}\\

\bexer (CC mars 2014)\\
On travaille en arithm\'etique flottante avec 14 chiffres significatifs.
On s'int\'eresse au calcul des solutions
de l'\'equation du second degr\'e 
$ax^2+bx+c=0$ \`a coefficients r\'eels, 
en particulier lorsque $b^2$ est grand devant $|ac|$, 
par exemple pour $x^2+12345678 x+1.0 =0$.
\begin{enumerate}
\item Donner une valeur approch\'ee des deux solutions de l'exemple
en appliquant la formule habituelle $r_\pm= (-b \pm \sqrt{b^2-4ac})/(2a)$ 
et discuter leur erreur relative. 
\item Comparer l'erreur relative pour la solution la moins pr\'ecise avec
l'erreur relative de la valeur approch\'ee obtenue en appliquant la formule 
$r_+ r_-=c/a$.
\item \'Ecrire une fonction
%sur votre copie d'examen une fonction Xcas 
prenant $a,b,c$ en arguments
et renvoyant deux solutions pr\'ecises de l'\'equation
(on distinguera deux cas en fonction du signe de $b$).
\end{enumerate}
\eexer


\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$ (en pratique, on ne
le calcule pas en r\'esolvant ce syst\`eme lin\'eaire mais par
la m\'ethode de la puissance)
\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

%\pagebreak

%\


\end{document}
