Interpolation polynomiale et approximation

Ibrahim Trabelsi

Cours - Analyse Numérique - 2 IM 1 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Plan

1 Introduction

2 La forme de Lagrange

3 Forme de Newton : différences divisées

4 Erreur d’interpolation

5 Approximation

Cours - Analyse Numérique - 2 IM 2 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Introduction

- Soit f (x ) = exp (x ).
- Déterminer P (X ) = ax 2 + bx + c f (x )
qui vérifie :
P (0) = f (0) = 1, P (0.5) =
f (0.5) = e0.5 et P (1) = f (1) = e
- Résoudre le système
 c = 1
0.52 a + 0.5b + 1 = e0.5
a+b+c = e

0 0.5 1

Cours - Analyse Numérique - 2 IM 3 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

- Soient (x0 , y0 ), (x1 , y1 ), · · · , (xn , yn ), (n + 1) points distincts

deux à deux.
Problème :
Existe-t-il un polynôme P ∈ Rn [X ] tel que
P (xi ) = yi , i = 0, 1, · · · , n.
Si oui, quel est son degré ? Est-il unique ? Quelle est
l’expression de P (x ) en fonction des données (xi , yi ) ?
Soit polyôme P (x ) = a0 + a1 x + · · · + an x n d’où le système de
(n + 1) équations et de (n + 1) inconnus c-à-d les coefficients
(ai ), i = 0, 1, · · · , n.

 a0 + a1 x0 + · · · + an x0n = P (x0 ) = y0
 a0 + a1 x1 + · · · + an x n = P (x1 ) = y1

1
.. ⇐⇒ AX = Y


 .
a0 + a1 xn + · · · + an xnn = P (xn ) = yn

Si xi 6= xj , ∀i 6= j la matrice A de Vandermonde est inversible
alors le polynôme existe et unique
Cours - Analyse Numérique - 2 IM 4 / 18
Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

La forme de Lagrange

Soit la base de Lagrange (L0 (X ), L1 (X ), · · · , Ln (X )) une base

de l’espase vectoriel Rn [X ].

Théorème
Il existe un polynôme unique Pn ∈ Rn [X ] tel que Pn (xi ) = yi
por i = 0, 1, · · · , n.
n n X − xj
Pn (X ) = ∑ yi Li (X ) avec Li (X ) = ∏ xi − xj
i =0 j =0,j 6=i

Remarque
Si on ajoute un autre point (xn+1 , yn+1 ) on doit refaire le calcul
de tous Li (X )!

Cours - Analyse Numérique - 2 IM 5 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Exemple

Déterminer le polynôme P2 qui interpole les points suivants

i 0 1 2
(−1, 1), (0, 0.5), et (1, 2). xi -1 0 1
yi 1 0.5 2
En utilisant la forme de Lagrange :
P2 (X ) = y0 L0 (X ) + y1 L1 (X ) + y2 L2 (X )
L0 (X ) = xX0− x1 X −x2 X −0 X −1 1
−x1 x0 −x2 = −1−0 −1−1 = 2 X (X − 1)
X −x0
X −x2 X +1 X −1
L1 ( X ) = x1 −x2 = 0+1 0−1 = −(X + 1)(X − 1)
x1 −x0
X −x0
X −x1 X +1 X −0 1
L2 ( X ) = x2 −x1 = 1+1 1−0 = 2 X (X + 1)
x2 −x0
d’où P2 (X ) = 1 ∗ 21 X (X − 1) + (0.5) ∗ (−(X + 1)(X − 1)) + 2 ∗
1 2 1 1
2 X (X + 1) = x + 2 X + 2

Cours - Analyse Numérique - 2 IM 6 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Forme de Newton : différences divisées

Soit la base de Newtion (W0 (X ), W1 (X ), · · · , Wn (X )).
Donc
n n −1
Pn ( X ) = ∑ αi Wi (X ) = α0 |{z}
1 +α1 (X − x0 ) + · · · + αn ∏ (X − xj )
i =0 j =0
| {z }
W0 ( X ) W1 ( X ) | {z }
Wn ( X )

définition
Le coefficient αi s’appelle différence divisée de f d’ordre k aux
points x0 , x1 , · · · , xi et l’on note

αi = f [x0 , x1 , · · · , xi ]
avec f [xi ] = f (xi ) pour i = 0, 1, · · · , n
Cours - Analyse Numérique - 2 IM 7 / 18
Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Proposition
- f [xi ] = f (xi ) ∀i ∈ {0, 1, · · · , n}
f [x ,··· ,xi ]−f [x0 ,x1 ,··· ,xi −1 ]
- f [x0 , x1 , · · · , xi ] = 1 xi −x0 , ∀i ∈ {1, · · · , n}

Exemple
f [x1 ]−f [x0 ]
- f [ x0 , x1 ] = x1 −x0 = f (xx11)− f (x0 )
−x0
f [x ]−f [x ] f (x )−f (x )
f [x1 , x2 ] = x22 −x1 1 = x22 −x1 1
f [x ,x ]−f [x ,x ]
- f [x0 , x1 , x2 ] = 1 x22 −x0 0 1

Cours - Analyse Numérique - 2 IM 8 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

n n −1
Pn ( X ) = ∑ αi Wi (X ) = α0 |{z}
1 +α1 (X − x0 ) + · · · + αn ∏ (X − xi )
n =0 j =0
| {z }
W0 (X ) W1 ( X ) | {z }
Wn ( X )

pour X = x0 ⇒ α0 = Pn (x0 ) = f (x0 ) = y0

Proposition
la forme de Newton du polynôme d’interpolation s’écrit :
n
Pn (X ) = f (x0 ) + ∑ f [x0 , x1 , · · · , xi ]Wi (X )
i =1

Remarque
Si on ajoute un autre point (xn+1 , yn+1 ) on doit just rajouter un
autre terme αn+1 Wn+1 (X ) dans le polynôme Pn+1 (X ).
Cours - Analyse Numérique - 2 IM 9 / 18
Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Exemple

Déterminer le polynôme P2 qui interpole les points suivants

(−1, 1), (0, 0.5), et (1, 2).
En utilisant la forme de Newton :
P2 (X ) = y0 + α1 W1 (X ) + α2 W2 (X ) =
y0 + α1 (X − x0 ) + α2 (X − x0 )(X − x1 )
xi f [xi ] f [ xi , xi + 1 ] f [ xi , xi + 1 , xi + 2 ]
-1 1=α0
f (x )−f (x )
α1 = f [x0 , x1 ] = x11 −x0 0 = −0.5
f [x1 ,x2 ]−f [x0 ,x1 ]
0 0.5 α2 = f [x0 , x1 , x2 ] = x2 −x0 =1
f (x2 )−f (x1 )
f [x1 , x2 ] = x2 −x1 = 1.5
1 2
d’où
P2 (X ) = 1 − 0.5(X + 1) + 1 ∗ (X + 1)(X − 0) = x 2 + 21 X + 1
2

Cours - Analyse Numérique - 2 IM 10 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Remarque
Soit f [x0 , · · · , xi ] = D0,i = αi , pour i= 0, · · · , n.
Pn (X ) = α0 + α1 (X − x0 ) + · · · + αn (X − x0 ) · · · (X − xn−1 )
= α0 + (X − x0 )[αn (X − x1 ) · · · (X − xn−1 ) + αn−1 (X −
x1 ) · · · (X − xn−2 ) + · · · + α1 ]
= α0 + (X − x0 )[α1 + (X − x1 )[· · · [· · · + (X − xn−2 )[αn−1 +
αn (X − xn−1 )]]]]

Algorithm 1: Algorithme forme de Newton

Result: tn = Pn (x )
x0 , · · · , xn , α 0 , · · · , α n ;
t0 = α n ;
for i=1 to n do
ti = α n − i + ( x − x n − i ) ti − 1 ;
end

Cours - Analyse Numérique - 2 IM 11 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Erreur d’interpolation

Proposition
Soit Pn le polynôme d’interpolation de Lagrange d’une fonction
f relativement aux points x0 , · · · , xn . Soit t un réel donné.
Supposons que f ∈ C n+1 (It ) où It est le plus petit segment
contenant x0 , · · · , xn et t.
Alors il existe c ∈ It tel que

|f (n+1) (c )| n
(n + 1)! i∏
|f (t ) − Pn (t )| = | t − xi |
=0

Cours - Analyse Numérique - 2 IM 12 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Exemple

Déterminer le polynôme P2 qui interpole les points suivants.

i 0 1 2
xi -1 0 1
yi e − 1 1 e
Pour t = 0.5 l’erreur est :

|f (3) (c )| 2
|f (0.5) − P2 (0.5)| =
3! ∏ |0.5 − xi |, c ∈ [−1, 1]
i =0

f (x ) = ex ⇒ f (3) (x ) = ex 6 e ∀x ∈ [−1, 1]

e e3 e
⇒ |f (0.5) − P2 (0.5)| 6 |0.5 + 1||0.5 − 0||0.5 − 1| = =
3! 68 16

Cours - Analyse Numérique - 2 IM 13 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Approximation linéaire
Déterminer P (X ) = a1 x + a0 qui passe la plus proche possible
des points (xi , yi ) au sens des moindres carrés.

 e0 = P (x0 ) − y0 = a1 x0 + a0 − y0
e = P (x1 ) − y1 = a1 x1 + a0 − y1
 1
e2 = P (x2 ) − y2 = a1 x2 + a0 − y2
f (x )
e2

e1

e0

x
0 0.5 1
Cours - Analyse Numérique - 2 IM 14 / 18
Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Approximation linéaire
Dans le cas général pour (n+1) points (xi , yi ), i = 0, . . . , n le
sytème s’écrit sous forme matricielle :
E = MC − Y
     
e0 1 x0   y0
 ..   .. ..  a0  .. 
E =  . M = . . , C = , Y =.
a1
en 1 xn yn
min F (C ) = min kE k2 = min kMC − Y k2
C C C
 

⇒ ∇F (C ) = ∂a ∂F
0
, ∂F
∂a1 = 0, 0
!
XY − X Y
⇒ C = (t MM )−1 .t MY = Y − a1 X , 2
X2 − X
∑ni=0 xi ∑ni=0 xi yi 2 ∑ni=0 xi2
avec X = n+1 , XY = n +1 , X = n +1
Cours - Analyse Numérique - 2 IM 15 / 18
Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Exemple
Déterminer P (X ) = a1 x + aO qui passe la plus proche possible
des points (0, 1), (0.5, 1.5), (1, 3) au sens des moindres
carrés.
X = 12 , Y = 11 , XY = 15 2 5
12 , X = 12⇒ a0 = 2, a1 = 56
 6 3 5
− 32
  15 
t 3 2 t − 1 2 4 t 2
( MM ) = 3 5 , ( MM ) = 3 3 , ( MY ) = 15
− 3
  2 5  4 2 4
a0
⇒ = 6
a1 2

Cours - Analyse Numérique - 2 IM 16 / 18

Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Approximation polynomiale
Déterminer P (X ) = a0 + a1 x + · · · + ap x p qui approxime les
points (xi , yi ), 0 6 i 6 n au sens des moindres carrés.
 p
 e0 = P (x0 ) − y0 = a0 + a1 x0 · · · + ap x0 − y0

..
.
en = P (xn ) − yn = a0 + a1 xn · · · + ap xnp − yn



Le sytème s’écrit sous forme matricielle : E = MC − Y

1 x0 . . . x0p
       
e0 a0 y0
 ..   .. .. .
..  , C =  ..  , Y =  ... 
.
E =  . M = . .
   

p
en 1 xn . . . xn ap yn

min F (C ) = min kE k2 = min kMC − Y k2

C C C
t −1 t
⇒ C = ( MM ) . MY
Cours - Analyse Numérique - 2 IM 17 / 18
Introduction Lagrange Forme de Newton Erreur d’interpolation Approximation

Exemple
Déterminer P (X ) = a2 X 2 + a1 x + a0 qui passe la plus proche
possible des points (0, 1), (0.5, 1.5), (1, 3) au sens des
moindres
 carrés.
3 32 54
  
1 0 0
M = 1 21 14  , (t MM ) =  32 45 98  , (t MM )−1 =
5 9 17
1 1 1
  4 8 16
−3
 
1 2 a0 1
−3 26 −24 ⇒ a1  = 0
2 −24 24 a2 2

Cours - Analyse Numérique - 2 IM 18 / 18