\NeedsTeXFormat{LaTeX2e}
\documentclass[10pt,a4paper]{amsart}
\usepackage{amsmath,amsfonts,amssymb,latexsym}
\usepackage{a4,mathptmx,helvet,courier}
\usepackage[francais]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\newcounter{exonum}[section]
\newenvironment{exo}{\begin{enumerate}\stepcounter{exonum}%
\renewcommand{\theenumi}{\thesection.\arabic{exonum}}%
\renewcommand{\labelenumi}{\bf\theenumi.}\item}{\end{enumerate}}

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

\begin{document} 

\pagestyle{empty}
\thispagestyle{empty}

{\footnotesize\noindent
Universit\'e Joseph Fourier, Grenoble I   \hfill $\bullet$ \hfill
L3 M\'ethodes num\'eriques                       \hfill $\bullet$ \hfill
Ann\'ee 2013/2014           \\[-2mm]\hrule}


\begin{center}
%  {\Large\bf Math\'ematique assist\'ees par ordinateur} \\
  Examen du 20 mai 2014, de 13h30 \`a 16h30. \\
  \it Documents, calculatrices et ordinateurs ultraportables
  d\'econnect\'es du r\'eseau autoris\'es.\\
  Ce sujet comporte 2 pages. 
Bar\^eme donn\'e \`a titre indicatif et non contractuel.
\end{center}

\section{Pr\'ecision (3 points)}
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}

\section{M\'ethode de la puissance (7 points)}
On souhaite d\'eterminer la racine $l$  de plus grand module d'un
polyn\^ome $P$. 
Pour cela on applique la m\'ethode
de la puissance \`a la matrice companion de $P$, 
matrice $M$ dont le polyn\^ome
caract\'eristique est $P$ (commande \verb|companion()| en Xcas).
\begin{enumerate}
\item Par exemple pour $P(x)=x^3+3x^2+7x+121$, on a 
$M=\left(\begin{array}{ccc}
0 & 0 & -121 \\
1 & 0 & -7 \\
0 & 1 & -3
\end{array}\right) $.
Prendre un vecteur al\'eatoire $v$ \`a coordonn\'ees dans l'intervalle
$[0,1]$, lui appliquer 29 et 30 fois la matrice, en d\'eduire une estimation $\lambda$
 de  la racine $l$ de $P$ qui est la plus grande en module.
%Donner une majoration de $|l|$.
\item Soit  $A$ une  matrice sym\'etrique r\'eelle de taille $n$.
On suppose qu'on a d\'etermin\'e (par la m\'ethode de la puissance)
un vecteur norm\'e $v$ tel que
$\| (Av-\lambda v\| < \varepsilon$. Soit $(v_1,...,v_n)$
les coordonn\'ees de $v$ dans une base propre orthonormale
de $A$ associ\'ee aux valeurs propres $(\lambda_1,...,\lambda_n)$.
Calculer $\| Av-\lambda v\|$, en d\'eduire que l'une des valeurs
propres au moins v\'erifie $| \lambda_k-\lambda | < \varepsilon$.
\item 
Peut-on appliquer le r\'esultat du (2) \`a $M$ 
pour d\'eterminer un encadrement de $l$~?\\
$P$ est un polyn\^ome, on peut donc en calculant le signe de $P(\lambda-\delta)$
et $P(\lambda+\delta)$ montrer que $P$ admet une racine dans 
$[\lambda-\delta,\lambda+\delta]$. Appliquer une m\'ethode de dichotomie
pour donner un encadrement certifi\'e de la racine correspondante de
$P$ \`a $10^{-8}$ pr\`es.
Proposer une autre m\'ethode qui permettrait d'acc\'el\'erer la convergence vers
cette racine.
\item Le polyn\^ome pourrait avoir un couple $(l_+,l_-)$ de racines complexes conjugu\'ees
de module maximal (c'est-\`a-dire, les autres racines $r_i$ de $P$ v\'erifient $|r_i| < |l_+| =|l_-|$). C'est le cas 
par exemple pour $Q(x)=x^3+4x+116$. On notera
$N$ la matrice companion de $Q$.
Proposer une modification de la matrice $N$ (avec un shift complexe) permettant
de d\'eterminer une estimation d'une des racines de ce couple par
la m\'ethode de la puissance et l'appliquer
(Remarque~: on ne peut plus utiliser d'arguments de signe pour certifier 
un encadrement d'une racine complexe de $Q$, mais on
peut montrer l'existence d'une racine dans un disque du plan complexe
de rayon $|Q/Q'(\lambda))| \times $degre$(Q)$).
% \item m\'ethode des it\'er\'ees inverses pour acc\'el\'erer la
% convergence et discussion sur le conditionnement?
\end{enumerate}


\section{M\'ethode des trap\`ezes et polyn\^omes trigonom\'etriques (6 points)}
\'Etant donn\'e une  fonction continue 
$f : [0,2\pi]\rightarrow \mathbb{R}$,  on note $I(f) = \int_0^{2\pi} f(x) {\rm d} x$
son int\'egrale sur $[0,2\pi]$ et ${\rm Trap}_N (f)$ la valeur approch\'ee de $I(f)$ par la m\'ethode des 
trap\`ezes  avec un pas constant $h=2\pi/N$, o\`u  $N>0$ est un entier. 
\begin{enumerate}
\item
Soit $f$ un polyn\^ome trigonom\'etrique 
de degr\'e inf\'erieur ou \'egal \`a $N-1$, de la forme
%
$$
f(x) = \sum_{k=-N+1}^{N-1} c_k e^{{\rm i} k x}
$$
%
avec $c_k \in \mathbb{C}$, $c_{-k} = \overline{c}_k$, $k=-N+1,\ldots, N-1$.
Montrer que ${\rm Trap}_N (f)$ donne le r\'esultat exact pour l'int\'egrale $I(f)$.
\item On consid\`ere la fonction $g(x) =\exp ( \sin x)$.
En utilisant la question 1 et le d\'eveloppement de l'exponentielle en 0, montrer que
l'erreur $E(g) = |I (g) - {\rm Trap}_N (g)|$ est major\'ee par $c/N!$, o\`u $c$ est une constante que vous d\'eterminerez.
\item
D\'eterminez \`a l'aide de Xcas l'augmentation de la pr\'ecision avec $h$ quand on divise $h$ par deux
(vous pourrez par exemple utiliser votre programme pour la m\'ethode des trap\`ezes r\'ealis\'e en TP).
Comparez cette pr\'ecision avec celles obtenues par les m\'ethodes des rectangles \`a gauche et \`a droite. Pouvez-vous expliquer les similitudes/diff\'erences 
des r\'esultats obtenus par ces trois m\'ethodes ?   
\end{enumerate}

\section{Ordres des m\'ethodes de Runge-Kutta (5 points)}
On consid\`ere une m\'ethode   de Runge-Kutta pour r\'esoudre l'\'equation diff\'erentielle 
$y'(t) = f( y(t), t  )$ sur l'intervalle $[0,1]$, donn\'ee par le tableau de coefficients
%
$$
\begin{array}{lllllll}
c_0=0 &  \vline &       0     &                &          &                 & \\
c_1   & \vline & \lambda_{10} &       0        &          &                 & \\
c_2   & \vline & \lambda_{20} &   \lambda_{21}  &    0      &                 & \\
\vdots & \vline & \vdots     &    \vdots      &   \ddots   & \ddots                 & \\
c_q    &  \vline & \lambda_{q0} & \lambda_{q 1} & \cdots   & \lambda_{q\,q-1} &  0 \\
\hline
1      &  \vline &   \mu_0     &  \mu_1         & \cdots   & \mu_{q-1}       & \mu_q 
\end{array}   
$$
%
On a donc $z_{n+1} = z_n + h \Phi (z_n, t_n,h)$ o\`u $h$ est le pas (suppos\'e constant), $z_0 = y(0)$,  $t_n = n h$ et
%
$$
\Phi (z, t,h ) = \sum_{i=0}^q \mu_i f (  z_{n,i}, t + h c_i )
$$
avec
$$z_{n,0} = z \; \text{  et  }\; 
z_{n,i} = z + h \sum_{j=0}^{i-1} \lambda_{i j} f (  z_{n,j}, t + h c_j  )\;,\;i=1,\ldots, q \;.
$$
%   
On note $p$ l'ordre de la m\'ethode. On rappelle que $p>0$.
%
\begin{enumerate}
\item Supposons que $f(y,t )=f(t)$ soit ind\'ependante de $y$. On calcule l'int\'egrale 
$\int_0^1 f(t) {\rm d} t$ en r\'esolvant l'\'equation diff\'erentielle ci-dessus avec la condition initiale $y(0)=0$ par la m\'ethode
de Runge Kutta RK4. Cela correspond-t-il \`a une  m\'ethode d'int\'egration num\'erique connue, si oui laquelle? Vous justifierez votre r\'eponse.
\item En utilisant un r\'esultat g\'en\'eral du cours sur l'ordre des m\'ethodes \`a un pas, appliqu\'e \`a une fonction $f(y,t )=f(t)$ ind\'ependante de $y$,
 montrer que pour $q$ quelconque l'on a 
$$
\sum_{i=0}^q \mu_i c_i^l = \frac{1}{l+1} \;\; \text{ pour } \;\; l=0,\ldots, p-1\;.
$$
\item En d\'eduire que la m\'ethode d'int\'egration num\'erique
%
$$
\int_0^1 g(u) {\rm d} u \simeq \sum_{i=0}^q \mu_i g ( c_i) 
$$
%
est d'ordre au moins $p-1$.
\item On rappelle qu'une m\'ethode d'int\'egration num\'erique \'el\'ementaire \`a $m$ points d'interpolation
est toujours d'ordre strictement inf\'erieur \`a $2m$ (voir l'exercice 2 de la feuille 7 de TD/TP). En d\'eduire
une majoration de $p$ en fonction de $q$. 
\end{enumerate}
%
\end{document}