\documentstyle[11pt,amsfonts,amsmath]{article}
\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
\def\integer{{\mathbb{Z}}}
\def\pinteger{{\mathbb{N}}}
\def\spinteger{{\mathbb{N}}^\star}
\def\real{{\mathbb{R}}}
\def\preal{{\mathbb{R}}_+}
\def\complex{{\mathbb{C}}}
\def\rational{{\mathbb{Q}}}
\def\tr{{\rm tr}}
\def\D{{\rm d}}
\def\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 Math \hfill  Universit\'e J. Fourier\\ 
\begin{center}
{\bf Feuille de TD 3} 
\end{center}

\vspace{0.5cm}






\exercice {\bf Algorithme d'Euclide pour les entiers.} 
D\'eterminer \`a l'aide de l'algorithme d'Euclide 
le plus petit commun diviseur (PGCD) de $1430$ et $1105$ et
deux entiers $u$ et $v$ satisfaisant l'identit\'e de Bezout,
%
$$PGCD(1430,1105) = 1430\,u + 1105\,v\;.$$  
%
Combien d'it\'erations sont-elles n\'ecessaires~?



\vspace{4mm}

\exercice {\bf Algorithme d'Euclide pour les polyn\^omes.}
Montrer que les polyn\^omes $R_0(X)=X^3 + X^2 + 1$ et $R_1(X)=X^2-1$ sont
  premiers entre eux. D\'eterminer  \`a l'aide de l'algorithme
  d'Euclide
des polyn\^omes $U$ et $V$ tels
  que $U R_0  + V  R_1  = 1$.

\vspace{4mm}

\exercice {\bf Exercice 5 du TP 4.}
\be
\item
Soit $P(X)=X^2-1$ et $Q(X)=X+2$. Montrer que $P$ et $Q$ 
sont premiers entre
eux  et  d\'eterminer des polyn\^omes $U$ et $V$ tels
  que $U P   + V Q  = 1$. 

\item
Montrer que $P(X)$ et $P'(X)$ sont premiers entre
eux et  d\'eterminer des polyn\^omes $W$ et $Z$ tels que $W P  + Z P'=
1$.

\item D\'eduire des questions 1. et 2. la d\'ecomposition
en \'el\'ements simples de
\[ f(x)=\frac{1}{(x^2-1)^2(x+2)}\]
\item D\'eterminer une primitive de $f$.
\item D\'eterminer le d\'eveloppement en s\'erie
enti\`ere  en 0 de $f(x)$.
\ee


\vspace{2mm}

\exercice {\bf Calcul approch\'e des racines d'un polyn\^ome.}
Peut-on appliquer la m\'ethode de Newton pour d\'eterminer des valeurs
approch\'ees des racines des polyn\^omes suivants ?
\be
\item $R(X)=X^2 + 10^{-8}$
\item $P_\lambda (X) = X^3 - 3 X + \lambda$, $\lambda \in \real$
\item $Q(X) = X^3$.
\ee
Si oui, donner pour chaque racine un domaine de valeurs initiales
$u_0$ telles que la
suite it\'er\'ee de Newton $(u_n)_{n \in \pinteger}$ converge vers la
racine cherch\'ee (pour $P_\lambda$, discuter les diff\'erents cas
de figure suivant les valeurs de $\lambda$).

\vspace{4mm}

\exercice {\bf Algorithme de Sturm.}  
D\'eterminer \`a l'aide de l'algorithme de Sturm le nombre de racines 
r\'eelles de $P(X) = X^3- 3 X$ dans les intervalles suivants~: 
$I_1=[-2,-1]$, $I_2= [-1,1]$ et $I_3= [1,2]$.

\vspace{4mm}

\exercice {\bf Syst\`emes d'\'equations non lin\'eaires}
\be
\item Soit $P$ et $Q$ deux polyn\^omes. Montrer que le syst\`eme
\begin{equation} \label{eq-systeme}
\begin{cases}
P(x) & = 0 \\
Q(x) & = 0
\end{cases}
\end{equation}
est \'equivalent \`a $PGCD(P,Q) (x) =0$. En d\'eduire que (\ref{eq-systeme})
admet une solution si et seulement si $P$ et $Q$ ne sont pas
premiers entre eux. Dans ce cas, comment sont reli\'es le nombre de solutions et
le degr\'e de $PGCD(P,Q)$~?
\item Soit $P(X)=X^3+\gamma$ et $Q(X) = X^2 + \alpha$ avec
  $\alpha$ et $\gamma \in \real$. Montrer que $P$ et $Q$ sont premiers entre
eux si et seulement si $\alpha^3 + \gamma^2 \not= 0$.\\
{\it Indication~:} utiliser l'identit\'e de Bezout
$PGCD(P,Q)= U P + V Q$ avec $U(X) = a X + b$ et $V( X) = c X^2 + d X + e$,
puis \'ecrire un syst\`eme lin\'eaire \`a 5 \'equations pour $a,b,c,d$ et $e$.
\item En d\'eduire que (\ref{eq-systeme}) admet une solution (dans 
$\complex$) si et seulement si $\alpha^3 + \gamma^2=0$. D\'eterminer 
dans ce cas les solutions.
\ee
 
\vspace{4mm}


\exercice {\bf Polyn\^omes d'interpolation~: formes de Lagrange et de
  Newton.} Soit $M_i= (x_i,y_i)$, $i=0,1,\cdots,n$, des points de
$\real^2$ tels que $x_0 < x_1 < \cdots < x_n$.  On pose
$$
l_i (x) = \prod_{j=0,j \not=i}^n \frac{x-x_j}{x_i-x_j} \;.
$$
\be
\item
Montrer que le polyn\^ome de degr\'e $n$ d\'efini par
%
\begin{equation} \label{eq-Lagrange}
P_n (X) = \sum_{i=0}^n y_i \, l_i (X)
\end{equation}
satisfait 
%
\begin{equation} \label{eq-interp}
P_n (x_i)=y_i \;\text{ pour tout $i=0,\ldots , n$}.
\end{equation}
%
\item  Montrer qu'il existe un unique polyn\^ome $P_n$ de degr\'e $n$
  satisfaisant (\ref{eq-interp}). Un tel polyn\^ome est appel\'e le
  {\it polyn\^ome interpolateur } de $(M_0,\cdots M_n)$. 
%{\it Indication~:} Si $P_n$ et $Q_n$ satisfont (\ref{eq-interp}),
%alors $P_n - Q_n$ est un polyn\^ome de degr\'e $n$ avec $n+1$ racines.

\item On cherche \`a pr\'esent $P_n$ sous la forme~:
\begin{equation} \label{eq-Newton}
P_n (X) = y_0 + y_{0,1} (X-x_0)  + y_{0,1,2} (X-x_0) ( X - x_1)  + \cdots 
+ y_{0,1,\cdots, n} \prod_{j=0}^{n-1} ( X - x_j )\;, 
\end{equation}
o\`u les constantes $y_{0,1},y_{0,1,2}, \cdots, y_{0,1,\cdots, n}$ sont \`a d\'eterminer.
Montrer que pour tout $n \geq 1$,
$$y_{0,1,\cdots ,n} =\frac{ y_{1,2\cdots ,n} - y_{0,1,\cdots ,
    n-1}}{x_{n}- x_0} \;,
$$
o\`u $y_{0,1\cdots ,n-1}$ et $y_{1,2,\cdots ,   n}$ sont respectivement
 les coefficients de plus haut degr\'e des polyn\^omes 
interpolateurs $P_{n-1}$ de $(M_0,\cdots M_{n-1})$
et $Q_n$ de $(M_1,\cdots
M_n$).
Quel est l'avantage de la forme de Newton (\ref{eq-Newton}) par
rapport \`a la forme de Lagrange (\ref{eq-Lagrange})~?  
\\
{\it Indication~:} On pourra d'abord montrer que, en vertu de 
(\ref{eq-interp}) et de l'unicit\'e de
$P_n$,    
$$
P_{n}(X) 
 = \frac{X - x_{n}}{x_0 - x_{n}} P_{n-1} (X) 
+ \frac{X - x_0}{x_n - x_0} Q_{n-1} (X) \;,
$$
puis on identifiera les coefficients de plus haut degr\'e des membres de
gauche et de droite.
\ee

\vspace{2mm}

\exercice {\bf Calcul approch\'e d'une int\'egrale.} Calculer les sommes finies
$$\sum_{i=1}^N i^2 \quad \text{et}  \quad \sum_{i=1}^N i^3$$
(on pourra utiliser la formule de somme
d'Euler-MacLaurin).
En d\'eduire une approximation de l'int\'egrale 
$$I = \int_0^1 x^3 \D x$$ 
en utilisant 
\be
\item la m\'ethode des rectangles \`a gauche
\item la m\'ethode du point milieu
\ee
pour un pas $h=1/N$. Comparer la valeur approch\'ee avec la valeur
exacte dans les deux cas. Quelle est la m\'ethode la plus pr\'ecise~?  


\vspace{4mm}

\exercice {\bf Pr\'ecision de la m\'ethode des trap\`ezes.}
Soit $f$ une fonction de classe $C^2 (\real)$ qui s'annule en dehors
d'un intervalle born\'e $[a,b]$. Montrer que la m\'ethode des
trap\`ezes permet de calculer l'int\'egrale 
\begin{equation} \label{eq-integrale}
I(f) = \int_a^b f (x) \, \D x
\end{equation}
avec une pr\'ecision d'ordre $1/N^2$.\\
{\it Indication~:} utiliser la formule de somme d'Euler-MacLaurin.

\vspace{4mm}

\exercice {\bf M\'ethodes de Newton-Cotes.}
La m\'ethode de Newton-Cotes d'ordre $n$ et de pas $h=b-a$ consiste
\`a \'evaluer l'int\'egrale (\ref{eq-integrale}) 
 en rempla\c{c}ant $f$ par son polyn\^ome interpolateur 
de Lagrange (\ref{eq-Lagrange}) aux points $x_i = a + h i /n$, $i=0,\cdots , n$. On
obtient ainsi une valeur approch\'ee  
$$
I_n(f) =  \sum_{i=0}^n f(x_i)\, \omega_i^{(n)} 
$$
de $I(f)$. Calculer les coefficients $\omega_i^{(n)}$ pour $n=2$ et pour $n=3$.
\\
{\it Indication~:} Au lieu de calculer les int\'egrales
$\int_{a}^{b} l_i (x) \, \D x$, on pourra remarquer que $I(f) = I_n(f)$    
si $f$ est un polyn\^ome de degr\'e inf\'erieur ou \'egal \`a $n$
(dans ce cas, $f$ est \'egal \`a son polyn\^ome interpolateur).

\vspace{4mm}

\exercice {\bf Proc\'ed\'e de 
Richardson-Romberg.} Soit  $f$ une fonction de classe $C^5(\real)$ dont on ne
conna\^{i}t les valeurs qu'en un nombre fini de points $x_0, \cdots,
x_n$ (autrement dit, on ne dispose pas d'une formule explicite pour
$f$
mais seulement d'un tableau de ses valeurs $y_i = f(x_i)$ aux points 
$x_i$, $i=0,\cdots ,n$). 
Pour estimer la d\'eriv\'ee de $f$ en $x_i$, on utilise la
formule approch\'ee
$$
f'(x_i) \simeq (D f)_i = \frac{f(x_{i+1}) - f(x_{i-1})}{x_{i+1}- x_{i-1}}\;.
$$
\be
\item On suppose qu'il existe $M>0$ tel que $| f''' (x) | \leq M \;\forall\;x \in \real$. 
Montrer que si les points $x_i$ sont r\'eguli\`erement
  espac\'es,
c'est-\`a-dire, si $x_{i+1}-x_i = h$, $i=0,\cdots , n-1$, avec
$h>0$ fix\'e, alors
$| f'(x_i) - (D f)_i | \leq M h^2/3$.
\item Appliquer le proc\'ed\'e d'acc\'el\'eration de la convergence de 
Richardson-Romberg pour obtenir une approximation de $f'(x_i)$ avec une
pr\'ecision d'ordre $h^4$.
\ee

 

  
\end{document}