Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

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.

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é (n+1) 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 f, 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é n s’écrivait comme suit :

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


o๠les l_k sont des polynà´mes de degré n 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 e_k 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

e_0=1


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 n, puisqu’il s’agit d’une famille de
(n+1) polynà´mes de degré échelonné.
- Le polynà´me d’interpolation de Newton de degré n 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é n, P_n(x) évalué en x_0 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


f[x_0] est appelée différence divisée d’ordre 0.

Le polynà´me d’interpolation de Newton de degré n, P_n(x) évalué en x_1 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]


f[x_0,x_1] est appelée différence divisée d’ordre 1.

Le polynà´me d’interpolation de Newton de degré n, P_n(x) évalué en x_2 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]


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 k.
En pratique lorsqu’on veut déterminer par exemple la différence divisée d’ordre 3
f[x_0,x_1,x_2,x_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é n

Le polynà´me d’interpolation de Newton de degré n 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 I le fermé défini par I=[\min(x,x_0),\max(x,x_n)] (le plus petit fermé contenant x et les x_i).

Théorème.

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


Preuve.Soit d(x)=f(x)-p(x). 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(n 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 x^n dans P_n 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 I le fermé défini par I=[\min(x,x_0),\max(x,x_n)] (le plus petit fermé contenant x et les x_i).

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 x=x_i le problème est réglé :

f(x)-P_n(x)=f(x_i)-P_n(x_i)=0.


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é (n+1) qui interpole f 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. X contient les points d’interpolations et Y les valeurs d’interpolation, P
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 ?

comments powered by Disqus