Méthode d’interpolation de Newton

Equipe AN

Analyes Numérique (AN)

ESPRIT

Polynômes d’interpolation de Newton

2

Soient n + 1 points de coordonnées (xi, yi)0≤i≤n tels que xi (cid:54)= xj, ∀i, j ∈ {0, ..., n} tels

que i (cid:54)= j.

Il existe un unique polynôme d’interpolation de Newton Pn ∈ Rn[X] vérifiant

Pn(xi) = yi, ∀i ∈ {0, · · · , n}.

Le polynôme Pn s’exprime comme suit:

n

(cid:88)

Pn(x) =

βiωi(x), x ∈ R

i=0

= β0. 1

(cid:124)(cid:123)(cid:122)(cid:125)

ω0

+ β1(x − x0)

(cid:124) (cid:123)(cid:122) (cid:125)

ω1

+ β2(x − x0)(x − x1)

(cid:125)

(cid:124)

(cid:123)(cid:122)

ω2

+ ....

.

+ βn(x − x0)(x − x1)...(x − xn−1)

(cid:125)

(cid:124)

(cid:123)(cid:122)

ωn

i−1

(cid:89)

ωi(x) =

(x − xi), ∀i ∈ {1, ..., n} et ω0(x) = 1.

j=0

Equipe AN

Analyes Numérique (AN)

ESPRIT

Les coefficients de Newton βi (i ∈ {0, · · · , n}) peuvent être déterminés en

utilisant la méthode des différences divisées, qui seront définies ci-dessous,

comme suit:

βi = [y0, ..., yi].

3

La famille de polynômes de Newton {ω0, ω1, · · · , ωn} associés aux points (xi, yi),

i ∈ {0, · · · , n} est une base de l’espace vectoriel Rn[X].

Equipe AN

Analyes Numérique (AN)

ESPRIT

3

La famille de polynômes de Newton {ω0, ω1, · · · , ωn} associés aux points (xi, yi),

i ∈ {0, · · · , n} est une base de l’espace vectoriel Rn[X].

Les coefficients de Newton βi (i ∈ {0, · · · , n}) peuvent être déterminés en

utilisant la méthode des différences divisées, qui seront définies ci-dessous,

comme suit:

βi = [y0, ..., yi].

Equipe AN

Analyes Numérique (AN)

ESPRIT

1 La différence divisée d’ordre 0 de xi (0 ≤ i ≤ n) est donnée par

2 La différence divisée d’ordre 1 de xi−1 et xi (0 < i ≤ n) est donnée par

[yi] = yi.

[yi−1, yi] =

yi − yi−1

xi − xi−1

·

Détermination des coefficients de Newton

4

Différences divisées

On considère (n + 1) points (xi, yi)0≤i≤n tels que xi (cid:54)= xj, ∀i, j ∈ {0, ..., n} tels que

i (cid:54)= j.

Equipe AN

Analyes Numérique (AN)

ESPRIT

2 La différence divisée d’ordre 1 de xi−1 et xi (0 < i ≤ n) est donnée par

[yi−1, yi] =

yi − yi−1

xi − xi−1

·

Détermination des coefficients de Newton

4

Différences divisées

On considère (n + 1) points (xi, yi)0≤i≤n tels que xi (cid:54)= xj, ∀i, j ∈ {0, ..., n} tels que

i (cid:54)= j.

1 La différence divisée d’ordre 0 de xi (0 ≤ i ≤ n) est donnée par

[yi] = yi.

Equipe AN

Analyes Numérique (AN)

ESPRIT

Détermination des coefficients de Newton

4

Différences divisées

On considère (n + 1) points (xi, yi)0≤i≤n tels que xi (cid:54)= xj, ∀i, j ∈ {0, ..., n} tels que

i (cid:54)= j.

1 La différence divisée d’ordre 0 de xi (0 ≤ i ≤ n) est donnée par

[yi] = yi.

2 La différence divisée d’ordre 1 de xi−1 et xi (0 < i ≤ n) est donnée par

[yi−1, yi] =

yi − yi−1

xi − xi−1

·

Equipe AN

Analyes Numérique (AN)

ESPRIT

Par exemple, pour n = 2, une différence divisée d’ordre 2 est donnée par

[y0, y1, y2] =

[y1, y2] − [y0, y1]

x2 − x0

y2−y1

x2−x1

− y1−y0

x1−x0

x2 − x0

=

5

3 La différence divisée d’ordre n des n + 1 points est définie par récurrence entre

deux différences divisées d’ordre n comme suit :

[y0, y1, · · · , yn] =

[y1, · · · , yn] − [y0, y1, · · · , yn−1]

xn − x0

·

Equipe AN

Analyes Numérique (AN)

ESPRIT

5

3 La différence divisée d’ordre n des n + 1 points est définie par récurrence entre

deux différences divisées d’ordre n comme suit :

[y0, y1, · · · , yn] =

[y1, · · · , yn] − [y0, y1, · · · , yn−1]

xn − x0

·

Par exemple, pour n = 2, une différence divisée d’ordre 2 est donnée par

[y0, y1, y2] =

=

[y1, y2] − [y0, y1]

x2 − x0

y2−y1

x2−x1

− y1−y0

x1−x0

x2 − x0

Equipe AN

Analyes Numérique (AN)

ESPRIT

β1 =

Pn(x1) =

βiωi(x1)

n

(cid:88)

i=0

= y0 + β1(x1 − x0)

Pn(x1) = y1







= β0 + β1(x1 − x0)

⇒ y0 + β1(x1 − x0) = y1.

β1 = y1−y0

x1−x0

= [y0, y1]: une différence divisée d’ordre 1.

β0 =

Pn(x0) =

n

(cid:88)

i=0

β0ωi(x0) = β0

Pn(x0) = y0 = [y0]







⇒ β0 = [y0] : une différence divisée d’ordre 0.

6

Equipe AN

Analyes Numérique (AN)

ESPRIT

6

⇒ β0 = [y0] : une différence divisée d’ordre 0.

β0 =

Pn(x0) =

n

(cid:88)

i=0

β0ωi(x0) = β0

Pn(x0) = y0 = [y0]







β1 =

Pn(x1) =

n

(cid:88)

i=0

βiωi(x1)

= β0 + β1(x1 − x0)

= y0 + β1(x1 − x0)

Pn(x1) = y1







⇒ y0 + β1(x1 − x0) = y1.

β1 = y1−y0

x1−x0

= [y0, y1]: une différence divisée d’ordre 1.

Equipe AN

Analyes Numérique (AN)

ESPRIT

7

βi (i ∈ {0, · · · , n}) =

Par récurrence,

βi = [y1,...,yi]−[y0,....,yi−1]

xi−x0

= [y0, ..., yi]: une différence divisée d’ordre i.

Equipe AN

Analyes Numérique (AN)

ESPRIT

Exercice

8

Retrouver l’expression du polynôme d’interpolation de la fonction f définie dans

l’exercice 1 en utilisant la méthode de Newton.

En utilisant la méthode de Newton,

Solution

P2(x) = β0 + β1(x − x0) + β2(x − x0)(x − x1),

avec

D’où

β0 = y0 = 2,

β1 = [y0, y1] =

y1 − y0

x1 − x0

= −1,

β2 = [y0, y1, y2] =

[y1, y2] − [y0, y1]

x2 − x0

=

y2−y1

x2−x1

− y1−y0

x1−x0

x2 − x0

= −

1

2

·

P2(x) = 2 − (x − x0) −

= −

1

2

x2 −

3

2

x + 1.

1

2

(x − x0)(x − x1)

Equipe AN

Analyes Numérique (AN)

ESPRIT

Exercice (Asynchrone)

9

Répondre aux questions de l’exemple introductif en utilisant la méthode

d’interpolation de Newton.

Equipe AN

Analyes Numérique (AN)

ESPRIT

10

Avantage de la méthode de Newton

Un des avantages de la méthode de Newton pour l’interpolation des points

(xi, yi)0≤i≤n tels que xi (cid:54)= xj, ∀i, j ∈ {0, ..., n} tels que i (cid:54)= j est le suivant:

Si on note par Pk le polynôme d’interplation tronqué (le polynôme de degré inférieur

ou égal à k, 0 ≤ k < n qui n’interpole que les points (xi, yi)0≤i≤k) exprimé dans la

base de polynômes de Newton {ω1, · · · , ωk}, comme suit :

Pk(x) = β0. 1

(cid:124)(cid:123)(cid:122)(cid:125)

ω0

+β1(x − x0)

(cid:124) (cid:123)(cid:122) (cid:125)

ω1

,

+....+βk(x − x0)(x − x1)...(x − xk−1)

+β2(x − x0)(x − x1)

(cid:125)

(cid:125)

(cid:124)

(cid:124)

(cid:123)(cid:122)

ω2

(cid:123)(cid:122)

ωk

alors Pk+1, le polynôme tronqué de degré inférieur ou égal à k + 1 interpolant les

points (xi, yi)0≤i≤k+1, sera exprimé en fonction de Pk comme suit :

.

Pk+1(x) = Pk(x) + βk+1(x − x0)(x − x1)..(x − xk)

(cid:125)

(cid:124)

(cid:123)(cid:122)

ωk+1

Equipe AN

Analyes Numérique (AN)

ESPRIT

11

Par conséquent, en considérant un polynôme Pn qui interpole les (n + 1) points

(xi, yi)0≤i≤n, et en ajoutant un autre point (xn+1, yn+1), alors le polynôme Pn+1

interpolant les n + 2 points peut être déduit de Pn comme suit :

.

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

(cid:125)

(cid:124)

(cid:123)(cid:122)

ωn+1

Equipe AN

Analyes Numérique (AN)

ESPRIT