Interpolation et approximation polynomiale

Jean-Philippe Chancelier
(last modiﬁcation date: October 10, 2017)

Version pdf de ce document
Version sans bandeaux

1 Interpolation polynomiale: matrice de Vandermonde
2 Polynôme d’interpolation de Lagrange
3 Évaluation du polynôme d’interpolation de Lagrange par l’algorithme de Neville
4 Diﬀérences divisées
5 Fonction de Lebesgue, points de Tchebychev
6 Approximation en norme L^∞ polynômes de Bernstein

1 Interpolation polynomiale: matrice de Vandermonde

On cherche à résoudre le problème d’interpolation polynomiale par résolution du système linéaire obtenu en écrivant le système de n + 1 équations à n + 1 inconnues. On cherche donc l’unique polynôme de degré n passant par les points (x_i,f_i)_i=0,…,n. Les points (x_i)_i=0,…,n étant tous distincts.

n def∑ j Pn(xi) = ajxi = f(xi), i = 0,...,n j=0

(1)

Soit en notation matricielle :

( 1 n) ( ) ( ) 1 x0 ... x 0 a0 f (x0 ) || 1 x11 ... xn1|| || a1|| || f (x1 )|| |( .. .. .. |) |( .. |) = |( .. |) . .1 ... .n . . 1 xn ... x n an f (xn )

(2)

Question 1 Écrire le code Scilab permettant de construire le polynôme d’interpolation par résolution du système linéaire utilisant le Vandermonde. On notera que la construction du Vandermonde peut se faire de façon vectorielle

Question 2 Utiliser le code précédent avec la fonction 1∕(1 + x²) et des points d’interpolations régulièrement espacés sur [−5, 5] et représenter graphiquement la fonction initiale et le polynôme d’interpolation. A partir de combien de points la résolution ne marche plus ? Explication ?

2 Polynôme d’interpolation de Lagrange

On utilise directement les polynômes de Lagrange pour réaliser l’interpolation polynomiale. Le i-ème polynôme de Lagrange s’écrit :

∏ L (x) d=ef∏-j⁄=i(x-−-xj)- i j⁄=i(xi − xj )

(3)

Et le polynôme d’interpolation s’écrit alors :

∑n Pn (x ) = fiLi(x) i=0

(4)

Question 3 Écrire le code Scilab qui construit de polynôme d’interpolation de Lagrange par construction directe à partir des données (x_i,f(x_i))_i=1,…,n. Reprendre l’exemple du paragraphe précédent et comparer ? Que se passe-t-il quand le nombre de points d’interpolation augmente ?

3 Évaluation du polynôme d’interpolation de Lagrange par l’algorithme de Neville

Pour évaluer le polynôme d’interpolation en un point on peut utiliser l’algorithme de Neville que l’on rappelle ici. Cet algorithme permet en outre une estimation récursive quand on rajoute progressivement des points d’interpolation. Soit P_{i₀…,i_k} le polynôme d’interpolation de degré k passant par les points (x_{i_p},f_{i_p})_p=0,…,k on établit facilement la formule récursive suivante :

(x-−-xi0)Pi1...,ik −-(x-−--xik)Pi0...,ik−1 Pi0...,ik = x − x ik i0

(5)

avec

Piα = fiα

(6)

Cette formule nous permet de calculer P_n(x) = P_0,…,n(x) pour une valeur de x ﬁxée.

Question 4 Programmer l’algorithme de Neville pour évaluer la valeur du polynôme d’interpolation en un point x. Puis le rendre vectoriel pour évaluer directement la valeur du polynôme pour n valeurs de x données dans un vecteur.

4 Diﬀérences divisées

L’algorithme de Neville est utilisé pour obtenir la valeur du polynôme d’interpolation en un point. Quand on cherche l’expression du polynôme on peut utiliser les diﬀérences divisées et la formule d’interpolation de Newton. On cherche le polynôme d’interpolation sous la forme :

∑n i∏−1 P(x) = a0 + ai (x − xk). i=1 k=0

(7)

Les diﬀérences divisées se déﬁnissent alors par

∑ n j−∏ 1 Pi0...,ik(x) = fi0 + fi0,...,ij (x − xk ). j=1 k=0

(8)

De la formule de récursion sur les polynômes P_{i₀…,i_k} on déduit, en identiﬁant les termes de plus haut degrés, une formule de récursion sur les diﬀérences divisées :

fi1...,ik −-fi0...,ik−1- fi0...,ik = xi − xi k 0

(9)

Question 5 Programmer la construction du polynôme d’interpolation aux moyens des diﬀérences divisées. On notera que pour n grand, une évaluation numérique des valeurs du polynôme obtenu par la formule d’interpolation de Newton par la fonction horner donne de meilleurs résultats que la même évaluation à partir du polynôme d’interpolation de Lagrange (utiliser la fonction 1∕(1 + x²) sur [−1, 1] )

Question 6 La formule de Newton permet une construction séquentielle des polynômes d’interpolation en rajoutant au fur et a mesure des points. Écrire une fonction qui met a jour et dessine les polynôme d’interpolation les point d’interpolation successifs étant obtenus en cliquant sur la fenêtre graphique.

5 Fonction de Lebesgue, points de Tchebychev

On regarde dans ce paragraphe le comportement de ω(x) = ∏
| ni=0(x − xi)| sur l’intervalle [−1, 1] en fonction du choix des points x_i. On regarde le cas des points régulièrement espacés et le cas des points de Tchebychev :

xi = cos(π(2k + 1)∕(2(n − 1) + 2)) k = 0,...,n − 1

(10)

On fait de même pour la fonction de Lebesgue :

n def∑ λ(x) = |Li(x)| i=0

(11)

Question 7 Tracer la fonction ω(x) pour des points x_i régulièrement espacés sur [-1,1] et pour les points de Tchebychev. Faites de même pour la fonction de Lebesgue. Que constatez vous ?

6 Approximation en norme L^∞ polynômes de Bernstein

On cherche ici à approximer une fonction sur [0, 1] par les polynômes de Bernstein :

∑n k k n−k Bn (f) = C nf(k∕n )x (1 − x ) k=0

(12)

On utilise le fait que pour x ﬁxé dans [0, 1] les coeﬃcients C_n^kx^k(1 − x)^n−k sont les probabilités d’une loi binomiale. La fonction Scilab binomial(x,n-1) est utilisée pour leurs calculs.

Question 8 Programmer le calcul des polynômes de Bernstein approchant une fonction continue sur [−1, 1]. Faites varier le degré du polynôme de Bernstein et superposez graphiquement la fonction et son approximation. Que constatez vous ?

Formations

Départements

Pratique

Recherche

Interpolation et approximation polynomiale

Contents

1 Interpolation polynomiale: matrice de Vandermonde

2 Polynôme d’interpolation de Lagrange

3 Évaluation du polynôme d’interpolation de Lagrange par l’algorithme de Neville

4 Diﬀérences divisées

5 Fonction de Lebesgue, points de Tchebychev

6 Approximation en norme L^∞ polynômes de Bernstein

L'École des Ponts ParisTech est membre fondateur de	L'École des Ponts ParisTech est certifiée

Formations

Départements

Pratique

Recherche

Interpolation et approximation polynomiale

Contents

1 Interpolation polynomiale: matrice de Vandermonde

2 Polynôme d’interpolation de Lagrange

3 Évaluation du polynôme d’interpolation de Lagrange par l’algorithme de Neville

4 Diﬀérences divisées

5 Fonction de Lebesgue, points de Tchebychev

6 Approximation en norme L∞ polynômes de Bernstein

6 Approximation en norme L^∞ polynômes de Bernstein