%%%%%%%%%%%%%%% ULM 1978 MATHS APPLI - CORRIGE %%%%%%%%%%%%
\input math3.sty
\input frpage.sty
\let\int=\INT
\everydisplay{\textstyle}

\grostitre{Ulm 78, Option M', \'epreuve pratique - Corrig\'e}

\razqnofalse
\Partie[Algorithme d'interpolation.] %I
\question %1
Voir le cours (polyn\^ome d'interpolation de Lagrange).

\question[Calcul progressif du polyn\^ome d'interpolation.] %2
Notons $Q(x)=\Frac{(x_\lambda -x)p_\lambda (x)-(x_\mu -x)p_\mu (x)}{x_\lambda -x_\mu }$. 
Comme $p_\lambda $ et $p_\mu $ sont de 
degr\'es $q-1$ au plus, $Q$ est de degr\'e $q$ au plus. D'autre part, 
on peut calculer $Q$ sur les points $x_i$: 
$$ \cases{
Q(x_i)=\frac{x_\lambda -x_i-x_\mu +x_i}{x_\lambda -x_\mu }f(x_i)=f(x_i)&si $i\ne \lambda ,\mu $\\
Q(x_\lambda )=\frac{x_\lambda -x_\mu }{x_\lambda -x_\mu }f(x_\lambda )\\
Q(x_\mu )=\frac{x_\lambda -x_\mu }{x_\lambda -x_\mu }f(x_\mu )\\} $$ 
L'unicit\'e vue \`a la
question 1 permet de conclure que $Q=\Pi f$.

\question[Algorithme de calcul.] %3
Le polyn\^ome $p_i^1$ interpole $f$ entre les points $x_0$ et 
$x_i$. Supposons que $p_i^m$ interpole $f$ en
$x_0,x_1,\dots,x_{m-1},x_i$, pour tout $i$. En calculant les
valeurs de $p_i^{m+1}$ en $x_0,x_1,\dots,x_m,x_i$, et en notant 
que son degr\'e vaut au plus $m+1$,nous validons l'hypoth\`ese de 
r\'ecurrence.

{\it Consid\'erations pratiques.}
Nous avons ici $\frac{q(q+1)}2$ polyn\^omes \`a calculer (nombre de 
couples $(l,i)$ tels que $l\le i$). Au niveau de la m\'emoire 
n\'ecessaire, il suffit de pouvoir ranger $q$ polyn\^omes, car ceux 
que l'on calcule \`a la $m+1$-i\`eme \'etape peuvent recouvrir ceux de 
l'\'etape pr\'ec\'edente.

Au niveau de la complexit\'e de l'algorithme, tout d\'epend du mode 
de repr\'esentation interne des polyn\^omes. Si nous repr\'esentons les 
polyn\^omes comme tableaux, en degr\'es croissants, le calcul de 
$p_i^{m+1}$ n\'ecessite 2 multiplications, 3 additions et une 
division pour chaque coefficient (cela se voit dans le code en 
Pascal ci-dessous). Comme le degr\'e de $p_i^{m+1}$ vaut $m+1$ au
plus, on peut escompter une complexit\'e au pire de l'ordre de 
$(m+1)(q-m)$ pour r\'ealiser toute la $m+1$-i\`eme \'etape (qui impose 
de calculer $q-m$ polyn\^omes). Au total, cette complexit\'e est de 
$$
\sum _{m=0}^{q-1}(m+1)(q-m)=\frac{q(q+1)(q+2)}6\sim \frac{q^3}6
\>.$$
Dans le cadre d'un logiciel de calcul formel (Maple ou TI92), la 
notion de complexit\'e ci-dessus n'est pas tr\`es pertinente,
essentiellement parce que le produit et la diff\'erence de deux 
polyn\^omes peut comporter nettement moins ou nettement plus de 
calculs que la simple approche par coefficients. Voici une
r\'ealisation de l'algorithme d'interpolation pour la TI-89 ou 
TI-92 (avec des raccourcis et optimisations): 

\verb
interpol(l,ex,v)                    (* l=liste des valeurs en abscisses *)
                                    (* ex=expression fonctionnelle      *)
Func                                (* v=variable de l'expression       *)
Local q,p,i,m                      
ex|v=l\flechedroite{}p                           (* appliquer fonction sur liste     *)
dim(l)-1\flechedroite{}q
For m,1,q:For i,m+1,q+1:((l[i]-v)*p[m]-(l[m]-v)*p[i])/(l[i]-l[m])\flechedroite{}p[i]:EndFor:EndFor
Return p[q+1]
EndFunc
\endverb

Voici \`a pr\'esent une prc\'edure en Pascal qui travaille au niveau des 
coefficients. Elle semble plus rapide car le syst\`eme interne de 
calcul formel (gestion des parenth\`eses) n'intervient pas.

\verb
type listecoeff=array[0..30] of real;

procedure Interpolation_Coeff(x,y:listecoeff;q:integer;var pinter:listecoeff);
                       (* x=liste des valeurs en abscisses                          *)
                       (* y=liste des valeurs en ordonn\'ees                          *)
                       (* q =nombre de points-1                                     *)
                       (* pinter =coefficients du polyn\^ome d'interpolation          *)
var p,i,m,j:integer;
                       (* On stocke les coefficients dans un tableau \`a 2 dimensions.*)
                       (* Chaque polyn\^ome a ses coefficients stock\'es en ligne,      *)
                       (* num\'erot\'es par degr\'es croissants \`a partir de 0.            *)
    pc:array[0..30] of listecoeff;
begin
for m:=0 to q do           (* initialisation                           *)
    begin
    pc[m,0]:=y[m];         (* au d\'ebut on a q+1 polyn\^omes de degr\'e 0   *)
    for i:=1 to q do pc[m,i]:=0.0
    end;
for m:=0 to q-1 do         (* m = num\'ero de l'\'etape qui s'appuie sur le point x[m] *)
    For i:=m+1 to q do     
        begin              (* \'etape m : polyn\^omes de degr\'e inf\'erieur ou \'egal \`a m+1 *)
        for j:=m+1 downto 1 do
            pc[i,j]:=(x[i]*pc[m,j]-x[m]*pc[i,j]+pc[i,j-1]-pc[m,j-1])/(x[i]-x[m]);
        pc[i,0]:=(x[i]*pc[m,0]-x[m]*pc[i,0])/(x[i]-x[m]);
        end;
pinter:=pc[q];
end;
\endverb

\Partie[Convergence du processus d'interpolation.] %II
\question[Estimation de l'erreur.] %4
Soit une constante $A$, et soit $\varphi $ la fonction auxiliaire 
d\'efinie par $\varphi (x)=f(x)-\Pi f(x)-A\prod_{i=0}^q(x-x_i)$. Cette
fonction s'annule sur tous les $x_i$. Choisissons, de plus, un 
point $y$ distinct des $x_i$, et fixons $A$ tel que $\varphi (y)=0$. La 
fonction auxilaire s'annule donc $q+2$ fois sur l'intervalle $I$. 
Elle est d\'erivable comme $f$ (\`a laquelle on a juste soustrait un 
certain polyn\^ome). D'apr\`es le th\'eor\`eme de Rolle appliqu\'e $q+1$
fois, $\varphi '$ s'annule en $q+1$ points distincts de $I$. En 
recomman\c cant nous parviendrons \`a savoir que $\varphi ^{(q+1)}$ s'annule 
1 fois. Or, $\varphi ^{(q+1)}(x)=f^{(q+1)}(x) -A(q+1)!$, puisque la
d\'eriv\'ee $n$-i\`eme de $x^n$ est $n!$. En reportant la valeur 
trouv\'ee de $A$ dans l'\'egalit\'e $\varphi (y)=0$ on a le r\'esultat voulu.

\question[Pour certaines fonctions le processus converge.] %5
Majorons l'\'ecart entre $f$ et son polyn\^ome d'interpolation \`a 
l'aide de la question pr\'ec\'edente, pour $x\in [a,b]$: 
$|f(x)-\Pi f(x)|\le \frac1{(q+1)!}(b-a)^{q+1}\Sup_{x\in I}|f^{(q+1)}(x)|$.
D\`es lors, si la fonction $f$ a, par exemple, ses d\'eriv\'ees toutes 
born\'ees sur $I$, l'\'ecart uniforme entre $f$ et ses polyn\^omes 
d'interpolation va tendre vers 0. De telles fonctions sont 
faciles \`a trouver, par exemple le sinus ou l'exponentielle. En ce 
qui concerne les fonctions rationnelle, l'ordre de grandeur de la 
d\'eriv\'ee $n$-i\`eme est $n!M^n$, la constante $M$ d\'ependant de la 
position de $a$ et $b$ par rapport aux p\^oles de la fraction (on 
le montre gr\^ace \`a la d\'ecomposition en \'el\'ements simples).

\Partie[Ph\'enom\`ene de Runge.] %III
\question[Parit\'e.] %6
Le polyn\^ome $\Pi f(-x)$ a le m\^eme degr\'e que $\Pi f$, prend les m\^emes 
valeurs que $f$ sur les points d'interpolation pusque ceux-ci 
sont sym\'etriquement distribu\'es par rapport \`a 0. L'unicit\'e du 
polyn\^ome d'interpolation, vue \`a la premi\`ere question, montre que 
$\Pi f$ est pair.

\question %7
Notons $h(x)=f(x)\prod_{j=0}^n\bigl(\frac{x_j^2-x^2}{x_j^2+1}\bigr)$ 
et $g(x)=f(x)-h(x)$. Il s'agit de montrer que $g$ est un polyn\^ome 
de degr\'e $2n$ au plus, co\"\i ncidant avec $f$ aux points 0 et $x_i$ 
(c'est suffisant car $h$ est manifestement paire). Cette derni\`ere
exigence est ais\'ee \`a assurer, vue la forme de produit de $g$.
D'autre part, en r\'eduisant au m\^eme d\'enominateur, il vient 
$$
g(x)=\frac{\textstyle\prod_{j=0}^n(x_j^2+1)-\prod_{j=0}^n(x_j^2-x^2)}{(1+x^2)\prod_{j=0}^n(x_j^2+1)}
\>,$$ 
fraction rationnelle n'ayant comme seul p\^oles \'eventuels $i$
et $-i$; mais son num\'erateur s'annule pour $x=i$ ou $x=-i$, donc 
il s'agit bien d'un polyn\^ome. Le degr\'e est $2n$ comme diff\'erence 
du degr\'e du num\'erateur et du d\'enominateur.

\question %8
On constate imm\'ediatement que la somme consid\'er\'ee ressemble \`a une 
somme de Riemann, associ\'ee \`a l'int\'egrale
$\int _0^a\ln\bigl|\frac{t^2-\xi ^2}{t^2+1}\bigr|\dt$. 
Malheureusement, il s'agit l\`a d'une int\'egrale g\'en\'eralis\'ee et nous 
devons pallier l'absence de r\'esultat dans le cours.

\Lemme.
Soit une fonction $f$ d\'ecroissante, continue sur $]\alpha ,+\infty [$, 
int\'egrable au voisinage de $\alpha $, et 
soit $x_j=\alpha +(j+\frac12)h$. Alors pour tout $\beta >\alpha $ on a: 
$$
I=\int _{\alpha }^\beta f(t)\dt=\Lim_{h\to 0}h\sum _{j=0}^{p(h)}f(x_j)
\>.$$
\Preuve
On a d\'ej\`a par d\'ecroissance de $f$: 
$I\ge h\sum _{j=1}^{p(h)}f(x_j)$ (en prenant les rectangles \og \`a gauche\fg ). 
D'autre part, avec des rectangles \og \`a droite\fg, on a
$$I\le \int _{[\alpha ,x_0]}f+h\sum _{j=0}^{p(h)}f(x_j)$$ 
de sorte que l'\'ecart entre $I$ et la somme de Riemann ne d\'epasse pas
$\int _{[\alpha ,x_0]}f+hf(x_0)$; cependant, on a $x_0-\alpha \le \frac h2$, donc aussi
$hf(x_0)\le 2\int _{[\alpha ,x_0]}f$ et finalement
l'\'ecart est inf\'erieur \`a $3\int _{[\alpha ,x_0]}f$, ce qui tend bien vers 0 
avec $h$, et le lemme est d\'emomtr\'e.

Le lemme pr\'ec\'edent s'applique entre 0 et $\xi $ puis entre $\xi $ et 
$a$, sachant que la fonction $t\mapsto \frac{\xi ^2-t^2}{t^2+1}$ est 
monotone de signe constant sur chacun de ces intervalles.
L'int\'egrale se calcule par parties. On trouve: 
$$
\int _0^a\ln\bigl|\frac{t^2-\xi ^2}{t^2+1}\bigr|\dt
=a\ln\bigl(\frac{a^2-\xi ^2}{a^2+1}\bigr)+\xi \ln\bigl(\frac{a+\xi }{a-\xi }\bigr)-2\arctan a
\>.$$

\question %9
Nous allons un peu d\'etourner la question, montrant d'abord que 
sur $[0,1]$ la convergence du processus d'interpolation de $f$ a 
bien lieu. Pour ce faire nous aurons besoin de la d\'eriv\'ee 
$n$-i\`eme de $f$. Une formule existe \`a cet effet: 
$$
f^{(n)}(\tan t)=\pm n!\cos^{n+1}t\cos((n+1)t+n\frac{\pi }2)
$$ 
Pour $n=0$ cette formule est \'evidente et se r\'esume \`a $\frac1{1+\tan^2t}=\cos^2t$.
Supposons que $$
f^{(n-1)}(\tan t)=\pm (n-1)!\cos^nt\cos(nt+(n-1)\frac{\pi }2)
\>.$$ 
D\'erivons une fois de plus: 
$$
\eqalign{
f^{(n)}(\tan t)\cos^{-2}t
&=\pm n!\cos^{n-1}t[-\sin t\cos(nt+(n-1)\frac{\pi }2)+\cos 
t\sin(nt+(n-1)\frac{\pi }2)]\\
&=\pm n!\cos^{n-1}t\sin((n+1)t+(n-1)\frac{\pi }2)
 =\pm n!\cos^{n-1}t\cos((n+1)t+n\frac{\pi }2)\\}
$$
ce qui ach\`eve la r\'ecurrence.
Sur $[0,1]$, on fait varier $t$ entre 0 et $\frac{\pi }4$, de sorte 
que la d\'eirv\'ee $n$-i\`eme de $f$ peut \^etre major\'ee en valeur
absolue par $(n+1)!\frac1{(\sqrt 2)^{n+2}}$. Revenant aux r\'esultats du
II, nous obtenons imm\'ediatement la convergence du processus sur 
$[-1,1]$. En particulier, en choisissant $a=1$ et $\xi \in [0,1]$ on 
aura la limite nulle.

Examinons \`a pr\'esent ce qui se passe avec $a=2$ et $\xi =a$.
Nous tirons de ce qui pr\'ec\`ede:
$$
\Lim_{h\to 0}h\ln\prod_{j=0}^{n_h}\bigl(\frac{x_j^2}{x_j^2+1}\bigr)
=4\ln4-2\ln5-2\arctan 2\approx 0,112>0
$$
(le choix de $a=2$ est ici assez miraculeux, car des valeurs 
l\'eg\`erement inf\'erieures donneraient un r\'esultat n\'egatif).

En cons\'equence, $\prod_{j=0}^{n_h}\bigl(\frac{x_j^2}{x_j^2+1}\bigr)$ 
doit tendre vers $+\infty $ lorsque $h$ tend vers 0, ce qui entra\^\i ne 
aussi 
$$
\Lim_{h\to 0}\bigl|f(2)-\Pi_h^{(2,2)}f(2)\bigr|=+\infty 
\>.$$
Il est clair que la situation est encore pire pour des valeurs 
sup\'erieures de $a$. En revanche, le choix de $\xi =0$ ne produit 
jamais cette situation car alors
$(a+\xi )\ln(a+\xi )+(a-\xi )\ln(a-\xi )-a\ln(a^2+1)-2\arctan a
=a\ln\frac{a^2}{a^2+1}-2\arctan a<0$.

En conclusion, les polyn\^omes d'interpolation ne sont des 
approximations d\'ecentes de la fonction que sur des intervalles 
pas trop longs.

\bye

% Fonction de calcul des coefficients pour la TI 92
intpolco(l,ex,v)
Func
    "l=liste des valeurs en abscisses"
    "ex=expression fonctionnelle"
    "v=variable de l'expression"
Local q,p,pc,i,m,j
    "Appliquer fonction sur liste"
ex|v=l\flechedroite{}p
    "La liste des valeurs est num\'erot\'ee de 1 \`a q+1"
dim(l)-1\flechedroite{}q
    "On stocke les coefficients dans un tableau \`a 2 dimensions"
identity(q+1)-1\flechedroite{}pc
augment((list\triangledroit{}mat(p))\Transpose,pc)\flechedroite{}pc
    "Chaque polyn\^ome a ses coefficients stock\'es en ligne, num\'erot\'es \`a partir de 1."
For m,1,q
For i,m+1,q+1
For j,m+1,2,-1
(l[i]*pc[m,j]-l[m]*pc[i,j]+pc[i,j-1]-pc[m,j-1])/(l[i]-l[m])\flechedroite{}pc[i,j]
EndFor
(l[i]*pc[m,1]-l[m]*pc[i,1])/(l[i]-l[m])\flechedroite{}pc[i,1]
EndFor
EndFor
Return pc[q+1]
EndFunc
