Mathématiques et algorithmique

1. On a \(\left[A_2\right]=-2\text{.}\)

2. On calcule

   \begin{equation*} \left[A_2,A_3\right]=\frac{\left[A_3\right]-\left[A_2\right]}{x_3-x_2}=\frac{4+2}{7-4}=2. \end{equation*}

3. On connait déjà

   \begin{equation*} \left[A_0,A_1\right]=\frac{1}{2}\quad\text{et}\quad=\left[A_1,A_2\right]=-9. \end{equation*}

   On calcule alors

   \begin{equation*} \displaystyle\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{-9-\frac{1}{2}}{4+1}=-\frac{19}{10}. \end{equation*}

4. On a

   \begin{equation*} \begin{array}{c|cccc} x_i&y_i&&&\\ \hline\\ -1&5&&&\\ &&\frac{1}{2}&&\\ 3&7&&-\frac{19}{10}&\\ &&-9&&\frac{\frac{11}{4}+\frac{19}{10}}{7+1}=\frac{93}{160}\\ 4&-2&&\frac{2+9}{7-3}=\frac{11}{4}&\\ &&2&&\\ 7&4&&&\\ \end{array} \end{equation*}

Commençons par calculer \(\left[A,B,C\right]\) :

Calculons ensuite \(\left[C,A,B\right]\) :

On a bien

1. La forme de Newton du polynôme interpolateur de ces trois points s'écrit

   \begin{align*} N(t)&=d_0+d_1(t-x_0)+d_2(t-x_0)(t-x_1)\\ &=d_0+d_1t+d_2t(t-2). \end{align*}

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

   \begin{equation*} \begin{cases}N(0)=4,\\N(2)=-1,\\N(5)=12,\end{cases} \end{equation*}

   i.e.

   \begin{equation*} \begin{cases} d_0&&&&&=&4,\\ d_0&+&2d_1&&&=&-1,\\ d_0&+&5d_1&+&15d_2&=&12. \end{cases} \end{equation*}

   Ce système linéaire est déjà triangulé.

   • La première équation donne \(d_0=4\text{.}\)

   • La deuxième équation donne

     \begin{equation*} d_0+2d_1=-1\text{,} \end{equation*}

     d'où

     \begin{align*} 4+2d_1&=-1,\\ 2d_1&=-5,\\ d_1&=-\frac{5}{2}. \end{align*}

   • La troisième équation donne

     \begin{equation*} d_0+5d_1+5d_2=0\text{,} \end{equation*}

     d'où

     \begin{align*} 4-\frac{25}{2}+15d_2&=12,\\ 15d_2&=12-4+\frac{25}{2}=\frac{41}{2},\\ d_2&=\frac{41}{30}. \end{align*}

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

   \begin{equation*} N(t)=4-\frac{5}{2}t+\frac{41}{30}t(t-2). \end{equation*}

2. Calculons les différences divisées des trois points :

   \begin{equation*} \begin{array}{c|ccc} x_i&y_i\\ \hline\\ 0&\left[A_0\right]=4&&\\ &&\left[A_0,A_1\right]=-\frac{5}{2}&\\ 2&\left[A_1\right]=-1&&\left[A_0,A_1,A_2\right]=\frac{41}{30}\\ &&\left[A_1,A_2\right]=\frac{13}{3}&\\ 5&\left[A_2\right]=12&& \end{array} \end{equation*}

   On trouve donc les mêmes coefficients qu'à la question précédente.

1. La forme de Newton du polynôme interpolateur de ces trois points s'écrit

   \begin{align*} N(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*}

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

   \begin{equation*} \begin{cases}N(1)=3,\\N(2)=6,\\N(3)=9\end{cases} \end{equation*}

   i.e.

   \begin{equation*} \begin{cases} d_0&&&&&=&3,\\ d_0&+&d_1&&&=&6,\\ d_0&+&2d_1&+&2d_2&=&9. \end{cases} \end{equation*}

   Ce système linéaire est déjà triangulé.

   • La première équation donne \(d_0=3\text{.}\)

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

     \begin{align*} 3+d_1&=6,\\ d_1&=3. \end{align*}

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

     \begin{align*} 3+6+2d_2&=9,\\ 2d_2&=0,\\ d_2&=0. \end{align*}

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

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

2. Calculons les différences divisées des trois points :

   \begin{equation*} \begin{array}{c|ccc} x_i&y_i\\ \hline\\ 1&\left[A_0\right]=3&&\\ &&\left[A_0,A_1\right]=3&\\ 2&\left[A_1\right]=6&&\left[A_0,A_1,A_2\right]=0\\ &&\left[A_1,A_2\right]=3&\\ 3&\left[A_2\right]=9&& \end{array} \end{equation*}

   On trouve donc les mêmes coefficients qu'à la question précédente.

Remarque : En regardant les trois points à interpoler de plus près, on s'aperçoit qu'il sont alignés car ils appartiennent tous les trois à la droite d'équation

Leur polynôme interpolateur est donc le polynôme dont le graphe correspond à cette droite, c'est-à-dire

Pour donner sa forme de Newton, il suffit d'effectuer la transformation algébrique suivante :

La forme de Newton du polynôme interpolateur de ces quatre points s'écrit

On cherche donc quatre nombres réels \(d_0,d_1,d_2,d_3\) tels que

i.e.

Le système correspondant aux trois premières équations a déjà été résolu à l'exercice 7.3.4, donc

La quatrième équation donne \(d_0+3d_1+6d_2+6d_3=0\text{,}\) d'où

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

1. On a

   \begin{align*} L(t)&=y_0\,L_0(t)+y_1\,L_1(t)+y_2\,L_2(t)+y_3\,L_3(t)\\ &=0\,L_0(t)+3\,L_1(t)-L_2(t)+7\,L_3(t)\\ &=3\frac{(t+2)(t-2)(t-3)}{(-1+2)(-1-2)(-1-3)}-\frac{(t+2)(t+1)(t-3)}{(2+2)(2+1)(2-3)}\\ &\qquad +7\frac{(t+2)(t+1)(t-2)}{(3+2)(3+1)(3-2)}\\ &=\frac{1}{4}(t+2)(t-2)(t-3)+\frac{1}{12}(t+2)(t+1)(t-3)\\ &\qquad +\frac{7}{20}(t+2)(t+1)(t-2). \end{align*}

2. Calculons les différences divisées de ces quatre points :

   \begin{equation*} \begin{array}{c|cccc} x_i&y_i&&&\\ \hline\\ -2&0&&&\\ &&3&&\\ -1&3&&-\frac{13}{12}&\\ &&-\frac{4}{3}&&\frac{41}{60}\\ 2&-1&&\frac{28}{12}&\\ &&8&&\\ 3&7&&&\\ \end{array} \end{equation*}

   La forme de Newton de leur polynôme interpolateur est donc

   \begin{align*} N(t)&=0+3(t+2)-\frac{13}{12}(t+2)(t+1)+\frac{41}{60}(t+2)(t+1)(t-2)\\ &=3(t+2)-\frac{13}{12}(t+2)(t+1)+\frac{41}{60}(t+2)(t+1)(t-2). \end{align*}

3. C'est fastidieux. Cliquez ici pour une preuve visuelle avec Desmos.

1. Calculons les différences divisées des trois points :

   \begin{equation*} \begin{array}{c|ccc} x_i&y_i\\ \hline\\ -2&3&&\\ &&\frac{-3-3}{1+2}=-2&\\ 1&-3&&\frac{\frac{5}{6}+2}{7+2}=\frac{17}{54}\\ &&\frac{2+3}{7-1}=\frac{5}{6}&\\ 7&2&& \end{array} \end{equation*}

   Donc

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

2. Calculons les différences divisées des trois points :

   \begin{equation*} \begin{array}{c|ccc} x_i&y_i\\ \hline\\ -2&-2&&\\ &&\frac{2+2}{-1+2}=4&\\ -1&2&&\frac{\frac{5}{6}-4}{5+2}=-\frac{19}{42}\\ &&\frac{7-2}{5+1}=\frac{5}{6}&\\ 5&7&& \end{array} \end{equation*}

   Donc

   \begin{equation*} P(t)=-2+4(t+2)-\frac{19}{42}(t+2)(t+1). \end{equation*}

3. Calculons les différences divisées de ces quatre points :

   \begin{equation*} \begin{array}{c|cccc} x_i&y_i&&&\\ \hline\\ 1&3&&&\\ &&\frac{-3-3}{2-1}=-6&&\\ 2&-3&&\frac{-1+6}{4-1}=\frac{5}{3}&\\ &&\frac{-5+3}{4-2}=-1&&\frac{\frac{14}{3}-\frac{5}{3}}{5-1}=\frac{3}{4}\\ 4&-5&&\frac{13+1}{5-2}=\frac{14}{3}&\\ &&\frac{8+5}{5-4}=13&&\\ 5&8&&&\\ \end{array} \end{equation*}

   Donc

   \begin{equation*} P(t)=3-6(t-1)+\frac{5}{3}(t-1)(t-2)+\frac{3}{4}(t-1)(t-2)(t-4). \end{equation*}

4. Calculons les différences divisées de ces quatre points :

   \begin{equation*} \begin{array}{c|cccc} x_i&y_i&&&\\ \hline\\ -1&3&&&\\ &&\frac{7-3}{4+1}=\frac{4}{5}&&\\ 4&7&&\frac{-5-\frac{4}{5}}{6+1}=-\frac{29}{35}&\\ &&\frac{-3-7}{6-4}=-5&&\frac{\frac{25}{24}+\frac{29}{35}}{10+1}=\frac{1571}{9240}\\ 6&-3&&\frac{\frac{5}{4}+5}{10-4}=\frac{25}{24}&\\ &&\frac{2+3}{10-6}=\frac{5}{4}&&\\ 10&2&&&\\ \end{array} \end{equation*}

   Donc

   \begin{equation*} P(t)=3+\frac{4}{5}(t+1)-\frac{29}{35}(t+1)(t-4)+\frac{1571}{9240}(t+1)(t-4)(t-6). \end{equation*}

1. On a

   \begin{equation*} \begin{array}{c|cccc} x_i&y_i&&&\\ \hline\\ 0{,}8&0{,}717\,356&&&\\ &&0{,}579\,503&&\\ 1{,}1&0{,}891\,207&&-0{,}448\,261&\\ &&0{,}265\,720&&-0{,}047\,988\\ 1{,}5&0{,}997\,495&&-0{,}491\;450&\\ &&-0{,}029\,150&&\\ 1{,}7&0{,}991\,665&&&\\ \end{array} \end{equation*}

2. On déduit de la question 1 que

   \begin{equation*} P(t)=0{,}717\,356+0{,}579\,503(t-0{,}8)-0{,}448\,261(t-0{,}8)(t-1{,}1). \end{equation*}

3. On déduit de la question 1 que

   \begin{equation*} Q(t)=0{,}891\,207+0{,}265\,720(t-1{,}1)-0{,}491\;450(t-1{,}1)(t-1{,}5). \end{equation*}

4. D'une part, on a

   \begin{align*} P(1{,}3)&=0{,}717\,356+0{,}579\,503(1{,}3\\ &\qquad-0{,}8)-0{,}448\,261(1{,}3-0{,}8)(1{,}3-1{,}1)\\ &\approx 0{,}962\,281. \end{align*}

   D'autre part, on a

   \begin{align*} Q(1{,}3)&=0{,}891\,207+0{,}265\,720(1{,}3-1{,}1)\\ &\qquad-0{,}491\;450(1{,}3-1{,}1)(1{,}3-1{,}5)\\ &\approx 0{,}964\,009. \end{align*}

   Par ailleurs, on a

   \begin{equation*} \sin(1{,}3)\approx 0{,}963\,558. \end{equation*}

   Donc \(P(1{,}3)\) constitue une approximation de \(\sin(1{,}3)\) qui lui est inférieure, tandis que \(Q(1{,}3)\) est une approximation supérieure.

1. Voici la table des différences divisées :

   \begin{equation*} \begin{array}{c|cccc} x_i&y_i&&&\\ \hline\\ 2014&3310&&&\\ &&-90&&\\ 2015&3220&&\frac{235}{3}&\\ &&145&&20\\ 2017&3510&&\frac{475}{3}&\\ &&620&&\\ 2018&4130&&&\\ \end{array} \end{equation*}

   La forme de Newton du polynôme interpolateur est donc

   \begin{align*} P(t)&=3310-90(t-2014)+\frac{235}{3}(t-2014)(t-2015)\\ &\qquad +20(t-2014)(t-2015)(t-2017). \end{align*}

2. On en déduit l'estimation suivante pour la donnée manquante :

   \begin{align*} P(2016)&=3310-90\cdot 2+\frac{235}{3}\cdot 2\cdot 1+20\cdot 2\cdot 1\cdot(-1)\\ &\approx 3247. \end{align*}

En utilisant le code donné à la section 7.2, on obtient les différences divisées de ces quatre points et on en déduit la forme de Newton de son polynôme interpolateur :

On calcule alors \(P(15000)\) et on trouve

On estime ainsi que Victor mettra \(4069\) secondes, i.e.

environ pour courir son prochain \(15\) kilomètres.

Soit \(A_0=(x_0;y_0),A_1=(x_1;y_1)\) et \(A_2=(x_2;y_2)\) trois points d'abscisses distinctes deux à deux. La forme de Newton de leur polynôme annulateur s'écrit

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

i.e.

Ce système linéaire est déjà triangulé.

• La première équation donne \(d_0=y_0\text{.}\)

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

  \begin{align*} y_0+(x_1-x_0)d_1&=y_1,\\ (x_1-x_0)d_1&=y_1-y_0,\\ d_1&=\frac{y_1-y_0}{x_1-x_0}. \end{align*}

• La troisième équation donne \(d_0+(x_2-x_0)d_1+(x_2-x_0)(x_2-x_1)d_2=y_2\text{,}\) d'où

  \begin{align*} &y_0+(x_2-x_0)\frac{y_1-y_0}{x_1-x_0}+(x_2-x_0)(x_2-x_1)d_2=y_2,\\ &(x_2-x_0)(x_2-x_1)d_2=y_2-y_0-(x_2-x_0)\frac{y_1-y_0}{x_1-x_0},\\ &(x_2-x_0)(x_2-x_1)d_2=y_2-y_1+y_1-y_0-(x_2-x_0)\frac{y_1-y_0}{x_1-x_0},\\ &(x_2-x_0)(x_2-x_1)d_2=y_2-y_1+\left(x_1-x_0-(x_2-x_0)\right)\frac{y_1-y_0}{x_1-x_0},\\ &(x_2-x_0)(x_2-x_1)d_2=y_2-y_1+\left(x_1-x_2\right)\frac{y_1-y_0}{x_1-x_0},\\ &d_2=\frac{y_2-y_1}{(x_2-x_0)(x_2-x_1)}+\left(x_1-x_2\right)\frac{y_1-y_0}{(x_1-x_0)(x_2-x_0)(x_2-x_1)},\\ &d_2=\frac{y_2-y_1}{(x_2-x_0)(x_2-x_1)}-\frac{y_1-y_0}{(x_1-x_0)(x_2-x_0)},\\ &d_2=\frac{\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0} }{x_2-x_0}. \end{align*}

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

i.e.

Il faut essentiellement ajouter une boucle permettant de calculer les polynômes de base \(N_j(t)\) à l'intérieur d'une boucle additionnant les \(d_j\cdot N_j(t)\text{.}\) Cela donne :

# entrées :
n = 3
x = [1.0, 2.0, 3.0, 4.0]
y = [-3.0, 7.0, 0.0, 5.0]
var('t') # ligne ajoutée
# instructions :
diffDiv = [y]
for j in range(1, n+1):
    nouvelleColonne = []
    for i in range(0, n-j+1):
        nouvelleDiffDiv = (diffDiv[j-1][i+1] - diffDiv[j-1][i]) / (x[i+j] - x[i])
        nouvelleColonne.append(nouvelleDiffDiv)
    diffDiv.append(nouvelleColonne)
N = diffDiv[0][0] # ligne ajoutée
for j in range(1, n+1): # ligne ajoutée
    Nj = 1 # ligne ajoutée
    for i in range(0, j): # ligne ajoutée
        Nj = Nj * (t - x[i]) # ligne ajoutée
    N = N + diffDiv[j][0] * Nj # ligne ajoutée
# sortie :
print(N) # ligne modifiée