Interpolation Q

Interpolation et approximation polynomiale
Jean-Philippe Chancelier
October 10, 2017
Contents
1 Interpolation polynomiale: matrice de Vandermonde 1
2 Polynôme d’interpolation de Lagrange 2
3 Évaluation du polynôme d’interpolation de Lagrange par l’algorithme de

Neville 2
4 Différences divisées 2
5 Fonction de Lebesgue, points de Tchebychev 3
6 Approximation en norme L∞ polynômes de Bernstein 4
1 Interpolation polynomiale: matrice de Vandermonde

On cherche à résoudre le problème d’interpolation polynomiale par résolution du système
linéaire obtenu en écrivant le système de n + 1 équations à n + 1 inconnues. On cherche donc
l’unique polynôme de degré n passant par les points (xi , fi )i=0,...,n . Les points (xi )i=0,...,n
étant tous distincts.
n
X
aj xji = f (xi ),
def
Pn (xi ) = i = 0, . . . , n (1)
j=0
Soit en notation matricielle :

    
1 x10 . . . xn0 a0 f (x0 )
1 x11 . . . xn1 
  a1   f (x1 ) 
   
 .. .. =
.  .   .  (2)

. . . . . ..   ..   .. 
1 x1n . . . xnn an f (xn )
1
Question 1 Écrire le code Scilab permettant de construire le polynôme d’interpolation par
résolution du système linéaire utilisant le Vandermonde. On notera que la construction du
Vandermonde peut se faire de façon vectorielle
Question 2 Utiliser le code précédent avec la fonction 1/(1+x2 ) et des points d’interpolations
régulièrement espacés sur [−5, 5] et représenter graphiquement la fonction initiale et le
polynôme d’interpolation. A partir de combien de points la résolution ne marche plus ?
Explication ?
2 Polynôme d’interpolation de Lagrange

On utilise directement les polynômes de Lagrange pour réaliser l’interpolation polynomiale.
Le i-ème polynôme de Lagrange s’écrit :
Q
def j6=i (x − xj )
Li (x) = Q (3)
j6=i (xi − xj )
Et le polynôme d’interpolation s’écrit alors :

n
X
Pn (x) = fi Li (x) (4)
i=0
Question 3 Écrire le code Scilab qui construit de polynôme d’interpolation de Lagrange par
construction directe à partir des données (xi , f (xi ))i=1,...,n . Reprendre l’exemple du para-
graphe précédent et comparer ? Que se passe-t-il quand le nombre de points d’interpolation
augmente ?
3 Évaluation du polynôme d’interpolation de Lagrange

par l’algorithme de Neville
Pour évaluer le polynô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 récursive quand on
rajoute progressivement des points d’interpolation. Soit Pi0 ...,ik le polynôme d’interpolation
de degré k passant par les points (xip , fip )p=0,...,k on établit facilement la formule récursive
suivante :
(x − xi0 )Pi1 ...,ik − (x − xik )Pi0 ...,ik−1

Pi0 ...,ik = (5)
x ik − x i0
avec
Piα = fiα (6)
Cette formule nous permet de calculer Pn (x) = P0,...,n (x) pour une valeur de x fixée.
2
Question 4 Programmer l’algorithme de Neville pour évaluer la valeur du polynôme d’interpolation
en un point x. Puis le rendre vectoriel pour évaluer directement la valeur du polynôme pour
n valeurs de x données dans un vecteur.
4 Différences divisées
L’algorithme de Neville est utilisé pour obtenir la valeur du polynôme d’interpolation en un
point. Quand on cherche l’expression du polynôme on peut utiliser les différences divisées
et la formule d’interpolation de Newton. On cherche le polynôme d’interpolation sous la
forme :
n
X i−1
Y
P (x) = a0 + ai (x − xk ) . (7)
i=1 k=0
Les différences divisées se définissent alors par

n j−1
X Y
Pi0 ...,ik (x) = fi0 + fi0 ,...,ij (x − xk ) . (8)
j=1 k=0
De la formule de récursion sur les polynômes Pi0 ...,ik on déduit, en identifiant les termes
de plus haut degrés, une formule de récursion sur les différences divisées :
fi1 ...,ik − fi0 ...,ik−1
fi0 ...,ik = (9)
x ik − x i0
Question 5 Programmer la construction du polynôme d’interpolation aux moyens des différences

divisées. On notera que pour n grand, une évaluation numérique des valeurs du polynôme
obtenu par la formule d’interpolation de Newton par la fonction horner donne de meilleurs
résultats que la même évaluation à partir du polynôme d’interpolation de Lagrange (utiliser
la fonction 1/(1 + x2 ) sur [−1, 1] )
Question 6 La formule de Newton permet une construction séquentielle des polynômes

d’interpolation en rajoutant au fur et a mesure des points. Écrire une fonction qui met a
jour et dessine les polynôme d’interpolation les point d’interpolation successifs étant obtenus
en cliquant sur la fenê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
Q
[−1, 1] en fonction du choix des points xi . On regarde le cas des points régulièrement espacés
et le cas des points de Tchebychev :
xi = cos(π(2k + 1)/(2(n − 1) + 2)) k = 0, . . . , n − 1 (10)
3
On fait de même pour la fonction de Lebesgue :
n
X
def
λ(x) = |Li (x)| (11)
i=0
Question 7 Tracer la fonction ω(x) pour des points xi régulièrement espacés sur [-1,1] et
pour les points de Tchebychev. Faites de même pour la fonction de Lebesgue. Que constatez
vous ?
6 Approximation en norme L∞ polynômes de Bern-

stein
On cherche ici à approximer une fonction sur [0, 1] par les polynômes de Bernstein :
n
X
Bn (f ) = Cnk f (k/n)xk (1 − x)n−k (12)
k=0
On utilise le fait que pour x fixé dans [0, 1] les coefficients Cnk xk (1 − x)n−k sont les
probabilités d’une loi binomiale. La fonction Scilab binomial(x,n-1) est utilisée pour leurs
calculs.
Question 8 Programmer le calcul des polynômes de Bernstein approchant une fonction con-
tinue sur [−1, 1]. Faites varier le degré du polynôme de Bernstein et superposez graphique-
ment la fonction et son approximation. Que constatez vous ?

Interpolation Q

Transféré par

Droits d'auteur :

Formats disponibles

Interpolation Q

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Interpolation Q

Transféré par

Droits d'auteur :

Formats disponibles

Interpolation et approximation polynomiale

2 Polynôme d’interpolation de Lagrange 2

3 Évaluation du polynôme d’interpolation de Lagrange par l’algorithme de

5 Fonction de Lebesgue, points de Tchebychev 3

6 Approximation en norme L∞ polynômes de Bernstein 4

1 Interpolation polynomiale: matrice de Vandermonde

Soit en notation matricielle :

2 Polynôme d’interpolation de Lagrange

Et le polynôme d’interpolation s’écrit alors :

3 Évaluation du polynôme d’interpolation de Lagrange

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

Les différences divisées se définissent alors par

Question 5 Programmer la construction du polynôme d’interpolation aux moyens des différences

Question 6 La formule de Newton permet une construction séquentielle des polynômes

5 Fonction de Lebesgue, points de Tchebychev

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

6 Approximation en norme L∞ polynômes de Bern-

Vous aimerez peut-être aussi