Les indices des matrices commencent à {0}. La sur-diagonale d’indice {s} d’une matrice d’ordre {n+1} est constituée des {M[i,i+s]}, {0\le i\le n-s} ; celle d’indice {0} est la diagonale.
Soient deux listes {x,y} de longueur {n+1}, les {x[i]} étant deux à deux distincts. On initialise {M} à la matrice diagonale de diagonale {y}. Puis, pour {s=1,\ldots,n}, on calcule {M[i,i+s]=\frac{M[i+1,i+s]-M[i,i+s-1]}{x[i+s]-x[i]}}pour {i=0,\ldots,n-s}.
I. 1. Expliquer pourquoi l’algorithme est correct et renvoie une matrice carrée d’ordre {n+1}, triangulaire supérieure.
I. 2. [P] Écrire matr(x,y) renvoyant la matrice sous forme de tableau Numpy, sans vérification des arguments. Tester avec x=[-1,0,1,2,3] et y=[1,2,-3,-2,-7] ; vérifier que la première ligne vaut [1,1,-3,2,-1].
II. Une forme du polynôme interpolateur de n + 1 points
Soient {n+1} points {A_k(x_k,y_k)} d’abscisses distinctes. On pose {H_0=1} et {H_k(X)=\prod\limits_{i=0}^{k-1}(X-x_i)}. Pour {0\le i\le k\le n}, {P_{i,k}} est l’unique polynôme de degré au plus {k-i} tel que {P_{i,k}(x_j)=y_j} pour {i\le j\le k}. En particulier {P_{i,i}=y_i}.
II. 1. Avec {A_0(-1,1)}, {A_1(0,2)}, {A_2(1,-3)}, {A_3(2,-2)} et {A_4(3,-7)}, montrer que {P_{0,4}=\sum\limits_{k=0}^4\alpha_kH_k}. Calculer les {\alpha_k} et les comparer à la première ligne de {M}.
III. [P] Tracer sur {[-1,3]}, en prenant {100} abscisses, le polynôme {\begin{array}{rl}P(t)&=1+(t+1)-3(t+1)t\\[4pt]&\quad+2(t+1)t(t-1)\\[4pt]&\quad-(t+1)t(t-1)(t-2)\end{array}}Faire également apparaître les points {A_0,\ldots,A_4}.