Analyse Numérique

ENSEM ISN 1A, Ana Num

Didier Schmitt

IECL

Printemps 2022

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation

Chapitre 3 : Interpolation et approximation

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Évaluation d’un polynôme : algorithme de Hörner

Évaluation d’un polynôme : algorithme de

Hörner

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Évaluation d’un polynôme : algorithme de Hörner

Le problème : évaluation d’un polynôme en un point

Soit P un polynôme de degré n

P (x) = an x n + an−1 x n−1 + ... + a2 x 2 + a1 x + a0 ,

que nous souhaitons évaluer en un point ξ

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Évaluation d’un polynôme : algorithme de Hörner

Le problème : évaluation d’un polynôme en un point

Soit P un polynôme de degré n

P (x) = an x n + an−1 x n−1 + ... + a2 x 2 + a1 x + a0 ,

que nous souhaitons évaluer en un point ξ

L’algorithme ”naturel” consiste à calculer chacun des produits ak ξ k

puis à faire leur somme.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Évaluation d’un polynôme : algorithme de Hörner

Le problème : évaluation d’un polynôme en un point

Soit P un polynôme de degré n

P (x) = an x n + an−1 x n−1 + ... + a2 x 2 + a1 x + a0 ,

que nous souhaitons évaluer en un point ξ

L’algorithme ”naturel” consiste à calculer chacun des produits ak ξ k

puis à faire leur somme.
Mais cette technique est généralement peu utilisée
à cause des erreurs qu’elle engendre.
à cause du nombre trop important d’opérations élémentaires qu’elle
met en jeu, surtout quand le degré est élevé : 2n − 1 multiplications
et n additions.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Évaluation d’un polynôme : algorithme de Hörner

Le problème : évaluation d’un polynôme en un point

Soit P un polynôme de degré n

P (x) = an x n + an−1 x n−1 + ... + a2 x 2 + a1 x + a0 ,

que nous souhaitons évaluer en un point ξ

L’algorithme ”naturel” consiste à calculer chacun des produits ak ξ k

puis à faire leur somme.
Mais cette technique est généralement peu utilisée
à cause des erreurs qu’elle engendre.
à cause du nombre trop important d’opérations élémentaires qu’elle
met en jeu, surtout quand le degré est élevé : 2n − 1 multiplications
et n additions.
On préfère donc généralement utiliser l’algorithme de Hörner

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Évaluation d’un polynôme : algorithme de Hörner

Le problème : évaluation d’un polynôme en un point

Soit P un polynôme de degré n

P (x) = an x n + an−1 x n−1 + ... + a2 x 2 + a1 x + a0 ,

que nous souhaitons évaluer en un point ξ

Algorithme de Hörner
L’algorithme de Hörner repose sur la factorisation suivante du polynôme :

P (x) = a0 + x (a1 + x (a2 + x (a3 + ... + x (an−2 + x(an−1 + xan )) . . .)))

Ainsi, on obtient l’algorithme

b := an ;
pour tous les i de n − 1 à 0 faire
b := ai + ξb;

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Évaluation d’un polynôme : algorithme de Hörner

Le problème : évaluation d’un polynôme en un point

Soit P un polynôme de degré n

P (x) = an x n + an−1 x n−1 + ... + a2 x 2 + a1 x + a0 ,

que nous souhaitons évaluer en un point ξ

Algorithme de Hörner
L’algorithme de Hörner repose sur la factorisation suivante du polynôme :

P (x) = a0 + x (a1 + x (a2 + x (a3 + ... + x (an−2 + x(an−1 + xan )) . . .)))

Ainsi, on obtient l’algorithme

b := an ;
pour tous les i de n − 1 à 0 faire
b := ai + ξb;
cet algorithme nécessite n additions et n multiplications
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation et Interpolation - Introduction

Approximation et Interpolation - Introduction

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation et Interpolation - Introduction

Introduction
L’approximation d’une fonction f consiste à chercher une fonction g
la ”plus proche possible” de f en un sens donné.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation et Interpolation - Introduction

Introduction
L’approximation d’une fonction f consiste à chercher une fonction g
la ”plus proche possible” de f en un sens donné.
Nous chercherons principalement à approximer une fonction par des
fonctions polynômes.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation et Interpolation - Introduction

Introduction
L’approximation d’une fonction f consiste à chercher une fonction g
la ”plus proche possible” de f en un sens donné.
Nous chercherons principalement à approximer une fonction par des
fonctions polynômes.
En effet nous avons le théorème suivant

Théorème de Weierstrass
Toute fonction continue sur un segment [a, b] est limite uniforme de
fonctions polynomiales sur ce segment.
Autrement dit, pour tout  > 0, il existe un polynôme P tel que

|f (x) − P(x)| < , ∀x ∈ [a, b].

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation et Interpolation - Introduction

Introduction
Dans la pratique, la fonction f sera connue uniquement par ses
valeurs en certains points x0 , .., xn .

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation et Interpolation - Introduction

Introduction
Dans la pratique, la fonction f sera connue uniquement par ses
valeurs en certains points x0 , .., xn .
À partir de la connaissance de f en ces points, nous souhaitons
”reconstruire le mieux possible” cette fonction i.e. trouver une
”bonne” approximation de f .

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation et Interpolation - Introduction

Introduction
Dans la pratique, la fonction f sera connue uniquement par ses
valeurs en certains points x0 , .., xn .
À partir de la connaissance de f en ces points, nous souhaitons
”reconstruire le mieux possible” cette fonction i.e. trouver une
”bonne” approximation de f .
On pourra imposer à l’approximation de passer exactement par les
points donnés. Dans ce cas, on parle d’interpolation.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation polynomiale

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Soit f : [a, b] → R connue en (n + 1) points distincts x0 , x1 , ...xn de

l’intervalle [a, b].
Il s’agit de construire un polynôme P de degré inférieur ou égal à n tel
que
P(xi ) = f (xi ), ∀i ∈ J0, nK.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Théorème
Il existe un et un seul polynôme Pn de degré inférieur ou égal à n vérifiant

Pn (xi ) = f (xi ), ∀i ∈ J0, nK.

Le polynôme s’écrit
n
X Y (x − xk )
Pn (x) = f (xi ) Li (x) avec Li (x) = .
(xi − xk )
i=0 k=0 k6=i

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Théorème
Il existe un et un seul polynôme Pn de degré inférieur ou égal à n vérifiant

Pn (xi ) = f (xi ), ∀i ∈ J0, nK.

Le polynôme s’écrit
n
X Y (x − xk )
Pn (x) = f (xi ) Li (x) avec Li (x) = .
(xi − xk )
i=0 k=0 k6=i

Le polynôme Pn est appelé polynôme d’interpolation de Lagrange de

la fonction f aux points (xi , f (xi ))i∈J0,nK .

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Théorème
Il existe un et un seul polynôme Pn de degré inférieur ou égal à n vérifiant

Pn (xi ) = f (xi ), ∀i ∈ J0, nK.

Le polynôme s’écrit
n
X Y (x − xk )
Pn (x) = f (xi ) Li (x) avec Li (x) = .
(xi − xk )
i=0 k=0 k6=i

Le polynôme Pn est appelé polynôme d’interpolation de Lagrange de

la fonction f aux points (xi , f (xi ))i∈J0,nK .
Les polynômes (Li (x))i∈J0,nK sont appelés polynômes de base de
Lagrange associés aux abscisses (xi )i∈J0,nK .
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Démonstration
Existence
Le polynôme Pn ainsi défini est un polynôme de degré n et comme
Li (xj ) = δij , il vérifie bien

Pn (xi ) = f (xi ), ∀i ∈ J0, nK.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Démonstration
Existence
Le polynôme Pn ainsi défini est un polynôme de degré n et comme
Li (xj ) = δij , il vérifie bien

Pn (xi ) = f (xi ), ∀i ∈ J0, nK.

Unicité
Soit Q un autre polynôme solution. Alors

Q(xi ) − P(xi ) = 0, ∀i ∈ J0, nK.

Ainsi Q − P est un polynôme de degré inférieur ou égal à n

s’annulant en (n + 1) points. Il est donc identiquement nul.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Exemple : avec deux points (n = 1)

(x − x1 ) (x − x0 )
P1 (x) = f (x0 ) + f (x1 ) ,
(x0 − x1 ) (x1 − x0 )
ce qui s’écrit encore

f (x1 ) − f (x0 )
P1 (x) = f (x0 ) + (x − x0 ) .
x1 − x0

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Exemple :
3,2

2,4

1,6

0,8

-0,4 0 0,4 0,8 1,2 1,6 2 2,4 2,8 3,2 3,6 4

-0,8

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Exemple :
3,2

2,4

1,6

0,8

-0,4 0 0,4 0,8 1,2 1,6 2 2,4 2,8 3,2 3,6 4

-0,8

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Exemple :
3,2

2,4

1,6

0,8

-0,4 0 0,4 0,8 1,2 1,6 2 2,4 2,8 3,2 3,6 4

-0,8

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation de Lagrange

Exemple :
3,2

2,4

1,6

0,8

-0,4 0 0,4 0,8 1,2 1,6 2 2,4 2,8 3,2 3,6 4

-0,8

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction sinus sur [−π, π] - 2 points d’interpolation équidistants

Interpolation de la fonction sinus

1
points d'interpolation
polynome d'interpolation
0.8
fonction exacte

0.6

0.4

0.2

-0.2

-0.4

-0.6

-0.8

-1
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction sinus sur [−π, π] - 3 points d’interpolation équidistants

Interpolation de la fonction sinus

1
points d'interpolation
polynome d'interpolation
0.8
fonction exacte

0.6

0.4

0.2

-0.2

-0.4

-0.6

-0.8

-1
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction sinus sur [−π, π] - 5 points d’interpolation équidistants

Interpolation de la fonction sinus

1.5
points d'interpolation
polynome d'interpolation
fonction exacte
1

0.5

-0.5

-1

-1.5
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction sinus sur [−π, π] - 6 points d’interpolation équidistants

Interpolation de la fonction sinus

1.5
points d'interpolation
polynome d'interpolation
fonction exacte
1

0.5

-0.5

-1

-1.5
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−1, 1] - 3 points d’interpolation équidistants

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
0.95
fonction exacte

0.9

0.85

0.8

0.75

0.7

0.65

0.6

0.55

0.5
-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−1, 1] - 4 points d’interpolation équidistants

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
0.95
fonction exacte

0.9

0.85

0.8

0.75

0.7

0.65

0.6

0.55

0.5
-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−1, 1] - 5 points d’interpolation équidistants

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
0.95
fonction exacte

0.9

0.85

0.8

0.75

0.7

0.65

0.6

0.55

0.5
-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−1, 1]- 10 points d’interpolation

équidistants

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
0.95
fonction exacte

0.9

0.85

0.8

0.75

0.7

0.65

0.6

0.55

0.5
-1 -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - 3 points d’interpolation équidistants

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
0.9
fonction exacte

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - 4 points d’interpolation équidistants

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
0.9
fonction exacte

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - 5 points d’interpolation équidistants

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
fonction exacte
0.8

0.6

0.4

0.2

-0.2

-0.4
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5]- 10 points d’interpolation

équidistants

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
fonction exacte
0.8

0.6

0.4

0.2

-0.2

-0.4
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Quelques exemples

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5]- 15 points d’interpolation

équidistants

Interpolation de la fonction de Runge

8
points d'interpolation
polynome d'interpolation
7 fonction exacte

-1
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Un but de l’interpolation étant de remplacer l’évaluation de f (x) par celle

de Pn (x), il est important de connaı̂tre l’erreur

En (x) = f (x) − Pn (x), x ∈ [a, b]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Théorème
Soit f : [a, b] −→ R, (n + 1) fois continument dérivable et Pn le
polynôme d’interpolation de Lagrange aux points (xi , f (xi ))i∈J0,nK .
Nous avons, alors
Mn+1
∀ x ∈ [a, b], |En (x)| ≤ |πn (x)|
(n + 1)!

où  
Mn+1 = max f (n+1) (x)
 
x∈[a,b]

et
n
Y
∀x ∈ [a, b], πn (x) = (x − xi ).
i=0

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = sin(x) pour x ∈ [a, b]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = sin(x) pour x ∈ [a, b]

On a Mn+1 ≤ 1.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = sin(x) pour x ∈ [a, b]

On a Mn+1 ≤ 1.
On obtient aussi facilement la majoration |πn (x)| ≤ (b − a)n+1 (pour
tout choix des n + 1 points xi ).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = sin(x) pour x ∈ [a, b]

On a Mn+1 ≤ 1.
On obtient aussi facilement la majoration |πn (x)| ≤ (b − a)n+1 (pour
tout choix des n + 1 points xi ).
Donc
(b − a)n+1
∀x ∈ [a, b] , |f (x) − Pn (x)| ≤
(n + 1)!

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = sin(x) pour x ∈ [a, b]

On a Mn+1 ≤ 1.
On obtient aussi facilement la majoration |πn (x)| ≤ (b − a)n+1 (pour
tout choix des n + 1 points xi ).
Donc
(b − a)n+1
∀x ∈ [a, b] , |f (x) − Pn (x)| ≤
(n + 1)!
Et par conséquent

∀x ∈ [a, b] , lim |f (x) − Pn (x)| = 0.

n→∞

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = 1/(1 + x 2 ) pour x ∈ [−a, a]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = 1/(1 + x 2 ) pour x ∈ [−a, a]

On montre (admis) que si les abscisses (xi ) sont équidistantes dans

[−a, a]
e −n
max |f (x) − Pn (x)| < C √ (2a)n+1 .
−a≤x≤a n log n

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = 1/(1 + x 2 ) pour x ∈ [−a, a]

On montre (admis) que si les abscisses (xi ) sont équidistantes dans

[−a, a]
e −n
max |f (x) − Pn (x)| < C √ (2a)n+1 .
−a≤x≤a n log n
Donc si 2a < e, En (x) converge vers 0 avec n.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = 1/(1 + x 2 ) pour x ∈ [−a, a]

On montre (admis) que si les abscisses (xi ) sont équidistantes dans

[−a, a]
e −n
max |f (x) − Pn (x)| < C √ (2a)n+1 .
−a≤x≤a n log n
Donc si 2a < e, En (x) converge vers 0 avec n.
Dans notre simulation a = 5 et dans ce cas, le majorant ci-dessus
tend vers l’infini. Nous pouvons donc rien affirmer sur En (x) !

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = 1/(1 + x 2 ) pour x ∈ [−a, a]

On montre (admis) que si les abscisses (xi ) sont équidistantes dans

[−a, a]
e −n
max |f (x) − Pn (x)| < C √ (2a)n+1 .
−a≤x≤a n log n
Donc si 2a < e, En (x) converge vers 0 avec n.
Dans notre simulation a = 5 et dans ce cas, le majorant ci-dessus
tend vers l’infini. Nous pouvons donc rien affirmer sur En (x) !
Notre calcul numérique laisse penser que En ne tend pas vers 0.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Exemple : f (x) = 1/(1 + x 2 ) pour x ∈ [−a, a]

On montre (admis) que si les abscisses (xi ) sont équidistantes dans

[−a, a]
e −n
max |f (x) − Pn (x)| < C √ (2a)n+1 .
−a≤x≤a n log n
Donc si 2a < e, En (x) converge vers 0 avec n.
Dans notre simulation a = 5 et dans ce cas, le majorant ci-dessus
tend vers l’infini. Nous pouvons donc rien affirmer sur En (x) !
Notre calcul numérique laisse penser que En ne tend pas vers 0.
On peut montrer que max |En (x)| ne tend pas vers 0 (phénomène de
|x|≤5
Runge).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Choix des abscisses d’interpolation

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Choix des abscisses d’interpolation

L’estimation d’erreur du théorème montre que l’erreur dépend
de la dérivée (n + 1) ième de f ,
du maximum de la fonction πn , qui lui ne dépend que du choix des
(xi ).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Choix des abscisses d’interpolation

L’estimation d’erreur du théorème montre que l’erreur dépend
de la dérivée (n + 1) ième de f ,
du maximum de la fonction πn , qui lui ne dépend que du choix des
(xi ).
On peut alors chercher à minimiser max |πn (x)| en choisissant au
a≤x≤b
mieux les points (xi ).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Choix des abscisses d’interpolation

L’estimation d’erreur du théorème montre que l’erreur dépend
de la dérivée (n + 1) ième de f ,
du maximum de la fonction πn , qui lui ne dépend que du choix des
(xi ).
On peut alors chercher à minimiser max |πn (x)| en choisissant au
a≤x≤b
mieux les points (xi ).
Il se trouve qu’un choix d’abscisses équidistantes n’est pas du tout
optimal, loin de là !

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’interpolation polynomiale

Choix des abscisses d’interpolation

L’estimation d’erreur du théorème montre que l’erreur dépend
de la dérivée (n + 1) ième de f ,
du maximum de la fonction πn , qui lui ne dépend que du choix des
(xi ).
On peut alors chercher à minimiser max |πn (x)| en choisissant au
a≤x≤b
mieux les points (xi ).
Il se trouve qu’un choix d’abscisses équidistantes n’est pas du tout
optimal, loin de là !
Le choix optimal est obtenu à l’aide des abscisses de Tchebychev :
 
a+b b−a (2i + 1)π
xi = + cos , i ∈ J0, nK.
2 2 2n + 2

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - 3 points d’interpolation de

Tchebychev

Interpolation de la fonction de Runge

1
points d'interpolation
polynome d'interpolation
fonction exacte
0.5

-0.5
-5 -4 -3 -2 -1 0 1 2 3 4 5

Erreur d'interpolation
0.4

0.2

-0.2

-0.4

-0.6

-0.8
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - 4 points d’interpolation de

Chebychev

Interpolation de la fonction de Runge

1
points d'interpolation
0.8 polynome d'interpolation
fonction exacte
0.6

0.4

0.2

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Erreur d'interpolation
0.8

0.6

0.4

0.2

-0.2
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - 5 points d’interpolation de

Tchebychev

Interpolation de la fonction de Runge

1
points d'interpolation
0.8
polynome d'interpolation
fonction exacte
0.6

0.4

0.2

-0.2
-5 -4 -3 -2 -1 0 1 2 3 4 5

Erreur d'interpolation
0.4

0.2

-0.2

-0.4

-0.6
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5]- 10 points d’interpolation de

Tchebychev

Interpolation de la fonction de Runge

1
points d'interpolation
0.8 polynome d'interpolation
fonction exacte
0.6

0.4

0.2

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Erreur d'interpolation
0.3

0.2

0.1

-0.1
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5]- 15 points d’interpolation de

Tchebychev

Interpolation de la fonction de Runge

1
points d'interpolation
0.8 polynome d'interpolation
fonction exacte
0.6

0.4

0.2

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Erreur d'interpolation
0.05

-0.05
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5]- 25 points d’interpolation de

Tchebychev

Interpolation de la fonction de Runge

1
points d'interpolation
0.8 polynome d'interpolation
fonction exacte
0.6

0.4

0.2

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Erreur d'interpolation
0.01

0.005

-0.005

-0.01
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Remarques
L’écriture du polynôme d’interpolation dans la base de Lagrange est
facile à obtenir et intéressante d’un point de vue théorique, mais peu
du point de vue numérique.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Remarques
L’écriture du polynôme d’interpolation dans la base de Lagrange est
facile à obtenir et intéressante d’un point de vue théorique, mais peu
du point de vue numérique.
L’évaluation du polynôme exprimé dans cette base requiert trop
d’opérations élémentaires !

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Remarques
L’écriture du polynôme d’interpolation dans la base de Lagrange est
facile à obtenir et intéressante d’un point de vue théorique, mais peu
du point de vue numérique.
L’évaluation du polynôme exprimé dans cette base requiert trop
d’opérations élémentaires !

C’est pourquoi, on préfère exprimer le polynôme d’interpolation Pn aux

abscisses (xi )i∈J0,nK dans la base de Newton associée à ces abscisses i.e
sous la forme :

Pn (x) = a0n + a1n (x − x0 ) + ... + ann (x − x0 ) (x − x1 ) ... (x − xn−1 )

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Pn (x) = a0n + a1n (x − x0 ) + ... + ann (x − x0 ) (x − x1 ) ... (x − xn−1 )

Remarques
Tout polynôme de degré inférieur ou égal à n peut se mettre sous
cette forme dès que les xi sont tous distincts.
Le coefficient ann est aussi le coefficient de x n dans Pn écrit sous sa
forme usuelle.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Avantages
On peut utiliser l’algorithme d’Hörner pour évaluer ce polynôme
Pn (x) = a0n +(x−x0 ) a1n + (x − x1 ) a2n + ... + (x − xn−2 )(an−1
n



+ (x − xn−1 )an )

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Avantages
On peut utiliser l’algorithme d’Hörner pour évaluer ce polynôme
Pn (x) = a0n +(x−x0 ) a1n + (x − x1 ) a2n + ... + (x − xn−2 )(an−1
n



+ (x − xn−1 )an )

La partie tronquée

a0n + a1n (x − x0 ) + ... + ann−1 (x − x0 ) (x − x1 ) ... (x − xn−2 )

est Pn−1 (x), le polynôme d’interpolation de la fonction f aux points

x0 , . . . , xn−1 .

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Avantages
On peut utiliser l’algorithme d’Hörner pour évaluer ce polynôme
Pn (x) = a0n +(x−x0 ) a1n + (x − x1 ) a2n + ... + (x − xn−2 )(an−1
n



+ (x − xn−1 )an )

La partie tronquée

a0n + a1n (x − x0 ) + ... + ann−1 (x − x0 ) (x − x1 ) ... (x − xn−2 )

est Pn−1 (x), le polynôme d’interpolation de la fonction f aux points

x0 , . . . , xn−1 .
Donc, connaissant Pn−1 , il suffit de calculer ann pour connaı̂tre Pn

Pn (x) = Pn−1 (x) + ann (x − x0 ) (x − x1 ) ... (x − xn−1 )

(utile, en particulier lorsqu’on ajoute un point !)

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Théorème
Le polynôme d’interpolation de Lagrange de la fonction f aux points
distincts (xi , f (xi ))i∈J0,nK est donné par :

n
X i−1
Y
Pn (x) = f [x0 ] + f [x0 , x1 , ...xi ] (x − xk )
i=1 k=0

où f [.] désigne les différences divisées de f définies par :

i = 0, ..., n f [xi ] = f (xi ),

f [x1 , ..., xk ] − f [x0 , ..., xk−1 ]

f [x0 , x1 , ..., xk ] := .
xk − x0

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Propriétés des différences divisées

Le coefficient f [x0 , x1 , ..., xn ] est invariant par des permutations sur
les xi : en effet, permuter les xi ne change pas le polynôme
d’interpolation et donc ne change pas le coefficient du terme de plus
haut degré.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Propriétés des différences divisées

Le coefficient f [x0 , x1 , ..., xn ] est invariant par des permutations sur
les xi : en effet, permuter les xi ne change pas le polynôme
d’interpolation et donc ne change pas le coefficient du terme de plus
haut degré.
Si f = Q un polynôme de degré q

0 si n > q
Q [x0 , x1 , ..., xn ] =
coeff. du terme de plus haut degré de Q si q = n

En effet, si q ≤ n, l’interpolé de Q n’est autre que Q lui-même !

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées

La table des différences divisées permet de calculer de façon inductive les
différences divisées d’une fonction selon le shéma suivant :
f (x0 ) = f [x0 ]
&
f (x1 ) = f [x1 ] → f [x0 , x1 ]
& &
f (x2 ) = f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]
& & &
. . . ..
. . . .
. . .
& & &
f (xn ) = f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] → ··· → f [x0 , x1 , . . . , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées

On retrouve sur la diagonale les coefficients de la formule de Newton
f (x0 ) = f [x0 ]
&
f (x1 ) = f [x1 ] → f [x0 , x1 ]
& &
f (x2 ) = f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]
& & &
. . . ..
. . . .
. . .
& & &
f (xn ) = f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] → ··· → f [x0 , x1 , . . . , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Ajout d’un point

On peut très facilement ajouter un point sans refaire tous les calculs
f (x0 ) = f [x0 ]
&
f (x1 ) = f [x1 ] → f [x0 , x1 ]
&
f (x2 ) = f [x2 ] → f [x1 , x2 ]
& &
. .
. .
. . &
f (xn ) = f [xn ] → f [xn−1 , xn ] → ··· → f [x0 , x1 , . . . , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Ajout d’un point

On peut très facilement ajouter un point sans refaire tous les calculs
f (x0 ) = f [x0 ]
&
f (x1 ) = f [x1 ] → f [x0 , x1 ]
&
f (x2 ) = f [x2 ] → f [x1 , x2 ]
& &
. .
. .
. . &
f (xn ) = f [xn ] → f [xn−1 , xn ] → ··· → f [x0 , x1 , . . . , xn ]

f (xn+1 ) = f [xn+1 ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Ajout d’un point

On peut très facilement ajouter un point sans refaire tous les calculs
f (x0 ) = f [x0 ]
&
f (x1 ) = f [x1 ] → f [x0 , x1 ]
&
f (x2 ) = f [x2 ] → f [x1 , x2 ]
& &
. .
. .
. . &
f (xn ) = f [xn ] → f [xn−1 , xn ] → ··· → f [x0 , x1 , . . . , xn ]
& & & &
f (xn+1 ) = f [xn+1 ] → f [xn , xn+1 ] → ··· → f [x1 , x2 , . . . , xn+1 ] → f [x0 , x1 , . . . , xn+1 ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Remarques
Nous avons (n+1)(n+2)
2 coefficients à calculer pour obtenir les (n + 1)
coefficients de la formule.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Remarques
Nous avons (n+1)(n+2)
2 coefficients à calculer pour obtenir les (n + 1)
coefficients de la formule.
On peut songer à utiliser un tableau bi-dimensionel (n + 1) × (n + 2)
pour stocker ces coefficients.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Remarques
Nous avons (n+1)(n+2)
2 coefficients à calculer pour obtenir les (n + 1)
coefficients de la formule.
On peut songer à utiliser un tableau bi-dimensionel (n + 1) × (n + 2)
pour stocker ces coefficients.
Toutefois un vecteur à (n + 1) composantes suffira !

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Étape 1

f [x0 ]

f [x1 ]

f [x2 ]

.
.
.

f [xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Étape 1

 
f [x0 ] f [x0 ]
 
f [x1 ]  f [x1 ]
 

 
 
f [x2 ]  f [x ]
2

d =
 

 
. .
 
.  . 
. 
 . 

 
f [xn ] f [xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Étape 2

 
f [x0 ] f [x0 ]
&  
f [x1 ] → f [x0 , x1 ]  f [x1 ]
 

&
 
 
f [x2 ] → f [x1 , x2 ]  f [x ]
2

d =
 
& 


. . .
 
. .  . 
. . 
 . 

&  
f [xn ] → f [xn−1 , xn ] f [xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Étape 2

 
f [x0 ] f [x0 ]
&  
f [x1 ] → f [x0 , x1 ] f [x0 , x1 ]
 
 
&
 
 
f [x2 ] → f [x1 , x2 ]  f [x1 , x2 ] 
d =
 
& 


. . .
 
. .  . 
. . 
 . 

&  
f [xn ] → f [xn−1 , xn ] f [xn−1 , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Étape 3

 
f [x0 ] f [x0 ]
&  
f [x1 ] → f [x0 , x1 ] f [x0 , x1 ]
 
 
& &
 
 
f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]  f [x1 , x2 ] 
d =
 
& & 


. . . .
 
. . .  . 
. . . 
 . 

& &  
f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] f [xn−1 , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule d’interpolation de Newton

Calcul des différences divisées - Étape 3

 
f [x0 ] f [x0 ]
&  
f [x1 ] → f [x0 , x1 ] f [x0 , x1 ]
 
 
& &
 
 
f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]  f [x0 , x1 , x2 ] 
d =
 
& & 


. . . .
 
. . .  . 
. . . 
 . 

& &  
f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] f [xn−2 , xn−1 , xn ]

et ainsi de suite ...

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Algorithme interpolation de Newton

pour tous les i de 0 à n faire

di := f (xi )
pour tous les j de 1 à n faire
pour tous les i de n à j faire
di := (di − di−1 )/(xi − xi−j )

Algorithme d’Hörner

b := dn
pour tous les i de n − 1 à 0 faire
b := di + (x − xi )b

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Remarque
Avec cet algorithme, il est toujours très facile d’ajouter un point
d’abscisse x−1 et d’obtenir les coefficients du polynôme Pn+1 sans être
obligé de refaire tous les calculs.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Remarque
Avec cet algorithme, il est toujours très facile d’ajouter un point
d’abscisse x−1 et d’obtenir les coefficients du polynôme Pn+1 sans être
obligé de refaire tous les calculs.

f (x0 ) = f [x0 ]
&
f (x1 ) = f [x1 ] → f [x0 , x1 ]
& &
f (x2 ) = f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]
& & &
. . . ..
. . . .
. . .
& & &
f (xn ) = f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] → ··· → f [x0 x1 , . . . , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Remarque
Avec cet algorithme, il est toujours très facile d’ajouter un point
d’abscisse x−1 et d’obtenir les coefficients du polynôme Pn+1 sans être
obligé de refaire tous les calculs.

f (x−1 ) = f [x−1 ]

f (x0 ) = f [x0 ]
&
f (x1 ) = f [x1 ] → f [x0 , x1 ]
& &
f (x2 ) = f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]
& & &
. . . ..
. . . .
. . .
& & &
f (xn ) = f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] → ··· → f [x0 x1 , . . . , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Remarque
Avec cet algorithme, il est toujours très facile d’ajouter un point
d’abscisse x−1 et d’obtenir les coefficients du polynôme Pn+1 sans être
obligé de refaire tous les calculs.

f (x−1 ) = f [x−1 ]
&
f (x0 ) = f [x0 ] → f [x−1 , x0 ]
&
f (x1 ) = f [x1 ] → f [x0 , x1 ]
& &
f (x2 ) = f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]
& & &
. . . ..
. . . .
. . .
& & &
f (xn ) = f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] → ··· → f [x0 x1 , . . . , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Remarque
Avec cet algorithme, il est toujours très facile d’ajouter un point
d’abscisse x−1 et d’obtenir les coefficients du polynôme Pn+1 sans être
obligé de refaire tous les calculs.

f (x−1 ) = f [x−1 ]
&
f (x0 ) = f [x0 ] → f [x−1 , x0 ]
& &
f (x1 ) = f [x1 ] → f [x0 , x1 ] → f [x−1 , x0 , x1 ]
& &
f (x2 ) = f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]
& & &
. . . ..
. . . .
. . .
& & &
f (xn ) = f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] → ··· → f [x0 x1 , . . . , xn ]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Remarque
Avec cet algorithme, il est toujours très facile d’ajouter un point
d’abscisse x−1 et d’obtenir les coefficients du polynôme Pn+1 sans être
obligé de refaire tous les calculs.

f (x−1 ) = f [x−1 ]
&
f (x0 ) = f [x0 ] → f [x−1 , x0 ]
& &
f (x1 ) = f [x1 ] → f [x0 , x1 ] → f [x−1 , x0 , x1 ]
& &
f (x2 ) = f [x2 ] → f [x1 , x2 ] → f [x0 , x1 , x2 ]
& & &
. . . ..
. . . .
. . .
& & &
f (xn ) = f [xn ] → f [xn−1 , xn ] → f [xn−2 , xn−1 , xn ] → ··· → f [x0 x1 , . . . , xn ]

et ainsi de suite...
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Retour à l’exemple de la fonction sinus

fonction sinus sur [−π, π] - 7 points d’interpolation - Newton-Horner

Interpolation de la fonction sinus - Methode Newton-Horner

1.5
points d'interpolation
1
polynome d'interpolation
fonction exacte
0.5

-0.5

-1

-1.5
-4 -3 -2 -1 0 1 2 3 4

Erreur d'interpolation
0.01

0.005

-0.005

-0.01
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Retour à l’exemple de la fonction sinus

fonction sinus sur [−π, π] - 21 points d’interpolation - Newton-Horner

Interpolation de la fonction sinus - Methode Newton-Horner

1
points d'interpolation
polynome d'interpolation
0.5 fonction exacte

-0.5

-1
-4 -3 -2 -1 0 1 2 3 4

-14 Erreur d'interpolation

10
1.5

0.5

-0.5

-1

-1.5
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Retour à l’exemple de la fonction sinus

fonction sinus sur [−π, π] - 71 points d’interpolation - Newton-Horner

Interpolation de la fonction sinus - Methode Newton-Horner

1
points d'interpolation
polynome d'interpolation
0.5 fonction exacte

-0.5

-1
-4 -3 -2 -1 0 1 2 3 4

Erreur d'interpolation
1

0.5

-0.5

-1
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Retour à l’exemple de la fonction sinus

fonction sinus sur [−π, π] - 71 points d’interpolation - Lagrange

Interpolation de la fonction sinus - Methode Lagrange

1
points d'interpolation
polynome d'interpolation
0.5 fonction exacte

-0.5

-1
-4 -3 -2 -1 0 1 2 3 4

-15 Erreur d'interpolation

10
2

-1

-2

-3
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

La formule de Newton peut parfois s’avérer instable numériquement

lorsque le nombre d’abscisses d’interpolation devient grand !

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule barycentrique de Lagrange

Pour éviter ces phénomènes d’instabilité numérique lorsque le nombre n

d’abscisses d’interpolation devient grand, il est préférable d’utiliser la
formule barycentrique de Lagrange :
pour tout x tel que x 6= xi , ∀ i ∈ J0, nK
n
P f (xi )
(x−xi )ωi
i=0
Pn (x) = n
1
P
(x−xi )ωi
i=0

avec
n
Y
∀ i ∈ J0, nK, ωi = (xi − xk ).
k=0
k6=i

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Formule barycentrique de Lagrange

n
P f (xi )
(x−xi )ωi
i=0
Pn (x) = n
1
P
(x−xi )ωi
i=0

Remarques
Cette formule n’est valable que pour x 6= xi ∀ i ∈ J0, nK.
Toutefois, pour x = xi , Pn (xi ) = f (xi ) qui est connu !
Il est nécessaire de calculer les (n + 1) coefficients (ωi ). Toutefois, ce
calcul ne sera fait qu’une seule fois !

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Retour à l’exemple de la fonction sinus

fonction sinus sur [−π, π] - 71 points d’interpolation - Formule

Barycentrique

Interpolation de la fonction sinus - Methode barycentrique

1
points d'interpolation
polynome d'interpolation
0.5 fonction exacte

-0.5

-1
-4 -3 -2 -1 0 1 2 3 4

-15 Erreur d'interpolation

10
1.5

0.5

-0.5

-1

-1.5
-4 -3 -2 -1 0 1 2 3 4

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation d’Hermite

Objectif
Soit f définie sur un intervalle [a, b] et soient x0 , . . . , xn n + 1 points de
[a, b]. l’objectif est de construire un polynôme d’interpolation P de f
vérifiant :
non seulement P(xi ) = f (xi ) pour tout 0 ≤ i ≤ n

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation d’Hermite

Objectif
Soit f définie sur un intervalle [a, b] et soient x0 , . . . , xn n + 1 points de
[a, b]. l’objectif est de construire un polynôme d’interpolation P de f
vérifiant :
non seulement P(xi ) = f (xi ) pour tout 0 ≤ i ≤ n
mais aussi P 0 (xi ) = f 0 (xi ) pour tout 0 ≤ i ≤ n

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation d’Hermite

Objectif
Soit f définie sur un intervalle [a, b] et soient x0 , . . . , xn n + 1 points de
[a, b]. l’objectif est de construire un polynôme d’interpolation P de f
vérifiant :
non seulement P(xi ) = f (xi ) pour tout 0 ≤ i ≤ n
mais aussi P 0 (xi ) = f 0 (xi ) pour tout 0 ≤ i ≤ n

c’est l’interpolation d’Hermite

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Interpolation d’Hermite

Théorème
Il existe un unique polynôme Pn de degré (2n + 1) vérifiant
Pn (xi ) = f (xi ), Pn0 (xi ) = f 0 (xi ) ∀i = 0, 1, . . . , n.

Le polynôme s’écrit
n
X n
X
Pn (x) = f (xi )Hi (x) + f 0 (xi )H̃i (x)
i=0 i=0

avec
Hi (x) = 1 − 2L0i (xi )(x − xi ) L2i (x) H̃i (x) = (x − xi )L2i (x).
 
et

Le polynôme Pn est appelé polynôme d’interpolation d’Hermite de la

fonction f aux points (xi , f (xi ))i∈J0,nK .
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Interpolation polynomiale

Erreur dans l’nterpolation d’Hermite

Théorème
Soit f : [a, b] −→ R, (2n + 2) fois continument différentiable et Pn le
polynôme d’interpolation d’Hermite aux points (xi , f (xi ))i∈J0,nK . Nous
avons alors
M2n+2  2 
|En (x)| ≤ π (x)
(2n + 2)! n
où  
M2n+2 = max f (2n+2) (x)
 
x∈[a,b]

et
n
Y
∀ x ∈ [a, b], πn (x) = (x − xi ).
i=0

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Approximation par morceaux

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Approximation par morceaux

Introduction
Pour éviter les instabilités du type phénomènes de Runge, on peut faire
de l’interpolation polynomiale de degré peu élevé sur des intervalles de
petites tailles :
étant donnée f : [a, b] → R connue en (n + 1) abscisses
a = x0 < x1 < ... < xn = b, on l’interpole par des fonctions continues
dont la restriction à chaque intervalle [xi−1 , xi ] est polynomiale.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Approximation par morceaux

Exemple : approximation linéaire par morceaux

La restriction de l’approximation P à l’intervalle [xi−1 , xi ] est donnée par :

f (xi ) − f (xi−1 )
Pi (x) = f (xi−1 ) + (x − xi−1 )
(xi − xi−1 )
= f [xi−1 ] + f [xi−1 , xi ] (x − xi−1 )

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Approximation par morceaux

Exemple : approximation linéaire par morceaux

La restriction de l’approximation P à l’intervalle [xi−1 , xi ] est donnée par :

f (xi ) − f (xi−1 )
Pi (x) = f (xi−1 ) + (x − xi−1 )
(xi − xi−1 )
= f [xi−1 ] + f [xi−1 , xi ] (x − xi−1 )

1,2

0,8

0,4

-3,2 -2,4 -1,6 -0,8 0 0,8 1,6 2,4 3,2

-0,4

-0,8

-1,2

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Approximation par morceaux

Exemple : approximation linéaire par morceaux

La restriction de l’approximation P à l’intervalle [xi−1 , xi ] est donnée par :

f (xi ) − f (xi−1 )
Pi (x) = f (xi−1 ) + (x − xi−1 )
(xi − xi−1 )
= f [xi−1 ] + f [xi−1 , xi ] (x − xi−1 )

1,2

0,8

0,4

-3,2 -2,4 -1,6 -0,8 0 0,8 1,6 2,4 3,2

-0,4

-0,8

-1,2

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Approximation par morceaux

Généralisation
sur chaque intervalle [xi , xi+1 ], on construit un polynôme
d’interpolation de Lagrange Pi,m de la fonction f à l’aide de (m + 1)
point de [xi , xi+1 ], y0i < y1i < · · · < ymi

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Approximation par morceaux

Généralisation
sur chaque intervalle [xi , xi+1 ], on construit un polynôme
d’interpolation de Lagrange Pi,m de la fonction f à l’aide de (m + 1)
point de [xi , xi+1 ], y0i < y1i < · · · < ymi
pour assurer la continuité, on impose

y0i = xi , ymi = xi+1 ∀i

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Approximation par morceaux

Théorème
Soit f : [a, b] −→ R et soient x0 < x1 < · · · < xn n + 1 points de [a, b].
Choisissons sur chaque intervalle [xi , xi+1 ] m+1 points
xi = y0i < y1i < · · · < ymi = xi+1 .
Alors, il existe une unique fonction fm,n continue sur [a, b] telle que
la fonction fm,n|[xi ,xi+1 ] est un polynôme de degré m
fm,n (yji ) = f (yji ) pour tout 0 ≤ j ≤ m et pour tout 0 ≤ i ≤ n
De plus, si f ∈ C([a, b], R), alors

hm+1
kf − fm,n k∞ ≤ kf (m+1) k∞
(m + 1)!

avec h = max |xi+1 − xi |

0≤i≤n−1

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Principe
Le mot ”spline” en anglais signifie ”languette élastique”.
Si f : [a, b] → R est une fonction connue en (n + 1) points
a = x0 < x1 < ... < xn = b, on s’intéresse à la courbe décrite par une
languette forcée de passer par les points (xi , f (xi )) pour tout i ∈ J0, nK.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Principe
Le mot ”spline” en anglais signifie ”languette élastique”.
Si f : [a, b] → R est une fonction connue en (n + 1) points
a = x0 < x1 < ... < xn = b, on s’intéresse à la courbe décrite par une
languette forcée de passer par les points (xi , f (xi )) pour tout i ∈ J0, nK.

Mathématiquement, ce problème peut être formulé comme suit : on

cherche une fonction s : [a, b] → R satisfaisant :

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Principe
Le mot ”spline” en anglais signifie ”languette élastique”.
Si f : [a, b] → R est une fonction connue en (n + 1) points
a = x0 < x1 < ... < xn = b, on s’intéresse à la courbe décrite par une
languette forcée de passer par les points (xi , f (xi )) pour tout i ∈ J0, nK.

Mathématiquement, ce problème peut être formulé comme suit : on

cherche une fonction s : [a, b] → R satisfaisant :
s(xi ) = f (xi ) pour tout i ∈ J0, nK.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Principe
Le mot ”spline” en anglais signifie ”languette élastique”.
Si f : [a, b] → R est une fonction connue en (n + 1) points
a = x0 < x1 < ... < xn = b, on s’intéresse à la courbe décrite par une
languette forcée de passer par les points (xi , f (xi )) pour tout i ∈ J0, nK.

Mathématiquement, ce problème peut être formulé comme suit : on

cherche une fonction s : [a, b] → R satisfaisant :
s(xi ) = f (xi ) pour tout i ∈ J0, nK.
s de classe C 2 sur [a, b]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Pour cela nous allons faire une interpolation par morceaux, en

prenant sur chaque intervalle [xi , xi+1 ] le polynôme d’interpolation
d’Hermite de la fonction f aux points xi et xi+1 (2 points, n = 1)

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Pour cela nous allons faire une interpolation par morceaux, en

prenant sur chaque intervalle [xi , xi+1 ] le polynôme d’interpolation
d’Hermite de la fonction f aux points xi et xi+1 (2 points, n = 1)
Il s’agit du polynôme de degré 3

si (x) = f (xi )Φ1,i (x) + f (xi+1 )Φ2,i (x) + di Φ̃1,i (x) + di+1 Φ̃2,i (x)

avec, en posant hi = xi+1 − xi ,

x − xi+1 2
   
x − xi
Φ1,i (x) = 1+2
hi hi
x − xi 2
   
x − xi+1
Φ2,i (x) = 1−2
hi hi
2
x − xi 2
  
x − xi+1
Φ̃1,i (x) = (x − xi ), Φ̃2,i (x) = (x − xi+1 )
hi hi

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

On remarquera que nous ne connaissons pas les valeurs f 0 (xi ) pour

faire cette interpolation d’Hermite

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

On remarquera que nous ne connaissons pas les valeurs f 0 (xi ) pour

faire cette interpolation d’Hermite
C’est pourquoi, nous avons posé

s 0 (xi ) = di , ∀ i ∈ J0, nK,

les coefficients di pouvant a priori être quelconques.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

On remarquera que nous ne connaissons pas les valeurs f 0 (xi ) pour

faire cette interpolation d’Hermite
C’est pourquoi, nous avons posé

s 0 (xi ) = di , ∀ i ∈ J0, nK,

les coefficients di pouvant a priori être quelconques.

Ainsi nous obtenons une fonction s définie sur [a, b] vérifiant
s(xi ) = f (xi ) pour tout i ∈ J0, nK, de classe C 2 sur [xi , xi+1 ] pour
tout i ∈ J0, n − 1K et de classe C 1 sur [a, b] (d’où l’intérêt de faire de
l’interpolation d’Hermite !)

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

La fonction s sera donc de classe C 2 sur [a, b] si et seulement si

si00 (xi+1 ) = si+1

00
(xi+1 ), ∀ i ∈ J0, n − 2K.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

La fonction s sera donc de classe C 2 sur [a, b] si et seulement si

si00 (xi+1 ) = si+1

00
(xi+1 ), ∀ i ∈ J0, n − 2K.

On obtient ainsi les (n − 1) relations : pour tout 1 ≤ i ≤ n − 1

     
di−1 2 2 di+1 f (xi−1 ) 1 1 f (xi+1 )
+ + di + =3 − 2 + 2
− f (xi ) +
hi−1 hi hi+1 hi hi−1 hi−1 hi2 hi2

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

La fonction s sera donc de classe C 2 sur [a, b] si et seulement si

si00 (xi+1 ) = si+1

00
(xi+1 ), ∀ i ∈ J0, n − 2K.

On obtient ainsi les (n − 1) relations : pour tout 1 ≤ i ≤ n − 1

     
di−1 2 2 di+1 f (xi−1 ) 1 1 f (xi+1 )
+ + di + =3 − 2 + 2
− 2 f (xi ) +
hi−1 hi hi+1 hi hi−1 hi−1 hi hi2

Pour compléter ce système, nous ajoutons des conditions qui vont

déterminer le type de splines utilisées
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Spline naturel : s 00 (a) = 0 et s 00 (b) = 0.

Ces conditions donnent alors les deux relations manquantes :
   
f (x1 ) f (x0 ) f (xn−1 ) f (xn )
2d0 + d1 = 3 − , dn−1 + 2dn = 3 − + .
h0 h0 hn−1 hn−1

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Spline naturel : s 00 (a) = 0 et s 00 (b) = 0.

Ces conditions donnent alors les deux relations manquantes :
   
f (x1 ) f (x0 ) f (xn−1 ) f (xn )
2d0 + d1 = 3 − , dn−1 + 2dn = 3 − + .
h0 h0 hn−1 hn−1

Spline scellé : on suppose données les pentes aux extrémités

s 0 (a) = d0 et s 0 (b) = dn .
Dans ce cas nous avons seulement un système à (n − 1) inconnues
et nous avons déjà (n − 1) équations.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Spline naturel : s 00 (a) = 0 et s 00 (b) = 0.

Ces conditions donnent alors les deux relations manquantes :
   
f (x1 ) f (x0 ) f (xn−1 ) f (xn )
2d0 + d1 = 3 − , dn−1 + 2dn = 3 − + .
h0 h0 hn−1 hn−1

Spline scellé : on suppose données les pentes aux extrémités

s 0 (a) = d0 et s 0 (b) = dn .
Dans ce cas nous avons seulement un système à (n − 1) inconnues
et nous avons déjà (n − 1) équations.
Spline périodique : si la fonction est périodique, il est naturel de
l’interpoler par une fonction périodique. On a alors :

s 0 (a) = s 0 (b) et s 00 (a) = s 00 (b).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Dans les trois cas, on obtient un système linéaire

Ad = b

dans lequel la matrice A est tridiagonale et à diagonale strictement

dominante, donc inversible.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Dans les trois cas, on obtient un système linéaire

Ad = b

dans lequel la matrice A est tridiagonale et à diagonale strictement

dominante, donc inversible.

Ainsi, ce système linéaire admet une unique solution, ce qui prouve

l’existence d’une fonction spline cubique à dérivée seconde continue
comme prévu.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Remarque
Dans le cas d’abscisses (xi ) équidistantes, on a hi = h pour tout
i ∈ J0, n − 1K et le système linéaire se simplifie considérablement.

Exemple : spline scellé

 
2 1
 1 4 1 
 
A=
 .. .. 
 ... . . 

 1 4 1 
1 2

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Les splines cubiques

Théorème : erreur du spline scellé

Soit f : [a, b] → R de classe C 4 , soit a = x0 < x1 < . . . < xn = b, (n + 1)
points de [a, b] et soit s le spline qui passe par les points (xi , f (xi )) et qui
satisfait s 0 (x0 ) = f 0 (x0 ) et s 0 (xn ) = f 0 (xn ).
Alors, avec h = max hi où hi = xi+1 − xi , on a
i

5 4
|f (x) − s(x)| ≤ h max |f (4) (ξ)|.
384 ξ∈[a,b]

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - Spline avec 7 points équidistants

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - Spline avec 9 points équidistants

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - Spline avec 11 points équidistants

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation par morceaux

Exemple

fonction x 7→ 1/(1 + x 2 ) sur [−5, 5] - Spline avec 15 points équidistants

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
-5 -4 -3 -2 -1 0 1 2 3 4 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Approximation au sens des moindres carrés

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Jusqu’à maintenant nous avons toujours considéré l’approximation

d’une fonction par un procédé d’interpolation à l’aide des valeurs
connues de la fonction f en des abscisses (xi ).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Jusqu’à maintenant nous avons toujours considéré l’approximation

d’une fonction par un procédé d’interpolation à l’aide des valeurs
connues de la fonction f en des abscisses (xi ).
Ceci suppose que les valeurs (f (xi )) soient connues exactement.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Jusqu’à maintenant nous avons toujours considéré l’approximation

d’une fonction par un procédé d’interpolation à l’aide des valeurs
connues de la fonction f en des abscisses (xi ).
Ceci suppose que les valeurs (f (xi )) soient connues exactement.
Or, souvent ce n’est pas le cas, en particulier lorsque les valeurs de f
proviennent de mesures expérimentales.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

1,5

0,5

-2,4 -2 -1,6 -1,2 -0,8 -0,4 0 0,4 0,8 1,2 1,6 2 2,4

-0,5

-1

-1,5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

1,5

0,5

-2,4 -2 -1,6 -1,2 -0,8 -0,4 0 0,4 0,8 1,2 1,6 2 2,4

-0,5

-1

-1,5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

1,5

0,5

-2,4 -2 -1,6 -1,2 -0,8 -0,4 0 0,4 0,8 1,2 1,6 2 2,4

-0,5

-1

-1,5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

1,5

0,5

-2,4 -2 -1,6 -1,2 -0,8 -0,4 0 0,4 0,8 1,2 1,6 2 2,4

-0,5

-1

-1,5

Une analyse succinte du phénomène ci-dessus, fréquent dans la réalité

physique, conduit à penser que ces valeurs mesurées f (xk ) contiennent
une information juste mais aussi un certain ”bruit”.
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Intuitivement, on est conduit à penser que les données f (xk ) contiennent

une première composante variant lentement : c’est elle qui fournit
l’information
une deuxième composante variant très rapidement : c’est celle qui
est due au ”bruit” inévitable.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Intuitivement, on est conduit à penser que les données f (xk ) contiennent

une première composante variant lentement : c’est elle qui fournit
l’information
une deuxième composante variant très rapidement : c’est celle qui
est due au ”bruit” inévitable.

L’objectif est d’éliminer la deuxième composante pour ne retenir que la

première.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Le principe de l’étude qui suit consiste à chercher une approximation g

de la fonction f sous la forme

g (x) = c1 θ1 (x) + c2 θ2 (x) + ... + cn θn (x)

où les θi sont des fonctions connues (par exemple des polynômes) et les
ci des coefficients à déterminer.

Implicitement, n sera assez grand pour contenir l’information, mais

suffisamment petit pour se débarrasser des ”bruits”.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Le principe de l’étude qui suit consiste à chercher une approximation g

de la fonction f sous la forme

g (x) = c1 θ1 (x) + c2 θ2 (x) + ... + cn θn (x)

où les θi sont des fonctions connues (par exemple des polynômes) et les
ci des coefficients à déterminer.

Ainsi dans notre exemple, on pourra déterminer c1 et c2 pour que les

déviations
{f (xk ) − (c1 + c2 xk ) ; k ∈ J0, pK}
soient les plus petites possibles.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Remarques
Contrairement à l’interpolation, on ne cherche pas nécessairement à
annuler ces déviations

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Introduction

Remarques
Contrairement à l’interpolation, on ne cherche pas nécessairement à
annuler ces déviations
Il existe plusieurs notions de ”le plus petit possible”
Celle utilisée dans le paragraphe précédent consiste à minimiser :

max |f (xk ) − (c1 + c2 xk )| .

0≤k≤p

On peut tout aussi bien penser à minimiser

X
|f (xk ) − (c1 + c2 xk )| .
0≤k≤p

Ceci conduira en général à des (c1 , c2 ) différents.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

C’est une troisième voie qui est le plus souvent choisie dans la pratique,
car elle conduit à un problème de minimisation quadratique en les
inconnues (ci ), à savoir : minimiser
X 2
|f (xk ) − (c1 + c2 xk )|
0≤k≤p

ou plus généralement minimiser

X 2
(f (xk ) − (c1 θ1 (xk ) + ... + cn θn (xk ))) .
0≤k≤p

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Posons
X 2
E (c1 , c2 , ..., cn ) = (f (xk ) − (c1 θ1 (xk ) + ... + cn θn (xk ))) .
0≤k≤p

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Posons
X 2
E (c1 , c2 , ..., cn ) = (f (xk ) − (c1 θ1 (xk ) + ... + cn θn (xk ))) .
0≤k≤p

Si E admet un minimum en c = (c1 , c2 , ..., cn ), alors on a

∂E
(c) = 0, ∀ı ∈ J1, nK
∂ci

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Posons
X 2
E (c1 , c2 , ..., cn ) = (f (xk ) − (c1 θ1 (xk ) + ... + cn θn (xk ))) .
0≤k≤p

Si E admet un minimum en c = (c1 , c2 , ..., cn ), alors on a

∂E
(c) = 0, ∀ı ∈ J1, nK
∂ci
soit encore
X
2 θi (xk ) (f (xk ) − (c1 θ1 (xk ) + ... + cn θn (xk ))) = 0, ∀ i ∈ J1, nK
0≤k≤p

système linéaire de n équations aux n inconnues c1 , c2 , ..., cn , appelées

parfois équations normales.
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Interprétation géométrique
Notons
e = (e0 , e1 , ..., ep ) le vecteur erreur de composantes

ek = f (xk ) − (c1 θ1 (xk ) + ... + cn θn (xk ))

θi = (θi (x0 ), θi (x1 ), ..., θi (xp )).

p
ui vi le produit scalaire dans Rp+1 .
P
hu, v i =
i=0

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Interprétation géométrique
Notons
e = (e0 , e1 , ..., ep ) le vecteur erreur de composantes

ek = f (xk ) − (c1 θ1 (xk ) + ... + cn θn (xk ))

θi = (θi (x0 ), θi (x1 ), ..., θi (xp )).

p
ui vi le produit scalaire dans Rp+1 .
P
hu, v i =
i=0

Alors, les équations normales expriment

he, θi i = 0, ∀i ∈ J1, nK.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Interprétation géométrique
Le vecteur erreur e doit donc être orthogonal à tous les vecteurs θi

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Interprétation géométrique
Le vecteur erreur e doit donc être orthogonal à tous les vecteurs θi
Géométriquement, cela revient à dire que le vecteur
c1 θ1 + c2 θ2 + ... + cn θn solution est la projection orthogonale du
vecteur P = (f (x0 ), ..., f (xp )) sur le sous espace engendré par les
(θi ).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Exemple : ajustement linéaire

Ici
n = 2, θ1 (x) = 1, θ2 (x) = x.
On cherche donc la fonction affine c1 + c2 x la plus voisine au sens des
moindres carrés des valeurs (xk , f (xk )).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Exemple : ajustement linéaire

Ici
n = 2, θ1 (x) = 1, θ2 (x) = x.
On cherche donc la fonction affine c1 + c2 x la plus voisine au sens des
moindres carrés des valeurs (xk , f (xk )).

Le système des équations normales devient alors

 X

 (f (xk ) − (c1 + c2 xk )) = 0

0≤k≤p
X


 xk (f (xk ) − (c1 + c2 xk )) = 0
0≤k≤p

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Exemple : ajustement linéaire

ou encore
p p
 !
 X X



 (p + 1)c 1 + x k c 2 = f (xk )
k=0 k=0
p p p
! !
X X X
2

xk c 1 + xk c 2 = xk f (xk )




k=0 k=0 k=0

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

ou encore en introduisant les notations suivantes :

p p
1 X 1 X 2
m= xk (moyenne des xk ), m2 = xk (moment d’ordre 2)
p+1 p+1
k=0 k=0

p p
1 X 1 X
f := f (xk ), f = xk f (xk ),
p+1 p+1
k=0 k=0
(
c1 + mc2 = f
mc1 + m2 c2 = f .

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

ou encore en introduisant les notations suivantes :

p p
1 X 1 X 2
m= xk (moyenne des xk ), m2 = xk (moment d’ordre 2)
p+1 p+1
k=0 k=0

p p
1 X 1 X
f := f (xk ), f = xk f (xk ),
p+1 p+1
k=0 k=0
(
c1 + mc2 = f
mc1 + m2 c2 = f .

Son unique solution est donnée par :

m2 f − mf f − mf
c1 = , c2 = .
m2 − m 2 m2 − m2
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
On vérifie que m2 6= m2 si les (xk ) sont distincts.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
On vérifie que m2 6= m2 si les (xk ) sont distincts.

Retour à l’exemple

k 0 1 2 3 4 5 6 7
xk -2 -1.5 -1 -0.5 0 0.5 1 1.5
f (xk ) -0.6 -0.22 0.2 0.05 0.8 0.72 1.15 1.235

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
On vérifie que m2 6= m2 si les (xk ) sont distincts.

Retour à l’exemple

k 0 1 2 3 4 5 6 7
xk -2 -1.5 -1 -0.5 0 0.5 1 1.5
f (xk ) -0.6 -0.22 0.2 0.05 0.8 0.72 1.15 1.235

m = −0.25, m2 = 1.375, f = 0.416875, f = 0.5834375.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
On vérifie que m2 6= m2 si les (xk ) sont distincts.

Retour à l’exemple

k 0 1 2 3 4 5 6 7
xk -2 -1.5 -1 -0.5 0 0.5 1 1.5
f (xk ) -0.6 -0.22 0.2 0.05 0.8 0.72 1.15 1.235

m = −0.25, m2 = 1.375, f = 0.416875, f = 0.5834375.

c1 = 0.54785714, c2 = 0.52392857
y = 0.54785714 + 0.52392857x
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
On vérifie que m2 6= m2 si les (xk ) sont distincts.

Retour à l’exemple

k 0 1 2 3 4 5 6 7
xk -2 -1.5 -1 -0.5 0 0.5 1 1.5
f (xk ) -0.6 -0.22 0.2 0.05 0.8 0.72 1.15 1.235

1,5

0,5

-2,4 -2 -1,6 -1,2 -0,8 -0,4 0 0,4 0,8 1,2 1,6 2 2,4

-0,5

Didier Schmitt IECL

Analyse Numérique -1
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Cas général
Dans le cas général, on montre que le système des équations normales a
toujours une solution. Il s’écrit

Ac = b

où
c = (c1 , ..., cn )
A est la matrice dont les coefficients sont {hθj , θi i}1≤i≤n ,1≤j≤n
b = (b1 , ..., bn ) avec bi = hf , θi i .

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
La matrice A est toujours une matrice symétrique

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
La matrice A est toujours une matrice symétrique
Si on choisit les facteurs θi (x) de telle façon que les produits
scalaires hθj , θi i soient nuls pour i 6= j, c’est-à-dire
p
X
θj (xk )θi (xk ) = 0, ∀i 6= j,
k=0

alors la matrice sera diagonale et il n’y a plus de résolution du

système linéaire à faire !

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
La matrice A est toujours une matrice symétrique
Si on choisit les facteurs θi (x) de telle façon que les produits
scalaires hθj , θi i soient nuls pour i 6= j, c’est-à-dire
p
X
θj (xk )θi (xk ) = 0, ∀i 6= j,
k=0

alors la matrice sera diagonale et il n’y a plus de résolution du

système linéaire à faire !
En effet dans ce cas, nous avons directement
hb, θi i
ci = , ∀ i ∈ J1, nK.
hθi , θi i

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Remarque
si les points xk sont équidistants dans l’intervalle [a, b], on a :
p p    
X X b−a b−a
0= θj (xk )θi (xk ) = θj a + k θi a + k
p p
k=0 k=0

or
p     Z b
X b−a b−a p
θj a + k θi a + k ∼ θj (x)θi (x)dx
p p b−a a
k=0

si p est assez grand.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Méthode des moindres carrées

Ainsi, une version continue de notre problème consiste à considérer les

polynômes (ou des fonctions plus générales) θi telles que
Z b
θj (x)θi (x)dx = 0.
a

cette intégrale représente également un produit scalaire sur l’espace

des fonctions
par analogie on dit que les deux fonctions sont orthogonales
le bon espace fonctionnel associé est alors L2 ([a, b])

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Polynômes orthogonaux

Nous allons maintenant étudier les suites de polynômes orthogonaux pour

des produits scalaires du type :
Z b
hP, Qi = P(x)Q(x)w (x)dx
a

où w est une fonction continue strictement positive sur ]a, b[

Définition
Par suite de polynômes orthogonaux, on entend une suite (finie ou infinie)
P0 (x), P1 (x), . . . telle que

Pi est de degré i

hPi , Pj i = 0, si i 6= j.

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Proposition
Soit (Pn ) une suite de polynômes orthogonaux ; alors
Tout polynôme Q de degré inférieur ou égal à k s’écrit de façon
unique
hPi , Qi
Q(x) = d0 P0 (x) + d1 P1 (x) + ... + dk Pk (x) avec di =
hPi , Pi i

Si Q est de degré < k, alors hQ, Pk i = 0

Si Ai désigne le coefficient du terme de plus haut degré de Pi , on a
la relation de récurrence à trois termes
Pi (x)
Pbi+1 (x) = (x−Bi )Pbi (x)−Ci Pbi−1 (x) où Pbi (x) := (polynôme normalisé)
Ai
D E D E
x Pbi (x), Pbi (x) Pbi (x), Pbi (x)
Bi = D E , Ci = D E.
Pbi (x), Pbi (x) Pbi (x), Pbi−1 (x)
Pi a exactement i zéros réels distincts
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Exemples classiques de polynômes orthogonaux

Polynômes de Jacobi

[a, b] = [−1, 1] et w (x) = (1 − x)α (1 + x)β

avec α > −1 et β > −1
On leur attribue des noms différents dans les cas particuliers suivants :
α = β = 0 : polynômes de Legendre. Une fois les polynômes
normalisés, on a la relation de récurrence :
(2n + 1)xPn (x) − nPn−1 (x)
Pn+1 (x) = .
n+1

α = β = − 21 : polynômes de Chebyshev de première espèce définis

par
Tn+1 (x) = 2xTn (x) − Tn−1 (x).
1
α=β= 2 : polynômes de Chebyshev de seconde espèce
Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Exemples classiques de polynômes orthogonaux

Polynômes de Laguerre

[a, b[ = [0, +∞[ et w (x) = e −x

La relation de récurrence s’écrit :
1
Pn+1 (x) = − (x − 2n − α − 1)Pn (x) + (n + α)Pn−1 (x)
n+1

Polynômes d’Hermite

2
]a, b[ = ]−∞, +∞[ et w (x) = e −x
La relation de récurrence s’écrit :

Hn+1 (x) = 2xHn (x) − 2nHn−1 (x)

Didier Schmitt IECL
Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Polynômes orthogonaux

Théorème
Soit f : [a, b] → R telle que
Z b
hf , f i = f 2 (x)w (x)dx < ∞.
a

Alors, pour tout k ≥ 1 (resp. k ≤ N − 1), si P0 , P1 , ..., Pk est une suite

de polynômes orthogonaux pour le produit scalaire h.i, il existe un et un
seul polynôme Q de la forme

Q(x) = c0 P0 (x) + c1 P1 (x) + ... + ck Pk (x)

minimisant hf − Q, f − Qi. Les coefficients sont donnés par

hPi , f i
ci = , i = 0, ..., k.
hPi , Pi i

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Polynômes orthogonaux

Exemple
Trouver le polynôme P de degré inférieur ou égal à 3 qui minimise
Z 1
2
(e x − P(x)) dx.
−1

On utilise comme base de polynômes les polynômes de Legendre, soit

   
3 1 5 3
L0 (x) = 1, L1 (x) = x, L2 (x) = x2 − , L3 (x) = x3 − x .
2 3 2 5

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Polynômes orthogonaux

Exemple
On calcule alors
Z 1 1
Z 1 2
hf , L0 i = e x dx = e − hf , L1 i = xe x dx =
−1 e −1 e

3
Z 1 
1

7 5
Z 1 
3

37
hf , L2 i = ex x2 − dx = e− hf , L3 i = ex x3 − dx = −5e+ .
2 −1 3 e 2 −1 5 e
2
D’autre part, on montre que hLi , Li i = 2i+1 .
On en déduit le polynôme solution :
P(x) = 1, 175201194L0 (x)+1, 10363824L1 (x)+0, 3578143506L2 (x)+0, 07045563367L3 (x).

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Polynômes trigonométriques

Remarque
les fonctions (cos(kx))k≥0 et (sin(kx))k≥0 sont orthogonales pour le
produit scalaire Z π
hf , g i = f (x)g (x)dx
−π

En effet, nous avons pour tout k 6= p

Z π Z π
1
cos(kx) cos(px)dx = [cos((k + p)x) + cos((k − p)x)] dx = 0.
−π 2 −π
Z π Z π
1
sin(kx) sin(px)dx = [cos((k − p)x) − cos((k − p)x)] dx = 0.
−π 2 −π

et pour tout k ≥ 0, p ≥ 0
Z π Z π
1
cos(kx) sin(px)dx = [sin((k + p)x) + sin((p − k)x)] dx = 0.
−π 2 −π

Didier Schmitt IECL

Analyse Numérique
Interpolation et approximation
Approximation au sens des moindres carrés

Polynômes trigonométriques

Théorème
Soit f : [−π, π] → R continue. Alors il existe une unique meilleure
approximation au sens des moindres carrés dans l’espace des polynômes
trigonométriques de la forme
n
X n
X
S(x) = a0 + ak cos(kx) + bk sin(kx).
k=1 k=1

Ses coefficients sont donnés par :

Z π
 1
 a0 = f (x)dx
2πZ −π



 π
 1
ak = f (x) cos(kx)dx
 π Z−π
 π
 bk = 1


 f (x) sin(kx)dx
π −π

Didier Schmitt IECL

Analyse Numérique