Accueil > Mathématiques > Interpolation > Interpolation polynômiale de type Newton et différences divisées.

Interpolation polynômiale de type Newton et différences divisées.

samedi 3 juin 2006, par Nadir SOUALEM

Mots-clés: base , base de Newton , différences divisées , erreur d’interpolation , interpolation , interpolation polynômiale , Newton , points d’interpolation , polynôme , polynôme d’interpolation , scilab .

Toutes les versions de cet article : [English] [français]

On étudie ici l’interpolation polynômiale de type Newton. Étant données une suite de (n+1) points et une fonction f, on doit déterminer un polynôme de degré n qui interpole f aux points considérés. On utilisera pour cela la notion de différences divisées.

Interpolation

Étant donné points $\{(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)\}$ . Les $(x_i)_{0 \leq i\leq n}$ sont appelés points d’interpolation. Les $(y_i)_{0 \leq i\leq n}$
représentent les valeurs d’interpolation. Pour interpoler une fonction , on définit ces valeurs d’interpolation comme suit :

$y_i=f(x_i), \quad \forall i=0,\ldots,n$

Rappels sur les polynôme d’interpolation de Lagrange

Nous avons vu que le polynôme d’interpolation de Lagrange de degré s’écrivait comme suit :

$P_n(x)= \sum_{k=0}^n l_k(x)f(x_k)$

où les sont des polynômes de degré qui forment une base de $\mathcal{P}_n$

$l_k(x)= \prod_{i=0,\, i\neq k}^{n} \frac{x-x_i}{x_k-x_i}=\frac{x-x_0}{x_k-x_0} \cdots \frac{x-x_{k-1}}{x_k-x_{k-1}} \frac{x-x_{k+1}}{x_k-x_{k+1}} \cdots \frac{x-x_{n}}{x_k-x_{n}}$

De tels polynômes ne sont pas pratiques puisque du point de vue numérique, il est difficile de déduire $l_{k+1}$ de
$l_{k}$ . Pour cela, on introduit le polynôme d’interpolation de Newton.

Propriétés du polynôme d’interpolation de Newton et de la base de Newton

Les polynômes de la base de Newton sont définis comme suit :

$e_k(x)=\prod_{i=0}^{k-1}(x-x_i)=(x-x_0) (x-x_1)\cdots(x-x_{k-1}),\quad k=1,\ldots,n.$

avec pour convention

en outre

$\begin{array}{rcl} e_1&=&(x-x_0)\\ e_2&=&(x-x_0)(x-x_1)\\ e_3&=&(x-x_0)(x-x_1)(x-x_2)\\ \vdots&&\vdots\\ e_n&=&(x-x_0)(x-x_1)\cdots(x-x_{n-1}) \end{array}$

L’ensemble des polynômes $(e_k)_{0 \leq k\leq n}$ (base de Newton) forment une base de l’espace $\mathcal{P}_n$ des polynômes de degré au plus , puisqu’il s’agit d’une famille de
polynômes de degré échelonné.
Le polynôme d’interpolation de Newton de degré relatif à la subdivision $\{(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)\}$ s’écrit :

$\begin{array}{rcl} P_n(x)&=&\displaystyle\sum_{k=0}^n \alpha_k e_k(x)\\ &=& \alpha_0 + \alpha_1(x-x_0)+\alpha_2(x-x_0)(x-x_1)\\ &&+\ldots +\alpha_n(x-x_0)(x-x_1)\cdots(x-x_{n-1}) \end{array}$

avec

$P_n(x_i)=f(x_i),\quad \forall i=0,\ldots,n.$

Il faut alors déterminer les coefficients $(\alpha_k)_{0 \leq k\leq n}$ . C’est l’objet de la prochaine partie intitulée les différences divisées.

Différences divisées

Le polynôme d’interpolation de Newton de degré , évalué en donne :

$P_n(x_0)= \sum_{k=0}^n \alpha_k e_k(x_0)=\alpha_0=f(x_0)=f[x_0]$

De manière générale, on note

$f[x_i]=f(x_i), \quad \forall i=0,\ldots,n$

est appelée différence divisée d’ordre 0.

Le polynôme d’interpolation de Newton de degré , évalué en donne :

$\begin{array}{lll} P_n(x_1)&=&\displaystyle \sum_{k=0}^n \alpha_k e_k(x_1)\\ &=&\alpha_0 + \alpha_1(x_1-x_0)\\ &=&f[x_0] + \alpha_1(x_1-x_0)\\ &=&f[x_1] \end{array}$

d’où

$\alpha_1=\frac{f[x_1]-f[x_0]}{x_1-x_0}=f[x_0,x_1]$

est appelée différence divisée d’ordre 1.

Le polynôme d’interpolation de Newton de degré , évalué en donne :

$\begin{array}{rcl} P_n(x_2)&=&\displaystyle \sum_{k=0}^n \alpha_k e_k(x_2)\\ &=&\alpha_0 + \alpha_1(x_2-x_0) +\alpha_2(x_2-x_0)(x_2-x_1) \\ &=&f[x_0] + f[x_0,x_1](x_2-x_0)+\alpha_2(x_2-x_0)(x_2-x_1) \\ &=&f[x_2] \end{array}$

on a alors :

$\begin{array}{rcl} \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)\\ \alpha_2&=&\displaystyle\frac{f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)}{(x_2-x_0)(x_2-x_1)}\\ \alpha_2&=&\displaystyle\frac{f[x_2]-f[x_0]}{(x_2-x_0)(x_2-x_1)}- \frac{f[x_0,x_1]}{x_2-x_1}\\ \alpha_2&=&\displaystyle\frac{f[x_0,x_2]-f[x_0,x_1]}{x_2-x_1} \end{array}$

on préfère en général l’écriture suivante :

$\begin{array}{rcl} \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)-f[x_1]+f[x_1]\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+f[x_1]-f[x_0] -f[x_0,x_1](x_2-x_0)\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+(x_1-x_0)f[x_0,x_1] -f[x_0,x_1](x_2-x_0)\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+(x_1-x_2)f[x_0,x_1]\\ \alpha_2(x_2-x_0)&=&\displaystyle\frac{f[x_2]-f[x_1]}{x_2-x_1}-f[x_0,x_1]\\ \alpha_2(x_2-x_0)&=&f[x_1,x_2]-f[x_0,x_1] \end{array}$

d’où

$\alpha_2=\displaystyle\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}=f[x_0,x_1,x_2]$

est appelée différence divisée d’ordre 2.
On obtient alors par récurrence :

$\alpha_k=\displaystyle\frac{f[x_1,\ldots,x_k]- f[x_0,\ldots,x_{k-1}]}{x_k-x_0}=f[x_0,\ldots,x_k]$

$f[x_0,\ldots,x_k]$ est alors appelée différence divisée d’ordre .
En pratique lorsqu’on veut déterminer par exemple la différence divisée d’ordre 3
, on a besoins des quantités suivantes

$\left[\begin{array}{ccccc} x_0 & f[x_0] & & & \cr x_1 & f[x_1] & f[x_0,x_1] & & \cr x_2 & f[x_2] & f[x_1,x_2] & f[x_0,x_1,x_2] & \cr x_3 & f[x_3] & f[x_2,x_3] & f[x_1,x_2,x_3] & f[x_0,x_1,x_2,x_3] \end{array}\right]$

puisque

$f[x_0,x_1,x_2,x_3]=\displaystyle\frac{f[x_1,x_2,x_3]- f[x_0,x_1,x_{2}]}{x_3-x_0}$

Propriété. Soit $E=\{0,1,\ldots,n\}$ . Soit $\sigma$ une permutation de $\mathfrak{S}(E)$ , alors

$f[x_{\sigma(0)},\ldots,x_{\sigma(n)}]=f[x_0,\ldots,x_{n}].$

Polynôme d’interpolation de Newton de degré

Le polynôme d’interpolation de Newton de degré s’écrit donc à l’aide des différences divisées successives :

$P_n(x)= f[x_0] + \sum_{k=1}^n f[x_0,\ldots,x_k] e_k(x)$

Erreur d’interpolation

On suppose que $f\in \mathcal{C}^{n}([a,b])$ et $x\in[a,b]$ . Soit le fermé défini par $I=[\min(x,x_0),\max(x,x_n)]$ (le plus petit fermé contenant et les ).

Théorème.

$\exists \xi \in I / f[x_0,\ldots,x_{n}]=\displaystyle\frac{f^{n}(\xi)}{n!}$

Preuve.Soit On a :

$d(x_i)=f(x_i)-P_n(x_i)=0\quad \forall i=0,\ldots,n$

Par application successive du théorème de Rolle( fois), $d^{(n)}(x)$ s’annule en un point $\xi\in I$ :

$d^{(n)}(\xi)=0.$

On a alors :

$f^{(n)}(\xi)=P_n^{(n)}(\xi)$

Or le coefficient de dans est $f[x_0,\ldots,x_{n}]$ , par suite

$f^{(n)}(\xi)=P_n^{(n)}(\xi)=n!\cdot f[x_0,\ldots,x_{n}]$

d’où

$f[x_0,\ldots,x_{n}]=\displaystyle\frac{f^{(n)}(\xi)}{n!}$

On suppose à présent que $f\in \mathcal{C}^{n+1}([a,b])$ et $x\in[a,b]$ . Soit le fermé défini par $I=[\min(x,x_0),\max(x,x_n)]$ (le plus petit fermé contenant et les ).

Théorème.

$\forall x\in [a,b],\quad \exists \xi \in I / f(x)-P_n(x)= \displaystyle\frac{f^{n+1}(\xi)}{(n+1)!} \displaystyle\prod_{i=0}^{n}(x-x_i)$

Preuve. Il existe deux preuves possibles, celle vue dans l’interpolation polynômiale de type Lagrange et la preuve suivante.

Pour le problème est réglé :

Soit $\hat{x}\in[a,b]$ , supposons à présent que $\hat{x}\neq x_i$ . Considérons l’unique polynôme $P_{n+1}$ de degré qui interpole aux points
$\{(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n),(\hat{x},f(\hat{x}))\}$ . $P_{n+1}$ satisfait

$\left\{\begin{array}{rcl} P_{n+1}(x_i)&=&f(x_i),\quad\forall i=0,\ldots,n \\ P_{n+1}(\hat{x})&=&f(\hat{x}). \end{array}\right.$

Le polynôme $P_{n+1}$ s’écrit :

$P_{n+1}(x)=P_{n}(x)+(x-x_0)\ldots(x-x_n)f[x_0,\ldots,x_{n},\hat{x}]$

or d’après le théorème précédent

$f[x_0,\ldots,x_{n},\hat{x}]=\displaystyle\frac{f^{(n+1)}(\xi)}{(n+1)!}$

En posant $x=\hat{x}$ , $P_{n+1}(\hat{x})=f(\hat{x})$ ,

$f(\hat{x})=P_{n}(\hat{x})+(\hat{x}-x_0)\ldots(\hat{x}-x_n)\displaystyle\frac{f^{(n+1)}(\xi)}{(n+1)!}$

$\hat{x}$ étant quelconque le théorème est démontré.

Exemple de calcul de polynôme d’interpolation de Newton

Étant donné 3 points $\{(0,1), (2,5),(4,17)\}$ . Nous allons déterminer le polynôme d’interpolation de Newton de degré 2 passant par ces points.

$\left[\begin{array}{ccccc} x_0=0 & f[x_0]=1 & & & \cr x_1=2 & f[x_1]=5 & f[x_0,x_1]=\displaystyle\frac{5-1}{2-0} = 2& & \cr x_2=4 & f[x_2]=17 & f[x_1,x_2]=\displaystyle\frac{17-5}{4-2}=6 & f[x_0,x_1,x_2]= \displaystyle\frac{6-2}{4-0}=1 & \end{array}\right]$

Par suite :

$\begin{array}{rcl} P_2(x)&=&f[x_0]+f[x_0,x_1]x+f[x_0,x_1,x_2]x(x-2)\\ &=&1+2x+x(x-2)\\ &=&1+x^2 \end{array}$

Scilab : calcul de polynôme d’interpolation de Newton

La fonction Scilab newton.sci permet de déterminer le polynôme d’interpolation de Newton. contient les points d’interpolations et les valeurs d’interpolation,
est le polynôme d’interpolation de Newton calculé à l’aide des différences divisées.

newton.sci

function[P]=newton(X,Y)//X nodes,Y values;P is the numerical Newton polynomial
n=length(X);// n is the number of nodes. (n-1) is the degree
for j=2:n,
  for i=1:n-j+1,Y(i,j)=(Y(i+1,j-1)-Y(i,j-1))/(X(i+j-1)-X(i));end,
end,
x=poly(0,"x");
P=Y(1,n);
for i=2:n, P=P*(x-X(i))+Y(i,n-i+1); end
endfunction;

On a alors :

-->X=[0;2;4]; Y=[1;5;17]; P=newton(X,Y)
 P = 1 + x^2

Un message, un commentaire ?

Si vous souhaitez aider financièrement le projet Math-Linux.com, vous pouvez aider notre équipe. Merci !!!

Links

Interpolation polynômiale de type Newton et différences divisées.

Interpolation

Rappels sur les polynôme d’interpolation de Lagrange

Propriétés du polynôme d’interpolation de Newton et de la base de Newton

Différences divisées

Polynôme d’interpolation de Newton de degré

Erreur d’interpolation

Exemple de calcul de polynôme d’interpolation de Newton

Scilab : calcul de polynôme d’interpolation de Newton

Un message, un commentaire ?

Si vous souhaitez aider financièrement le projet Math-Linux.com, vous pouvez aider notre équipe. Merci !!!

Mathématiques

Dans la même rubrique

Mots-clés