Interpolation Numerique

8/3/2019 Interpolation Numerique

1/28

.

Interpolation Numrique

Pablo CROTTI, Mathias RIME

Mini-projet effectu au sein de la section de MathmatiquesEt 2007

Professeur responsable Alfio QuarteroniAssistant Benjamin Stamm


2/28

Introduction

Linterpolation numrique consiste de manire gnrale approximer une fonction dont onne connat les valeurs quen certains points. Plus prcisment, tant donn n + 1 couples (xi, yi),le problme consiste trouver une fonction = (x) telle que (xi) = yi pour i = 0, . . . , n. On

dit alors que interpole {yi} aux noeuds {xi}. La forme de la fonction dpend du problmeet du but de linterpolation. En effet, peut tre un polynme, et on parle alors dinterpolationpolynomiale, ou bien peut tre un polynme trigonomtrique, ou une fonction polynomiale parmorceaux, et on dit alors que est une interpolation par morceaux.

Lintrt et le mode dutilisation dune fonction dinterpolation dpend surtout de la prove-nance des donnes. Les quantits yi peuvent, par exemple, reprsenter les valeurs aux noeudsxi dune fonction f connue analytiquement. La fonction dinterpolation permet alors de simpli-fier des calculs numriques dintgrales ou de drives. Dautre part, les quantits yi peuventreprsenter des donnes exprimentales quil faut synthtiser, vu leur nombre parfois lev.

Le but de ce mini-projet est dintroduire les notions de base de linterpolation dans le cadredune fonction une variable. Nous parlerons de linterpolation polynomiale de Lagrange avec

noeuds quirpartis, de linterpolation polynomiale par morceaux, ainsi que de lapproximationau sens des moindres carrs.Pour mieux comprendre et illustrer ce quest linterpolation numrique, nous mettons deux

fonctions en exemple (Sinus et Runge) avec lutilisation des polynmes de Lagrange sur unou plusieurs morceaux. Ces deux exemples montrent que linterpolation par morceaux est bienmeilleure quune approximation polynomiale avec des points dinterpolation quirpartis lorsquele nombre de morceaux est grand.

Nous tenons remercier Benjamin Stamm, notre assistant responsable, pour sa correctionrapide et trs attentive de notre projet, ainsi que pour sa disponibilit.

2


3/28

Table des matires

Introduction 2

Table des figures 4

1 Approximation par les moindres carrs 5

1.1 Rappels dalgbre linaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Meilleure approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Problme des moindres carrs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Problme des moindres carrs pour des fonctions . . . . . . . . . . . . . . . . . . 7

2 Interpolation polynomiale & noeuds quirpartis 10

2.1 Polynme de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2 Erreur dinterpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Dfauts de linterpolation polynomiale avec noeuds quirpartis . . . . . . . . . . 142.4 Stabilit du polynme dinterpolation . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Interpolation de Lagrange par morceaux 17

4 Forme de Newton du polynme dinterpolation 20

4.1 Quelques proprits des diffrences divises de Newton . . . . . . . . . . . . . . . 204.2 Erreur dinterpolation avec les diffrences divises . . . . . . . . . . . . . . . . . . 21

5 Interpolation dHermite-Birkhoff 23

Conclusion 24

Rfrences 25

ANNEXE : CODES MATLAB 26

3


4/28

Table des figures

1.1 Projection du vecteur v dans le sous-espace W . . . . . . . . . . . . . . . . . . . 51.2 Lissage de donnes alatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1 Erreur dinterpolation du sinus avec noeuds quirpartis . . . . . . . . . . . . . . 13

2.2 Interpolations de sinus avec degr 2,3,4,5,6,8 . . . . . . . . . . . . . . . . . . . . . 132.3 Contre-exemple de Runge : Interpolation de degr 2,4,5,8 et 12 . . . . . . . . . . 152.4 Contre-exemple de Runge : Erreurs dinterpolation avec noeuds quirepartis . . . 163.1 Interpolation linaire par morceaux de la fonction sinus . . . . . . . . . . . . . . . 173.2 Erreurs pour linterpolation par morceaux de la fonction sinus . . . . . . . . . . . 183.3 Interpolation linaire par morceaux de la fonction de Runge . . . . . . . . . . . . 183.4 Erreurs dinterpolation par morceaux de la fonction de Runge . . . . . . . . . . . 19

4


5/28

1 Approximation par les moindres carrs

Dans cette partie du rapport nous allons tudier une mthode appele approximation ausens des moindres carrs. Cette mthode permet dapproximer un ensemble de couples (xi, yi)obtenus de manire alatoires ou par lintermdiaire dune fonction. Lapproximation nest pas

une interpolation car la fonction rsultante obtenue aprs calcul ne passe pas forcment par tousles couples (xi, yi). En effet, lapproximation par les moindres carrs est obtenue en rsolvant unsystme dquations linaires surdtermin.

1.1 Rappels dalgbre linaire

Dfinition 1.1. Soit V un R-espace vectoriel de dimension finie muni dun produit scalaire, . Soient W un sous-espace vectoriel de V et (w0, w1, . . . , wn) une base orthogonale de W.Soit v V et soit W(v) W, la projection orthogonale du vecteur v sur le sous-espace W,dfinie par :

W(v) :=n

i=0v, wi

wi, w

i

wi. (1.1)

Dfinition 1.2. Soit V un R-espace vectoriel de dimension finie muni dun produit scalaire, et soit W un sous-espace vectoriel de V. Lespace orthogonal W est lensemble notW dfini par :

W := { v V | w, v = 0 w W}.

Cest un sous-espace vectoriel de V. En effet 0 W, et si w1, w2 W, , R alorsw W on a w1 + w2, w = w1, w + w2, w = 0. Donc w1 + w2 W. Remarquonsque pour tout v V on a v W(v) W. De plus, si A Mnm(R) alors nous avonsIm(A) = Ker(At) et Ker(A) = Im(At) o on note par At la transpose de A.

1.2 Meilleure approximation

Thorme 1.3 ([Hess06],page 62). Soit V un Respace vectoriel muni dun produit scalaire, . Soit W un sous-espace vectoriel de V et soit v V. Alors W(v) est la meilleureapproximation de v dans W, dans le sens o

v W(v)< v w, w W, w = W(v)

o . est la norme engendre par le produit scalaire , .

W

V

W(v)v v -

W(v)

Fig. 1.1 Projection du vecteur v dans le sous-espace W

5


6/28

Dmonstration. Soit w W. On a

v w2= v W(v) W

+ W(v) w W

2.

Par le thorme de Pythagore nous avonsv w2= v W(v)

2+W(v) w2.

Dov W(v)

2 v w2,

avec galit si et seulement siW(v) w

2= 0 ,

ce qui quivaut w = W(v).

1.3 Problme des moindres carrs

Etant donn A Mnm(R) et b Rn, il se peut que le systme dquations linaires Ax = bavec x Rm soit inconsistant, quil ny ait pas de solution. La mthode des moindres carrsconsiste trouver une valeur de x qui minimise la norme euclidienne de Axb. Selon le Thorme1.3, la meilleure approximation de b dans Im(A) est

Im(A)(b).

Or

b Im(A)(b) Im(A) = Ker(At).

Alors, siAx = Im(A)(b),

on aAtb AtAx = At(b Ax

Ker(At)

) = 0.

DoAtAx = Atb. (1.2)

Si AtA est inversible, le systme a une solution unique

x = (AtA)1Atb, (1.3)

Ax = A(AtA)1Atb. (1.4)

On appelle lquation (1.2) le systme normal du systme inconsistant et lquation (1.3) lesystme associ au moindre carrs.

6


7/28

1.4 Problme des moindres carrs pour des fonctions

Nous considrons ici lapproximation non pas de vecteurs mais de fonctions relles. Luti-lisation des moindres carrs pour les fonctions permet de synthtiser un ensemble de donnes,souvent rsultats dexpriences, sous forme de polynmes, de polynmes trigonomtriques oudexponentielles. Cette forme synthtique des donnes permet ainsi par la suite dextrapoler desvaleurs diffrentes des noeuds de base.

Considrons les donnes {(xi, yi), i = 0, . . . , n} o yi peut tre vu comme la valeur f(xi)prise par une fonction f au noeud xi, f tant inconnue priori. Pour un entier m 1 donn(en gnral m n ), dfinissons Pm = {v : R R : v(x) = a0 + a1x + . . . + anxn , ai R i }lensemble des polynmes de degr plus petit ou gal m. On cherche un polynme f Pmvrifiant lingalit

ni=0

[yi f(xi)]2

ni=0

[yi pm(xi)]2, (1.5)

pour tout polynme pm de degr au plus m. Si elle existe, f est appele meilleure approximationau sens des moindres carrs dans Pm des donnes {(xi, yi), i = 0, . . . , n}. moins que m n,il nest en gnral pas possible davoir f(xi) = yi pour tout i = 0, . . . , n. En posant

f(x) = a0 + a1x + + amxm,

o les coefficients a0, . . . , am R sont inconnus, le problme (1.5) peut tre reformul ainsi :trouver a0, a1, . . . , am tels que

(a0, a1, . . . , am) =min

{bi, i=0,...,m}(b0, b1, . . . , bm),

o

(b0, b1, . . . , bm) =

n

i=0 [yi (b0 + b1xi + + bmxmi )]

2.

Rsolvons ce problme dans le cas particulier o m = 1. Puisque

(b0, b1) =n

i=0

[y2i + b20 + b

21x

2i + 2b0b1xi 2b0yi 2b1xiyi],

le graphe de est un parabolode convexe. Le point (a0, a1) o atteint son minimum satisfaitles conditions

b0(a0, a1) = 0 ,

b1(a0, a1) = 0.

En calculant explicitement les deux drives partielles, on obtient

ni=0

[a0 + a1xi yi] = 0 ,n

i=0

[a0xi + a1x2i xiyi] = 0,

qui est un systme de deux quations deux inconnues a0 et a1 :

a0(n + 1) + a1

ni=0

xi =n

i=0

yi,

a0

ni=0

xi + a1

ni=0

x2i =n

i=0

yixi.

7


8/28

En posant D = (n + 1)n

i=0 x2i (

ni=0 xi)

2, la solution scrit, grce la rgle de Cramer :

a0 =1

D

n

i=0

yi

nj=0

x2j n

j=0

xj

ni=0

xiyi

,

a1 = 1D(n + 1) n

j=0

xiyi

nj=0

xj

ni=0

yi.Le polynme correspondant f(x) = a0 + a1x sappelle la droite des moindrs carrs, ou dergression linaire.

Cette approche peut tre gnralise de plusieurs manires. La premire gnralisation consiste prendre un m plus grand. Le systme linaire (m + 1) (m + 1) associ est symtrique et a laforme suivante :

a0(n + 1) + a1n

i=0 xi + . . . + amn

i=0 xmi =

ni=0 yi

a0ni=0 xi + a1ni=0 x2i + . . . + am ni=0 xm+1i = ni=0 xiyi... ... ... ... ...a0n

i=0 xmi + a1

ni=0 x

m+1i + . . . + am

ni=0 x

2mi =

ni=0 x

mi yi

Quand m = n, le polynme des moindres carrs concide avec le polynme dinterpolation deLagrange (que nous tudierons au prochain chapitre).

Une gnralisation de lapproximation au sens des moindres carrs consiste utiliser dans(1.5) des fonctions f et pm qui ne sont pas des polynmes mais des fonctions dun espace vectorielVm engendr par m + 1 fonctions indpendantes j , j = 0, . . . , m.

On peut considrer par exemple des fonctions trigonomtriques j (x) = cos(j x) (pour unparamtre = 0 donn), des fonctions exponentielles j (x) = ej x (pour un > 0 donn). Le

choix des fonctions j est en pratique dict par la forme suppose de la loi dcrivant les donnes.Le lecteur pourra vrifier que les composantes de

f(x) =m

j=0

ajj (x),

sont les solutions du systme suivant (appel quations normales)

BTBa = BTb,

o B est la matrice rectangulaire (n + 1) (m + 1) de coefficients bij = j (xi), a est le vecteur

des inconnues et b le vecteur des donnes.

8


9/28

Exemple 1.4. Lissage de donnes alatoires. Nous allons montrer comment on peut lisserou synthtiser des donnes gnres alatoirement. Nous avons gnr un ensemble de 10 pointsreprsentant des perturbations dune loi quadratique (ici la fonction de base est f(x) = 10x2).Le Programme 1 en annexe montre le code MATLAB utilis pour gnrer les donnes et lesafficher.

Nous avons utilis la mthode des moindres carrs pour approximer ces points avec unpolynme du deuxime degr, le choix le plus judicieux, et nous avons effectu une interpolationde Lagrange de degr 9 (voir section suivante). On remarque sur la Figure 1.2 que pour des jeuxde donnes lgrement diffrents, lapproximation au sens des moindres carrs ne change quetrs peu. Cest en fait une mthode stable numriquement, ce qui nest pas (pas toujours) le casde linterpolation de Lagrange, voir le contre-exemple dans lExemple 2.9.

Nous pouvons de plus tenter dextrapoler la valeur de la fonction en x = 2. En effet, unevaleur gnre pour x = 2 est f(2) = 40.8998, la valeur de lapproximation quadratique est2f(2) = 42.2559, alors que la valeur du polynme interpolant est 9f(2) = 7.0738 105 !Lapproximation par les moindres carrs donne ainsi une bonne reprsentation des donnes,mme aux points o lon ne connat pas la fonction, et lutilisation de linterpolation de Lagrange

nest pas judicieuse pour ce genre de problme.

0 0.2 0.4 0.6 0.8 15

0

5

10

15

(a) Lissage 1

0 0.2 0.4 0.6 0.8 15

0

5

10

15

(b) Lissage 2

Fig. 1.2 Comparaison entre la mthode des moindres carrs et linterpolation de Lagrangepour lisser des donnes exprimentales (croix). En trait plein lapproximation de degr 2 ausens des moindres carrs ; en trait discontinu le polynme dinterpolation de Lagrange de degr 9

9


10/28

2 Interpolation polynomiale & noeuds quirpartis

2.1 Polynme de Lagrange

Nous voulons trouver un polynme m Pm passant par n + 1 couples (xi, yi), appelpolynme dinterpolation ou polynme interpolant, tel que

m(xi) = amxmi + + a1xi + a0 = yi i = 0, . . . , n .

Les points xi sont appels noeuds dinterpolation. Si n = m le problme est sr ou sous dtermin.Si n=m, nous avons le thorme suivant :

Thorme 2.1. Etant donne n + 1 points distincts x0, . . . , xn et n + 1 valeurs correspondantesy0, . . . , yn, il existe un unique polynme n Pn tel que n(xi) = yi pour i = 0, . . . , n.

Dmonstration. Montrons lexistence en construisant n. Posons

i P

n : i(x) =

n

j=0j=i

x xj

xi xj i = 0, . . . , n .

Nous allons montrer que { i, i = 0, . . . , n } est une base de Pn. Remarquons que commeCard{ i, i = 0, . . . , n } = n + 1 = dimPn, il suffit de montrer que les i sont linairementsindpendants, cest--dire que :

ni=0

ii = 0

0 = 1 = = n = 0 avec i R,

Or i(xj ) = ij , o ij est le symbole de Kroenecker. Ainsi nous trouvons

j = 0, . . . , n 0 =n

i=0

ii(xj ) =n

i=0

iij = j .

Donc lensemble des polynmes caractristiques est une base de Pn. En dcomposant n surcette base on a

n(x) =n

j=0

bj j(x).

Or on veut

n(xi) =n

j=0 bj j (xi) = yi , i = 0, . . . , n .Comme j (xi) = ij on obtient bi = yi. Le polynme dinterpolation existe et scrit de cettemanire

n(x) =n

i=0

yii(x). (2.1)

Lunicit se montre comme ceci. Supposons quil existe m de degr m n, tel que m(xi) = yi,pour i = 0, . . . , n. La diffrence n m est encore un polynme de degr n et sannule alorsen n + 1 points distincts xi, elle est donc nulle. Ainsi m = n.

10


11/28

La formule (2.1) est appele formule dinterpolation de Lagrange, et les polynmes i(x) sontles polynmes caractristiques (de Lagrange).

Si yi = f(xi) pour une certaine fonction f donne, le polynme n(x) sera not nf(x)

Dfinition 2.2. Le polynme nodale de degr n + 1, not n+1, est dfinit par :

n+1(x) =

ni=0

(x xi).

Proposition 2.3. Le polynme dinterpolation n scrit sous la forme suivante :

n(x) =n

i=0

n+1(x)

(x xi)n+1(xi)

yi.

Dmonstration. Nous avons

n+1(x) =n

j=0

ni=0i=j

(x xi),

ainsi

n+1(xi) =n

j=0j=i

xi xj,

et finalementn+1(x)

(x xi)n+1(xi)

=n

j=0j=ix xjxi xj

= i(x).

Et on retrouve la formule (2.1).

Exemple 2.4. Considrons les couples de points suivants (0, 0), (1, 2), (2, 0) avec (x0 = 0, y0 =0), . . . , (x2 = 2, y2 = 0) pour un degr polynomiale n = 2. Aprs avoir calcul les polynmescaractristiques nous obtenons les rsultats suivants

0(x) =x2 3x + 2

2

1(x) = x2 + 2x

2(x) =x2 x

2.

Ce qui nous donne

2(x) = 0(x2 3x + 2

2) + 2(x2 + 2x) + 0(

x2 x

2) = 2x2 + 4x

2.2 Erreur dinterpolation

Dans cette section, nous donnons une valuation de lerreur dinterpolation faite quand onremplace une fonction f (donne) par le polynme nf qui linterpole aux noeuds x0, x1, . . . , xn(par forcment quirpartis). De plus, nous obtenons une estimation plus fine de lerreur maxi-male dans le cas particulier o les noeuds sont quirpartis sur un intervalle [a, b].

11


12/28

Thorme 2.5. Soient x0, . . . , xn, n + 1 noeuds distincts et soit x un point appartenant audomaine de dfinition de f. On suppose que f Cn+1(Ix), o Ix est le plus petit intervallecontenant les noeuds x0, . . . , xn et x. Lerreur dinterpolation au point x est donne par

En(x) := f(x) nf(x) =f(n+1)()

(n + 1)!n+1(x) (2.2)

o Ix et n+1 est le polynme nodal de degr n + 1.

Dmonstration. Le rsultat est trivial si x concide avec lun des noeuds dinterpolation carn+1(xi) = 0 i = 0, . . . , n. Autrement, dfinissons pour t Ix la fonction G(t) = En(t) n+1(t)En(x)/n+1(x). Comme nous savons que f Cn+1(Ix) et que n+1 est un polynmealors G Cn+1(Ix) et possde au moins n + 2 zros distincts dans Ix. En effet,

G(xi) = En(xi) n+1(xi)En(x)/n+1(x) = 0, i = 0, . . . , n

G(x) = En(x) n+1(x)En(x)/n+1(x) = 0.

Par le thorme des valeurs intermdiaires, G

admet au moins n + 1 zros distincts, et par

rcurrence G(j)

a au moins n + 2 j zros distincts. Par consquent, G(n+1)

a au moins un zro,quon note . Dautre part, puisque E(n+1)n (t) = f(n+1)(t) et

(n+1)n+1 (x) = (n + 1)! on obtient

G(n+1)(t) = f(n+1)(t) (n + 1)!

n+1(x)En(x)

ce qui donne, avec t = , lexpression voulue pour En(x).

Corollaire 2.6. Soient x0, x1, . . . , xn [a, b], n + 1 noeuds quirpartis avec x0 = a et xn = b.On suppose que f Cn+1([a, b]). Lerreur dinterpolation sur [a, b] est estime par

En(f) = maxx[a,b]

|f(x) nf(x)| 1

4(n + 1) b a

n n+1

maxx[a,b]

|f(n+1)(x)| (2.3)

Dmonstration. Notons f= maxx[a,b]|f(x)|. Le thorme 2.5 nous donne dj que

En(f) f(n+1)

(n + 1)!n+1. (2.4)

Il reste estimer n+1. Soit x [a, b] avec x = xi i. On a que x Ik = (xk1, xk) pourun certain k { 1, . . . , n }. Comme les noeuds sont quirepartis, nous avons xi+1 = xi + h, oh = ( ba

n). On obtient

maxxIk

|(x xk1)(x xk)| =h2

4

de plus on peut estimer |x xk2| par 2h, |x xk3| par 3h etc. Do

n+1= maxx[a,b]

n

i=0

(x xi)

h2

4

(hn1n!) =

n!

4hn+1 (2.5)

En substituant (2.5) dans (2.4) on obtient

En(f) f(n+1)

(n + 1)!n+1 =

f(n+1)(n + 1)!

n!

4

b a

n

n+1=

1

4(n + 1)

b a

n

n+1max

x[a,b]|f(n+1)(x)|,

ce quil fallait dmontrer.

12


13/28

Exemple 2.7. Interpolation de la fonction sinus. Nous avons appliqu linterpolation deLagrange la fonction f(x) = sin(x) sur lintervalle [0, 3], cela pour les degrs allant de 2 8.Nous voyons dans la Figure 2.2(a) & (b), que linterpolation semble converger vers la fonctionsin(x) lorsque le degr augmente. Cela semble aussi vident dans le graphique 2.1 et la table 2.1o nous comparons lerreur effective due linterpolation et lestimation thorique donne par

la formule (2.3).Bien que cela conduise penser que le polynme interpolant converge vers la fonction f

quand n , nous verrons dans la section suivante que cela dpend en grande partie du choixdes noeuds dinterpolation.

2 3 4 5 6 7 801234

56789

Degr

E

rreurs

Fig. 2.1 Erreur thorique (carrs) et erreur calcule (ronds) de linterpolation du sinus

0 2 4 6 8

1

0.5

0

0.5

1

1.5

(a) 2f (trait mixte), 3f (pointills) et4f (trait discontinu).

0 2 4 6 8

1

0.5

0

0.5

1

1.5

(b) 5f (trait discontinu), 6f (trait mixte) et8f (pointills).

Fig. 2.2 Interpolation de Lagrange avec noeuds quirpartis de la fonction f(x) = sin(x) (traitplein).

13


14/28

Tab. 2.1 Tableau comparatif des erreurs dinterpolation du sinus pour les degrs 2 8. Onremarque que lerreur calcule est bien moindre que lestimation derreur thorique et que cesdeux erreurs tendent vers 0 lorsque n augmente

n En(sin) =max

x[0,3]| sin(x) sin(x)| 14(n+1)(3n )n+1max

x[0,3]| sin(n+1)(x)|2 1.5925 8.72053 1.0000 6.08814 0.6363 3.63105 0.4224 1.86896 0.1301 0.84277 0.0895 0.33758 0.0162 0.1214

2.3 Dfauts de linterpolation polynomiale avec noeuds quirpartis

Nous tudions dans cette section le comportement de lerreur dinterpolation lorsque n tendvers linfini. On rappel que la norme du maximum dune fonction f C0([a, b]) est dfinie par

f = maxx[a,b]

|f(x)|

Nous introduisons une matrice triangulaire infrieure X de taille infinie appele matrice din-terpolationsur [a, b] dont les coefficients xij pour i, j = 0, 1, . . . , reprsentent des points de [a, b],avec lhypothse que sur chaque ligne les coefficients sont tous distincts. Pour n 0, la n+1-meligne de X contient n + 1 valeurs distinctes que lon identifie des noeuds. Pour une fonctionf donne, on peut dfinir de faon unique un polynme nf de degr n qui interpole f en ces

noeuds (le polynme nf dpend de X et de f). Pour une fonction f donne et pour une matricedinterpolation X, on dfinit lerreur dinterpolation

En,(X) = f nf, n = 0, 1, . . .

On note pn Pn la meilleure approximation polynomiale, i.e linterpolation pour laquelle

En = f pn f qn qn Pn.

On a alors le rsultat suivant :

Proprit 2.8. Soient f C0([a, b]) et X une matrice dinterpolation sur [a, b]. Alors

En,(X) En(1 + n(X)), n = 0, 1, . . .

o n(X) dsigne la constante de Lebesgue de X dfinie par

n(X) =

n

j=0

|(n)j |

et o (n)j Pn est le j-ime polynme caractristique associ la n + 1-ime ligne de X,

cest--dire le polynme satisfaisant (n)j (xnk) = jk , j ,k = 0, 1, . . .

14


15/28

Puisque En ne dpend pas de X, toute linformation concernant les effets de X sur En,(X)doit tre cherche dans n(X). Bien quil existe une matrice dinterpolation X telle que n(X)soit minimum, la dtermination explicite de ses coefficients nest en gnral pas une tche facile.Aussi, pour tout choix de X, il existe une constante C > 0 telle que (voir [Erd61])

n(X) >2

log(n + 1) C, n = 0, 1, . . .

Cette proprit implique que n(X) quand n , ce qui a des consquences importantes :on peut en particulier montrer que pour une matrice dinterpolation X sur un intervalle [a, b], ilexiste toujours une fonction continue f sur [a, b] telle que nf ne converge pas uniformment versf. Ainsi, linterpolation polynomiale ne permet pas dapprocher convenablement toute fonctioncontinue. Cest ce que montre lexemple suivant.

Exemple 2.9. Contre-exemple de Runge. Tentons dapprocher la fonction suivante

f(x) =1

1 + x2, 5 x 5 (2.6)

en utilisant linterpolation de Lagrange avec noeuds quirpartis. On peut vrifier quil existedes points x lintrieur de lintervalle dinterpolation tels que

limn

|f(x) nf(x)| = 0.

En particulier, linterpolation de Lagrange diverge pour |x| > 3.63 . . . . Ce phnomne est parti-culirement vident au voisinage des extrmits de lintervalle dinterpolation, comme le montrela Figure 2.3(b). Il est d au fait que les noeuds sont quirpartis. Notons quen choisissant conve-nablement les noeuds, on peut tablir la convergence uniforme du polynme dinterpolation versla fonction f.

5 0 50.5

0

0.5

1

(a) 2f (trait mixte), 4f (pointills) et 5f(trait discontinu).

5 0 54

3

2

1

0

1

(b) 8f (trait discontinu) et 12f (traitmixte).

Fig. 2.3 Contre-exemple de Runge : interpolation de Lagrange avec noeuds quirpartis de lafonction f(x) = 1/(1 + x2) (trait plein)

15


16/28

2 3 4 5 6 7 8 9 10 11 120

1

2

3

4

Degr

E

rreurs

Fig. 2.4 Contre-exemple de Runge : Erreur dinterpolation pour la fonction f(x) = 1/(1 + x2)

2.4 Stabilit du polynme dinterpolation

On note f les valeurs rsultant de la perturbation dun ensemble de donnes f(xi) en des

noeuds xi [a, b], i = 0, . . . , n. La perturbation peut tre due, par exemple, aux erreurs darrondiou des erreurs dans des mesures exprimentales. En notant nf le polynme qui interpole lesvaleurs f(xi), on a

nf nf = maxaxb

nj=0

(f(xj ) f(xj ))j (x)

n(X) max

i=0,...,n|f(xi) f(xi)|

Par consquent, de petites modifications sur les donnes ninduisent des petites modifications surle polynme dinterpolation que si la constante de Lebesgue est petite. Cette constante joue le

role de conditionnementpour le problme dinterpolation. Comme on la not prcdemment, ncrot quand n . En particulier, pour linterpolation de Lagrange sur des noeuds quirpartison peut montrer que

n(X) 2n+1

en log n,

o e = 2.7183 . . . est le nombre de Neper. Ceci montre que, pour n grand, cette forme dinterpo-lation peut devenir instable. Remarquer quon a laiss de ct jusqu prsent les erreurs lies la construction de nf. On peut nanmoins montrer que leurs effets sont en gnral ngligeables.

16


17/28

3 Interpolation de Lagrange par morceaux

Lorsquon a des noeuds dinterpolation quirpartis, nous avons vu quon ne peut pas garantirde convergence uniforme de nf vers f. Cependant, linterpolation de Lagrange de bas degr estassez prcise quand on lutilise sur des intervalles petits (y compris avec des noeuds quirpartis).

On peut donc introduire une partition h de [a, b] en N sous-intervalles Ij = [xj , xj+1] de longeurhj , avec h = max0jN1 hj , tels que [a, b] = N1j=0 Ij et dutiliser une interpolation de Lagrange

sur chaque Ij en k + 1 noeuds quirpartis {x(i)j , 0 i k}, avec k petit. Pour k 1 et pour

une partition h donne, on introduit

Xkh = {v C0([a, b]) : v|Ij Pk(Ij ) Ij h j = 0, . . . , N 1}

qui est lespace des fonctions continues sur [a, b] dont la restriction chaque Ij est polynomialede degr k. Pour toute fonction f continue sur [a, b], le polynme dinterpolation par morceaux

khf concide sur chaque Ij avec linterpolant de f|Ij aux k + 1 noeuds {x(i)j , 0 i k}. Par

consquent, si f Ck+1([a, b]), en utilisant lquation (2.2) dans chaque intervalle, on obtient

lestimation derreur suivante

f khf Chk+1f(k+1). (3.1)

On peut obtenir une petite erreur dinterpolation mme pour des valeurs de k peu leves, dslors que h est assez petit .Remarque : Par la suite nous utiliserons la notation kNf pour le polynme dinterpolation dedegr k sur N morceaux.

0 2 4 6 8

1

0.5

0

0.5

1

(a) 14f (trait mixte) et 1

8f (trait discontinu).

0 2 4 6 8

1

0.5

0

0.5

1

(b) 110f (trait mixte) et 1


Fig.

3.1 Interpolation linaire par morceaux de la fonction f(x) = sin(x) (trait plein).

Exemple 3.1. Interpolation par morceaux du sinus. Nous avons vu dans lexemple 2.7 lersultat de linterpolation de Lagrange du sinus sur lintervalle [0, 3]. Nous faisons ici de mmepour linterpolation linaire (de degr k = 1) par morceaux.

On remarque dans la Figure 3.1(b) que linterpolation converge rapidement vers la fonctionlorsque quon augmente le nombre de morceaux. Dans la Figure 3.2 nous avons reprsent lerreurdinterpolation ainsi que son estimation thorique donne par la formule (3.1).

Lutilisation dechelles logarithmiques permet de mettre en vidence lexposant de h dansla formule. En effet, dans le cas o la partition est rgulire, on a h = (b a)/N, o N est le

17


18/28

nombre de morceaux. Le log nous donne donc :

log

f khf

C + (k + 1)log(h)

= (C + (b a)) (k + 1) log(N) (3.2)

o C = log Cf(k+1). Ici k = 1, donc la courbe derreur thorique, en echelle logarithmique,est une droite de pente 2, et on voit que lerreur dinterpolation converge rapidement vers cettedroite. Ainsi, partir dun N assez grand, en doublant le nombre de morceaux, on quadruple ledegr de prcision.

2 3 4 5 6 7 8 10 15 20 30 4010

3

102

101

100

101

log(N)

Er

reur(log)

Fig. 3.2 Erreurs (ronds) pour linterpolation linaire par morceaux de la fonction sinus. Entrait plein lestimation thorique.

Exemple 3.2. Interpolation par morceaux de la fonction de Runge. Dans lExemple 2.9

nous avons interpol la fonction f(x) = 1/(1 + x2

) sur lintervalle [5, 5] avec des noeuds qui-rpartis. Nous avions vu que cette interpolation ne converge pas uniformment vers la fonctionlorsque le degr n tend vers linfini. Ici nous obtenons de bien meilleurs rsultats en effectuantune interpolation linaire par morceaux sur cette fonction.

La Figure 3.3(a) montre des polynmes dinterpolation avec un nombre impair de morceaux,et dans la partie (b) les polynmes pour un nombre pair de morceaux. On voit quen partitionnantlintervalle en morceaux de mme longueur, la symtrie de la fonction influe sur le rsultat delinterpolation.

5 0 50

0.2

0.4

0.6

0.8

1

(a) 15f (trait mixte) et 1


5 0 50

0.2

0.4

0.6

0.8

1

(b) 14f (trait mixte) et 1


Fig. 3.3 Interpolation linaire par morceaux de la fonction f(x) = 1/(1 + x2) (trait plein).

18


19/28

Dans la Figure 3.4, nous avons compar lerreur effective et lestimation thorique commefait prcdemment dans lExemple 3.1 concernant linterpolation linaire par morceaux du sinus. nouveau, linterpolation par morceaux converge vers la fonction, et lerreur effective converge,en chelle logarithmique, vers la droite thorique de pente 2.

1 3 5 7 9 13 21 29 3910

2

101

100

101

102

log(N)

Erreur(log)

(a) N impairs

2 4 6 8 10 14 20 26 32 4010

2

101

100

10

1

log(N)

Erreur(log)

(b) N pairs

Fig. 3.4 Erreurs (ronds) pour linterpolation linaire par morceaux de la fonction de Runge.En trait plein lestimation thorique.

19


20/28

4 Forme de Newton du polynme dinterpolation

La forme de Lagrange (2.1) du polynme dinterpolation nest pas la plus commode dunpoint de vue pratique. Nous introduisons dans cette section une forme alternative dont le cotde calcul est moins lev. Notre but est le suivant : tant donn n+1 paires { xi, yi }, i = 0, . . . , n

on veut reprsenter n (tel que n(xi) = yi avec i = 0, . . . , n) comme la somme de n1 (telque n1(xi) = yi pour i = 0, . . . , n 1) et dun polynme de degr n qui dpend des noeudsxi et dun seul coefficient inconnu. On pose donc

n(x) = n1(x) + qn(x), (4.1)

o qn Pn. Puisque qn(xi) = n(xi) n1(xi) = 0 pour i = 0, . . . , n 1, on a ncessairement

qn(x) = an(x x0) (x xn1) = ann(x).

Pour dterminer le coefficient an, supposons que yi = f(xi), i = 0, . . . , n, o f est une fonctiondonne, pas ncessairement sous forme explicite. Puisque nf(xn) = f(xn), on dduit de (4.1)que

an =f(xn) n1f(xn)

n(xn). (4.2)

Le coefficient an est appel nime diffrence divise de Newton et on le note en gnral

an = f[x0, x1, . . . , xn] (4.3)

pour n 1. Par consquent, (4.1) devient

nf(x) = n1f(x) + n(x)f[x0, . . . , xn]. (4.4)

En posant y0 = f(x0) = f[x0] et 0 = 1, on obtient partir de (4.4) la formule suivante par

rcurrence sur n

nf(x) =n

k=0

k(x)f[x0, . . . , xk]. (4.5)

Daprs lunicit du polynme dinterpolation, cette expression dfinit le mme polynme que leformule de Lagrange. La forme (4.5) est communment appele formule des diffrences divisesde Newton du polynme dinterpolation.

4.1 Quelques proprits des diffrences divises de Newton

On remarque que la nime diffrence divise f[x0, . . . , xn] = an est le coefficient de xn dans

nf. En isolant ce coefficient dans (2.2) et en lidentifiant avec le coefficient correspondant dansla formule de Newton (4.5), on obtient la dfinition explicite

f[x0, . . . , xn] =n

i=0

f(xi)

n+1(xi). (4.6)

Cette formule a des consquences remarquables :

1. la valeur prise par la diffrence divise est invariante par permutation des indices desnoeuds. Ceci peut tre utilis avec profit quand des problmes de stabilit suggrentdchanger des indices (par exemple, si x est le point o le polynme doit tre calcul,il peut tre commode dintroduire une permutation des indices telle que |x xk| |x x

k1| pour k = 0, . . . , n) ;

20


21/28

2. si f = g + h pour , R, alors

f[x0, . . . , xn] = g[x0, . . . , xn] + h[x0, . . . , xn];

3. si f = gh, on a la formule suivante (appele formule de Leibniz) (voir [Die93])

f[x0, . . . , xn] =n

j=0

g[x0, . . . , xj ]h[xj , . . . , xn];

4. une manipulation algbrique de (4.6) donne la formule de rcurrence suivante permettantle calcul des diffrences divises

f[x0, . . . , xn] =f[x1, . . . , xn] f[x0, . . . , xn1]

xn x0. (4.7)

laide de la formule (4.7), on peut calculer les diffrences divises de Newton sous forme dunematrice triangulaire infrieure stocke sous la forme suivante. Les coefficients intervenant dans

x0 f[x0]x1 f[x1] f[x0, x1]x2 f[x1] f[x1, x2] f[x0, x1, x2]

......

.... . .

xn f[xn] f[xn1, xn] f[xn2, xn1, xn] . . . f [x0, . . . , xn]

la formule de Newton sont les lments diagonaux de la matrice..

En utilisant (4.7), seulement n(n + 1) additions et n(n + 1)/2 divisions sont ncessaires pourconstuire la matrice complte. Si on disposait de la valeur prise par f en un nouveau noeud

xn+1, on aurait calculer seulement une ligne supplmentaire (f[xn, xn+1], . . . , f [x0, . . . , xn+1]).Ainsi, pour construire n+1f partir de nf, il suffit dajouter nf le terme an+1n+1(x),ce qui ncessite (n + 1) divisions et 2(n + 1) additions.

.Remarquer que f[x0, . . . , xn] = 0 pour tout f Pn1. Nanmoins cette proprit nest pastoujours satisfaite numriquement car le calcul des diffrences divises peut tre fortement affectpar des erreurs darrondi.

4.2 Erreur dinterpolation avec les diffrences divises

Soit nf le polynme dinterpolation de f aux noeuds x0, . . . , xn et soit x un noeud distinct

des prcdents ; en posant xn+1 = x, on note n+1f le polynme interpolant f aux noeudsxk, k = 0, . . . , n + 1. En utilisant la formule des diffrences divises de Newton, on a

n+1f(t) = nf(t) + (t x0) (t xn)f[x0, . . . , xn, t].

Puisque n+1f(x) = f(x), on obtient lexpression suivante pour lerreur dinterpolation ent = x :

En(x) = f(x) nf(x) = n+1f(x) nf(x)

= (x x0) (x xn)f[x0, . . . , xn, x]

= n+1(x)f[x0, . . . , xn, x]. (4.8)

21


22/28

En supposant f C(n+1)(Ix) et en comparant (4.8) (2.2), on a donc

f[x0, . . . , xn, x] =f(n+1)()

(n + 1)!(4.9)

pour un certain Ix. Comme (4.9) est le reste du dveloppement de Taylor de f, la formule

dinterpolation de Newton (4.5) peut tre vue comme un dveloppement tronqu autour de x0( condition que |xn x0| ne soit pas trop grand).

22


23/28

5 Interpolation dHermite-Birkhoff

On peut gnraliser linterpolation de Lagrange dune fonction f pour prendre en compte, enplus de ses valeurs nodales, les valeurs de ses drives en certains noeuds (ou en tous les noeuds).

On se donne (xi, f(k)(xi)), pour i = 0, . . . , n , k = 0, . . . , mi o mi N.

En posant N = ni=0(mi + 1), on peut montrer (voir [Dav63]) que si les noeuds xi sont dis-tincts, il existe un unique polynme HN1 PN1, appel polynme dinterpolation dHermite,tel que

H(k)N1(xi) = y

(k)i , pour tous i = 0, . . . , n , et k = 0, . . . , mi.

Ce polynme scrit

HN1(x) =n

i=0

mik=0

y(k)i Lik(x) (5.1)

o y(k)i = f(k)(xi), pour tous i = 0, . . . , n , et k = 0, . . . , mi. Les fonctions Lik PN1 sont

appeles les polynmes caractristiques dHermite et sont dfinies par les relations

dpdxp

(Lik)(xj ) = 1 si i = j et k = p

0 sinon

En dfinissant les polynmes

ij (x) =(x xj )

j

j

nk=0k=i

x xkxi xk

mk+1, i = 0, . . . , n, j = 0, . . . , mi

et en posant Limi(x) = imi(x) pour i = 0, . . . , n, on a les relations de rcurrence suivantes pourles polynmes Lij

Lij(x) = ij (x) mi

k=j+1

(k)ij (xi)Lik(x) j = mi 1, mi 2, . . . , 0.

Concernant lerreur dinterpolation, on a lestimation

f(x) HN1(x) =f(N)()

N!N(x) x R,

o I(x; x0, . . . , xn) et N est le polynme de degr N dfini par

N = (x x0)m0+1(x x1)

m1+1 (x xn)mn+1,

avec I(x; x0, . . . , xn) le plus petit intervalle contenant x, x0, . . . , xn.

23


24/28

Conclusion

Dans ce projet nous avons abord lapproximation au sens des moindres carrs, linterpolationpolynomiale avec noeuds quirpartis sur un ou plusieurs morceaux, ainsi que linterpolationdHermite-Birkhoff qui prend en compte les valeurs aux noeuds, des drives dune fonction

en plus des valeurs de cette fonction. Il existe beaucoup dautres extensions de linterpolationnumrique :La premire est ce quon appelle les fonctions splines, qui sont en fait des interpolations poly-

nomiales par morceaux, mais qui demandent en plus que les drives des polynmes interpolantssoient gales, cela aux points de jointure entre les morceaux. On obtient ainsi une fonction po-lynomiale par morceaux qui est (au moins) C1, vue sur lensemble du domaine dinterpolation.Ensuite, linterpolation peut se faire non pas grce des polynmes, mais par exemple avec despolynmes trigonomtriques, ou des fonctions exponentielles.

La seconde extension concerne la dimension du problme. En effet, il est possible dinterpo-ler des courbes paramtres (dans le plan ou lespace) et dinterpoler des surfaces de lespace(surfaces paramtres, ou fonction de R2 dans R). Les lecteurs interresss trouverons plus din-

formation sur ces sujets dans [Quart07].

24


25/28

Rfrences

[Axler97] S. Axler. (1997) Linear Algebra Done Right (Second Edition). Undergraduate Textsin Mathematics, Springer-Verlag.

[Dav63] Davis P. (1963) Interpolation and Approximation. Blaisdell Pub., New York

[Die93] Dierckx P. (1993) Curve and Surface Fitting with Splines. Claredon Press, New York.[Erd61] Erds P. (1961) Problems and Results on the Theory of Interpolation. Acta Math. Acad.

Sci. Hungar. 44 : 235-244

[Hess06] Hess Bellwald K. (2006) Algbre Linaire I / II (notes manuscrites de Pablo CROTTI)

[Quart07] A. Quarteroni, R. Sacco and F. Saleri, (2007) Mthodes numriques. Springer, Italia.

25


26/28

.

ANNEXE : CODES MATLAB

26


27/28

Programme 1 - Lissage : Gnration et lissage de donne alatoire

function Lissage

% LISSAGE Approxime un jeu de 10 points, perturbation dune loi quadratique

x = linspace(0,1,10);

f = 10*x.2+rand(size(x)); % perturbations sur la loi quadratiquepol9 = polyfit(x,f,9); % polynme interpolant de degr 9

pol2 = polyfit(x,f,2); % approximation de degr 2 au sens des moindres carrs

x2 = linspace(0,1,100);

y9 = polyval(pol9,x2);

y2 = polyval(pol2,x2);

figure(Name,Lissage);

axes(Box,on);

hold on;

plot(x,f,+r);

plot(x2,y9,--b);

plot(x2,y2,-k);x = 2 ;

f2 = 10*x.2+rand(size(x)) %valeur relle de f au point x=2

y92 = polyval(pol9,2) %valeur du polynme interpollant en x=2

y22 = polyval(pol2,2) %valeur de lapproximation en x=2

legend(char(f,Degr 9,Degr 2),Location,NorthEastOutside);

return;

27


28/28

Documents

Interpolation Numerique