\newtheorem{exo}{Exercice}
\include{base}
\newcommand{\motscles}[1]{\marginpar{$\,$\textbf{#1}}}
\newcommand{\dessinb}{\unitlength=1cm
\begin{center}
 \fbox{
   \begin{picture}(6,3)
    \put(0.2,1){\line(1,0){5.6}}
    \put(0.2,0.2){\line(0,1){2.6}}
    \end{picture}
 }
\end{center}}
\newcommand{\dessint}{\unitlength=1cm
\begin{center}
 \fbox{
   \begin{picture}(6,3)
    \put(0.2,0.3){\line(1,0){5.6}}
    \put(3,0.2){\line(0,1){2.6}}
    \end{picture}
 }
\end{center}}
\begin{document}
\pagestyle{empty} \noindent{\Large SUP TSI SOA}\vskip0.1cm \hrule
\begin{center}M\'ETHODES D'APPROXIMATION\end{center}
\section{Généralités}
\noindent On cherche une valeur approchée d'une solution d'une
équation du type $f(x)=0$ (ou $f(x)=x$) où $f$ est une fonction
continue, voire plusieurs fois dérivable sur un intervalle $I$. On
suppose de plus qu'il y a au moins une  solution de l'équation sur
l'intervalle $I$.\\ Quel théorème nous permet d'affirmer qu'il
existe une solution de l'équation $f(x)=0$ lorsque qu'il existe
$a$ et $b$ dans $I$ tels que
$f(a)f(b)\le0$~? \\
Pour chacune des méthodes suivantes nous allons construire une
suite récurrente $(x_n)$ qui se rapproche d'une solution, et nous
arrêterons le calcul de la suite lorsque nous serons proche de la
solution à une erreur $\epsilon$ près donnée. On peut dire que
$x_n$ est une valeur approchée à $\epsilon$ près d'une solution de
$f(x)=0$ si $f(x_n)f(x_n+\epsilon)\le0$ ou si
$f(x_n-\epsilon)f(x_n)\le0$.
\begin{exo}
\'Ecrire une procédure nommée APPROCHE qui prend en argument une
fonction continue, un réel $x_n$ et une marge d'erreur $\epsilon$
et qui renvoie $true$ si $x_n$ est une valeur approchée d'une
solution de $f(x)=0$ à $\epsilon$ près, et $false$ dans les autres
cas. Tester la procédure sur un ou deux exemples.\motscles{if, or}
\end{exo}
Pour visualiser la rapidité de convergence de la suite, on se sert
de la procédure DESSIN suivante~:
\begin{verbatim}
> with(plots):
> with(plottools):
> DESSIN:=proc(f,x,n)
> local i,t,l,courbe,a,b:
> a:=min(seq(x[i],i=0..n))-0.1:b:=max(seq(x[i],i=0..n))+0.1:
> for i from 0 to n do
> t[i]:=textplot([x[i],0.05,"x".i],align=ABOVE):
> l[i]:=line([x[i],0],[x[i],f(x[i])],linestyle=2);
> od:
> courbe:=plot(f(t),t=a..b):
> display([courbe,seq(t[i],i=0..n),seq(l[i],i=0..n)]);
> end;
\end{verbatim}
Cette procédure prend comme arguments la fonction, un tableau de
valeurs représentant la suite et le rang jusqu'auquel on veut
aller, par exemple si $n$ vaut $3$, $x_0$, $x_1$, $x_2$ et $x_3$
seront représentés sur le dessin.
\section{Crible}
La méthode la plus simple consiste à cribler l'intervalle $I$ par
des espacements de plus en plus petits. $pasinit$ représente le
pas initial servant à cribler. Sitôt que l'on a trouvé des valeurs
de signes opposés par la fonction $f$, on fait demi-tour et on
réduit le pas en le multipliant par un $facteur$ contractant,
compris strictement entre $0$ et $1$. $depart$ représente la
valeur $x[0]$ et $e$ l'erreur maximum recherchée.
\begin{verbatim}
Digits:=100:
> CRIBLE := proc(f,depart,e,pasinit,facteur)
> local x,i,pas:
> x[0]:=depart:pas:=pasinit:i:=0:
> while(not(APPROCHE(f,x[i],e)) and i<1000) do
> x[i+1]:=evalf(x[i]+pas):
> if (f(x[i+1])*f(x[i])<=0) then pas:=-pas*facteur fi;
> i:=i+1;
> od:
> printf("%d itérations, valeur trouvée : %.40f",i,x[i]);DESSIN(f,x,min(i,9));
> end;
\end{verbatim}
Tester la procédure avec $f(x)=x-cos(x)$, $x_0=0,2$ et $pas=1$
(choisir le facteur). Que penser de la rapidité de convergence~?
\section{Dichotomie} La méthode dichotomique ressemble à la
précédente, mais au lieu de construire une suite, on construit
deux suites représentant les extrémités d'un segment contenant un
zéro de $f$, $f$ prenant des valeurs de signes opposés aux
extrémités. On remplace à chaque fois une des extrémités (celle
dont l'image par $f$ est de même signe que l'image du milieu) par
le milieu du segment. \begin{exo} Adapter la méthode précédente
pour fabriquer la procédure DICHOTOMIE prenant comme arguments
$f$, $a$, $b$ (extrémités initiales) et la marge d'erreur maximum
souhaitée $e$.\end{exo}
\section{Point fixe}
Cette fois-ci l'objectif est de résoudre des équations de la forme
$f(x)=x$. Pour cela, sous certaines conditions que l'on verra plus
tard, on peut essayer de construire une suite récurrente à l'aide
de la fonction $f$, en fixant $x_0$ dans $I$ puis en posant
$x_{n+1}=f(x_n)$ pour tout $n\in\N$. \begin{exo} (exercice
mathématique) On suppose que $f$  admet au moins un point fixe $r$
dans $I$ et que, de plus, $f$ est dérivable sur $I$,  et que sa
dérivée vérifie~:
$$\exists k\in[0;1[,\forall x\in I,\quad |f'(x)|\le k$$
\begin{enumerate}
\item Montrer que pour tout $(x,y)\in I^2,\quad |f(x)-f(y)|\le
k|x-y|$ \item En déduire que $f$ admet un unique point fixe dans
$I$. \item En admettant que la suite définie par la donnée de
$x_0\in I$ et la relation de récurrence $x_{n+1}=f(x_n)$ est bien
définie, montrer qu'elle vérifie~:
$$\forall n\in\N,\quad |x_n-r|\le k^n|x_0-r|$$
En déduire qu'elle converge vers $r$.
\end{enumerate}
\end{exo}
\begin{exo} Programmer la procédure FIXE, qui prend comme
arguments la fonction $f$, la valeur de départ $x_0$ et la marge
d'erreur maximum $\epsilon$. Tester la procédure avec la fonction
cosinus.
\end{exo}
\section{Newton-Raphson}
La méthode de Newton-Raphson est basée sur l'utilisation de la
tangente en un point de la courbe d'une fonction $f$. Plus
précisément, le choix d'une première valeur $x_0$ approchée d'un
zéro réel à localiser détermine un premier point $(x_0,f(x_0))$
sur la courbe qui sera considéré comme un premier point de
tangence. Ce nombre est appelé  amorce  du procédé itératif de
Newton-Raphson. L'abscisse  du point d'intersection de la première
tangente avec l'axe des $x$  sera considéré comme une deuxième
valeur $x_1$ approchée du zéro à localiser. À son tour, cette
valeur permettra de considérer un deuxième point de tangence
$(x_1,f(x_1))$ . À nouveau, l'abscisse  du point d'intersection de
la deuxième tangente avec l'axe des $x$  sera considéré comme une
troisième valeur $x_2$ approchée du zéro. En poursuivant ce
procédé itérativement, on obtiendra, sous certaines conditions,
une séquence de différentes valeurs $x_0$, $x_1$, $x_2$, $x_3$,
$\dots$ qui vont se rapprocher de plus en plus d'un zéro réel de
la fonction $f$.\\
Rappelons que l'équation d'une droite passant par un point $(a,b)$
de pente $m$ est donnée par $$y=m(x-a)+b$$

Si la fonction $f$ est une fonction dérivable en $x_k$, la pente
de la tangente à la courbe passant par le point $(x_k,f(x_k))$ est
directement donnée par $m=f'(x_k)$. Alors, l'équation de chaque
tangente à la courbe d'équation passant par le point
$(x_k,f(x_k))$ est donnée par

$$y = f'(x_k)(x-x_k)+f(x_k)$$

L'abscisse du point d'intersection de la $k$-ième tangente avec
l'axe des $x$ est évidemment la racine de l'équation
$0=f'(x_k)(x-x_k)+f(x_k)$. En résolvant, pour $x$, cette équation,
on obtient $$x=x_k-\frac{f(x_k)}{f'(x_k)}$$

Or, la valeur de $x$ est précisément la prochaine approximation
qui est pris en charge dans ce procédé itératif. On déduit donc
que $$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$$

Cette équation est appelée équation de récurrence de
Newton-Raphson.
\begin{exo} Adapter la méthode FIXE
pour fabriquer la procédure NEWTON prenant comme arguments $f$,
$x_0$ (amorce) et la marge d'erreur maximum souhaitée $e$.
Rajouter dans la procédure DESSIN le tracé des tangentes. Tester
la procédure avec la fonction $f(x)=x-cos(x)$ et observer ce qui
se passe pour différentes valeurs de départ, en particulier pour
$x_0=1$ et $x_0=4$. \motscles{line}\end{exo}
\begin{exo} Avec la procédure précédente, trouver des valeurs
approchées à $10^{-30}$ près de la fonction
$f(x)=8x^4-14x^3-9x^2+11x-1$. Essayer de repérer la façon de
choisir les amorces.
\end{exo}
\end{document}
