\documentclass[11pt,amsfonts,amsmath]{article}
\usepackage{times}
\usepackage{amssymb}
\textheight 25.6cm \textwidth 16.9cm
\oddsidemargin 0pt \evensidemargin 0pt

\def\bbox#1{\mbox{\boldmath{$#1$}}}
%Changes by Kay Wiese the 22.4.1994
\setlength{\topmargin}{0cm}
\setlength{\hoffset}{-0.6cm}
\setlength{\voffset}{-.5cm}
\setlength{\headsep}{0cm}
\setlength{\headheight}{0cm}
\setlength{\topskip}{0cm}
%Personnal definitions of D. Spehner, 21.10.02
%%%%%%%%%% 1. ensemble numeriques
\newcommand{\integer}{{\mathbb{Z}}}
\newcommand{\pinteger}{{\mathbb{N}}}
\newcommand{\spinteger}{{\mathbb{N}}^\star}
\newcommand{\real}{{\mathbb{R}}}
\newcommand{\preal}{{\mathbb{R}}_+}
\newcommand{\complex}{{\mathbb{C}}}
\newcommand{\rational}{{\mathbb{Q}}}
\newcommand{\tr}{{\rm tr}}
\newcommand{\D}{{\rm d}}
\newcommand{\I}{{\rm i}\,}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}  
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}      
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\ul}{\underline}
\newcommand{\ba}{\begin{tabular}}
\newcommand{\ea}{\end{tabular}}
\newcommand{\ns}{\normalsize}    


\newcounter{exercice}
\newcommand{\exercice }
{\noindent \textbf{Exercice \addtocounter{exercice}{1}
\arabic{exercice}.} }
\setcounter {exercice}{0}

\begin{document}

\noindent%
L2-M249, 2005-2006, parcours Maths \hfill  Universit\'e J. Fourier\\ 
\begin{center}
{\bf Feuille de TD 1} 
\end{center}

\vspace{0.5cm}


\exercice {\bf Entiers en base 2 et en base 16.}  
\be
\item
Soit $n_1$ l'entier s'\'ecrivant $1234$ en base $16$. Donner 
$n_1$ en base $10$.
\item
Soit $n_2$ l'entier s'\'ecrivant $6000$ en base $10$. 
\'Ecrire $n_2$ en base $16$ puis en base $2$.

\ee
 
\vspace{1mm}

\exercice  {\bf Op\'erations en base 2.}
Donner les tables d'addition et de multiplication en base $2$.
Calculer la somme, la diff\'erence et le produit des 
2 entiers s'\'ecrivant $1101$ et $1011$ en base $2$
en utilisant l'algorithme ``\'ecole primaire'' en base $2$.
V\'erifiez vos r\'esultats en les comparant \`a ceux obtenus en base $10$.    

\vspace{3mm}

\exercice {\bf Fractions en base 2.}
\'Ecrire les nombres d\'ecimaux $0.25$, $0.1875$ et $0.3$ en base
$2$. Comment ces nombres sont-ils cod\'es sur un ordinateur disposant
de $52$ bit pour la mantisse et de $11$ bit pour l'exposant~? Le
codage est-il exact~? 
 
\vspace{3mm}

\exercice {\bf Erreur relative pour l'inverse.}
Donner l'erreur relative de $1/x$ par rapport \`a $1/x_0$ en fonction
de l'erreur relative $\epsilon = \vert x-x_0 \vert / \vert x_0 \vert$
de $x$ par rapport \`a $x_0$ (on pourra se limiter au plus bas ordre 
en $\epsilon$).

\vspace{3mm}

\exercice {\bf M\'ethode de Horner (1).}
Il s'agit d'\'evaluer efficacement un polyn\^ome en un point.
On pose $b_0=P(\alpha )$ et on \'ecrit~:
\[ P(X)-b_0=(X-\alpha )Q(X) \]
o\`u~:
\[ Q(X) = b_n X^{n-1} + ... +b_2 X + b_1 \; . \]
On calcule alors par ordre d\'ecroissant $b_n$, $b_{n-1}$, ..., $b_0$.
\be
\item
Donner $b_n$ en fonction de $a_n$ puis $b_i$
en fonction de $a_i$ et $b_{i+1}$ pour $i = n-1, n-2,
\ldots , 1$. 
\item 
Appliquer la m\'ethode ci-dessus pour calculer $P(\alpha )$ pour
$P(X)=X^3+7X^2+7X$ et $\alpha=16$. 

\item M\^eme question pour $P(X)=X^5+4 X^4+3 X^3$ et $\alpha=5$. En d\'eduire
  l'\'ecriture en base $10$ de l'entier s'\'ecrivant $143000$ en base $5$. 
\ee
 
\vspace{3mm}

\exercice {\bf M\'ethode de Horner (2).}
Pour calculer tous les coefficients du d\'eveloppement de Taylor du
polyn\^ome $P(X)$ en un point, on pose $P_0(X)=P(X)$ et on r\'ep\`ete
l'algorithme de l'exercice pr\'ec\`edent pour calculer successivement
les coefficients des polyn\^omes $P_0(X), P_1(X), \ldots , P_n(X)$
d\'efinis par~:
\begin{eqnarray*}
P_0(X) & = & ( X - \alpha ) P_1(X) + P_0 ( \alpha ) \\
P_1(X) & = & ( X - \alpha ) P_2(X) + P_1 ( \alpha ) \\
 ... & & \\
P_{n-1}(X) & = & ( X - \alpha ) P_n (X) + P_{n-1} ( \alpha )
\end{eqnarray*}
jusqu'\`a ce que l'on obtienne un polyn\^ome de degr\'e z\'ero,
$P_n(X)=const$.
\be
\item Montrer que 
$$
P(X)= (X-\alpha)^n P_n ( \alpha) + (X-\alpha)^{n-1} P_{n-1}( \alpha)+
\cdots (X-\alpha) P_1 ( \alpha) + P_0 ( \alpha ) \; .
$$
Comment sont reli\'es $P_i(\alpha)$ et la $i$-i\`eme d\'eriv\'ee 
$P^{[i]} (\alpha)$ de $P$ au point $\alpha$~?

\item Utiliser cette m\'ethode pour calculer $P^{[i]} (\alpha)$,
  $i=0,1,2,3$,
pour $P(X)=X^3 - 2 X + 5$ et $\alpha=39$.
\ee

\vspace{4mm}

\exercice {\bf Th\'eor\`eme du point fixe.} Soit 
$f:[a,b] \rightarrow [a,b]$ une fonction satisfaisant  
les hypoth\`eses du th\'eor\`eme du point fixe
vu en cours. 
\be
\item Montrer que $f$ est contractante,
c'est-\`a-dire, il existe $k\geq 0$, $k < 1$ tel que
$\vert f(u)-f(v)\vert \leq k \vert u-v \vert$ pour tout $u,v \in [a,b]$.
\item En d\'eduire que le nombre de d\'ecimales de 
$u_n = f^n (u_0)$ co\"{\i}ncidant avec celles du point fixe 
$\ell = \lim_{n \rightarrow \infty} u_n$
augmente (au moins) proportionnellement \`a $n$ quand $n$ cro\^{\i}t
({\it convergence lin\'eaire}).     
\item Si l'on suppose de plus que $f$ est de classe 
$C^2([a,b])$ et que $f'(\ell)=0$,  montrer que   
le nombre de d\'ecimales de 
$u_n$ co\"{\i}ncidant avec celles de $\ell$
augmente beaucoup plus rapidement avec $n$~: (au moins) 
comme $2^n$ 
({\it convergence exponentielle}).\\
{ \it Indication~:} Utiliser la formule de Taylor avec reste \`a
l'ordre 2.
   
\ee

\vspace{4mm}

 
\exercice {\bf Points fixes instables.}
On veut r\'esoudre l'\'equation 
\begin{equation} \label{eq1}
e^u -2=u \mbox{ , } u>0
\end{equation}
 par la m\'ethode du
point fixe.
\be
\item La fonction $f(u)=e^u -2$ est-elle contractante sur
  $[0,\infty[$~? 
Tracer  sur le graphe de $f$ les premi\`eres valeurs de la suite 
it\'er\'ee $u_n = f^n (u_0)$ pour une valeur initiale $u_0>0$. 
La suite converge t'elle~?\\
En consid\'erant l'inverse $f^{-1}$, trouver une m\'ethode de point fixe 
pour r\'esoudre ~(\ref{eq1}) num\'eriquement.\\ 
Justifier la convergence et donner une majoration th\'eorique de l'erreur. \\ 
Donner la solution approch\'ee et le nombre d'it\'erations n\'ecessaires pour
avoir une pr\'ecision de $10^{-6}$ en prenant $u_0=1$.
\item Utiliser la m\^eme m\'ethode  pour r\'esoudre num\'eriquement
l'\'equation
$$
\tan(u)=u \mbox{ , }
\pi/2<u<3 \pi/2\;.
$$
\item \'Etant donn\'e une fonction  non contractante quelconque
$f:[a,b]\rightarrow \real$,
sous quelles conditions sur $f$ 
votre m\'ethode est-elle applicable~?
\ee

 
\vspace{2mm}


 \exercice {\bf M\'ethode de Newton.} Utiliser la m\'ethode de Newton
pour r\'esoudre l'\'equation (\ref{eq1}). 
Justifier la convergence et donner une majoration th\'eorique de
l'erreur. \\
Combien d'it\'erations
sont-elles n\'ecessaires pour avoir une pr\'ecision de $10^{-6}$ en 
prenant $x_0=1$ (comparer avec le r\'esultat de l'exercice 8)~?
Peut-on choisir $x_0=0$~?

\vspace{4mm}

\exercice {\bf Probl\`emes de convergence~?}
Soit $g(u)=\arctan(u)$. On note $(x_n)_{n \in
  \pinteger}$ la suite it\'er\'ee obtenue en appliquant 
la m\'ethode de Newton \`a
l'\'equation
$g(r)=0$ en
partant de $x_0$.
\be
\item
D\'eterminer
num\'eriquement
une valeur $a>0$ telle que si $x_0=a$, la suite $(x_n)_{n \in
  \pinteger}$
oscille entre les deux valeurs $\pm a$ de part et d'autre de la solution 
exacte $r=0$. \\
{ \it Indication~:} On pourra par exemple chercher $a$ par une
m\'ethode de point fixe en supposant $a \in [ 1,\sqrt{3} ]$.
\item
D\'eterminer {\it graphiquement} 
le comportement de $(x_n)_{n \in  \pinteger}$ quant $n \rightarrow
\infty$ pour $\vert x_0 \vert < a$ et pour $\vert x_0 \vert > a$.
\ee

\vspace{2mm} 

\exercice {\bf Calcul de $x^{1/4}$.} 
On veut d\'eterminer une valeur approch\'ee de la racine quatri\`eme
d'un nombre r\'eel positif. 
On commence par chercher une valeur approch\'ee de $y=(1+x)^{1/4}$
pour $x \geq 0$.
\begin{enumerate}
\item 
On suppose que $x=1$ (donc $y=2^{1/4}$).\\
Donner un polyn\^ome $P(X)$ de degr\'e 4, \`a coefficients entiers
et tel que $P(y)=0$. Donner la suite 
$u_{n+1}=f(u_n)$ obtenue en appliquant la m\'ethode de Newton \`a $P$.\\
Donner une valeur $u_0$ pour laquelle la suite $u_n$ converge
vers $y$ (justifier la convergence de la suite $(u_n)_{n \in \pinteger}$ pour cette
valeur de $u_0$).\\
Calculer $u_4$, en d\'eduire un encadrement de $2^{1/4}$.\\
Peut-on appliquer la m\^eme m\'ethode pour $x \geq 0$
quelconque?
\item On suppose que l'on a calcul\'e $2^{1/4}$ \`a $10^{-16}$ pr\`es.
Proposer une m\'ethode permettant de calculer une valeur
approch\'ee de $x^{1/4}$ pour $x \geq 0$,
en utilisant l'\'ecriture mantisse-exposant de $x$ 
en base 2~:
\[ x = 2^e (1+m), \quad e \in \integer, m \in [0,1[ \]
et en utilisant la m\'ethode ci-dessus.
Discuter la pr\'ecision de l'approximation obtenue.
\end{enumerate}
 

\end{document}