\documentclass[11pt,amsfonts,amsmath]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\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
\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-mat406  \hfill  Travaux dirig\'es \hfill Universit\'e Grenoble Alpes\\ 




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

\vspace{4mm}

\exercice {\bf Algorithme d'Euclide pour les polyn\^omes.}
On considère les polyn\^omes $R_0(X)=X^3 + X^2 + 1$ et $R_1(X)=X^2-1$.
D\'eterminer  \`a l'aide de l'algorithme  d'Euclide
étendu $G$, un PGCD de $R_0$ et $R_1$, et
des polyn\^omes $U$ et $V$ tels que $U R_0  + V  R_1  = G$.

\vspace{4mm}

\exercice {\bf Euclide étendu, primitive/s\'eries enti\`eres.}
Soit $P(X)=X^2-1$.
\be
\item Vérifier à la calculatrice 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 En d\'eduire une primitive de $\frac{1}{P^2}$
en remplaçant le numérateur par la relation trouvée et
en effectuant une intégration par parties pour le terme $ZP'/P^2$.
\item Déterminer une primitive de
\[ f(x)=\frac{1}{(x^2-1)(x+2)}\]
\item Soit $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 En déduire le terme d'ordre $n$ du 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 Racine complexe}
Soit $P=x^3+x+1$ et $r=\frac{1}{3}+\frac{7}{6}i$. D\'eterminer un disque du plan
complexe de centre $r$ contenant au moins une racine de $P$. Am\'eliorer la
pr\'ecision en effectuant une it\'eration de la m\'ethode de Newton.
Discuter les avantages/inconv\'enients \`a utiliser des rationnels
vs des nombres flottants approch\'es.
Que peut-on dire des autres racines de $P$~?

\vspace{4mm}

\exercice{\bf Racines multiples}
Soit $P=x^6+5x^5+6x^4+x^3+6x^2+5x+1$. En utilisant le pgcd de $P$
et sa d\'eriv\'ee, d\'eterminer un polyn\^ome ayant les m\^emes
racines que $P$ mais toutes de multiplicit\'e 1. Appliquer la
m\'ethode de Newton pour trouver les racines r\'eelles de $P$.

\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}
\left\{ \begin{array}{ccc}
P(x) & = &0 \\
Q(x) & =& 0
\end{array} \right.
\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{2mm}

\exercice {\bf Interpolation}\\
Déterminer le polynôme d'interpolation de $1/x$ aux points $1,2,3$
en effectuant à la main l'algorithme des différences divisées.
Tracer sur l'intervalle $[0,4]$ la représentation graphique de
$1/x$ et de son polynôme d'interpolation.

\vspace{2mm}

\exercice{\bf Erreur d'interpolation}\\
Soit $f(x)=\ln(1+x)$ définie sur l'intervalle $[0,1]$. On se fixe
$n \geq 2$ et on calcule
le polynôme d'interpolation de $f$ aux $n+1$ 
points $x_k=\frac{k}{n}, k \in [0,n]$.
Par exemple pour $n=4$, on calcule le polynôme aux 5 points 
$x_0=0, x_1=1/4, x_2=1/2, x_3=3/4, x_4=1$.
\be
\item Déterminer un majorant de l'erreur d'interpolation lorsque $n=4$.
\item Que se passe-t-il lorsque $n$ est grand~?
\ee

\vspace{2mm}

\exercice {\bf Interpolation et précision (juin 2022)}\\
Soit $x_0=10^4, x_1=10^4+1, x_2=10^4+2$ et $y_0=1, y_1=0,y_2=2$.
Soit $P$ le polyn\^ome d'interpolation de degr\'e au plus 2
passant par les points $(x_0,y_0), (x_1,y_1), (x_2,y_2)$.
\begin{enumerate}
\item D\'eterminer $P$ par l'algorithme des diff\'erences divis\'ees sous la
forme
$$ N(x)=\alpha_0 + (x-x_0) (\alpha_1+(x-x_1)\alpha_2)$$
\item D\'evelopper $P$ sous la forme
$$ D(x)=a_2 x^2 + a_1 x +a_0$$
\item Soit $x=10^4+1/3$. D\'eterminer $P(x)$ en calcul exact.
\item On calcule maintenant en approch\'e, $x=10000.0+1.0/3.0$.
D\'eterminer une valeur approch\'ee de
$P(x)$ en utilisant la forme $N(x)$ et la forme $D(x)$.
\item On suppose qu'on travaille avec des flottants avec une
  pr\'ecision relative de 15 chiffres (\verb|1e-15|).
Estimer l'erreur absolue sur $x-x_0$ et $x-x_1$, en d\'eduire
l'erreur relative sur $N(x)$.
\item Estimer l'erreur relative sur $D(x)$ en comparant $a_0$ avec
$D(x)$.
\item Expliquez la pr\'ecision
  des r\'esultats de la question 4.
Quelle forme faut-il choisir
  pour minimiser les erreurs~?
\end{enumerate}

%% \vspace{2mm}

%% \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 \;\mbox{ 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 Comparaison int\'egrale exacte et approchée.}\\
Calculer les sommes finies
$$\sum_{i=1}^N i^2 \quad \mbox{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 Méthode du point milieu}\\
Déterminer une valeur approchée de
\[ \int_0^1 \exp(-x^2) \ dx \]
en appliquant la méthode du point milieu avec $N=10$ 
subdivisions. Donner et justifier
une majoration de l'erreur commise.



\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éthode de Simpson}\\
Le but de cet exercice est de calculer pour $x \in [0,1]$ donn\'e une
approximation de l'int\'egrale d\'efinie par~:
\[ (E) \quad \quad \quad
 F(x)=  \int_0^x  \exp(\exp(t)) \ dt  
\]
o\`u $\exp$ d\'esigne la fonction exponentielle, on notera~:
\[ f(t)=\exp(\exp(t)) \]
\begin{enumerate}
\item Calculer la d\'eriv\'ee quatri\`eme de $f$. 
Déterminer la valeur du maximum
de $|f^{[4]}(t)|$ pour $t\in [0,1]$, que l'on notera $M_4$.
\item D\'eterminer le nombre $N$ de subdivisions qui assure que
la m\'ethode de Simpson donne une valeur approch\'ee de $F(1)$ 
\`a $1e-4$ pr\`es et \`a $1e-8$ pr\`es.
Calculer une valeur approch\'ee de $F(1)$ \`a $1e-8$ pr\`es.
\item Soit $x \in [0,1]$.
D\'eterminer le nombre $N$ de subdivisions qui assure que
la m\'ethode de Simpson donne une valeur approch\'ee de $F(x)$
\`a $1e-8$ pr\`es, on exprimera $N$ en fonction de $x$.
\item Pourrait-on calculer une valeur approch\'ee de $F(x)$
par un d\'eveloppement en s\'eries enti\`eres~? Si oui, indiquez
comment proc\'eder, si non, expliquez pourquoi.
\end{enumerate}


%% \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 $\int f(t) \ dt$
%%  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

\vspace{4mm}
 
\exercice{\bf Intégrale par diverses méthodes (mai 2023)}\\
On souhaite calculer une valeur approchée de
$$ F(x)=\int_0^x \frac{\ln(1+t)}{t} \ dt, \quad x \in [0,1]$$ 
On pose
$$ f(t)=\frac{\ln(1+t)}{t} $$

\noindent {\bf Partie 1: séries entières.}
\begin{enumerate}
\item Donner le développement en séries entières de $f$ et son rayon
  de convergence
\item En déduire le développement en série entière de $F$
\item Déterminer une majoration du reste d'ordre $N$
  du développement en série de $F$
  en fonction de $x$.
\item En déduire une valeur de $N$ pour laquelle le reste d'ordre $N$
  est plus petit
  que \verb|1e-5| pour tout $x\in[0,1/2]$
\item Donner un rationnel dont on peut certifier qu'il s'agit d'une
  valeur approchée de $F(1/2)$ à \verb|1e-5| près
  \item Que se passe-t-il si $x=1$~? 
\end{enumerate}

\noindent {\bf Partie 2: méthode du point milieu et de Simpson}\\
On a
$$ F(1)=F(\frac{1}{2})+ I, \quad I=\int_{\frac{1}{2}}^1 \frac{\ln(1+t)}{t} \ dt$$
  et on va déterminer une valeur approchée de $I$,
  l'intégrale de $f$ entre 1/2 et 1,
  par la méthode du point milieu ou de Simpson.
\begin{enumerate}
\item Déterminer  $f''$ (on pourra utiliser sans justifications
  le résultat de la calculatrice).
  En déduire $M_2$ un majorant de $|f''|$
  sur $[1/2,1]$ (justifiez).
\item Combien de subdivisions sont-elles nécessaires pour avoir
  une valeur approchée de $I$ à \verb|1e-5| près par la méthode
  du point milieu~?
\item Reprendre les deux questions précédentes en utilisant la méthode
  de Simpson.
\item Déterminer une valeur approchée de $I$ à \verb|1e-5| par
  la méthode du point milieu ou par la méthode de Simpson. On donnera
  cette valeur d'abord sous la forme d'une somme puis sa valeur approchée
  obtenue à la calculatrice.
\end{enumerate}


  
\end{document}
