%
%
% Cours Interpolation Polynomiale
%
%
%
\documentclass{article}

\usepackage{amsfonts,amsmath}

\usepackage[latin1]{inputenc} % accents 8 bits dans le fichier
\usepackage[T1]{fontenc}      % accents codés dans la fonte

\newtheorem{thm}{Théorème}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollaire}
\newtheorem{expl}{Exemple}
\newtheorem{defi}{Définition}
\newtheorem{propri}{Propriété}
\newtheorem{nota}{Notation}
\newtheorem{rem}{Remarque}

\title{Interpolation polynomiale : cours à reproduire lors du TP Latex numéro 3}
\author{}
\date{le 8 février 2012}

\begin{document}
 
\maketitle

Soit $n$ un entier. 
Afin d'alléger les notations, 
$\mathbb{P}_n$ désigne l'espace des polynômes 
à coefficients réels de degré inférieur ou égal à $n$. 
Rappelons que $\mathbb{P}_n$ est un 
$\mathbb{R}$-espace vectoriel de dimension $n+1$.


\section{Motivation} 
%
%
Considérons $n+1$ points $(x_0,y_0), (x_1,y_1), \ldots , (x_n,y_n)$ du plan $\mathbb{R}^2$, d'abscisses distinctes deux à deux. 


\begin{expl}
%
Dans le contexte des sciences expérimentales, 
ces données peuvent provenir d'une expérience, 
par exemple la température $y$ (en degrés) 
en fonction du temps $x$ (en heures).
%
\begin{center}
\begin{tabular}{|*{3}{c|}}
   \hline
   $i$ & $x_i$  & $y_i$ \\
   \hline
   $0$ &   $0$  &   $5$ \\
   $1$ &   $6$  &  $10$ \\
   $2$ &  $12$  &  $19$ \\
   $3$ &  $18$  &  $18$ \\
   \hline
\end{tabular}
\end{center}
%
\end{expl}



Nous voulons représenter le phénomène observé 
par une fonction $P$ polynômiale. 
Ce polynôme doit vérifier 
\begin{equation}
P(x_i)=y_i, \; \forall i=0,\ldots,n . 
\end{equation}





\section{Le polynôme de Lagrange}
%
%
%
Pour $i \in \left\{0,\ldots,n\right\}$, définissons le polynôme $\ell_i$ par : 
%
\begin{equation}
  \ell_i(x) = 
  \prod_{ j=0,\ldots,n , ~ j \neq i } \frac{x-x_j}{x_i-x_j} . 
\end{equation}

Le polynôme $\ell_i$ est de degré $n$ exactement. 
Soit $k \in \left\{0,\ldots,n\right\}$, il vérifie
%
\begin{equation}
  \ell_i(x_k) = 
  \left\{ 
  \begin{array}{l} 
    0 \; \text{si} \; k \neq i \\ 
    1 \; \text{si} \; k = i 
  \end{array} 
  \right. 
\end{equation}

Posons 
%
\begin{equation}
  \label{eq:poly_interp_langrange}
   p_n(x) = \sum_{i=0}^{n} y_i \ell_i(x) .
\end{equation}
%
Le polynôme $p_n$ est de degré inférieur ou égal à $n$. 
Soit $k \in \left\{0,\ldots,n\right\}$, il vérifie
%
\begin{equation}
  p_n(x_k) = \sum_{i=0}^{n} y_i \delta_{i\,k} = y_k . 
\end{equation}



\begin{thm}
%
\label{thm:poly_interp_lagrange}
%
Soient $n+1$ points $(x_0,y_0), (x_1,y_1), \ldots , (x_n,y_n)$ du plan $\mathbb{R}^2$, d'abscisses distinctes deux à deux. 
Il existe un \textbf{unique} polynôme $p \in \mathbb{P}_n$ tel que 
%
\begin{equation}
  \label{eq:poly_interp} 
  p(x_i) = y_i, \; \forall i \in \left\{0,\ldots,n\right\} , 
\end{equation}
%
c'est le polynôme $p_n$ défini par~\eqref{eq:poly_interp_langrange}. 
Il est appelé \textbf{polynôme d'interpolation de Lagrange} aux points $(x_i,y_i)$, $i=0,\ldots,n$. 
%
\end{thm}



\begin{rem}
Il existe une infinité de polynôme $p$ vérifiant~\eqref{eq:poly_interp}, par exemple : 
$$
  p(x) = p_n(x) + \lambda \prod_{i=0}^{n} (x-x_i), 
$$
où $p_n$ est le polynôme d'interpolation de Langrange aux points $x_i, \; i=0, \ldots, n$ et $\lambda$ est un réel quelconque. 
\end{rem}



\begin{rem}
Lorsque les points $x_i$ sont distincts deux à deux, 
l'ensemble $\mathcal{B}=\left\{ \ell_0, \ldots, \ell_n  \right\}$ 
est une \textbf{base} de $\mathbb{P}_n$, 
appellée \textbf{base de Lagrange} associée aux points 
$x_0, \ldots, x_n$. 
\end{rem}




\section{Forme de Newton du polynôme d'interpolation}
%
Soit $f$ une fonction définie sur un intervalle $I$ 
contenant les abscisses $x_i, \, i=0,\ldots,n$.



\begin{nota} 
Soient $k \in \left\{ 0, \ldots, n \right\}$ et $i$ entier inférieur ou égal à $k$. 
Le polynôme d'interpolation de Lagrange de $f$ aux points $x_i, \ldots, x_k$ est noté : 
\begin{equation*}
  p_{i \to k} .   
\end{equation*}
Lorsque $i=0$, on note
\begin{equation*}
  p_k = p_{0 \to k} .
\end{equation*}
\end{nota}



\begin{defi}
Soient $k \in \left\{ 0, \ldots, n \right\}$ et $i$ entier inférieur ou égal à $k$. Le polynôme $p_{i \to k}$ est de degré inférieur ou égal à $k-i$
\begin{equation*}
  p_{i \to k} \in \mathbb{P}_{k-i} .  
\end{equation*}
On note $f[x_i, \ldots, x_k]$ le coefficient dans $p_{i \to k}$ qui porte sur $x^{k-i}$. 
Ce coefficient est appelé \textbf{différence divisée} d'ordre $k-i$.
\end{defi}



\begin{rem}
Les différences divisées d'ordre $0$ sont données par 
\begin{equation}
  \label{eq:def_diff_div_0}
  f[x_i] = f(x_i), \; \forall i=0, \ldots, n .
\end{equation}
\end{rem}



Soit $k \in \left\{1,\ldots,n\right\}$, le polynôme $q_k = p_k - p_{k-1} \in \mathbb{P}_k$ et vérifie $q_k(x_i) = 0, \; \forall i \in \left\{0,\ldots,k-1\right\}$. 
Il s'ensuit que 
\begin{equation*}
  q_k(x) = C (x-x_0) \ldots (x-x_{k-1}) , 
\end{equation*}
où $C$ est une constante réelle. 
La constante $C$ est le coefficient qui porte sur $x^k$ dans $q_k$, c'est le même que dans $p_k$. 
On a donc : 
\begin{equation}
  \label{eq:def_diff_div_k}
  p_k(x) = p_{k-1}(x) + f[x_0,\ldots,x_k] \prod_{i=0}^{k-1}(x-x_i) , 
\end{equation}



\begin{defi}
On déduit des relations~\eqref{eq:def_diff_div_0} et~\eqref{eq:def_diff_div_k} que 
\begin{equation}
  \label{eq:forme_de_newton}
  p_n(x) = f[x_0] + \sum_{k=1}^{n} f[x_0,\ldots,x_k] \prod_{i=0}^{k-1}(x-x_i) .
\end{equation}
Cette décomposition est appelée \textbf{forme de Newton} du polynôme d'interpolation. 
\end{defi}



\begin{defi}
Les polynômes
\begin{equation}
  \label{eq:polynome_newton}
  N_k(x) = \prod_{i=0}^{k-1}(x-x_i)
\end{equation}
sont appelés \textbf{polynômes de Newton}. 
L'ensemble $\mathcal{C}=\left\{N_k , \; k=0, \ldots, n  \right\}$ 
est une \textbf{base} de $\mathbb{P}_n$, 
appellée \textbf{base de Newton}
\end{defi}



\begin{thm}
\label{thm:diff_div}
Soient $k \in \left\{ 1, \ldots, n \right\}$ et $i$ entier inférieur à $k$. On a la relation suivante : 
\begin{equation*}
  f[x_i, \ldots, x_k] = \frac{f[x_{i+1}, \ldots, x_k] - f[x_i, \ldots, x_{k-1}]}{x_k-x_i} .
\end{equation*}
\end{thm}






\begin{prop}
En factorisant la forme de Newton~\eqref{eq:forme_de_newton}, 
il vient : 
$$
p_n(x) = f[x_0] + (x-x_0) \bigg( 
f[x_0,x_1] + (x-x_1) \Big( 
\ldots \big( f[x_0,\ldots,x_{n-1}] + (x-x_{n-1}) f[x_0,\ldots,x_{n}] \big) \Big) \bigg) .
$$
L'algorithme de H\"orner s'écrit 
\begin{itemize}
\item Initialisation : 
$$
  p \leftarrow f[x_0,\ldots,x_{n}]
$$
\item Pour $k$ décroissant de $n-1$ à $0$ faire :
$$
  p \leftarrow f[x_0,\ldots,x_{k}] + (x-x_k) ~ p . 
$$
\end{itemize}
\end{prop}




\end{document}


