Interpolation polynomiale de type Newton et différences divisées.
On étudie ici l’interpolation polynomiale de type Newton. Etant données une suite de (n+1) points et une fonction f, on doit déterminer un polynome 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 polynome d’interpolation de Lagrange
Nous avons vu que le polynome 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 polynomes 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 polynomes 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 polynome d’interpolation de Newton.
Propriétés du polynome d’interpolation de Newton et de la base de Newton
- Les polynomes $e_k$ de la base de Newton sont définis comme suit:
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 polynomes $(e_k)_{0 \leq k\leq n}$(base de Newton) forment une base de l’espace $\mathcal{P}_n$ des polynomes de degré au plus $n$, puisqu’il s’agit d’une famille de $(n+1)$ polynomes de degré échelonné.
- Le polynome 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:
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 polynome 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 polynome 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 polynomiale de type Lagrange->article40] 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 polynome $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 polynome $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 polynome d’interpolation de Newton
étant donné 3 points ${(0,1), (2,5),(4,17)}$. Nous allons déterminer le polynome 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 polynome d’interpolation de Newton
La fonction Scilab newton.sci permet de déterminer le polynome d’interpolation de Newton. $X$ contient les points d’interpolations et $Y$ les valeurs d’interpolation, $P$ est le polynome d’interpolation de Newton calculé à l’aide des différences divisées.
newton.sci
On a alors:
Si vous avez trouvé cet article ou ce site utile et souhaitez soutenir notre travail, veuillez envisager de faire un don. Merci !
Aidez-nous