Avancer

Section 7.1 Présentation

Au chapitre 6, on a vu comment calculer la forme de Lagrange

\begin{equation*} y_0\,L_0(t)+y_1\,L_1(t)+\cdots+y_n\,L_n(t) \end{equation*}

du polynôme interpolateur de \(n+1\) points d'abscisses distinctes deux à deux

\begin{equation*} A_0=(x_0;y_0),\;A_1=(x_1;y_1),\;\ldots,\;A_n=(x_n;y_n)\;\in\mathbb{R}^2. \end{equation*}

C'est une technique très simple d'un point de vue théorique, mais elle présente un inconvénient majeur : il faut refaire tous les calculs chaque fois qu'on ajoute un point à interpoler.

Dans ce chapitre, nous nous intéressons à la forme de Newton du polynôme interpolateur

\begin{equation*} d_0+d_1\,N_1(t)+\cdots+d_n\,N_n(t) \end{equation*}

où

\begin{equation*} N_i(t)=(t-x_0)(t-x_1)\cdots(t-x_{i-1}) \end{equation*}

est un polynôme de degré \(i\) pour \(i=1,2,\ldots,n\text{.}\)

Comment calculer les coefficients \(d_i\text{?}\)

Déterminons la forme de Newton du polynôme interpolateur des trois points

\begin{equation*} A_0=(1;-3),\; A_1=(2;7)\;\text{et}\; A_2=(3;0). \end{equation*}

On a

\begin{align*} N(t)&=d_0+d_1\,N_1(t)+d_2\,N_2(t)\\ &=d_0+d_1(t-x_0)+d_2(t-x_0)(t-x_1)\\ &=d_0+d_1(t-1)+d_2(t-1)(t-2) \end{align*}

et on cherche donc trois nombres réels \(d_0,d_1,d_2\) tels que

\begin{equation*} \begin{cases}N(1)=-3,\\N(2)=7,\\N(3)=0,\end{cases} \end{equation*}

ce qui équivaut à résoudre le système triangulaire

\begin{equation*} \begin{cases} d_0&&&&&=&-3,\\ d_0&+&d_1&&&=&7,\\ d_0&+&2d_1&+&2d_2&=&0.\\ \end{cases} \end{equation*}
  • La première équation donne tout de suite \(d_0=-3\text{.}\)

  • La deuxième équation donne \(d_0+d_1=7\text{,}\) d'où

    \begin{align*} -3+d_1&=7,\\ d_1&=7+3=10. \end{align*}

  • La troisième équation donne \(d_0+2d_1+2d_2=0\text{,}\) d'où

    \begin{align*} -3+2\cdot 10+2d_2&=0,\\ 2d_2&=3-20=-17,\\ d_2&=-\frac{17}{2}. \end{align*}

La forme de Newton du polynôme interpolateur de ces trois points est donc

\begin{equation*} N(t)=-3+10(t-1)-\frac{17}{2}(t-1)(t-2). \end{equation*}

Notons pour finir qu'il s'agit bien du même polynôme que celui déjà calculé aux exemples 6.1.3 et 6.1.9. En effet, on a

\begin{align*} N(t)&=-3+10(t-1)-\frac{17}{2}(t-1)(t-2)\\ &=-3+10(t-1)-\frac{17}{2}(t^2-3t+2)\\ &=-3+10t-10-\frac{17}{2}t^2+\frac{51}{2}t-17\\ &=-30+\frac{71}{2}t-\frac{17}{2}t^2. \end{align*}

Il existe un outil qui permet de calculer les coefficients \(d_i\) de la forme de Newton de manière systématique : les différences divisées.

Définition 7.1.2. Différences divisées.

Soit \(n\geq 0\) un entier et

\begin{equation*} A_0=(x_0;y_0),\; A_1=(x_1;y_1),\;\ldots,\; A_n=(x_n;y_n)\;\in\mathbb{R}^2 \end{equation*}

\(n+1\) points d'abscisses distinctes deux à deux.

Voici comment on calcule les différences divisées associées à ces \(n+1\) points quand on sélectionne un, deux, trois, et, plus généralement, \(k\) points parmi ces derniers.

  • Un point :

    \begin{equation*} \left[A_i\right]=y_i \end{equation*}

    pour \(0\leq i\leq n\text{.}\)

  • Deux points :

    \begin{equation*} \left[A_{i_1},A_{i_2}\right]=\frac{\left[A_{i_2}\right]-\left[A_{i_1}\right]}{x_{i_2}-x_{i_1}}=\frac{y_{i_2}-y_{i_1}}{x_{i_2}-x_{i_1}} \end{equation*}

    pour \(0\leq i_1<i_2\leq n\text{.}\)

  • Trois points :

    \begin{equation*} \left[A_{i_1},A_{i_2},A_{i_3}\right]=\frac{\left[A_{i_2},A_{i_3}\right]-\left[A_{i_1},A_{i_2}\right]}{x_{i_3}-x_{i_1}}=\frac{\frac{y_{i_3}-y_{i_2}}{x_{i_3}-x_{i_2}}-\frac{y_{i_2}-y_{i_1}}{x_{i_2}-x_{i_1}}}{x_{i_3}-x_{i_1}} \end{equation*}

    pour \(0\leq i_1<i_2<i_3\leq n\text{.}\)

  • \(k\) points :

    \begin{equation*} \left[A_{i_1},\ldots,A_{i_k}\right]=\frac{\left[A_{i_2},\ldots,A_{i_k}\right]-\left[A_{i_1},\ldots,A_{i_{k-1}}\right]}{x_{i_k}-x_{i_1}} \end{equation*}

    pour \(0\leq i_1<\ldots<i_k\leq n\text{.}\)

Notez que cette définition est récursive : pour calculer une différence divisée de \(k\) points, il faut déjà savoir le faire pour \(k-1\) points.

Soit \(A_0=(1;-3),\;A_1=(2;7)\) et \(A_2=(3;0)\) les trois points de l'exemple 7.1.1. Calculons les différences divisées suivantes :

\begin{equation*} \left[A_0\right],\;\left[A_0,A_1\right]\;\text{et}\;\left[A_0,A_1,A_2\right]. \end{equation*}

  • Pour le premier point :

    \begin{equation*} \left[A_0\right]=y_0=-3. \end{equation*}

  • Pour les deux premiers points :

    \begin{align*} \left[A_0,A_1\right]&=\frac{\left[A_1\right]-\left[A_0\right]}{x_1-x_0}\\ &=\frac{y_1-y_0}{x_1-x_0}\\ &=\frac{7-(-3)}{2-1}\\ &=10. \end{align*}

  • Pour les trois points :

    \begin{align*} \left[A_0,A_1,A_2\right]&=\frac{\left[A_1,A_2\right]-\left[A_0,A_1\right]}{x_2-x_0}\\ &=\frac{\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}\\ &=\frac{\frac{0-7}{3-2}-\frac{7+3}{2-1}}{3-1}\\ &=\frac{-7-10}{2}\\ &=-\frac{17}{2}. \end{align*}

Afin d'exploiter la nature récursive des différences divisées, on peut utiliser la présentation classique qui suit :

\begin{equation*} \begin{array}{c|ccc} x_i&y_i=\left[A_i\right]&\left[A_{i_1},A_{i_2}\right]&\left[A_{i_1},A_{i_2},A_{i_3}\right]\\ \hline\\ 1&-3&&\\ &&\frac{7-(-3)}{2-1}=10&\\ 2&7&&\frac{-7-10}{3-1}=-\frac{17}{2}\\ &&\frac{0-7}{3-2}=-7&\\ 3&0&& \end{array} \end{equation*}

i.e.

\begin{equation*} \begin{array}{c|ccc} x_i&y_i&&\\ \hline\\ x_0=1&\left[A_0\right]=-3&&\\ &&\left[A_0,A_1\right]=10&\\ x_1=2&\left[A_1\right]=7&&\left[A_0,A_1,A_2\right]=-\frac{17}{2}\\ &&\left[A_1,A_2\right]=-7&\\ x_2=3&\left[A_2\right]=0&& \end{array} \end{equation*}
Remarque 7.1.4.

Les trois différences divisées de l'exemple 7.1.3 correspondent aux trois coefficients de la forme de Newton calculés à l'exemple 7.1.1, i.e.

\begin{equation*} d_0=\left[A_0\right],\; d_1=\left[A_0,A_1\right]\;\text{et}\; d_2=\left[A_0,A_1,A_2\right]. \end{equation*}

Autrement dit, la forme de Newton du polynôme interpolateur des trois points \(A_0,A_1,A_2\) est donnée par

\begin{equation*} N(t)=\left[A_0\right]+\left[A_0,A_1\right](t-1)+\left[A_0,A_1,A_2\right](t-1)(t-2). \end{equation*}

Ce n'est pas un hasard, c'est toute la force de l'interpolation newtonienne.

Notons \(P(t)\) le polynôme interpolateur de ces \(n+1\) points et \(N(t)\) le polynôme défini par la formule ci-dessus. Nous allons scinder cette preuve en deux étapes.

  • Étape 1 : Montrer par récurrence sur \(n\) que le coefficient de degré \(n\) de \(P(t)\) est égal à la différence divisée \(\left[A_0,\ldots,A_n\right]\text{.}\)
  • Étape 2 : Montrer par récurrence sur \(n\) que \(P(t)=N(t)\text{.}\)

Commençons donc par l'étape 1. Pour un point (\(n=0\)), la propriété est triviale. Supposons-la donc vérifiée pour \(n\) points et notons alors \(A(t)\) le polynôme interpolateur des \(n\) premiers points \(A_0,\ldots,A_{n-1}\text{,}\) et \(B(t)\) le polynôme interpolateur des \(n\) derniers \(A_1,\ldots,A_n\text{.}\) Par unicité du polynôme interpolateur, on a

\begin{equation*} P(t)=\frac{(t-x_0)B(t)-(t-x_n)A(t)}{x_n-x_0}, \end{equation*}

puisque le terme de droite est un polynôme de degré \(n\) au plus valant \(y_k\) en \(t=x_k\) pour tout \(0\le k\le n\text{.}\) Par hypothèse de récurrence appliquée à \(A(t)\) et à \(B(t)\text{,}\) on en déduit que le coefficent de degré \(n\) dans \(P(t)\) vaut

\begin{equation*} \frac{\left[A_1,\ldots,A_n\right]-\left[A_0,\ldots,A_{n-1}\right]}{x_n-x_0}, \end{equation*}

i.e. \(\left[A_0,\ldots,A_n\right]\text{,}\) d'après la formule de récurrence définissant les différences divisées.

Passons maintenant à l'étape 2. Pour un point (\(n=0\)), la propriété est à nouveau triviale. Supposons-la donc vérifiée pour \(n\) points et notons encore \(A(t)\) le polynôme interpolateur des \(n\) premiers points \(A_0,\ldots,A_{n-1}\text{.}\) Alors le polynôme \(P(t)-A(t)\) est de degré \(n\) au plus, et il s'annule au moins \(n\) fois, en \(x_0,\ldots,x_{n-1}\text{.}\) On a donc la factorisation

\begin{equation*} P(t)-A(t)=\lambda(t-x_0)\cdots(t-x_{n-1}) \end{equation*}

où, d'après l'étape 1, le coefficient \(\lambda\) et égal à \(\left[A_0,\ldots,A_n\right]\text{.}\) En appliquant enfin l'hypothèse de récurrence à \(A(t)\text{,}\) i.e. aux \(n\) premiers points \(A_0,\ldots,A_{n-1}\text{,}\) on obtient bien la formule \(P(t)=N(t)\) pour \(n+1\) points.

Déterminons la forme de Newton \(N(t)\) du polynôme interpolateur des quatre points suivants :

\begin{equation*} A_0=(1;-3),\; A_1=(2;7),\; A_2=(3;0)\;\text{et}\; A_3=(4;5). \end{equation*}

Nous devons calculer les différences divisées suivantes :

\begin{equation*} \left[A_0\right],\;\left[A_0,A_1\right],\;\left[A_0,A_1,A_2\right]\;\text{et}\;\left[A_0,A_1,A_2,A_3\right]. \end{equation*}

Présentons nos calculs dans un tableau :

\begin{equation*} \begin{array}{c|cccc} x_i&y_i&&&\\ \hline\\ 1&\left[A_0\right]=-3&&&\\ &&\left[A_0,A_1\right]=10&&\\ 2&\left[A_1\right]=7&&\left[A_0,A_1,A_2\right]=-\frac{17}{2}&\\ &&\left[A_1,A_2\right]=-7&&\left[A_0,A_1,A_2,A_3\right]=\frac{29}{6}\\ 3&\left[A_2\right]=0&&\left[A_1,A_2,A_3\right]=6&\\ &&\left[A_2,A_3\right]=5&&\\ 4&\left[A_3\right]=5&&&\\ \end{array} \end{equation*}

On a donc

\begin{equation*} N(t)=-3+10(t-1)-\frac{17}{2}(t-1)(t-2)+\frac{29}{6}(t-1)(t-2)(t-3). \end{equation*}
Remarque 7.1.7.

À l'exemple 7.1.6, on a ajouté le point \(A_3=(4;5)\) aux trois points \(A_0=(1;-3),A_1=(2;7)\) et \(A_2=(3;0)\) de l'exemple 7.1.1. La forme de Newton du polynôme interpolateur est alors passée de

\begin{equation*} N(t)=-3+10(t-1)-\frac{17}{2}(t-1)(t-2) \end{equation*}

à

\begin{equation*} N(t)=-3+10(t-1)-\frac{17}{2}(t-1)(t-2)+\frac{29}{6}(t-1)(t-2)(t-3). \end{equation*}

Seul le coefficient \(29/6\) correspondant au terme de degré \(3\) s'est ajouté : à la différence de la forme de Lagrange, la forme de Newton permet d'ajouter un point à interpoler sans avoir à reprendre tous les calculs.

Remarque 7.1.8.

Comparons la forme de Lagrange et la forme de Newton pour le polynôme interpolateur de trois points d'abscisses distinctes deux à deux

\begin{equation*} A_0=(x_0;y_0),\: A_1=(x_1;y_1)\;\text{et}\; A_2=(x_2;y_2). \end{equation*}

Voici sa forme de Lagrange :

\begin{align*} L(t)&=y_0\,L_0(t)+y_1\,L_1(t)+y_2\,L_2(t)\\ &=y_0\frac{(t-x_1)(t-x_2)}{(x_0-x_1)(x_0-x_2)}+y_1\frac{(t-x_0)(t-x_2)}{(x_1-x_0)(x_1-x_2)}+y_2\frac{(t-x_0)(t-x_1)}{(x_2-x_0)(x_2-x_1)}. \end{align*}

Et voilà sa forme de Newton :

\begin{align*} N(t)&=\left[A_0\right]+\left[A_0,A_1\right](t-x_0)+\left[A_0,A_1,A_2\right](t-x_0)(t-x_1)\\ &=y_0+\frac{y_1-y_0}{x_1-x_0}\cdot(t-x_0)+\frac{\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}\cdot(t-x_0)(t-x_1). \end{align*}

Pour évaluer la forme de Lagrange écrite ainsi, on a besoin de \(14\) additions / soustractions et de \(12\) multiplications / divisions. Quant à la forme de Newton, elle requiert \(13\) additions / soustractions et \(7\) multiplications / divisions. C'est nettement mieux, et cela peut encore être amélioré en appliquant la méthode de Horner :

\begin{equation*} N(t)=y_0+(t-x_0)\cdot\left(\frac{y_1-y_0}{x_1-x_0}+\frac{\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}\cdot(t-x_1)\right). \end{equation*}

On tombe alors à \(12\) additions / soustractions et \(6\) multiplications / divisions.

Forme de Newton et différences divisées : Calculer efficacement un polynôme interpolateur.
  • Objectif : Étant donné \(n+1\) points \(A_0=(x_0;y_0),\ldots,A_n=(x_n;y_n)\) d'abscisses distinctes deux à deux, déterminer le seul polynôme \(N(t)\) de degré \(n\) au plus qui passe par tous ces points.

  • Principe : Construire \(N(t)\) comme combinaison linéaire des polynômes

    \begin{equation*} N_i(t):=(t-x_0)(t-x_1)\cdots(t-x_{i-1}) \end{equation*}

    en posant

    \begin{equation*} N(t):=d_0+d_1\,N_1(t)+\cdots+d_n\,N_n(t) \end{equation*}

    où le coefficient \(d_i\) est la différence divisée associée aux points \(A_0=(x_0;y_0),\ldots,A_i=(x_i;y_i)\text{,}\) c'est-à-dire

    \begin{equation*} d_i=\left[A_0,\ldots,A_i\right] \end{equation*}

  • Terminologie : On appelle \(d_0+d_1\,N_1(t)+\cdots+d_n\,N_n(t)\) la forme de Newton du polynôme interpolateur des points \(A_0,A_1,\ldots,A_n\text{.}\) Il s'agit du même polynôme que celui obtenu par interpolation de Lagrange, mais écrit différemment.

  • Avantages :

    • À la différence de la forme de Lagrange, la forme de Newton permet d'ajouter un point d'interpolation sans avoir à reprendre tous les calculs.
    • Grâce à la technique des différences divisées, le calcul de la forme de Newton nécessite moins d'opérations que celui de la forme de Lagrange.
  • Voir aussi : Notes de cours de Jérôme.