Soit $f: I \to \R$ une fonction connue seulement en  $n+1$ 
points $x_0$, $x_1$, \ldots, $x_n$, 
tous dans $I$. Ce sont par exemples les points 
en lesquels la fonction $f$ a pu être évaluée.
Peut-on déterminer un polynôme $p$ de degré au plus égal à $n$ prenant les 
mêmes valeurs que la fonction $f$ en $x_0$, $x_1$, \ldots, $x_n$.
Si un tel polynôme $p$ existe, on dit alors que $p$ interpole $f$ aux points 
(au n{\oe}uds) $x_0$, $x_1$, \ldots, $x_n$.

\section{Formalisation du problème}
\begin{Def}[Interpolation]
  On dit qu'un polynôme $p$ de degré $n$ interpole $f$ aux points
  $x_0$, $x_1$, \ldots, $x_n$ si pour tout $i$, $0 \le i \le n$, on a 
  $p(x_i) = f(x_i)$.
\end{Def}



\begin{Prop}[Unicité du polynome d'interpolation]
Si $p$ de degré inférieur ou égal à $n$ interpole $f$ en 
$x_0$, $x_1$, \ldots, $x_n$, alors $p$ est unique.
\end{Prop}

\begin{Def}[Base de Lagrange]
  On appelle base de Lagrange associée au support 
  $\{x_0, x_1, \ldots, x_n\}$ l'ensemble des polynômes $l_i$, 
  $0 \le i \le n $ définis par 
  $$
  l_i = \prod_{
    \begin{scriptsize}
    \begin{array}{ll} 
        j = 0 \\ 
      j \neq i
    \end{array}
  \end{scriptsize}
}^n
\dfrac{x - x_j}{x_i - x_j}
  $$
\end{Def}

\begin{Prop}[Existence du polynome d'interpolation]
  Le polynôme $p$ défini par 
  $p(x) = \sum_{i=0}^n f(x_i)l_i(x)$, où les $l_i$ forment la base de Lagrange,  
  interpole $f$ 
  en $x_0$, $x_1$, \ldots, $x_n$.
  On parle d'\emph{interpolation de Lagrange} dans ce cas.
\end{Prop}

\begin{Exo}
Montrer les résultats suivants:
\begin{enumerate}
\item Le polynôme de degré 0 qui interpole $f$ en $x_0$ est donné par 
  $p(x) = f(x_0)$.
\item Soit $x_0$ et $x_1$ deux réels distincts.
  Le polynôme de degré inférieur 1 qui interpole $f$ en $x_0$ et $x_1$ 
  est donné par  $p(x) = f(x_0) + \frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)$.
\end{enumerate}
\end{Exo}

\section{Détermination efficace du polynôme d'interpolation}
On peut écrire le polynôme $p$ qui interpole $f$ 
en $x_0$, $x_1$, \ldots, $x_n$ sous sa forme \og de Newton \fg{} 
$$
p(x) = \sum_{i=0}^n d_i \left[  \prod_{j=0}^{i-1} (x - x_j)\right],
$$
où les $d_i$ sont à déterminer.

On peut alors démontrer le résultat suivant. 

\begin{Prop}[Construction iterrative selon la forme de Newton]
Pour tout $k \in \{1, \ldots, n\}$, on a:
$$p_i(x) = p_{i-1}(x) + d_i  \left[  \prod_{j=0}^{i-1} (x - x_j)\right].$$
\end{Prop}

Ainsi pour obtenir $p$ sur $x_0$, $x_1$, \ldots, $x_n$, il suffit:
\begin{itemize}
\item de calculer $d_0$, pour définir $p_0$ qui interpole $f$ sur $x_0$,
\item de calculer $d_1$, pour définir $p_1$  qui interpole $f$ sur $x_0$ 
  et $x_1$,
\item \ldots
\item de calculer $d_n$, pour définir $p_n$  qui interpole $f$ sur 
  $x_0$, $x_1$, \ldots, $x_n$.
\end{itemize}

Le coefficient $d_i$ est le coefficient dominant de $p_i$: il dépend 
de $f$ et de $x_0$, $x_1$, \ldots, $x_i$. On appelle ce nombre la 
\og différence divisée\fg{} et on le note $d_i = f[x_0, \ldots,x_i]$.
On admettra la méthode suivante pour calculer la table des différences 
divisées.


\begin{Prop}[Calcul des différences divisées]
On a:
\begin{enumerate}
\item $f[x_i] = f(x_i)$ pour tout $i \in \{0, \ldots, n\}$;
\item $f[x_i,x_{i+1}, \ldots, x_{i+j}] = 
  \dfrac{f[x_{i+1}, \ldots, x_{i+j}]- f[x_i,x_{i+1}, \ldots, x_{i+j-1}]}{x_{i+j}-x_{i}}$
\end{enumerate}
Ainsi on obtient:
$$
\begin{array}{llllll}
x_0 & \bf{f[x_0]} & \bf{f[x_0,x_1]} & \bf{f[x_0,x_1,x_2]} & \ldots & 
\bf{f[x_0,x_1,x_2,x_3\ldots,x_n]}\\
x_1 & f[x_1]      & f[x_1,x_2]         &  \ldots & f[x_1,x_2,x_3,\ldots,x_n] \\
\ldots \\
x_{n-1} & f[x_{n-1}] & f[x_{n-1},x_n]\\
x_n & f[x_n]
\end{array} 
$$
\end{Prop}


Les coefficients sur la première ligne fournissent les coefficients 
de la forme de Newton de $p_n$ relative aux centres 
$x_0$, \ldots $x_{n}$:
$p_n(x) = 
f[x_0] + f[x_0,x_1](x-x_0) +  f[x_0,x_1,x_2](x-x_0)(x-x_1) + \ldots
+ f[x_0,\ldots,x_n](x-x_0)(x-x_1)\ldots(x-x_{n-1})
$

\begin{Exo}
On donne trois valeurs d'une fonction $f$ définie sur $[1,6]$:
$f(1) = 1,5709$,  
$f(4) = 1,5727$ et   
$f(6) = 1,5751$.  
\begin{enumerate}
\item En utilisant les polynômes de Lagrange relatifs au support $\{1,4\}$,
fournir une valeur approchée de $f(3,5)$ grâce au polynôme d'interpolation 
de $f$ de degré un.
\item En utilisant les polynômes de Lagrange relatifs au support $\{1,4,6\}$,
fournir une valeur approchée de $f(3,5)$ grâce au polynôme d'interpolation 
de $f$ de degré deux.
\item Traiter de nouveau ces deux questions en utilisant une forme de Newton.
\item Comparer ces deux méthodes et conclure.
\end{enumerate}
\end{Exo}



\begin{TP}[Première interpolation]
\begin{enumerate}
\item Construire l'algorithme qui:
\begin{itemize}
\item prend en entrée $x_0, \ldots,x_n$ et $f(x_0), \ldots, f(x_n)$;
\item retourne la matrice \verb+diff_div+ de taille $(n+1)\times(n+1)$ telle
que \verb+diff_div[i][j]+$=f[x_i, \ldots,x_{i+j}]$ pour 
$i\in\{0,\ldots,n\}$ et $j\in \{0, \ldots, n-i\}$ comme définie
dans la proposition précédente.
\end{itemize}
\item Dans le cadre d'un processus industriel, on a noté le temps d'exécution 
$T(n)$ d'un algorithme sur des données de taille $n$ dans le tableau suivant:
$$
\begin{array}{|l||l|l|l|}
\hline 
n & 10 & 25 & 60 \\
\hline
T(n) & 2,3 & 8,0 & 24,6 \\
\hline
\end{array}
$$
\begin{enumerate}
\item Déterminer le polynôme $p$ d'interpolation de $T$ sur le support
$\{10,25,60\}$ en utilisant la méthode développée à la première partie.
\item En déduire le temps $T(n)$ pour un traitement de données de 
taille $n$, avec $n \in \{15,40,100\}$.
\item Représenter le tracé de $p$.
\end{enumerate}
\end{enumerate}
\end{TP}

\begin{TP}[Choix du support]
L'objectif du TP est de montrer que des points régulièrement répartis sur 
un support contraint peu le polynôme sur les bords de celui-ci.
Ainsi l'approximation peu s'en trouver dégradée sur les bords.

On se place sur $[a,b]= [-1,1]$ et on considère deux 
interpolations de $f(x)=e^x$ correspondant à deux choix de supports.
\begin{enumerate}
\item Premier choix: Pour tout $i \in \{0,\ldots,8\}$, on construit 
  $x_i = -1 + 0,25i$.
\begin{enumerate}
\item Déterminer le polynôme $p_1$ d'interpolation de $f$ sur 
  $\{x_0,\ldots,x_8\}$ à l'aide de la méthode développée au TP précédent.
\item Représenter $p_1$ en faisant apparaître les points d'abscisse $x_0$,\ldots, 
$x_8$.
\item Représenter la fonction $e_1(x) = | f(x)-p_1(x) |$  pour tout $x\in[-1,1]$. 
\end{enumerate}
\item Second choix: Pour tout $i \in \{0,\ldots,8\}$, on construit 
  $t_i = \cos(\frac{\pi}{2}\frac{2i+1}{9})$.
\begin{enumerate}
\item Déterminer le polynôme $p_2$ d'interpolation de $f$ sur 
  $\{t_0,\ldots,t_8\}$ à l'aide de la méthode développée au TP précédent.
\item Représenter $p_2$ en faisant apparaître les points d'abscisse 
  $t_0$,\ldots, $t_8$.
\item Représenter la fonction $e_2(x) = | f(x)-p_2(x) |$  pour tout $x\in[-1,1]$. 
\end{enumerate}
\item Conclure
\end{enumerate}
\end{TP}
