Chapitre II Interpolation et Approximation PDF

Chapitre II Interpolation et Approximation

degré 2 qui ne change plus les valeurs de y0 et de y1. Si x est entre 4 et 5

Cours V : Analyse numérique Interpolation et Résolution déquation

Le modèle est optimisé entre tous les doublets ? lissage régression. 1/ Interpolation linéaire. Définition : Entre deux valeurs successives des abscisses

Interpolation de variables régionales et cartographie automatique

donc on trouve. Cas d'un triangle: FIG. 4. Interpolation entre deux points (M sur la ligne). è=0etè

Analyse Numérique

Ces deux notions toujours présentes en analyse numérique

INTERPOLATION INTÉGRATION ET DÉRIVATION NUMÉRIQUE

1.2.1 Interpolation par morceaux de degrés 0. Il s'agit de considérer qu'entre deux points la valeur de la fonction vaut une constante

Estimation et interpolation de données spatiales

Mots clés: interpolation spatial

Piézométrie des systèmes aquifères : outils de cartographie et

Raccordement des interpolations en zone de transition nappe libre ? nappe captive. - Calcul de différence de niveaux piézométriques entre deux années

Chapitre 2 Interpolation polynomiale

relation entre m et d. Soit i et j deux entiers entre 0 et d. ... Les nombres ai s'appellent les points d'interpolation et les valeurs fi sont les ...

Partie 1 : Série statistique à deux variables

Partie 2 : Ajustement affine. 1) Interpolation extrapolation. L'objectif est

Chapitre II Interpolation et Approximation

valeurs du signal original il suffit de stocker quelques coefficients de la transform?e de Fourier discr`ete sans perdre de l'information visible. Page 18. 40.

Chapitre 2 Interpolation polynomiale - univ-toulousefr

soit i entier entre 0 et dona p(a i)=!d j=0 f jl jd(a i)= d j=0 f j? ji = f i en utilisant le th´eor`eme 2 ! Les nombres a i s’appellent les points d’interpolationet les valeurs f i sont les valeurs interpol´ees Lorsque f i = f(a i) f est la fonction interpol´ee L’uniquepolynˆomep ?P d tel que p(a i)=f(a

interpolation - Définitions synonymes conjugaison exemples Dico en

d’interpolation xi les valeurs yi c `a d ?(xi) = yi ?i On dit que ?(x) interpole {yi}n i=0 aux noeuds {xi} n i=0 On parle d’interpolation polynomiale quand ?(x) est un polynˆome d’interpolation trigonom´etrique quand ?(x) est un polynˆome trigonom´etrique

Chapitre II Interpolation et Approximation

Demonstration ´ Nous utilisons deux ide´es : 1 On procede par r` ecurrence ´ Pour n= 1 et en tenant compte des premiers deux points nous avons p(x) = y0 +(x?x0) y1 ?y0 x1 ?x0 (1 6) Puis pour n= 2 en rajoutant le point (x2y2) on essaie de baˆtir la` dessus un polynoˆme de degre´ 2 qui ne change plus les valeurs de y0 et de

STATISTIQUES À DEUX VARIABLES - maths et tiques

Définitions : L'interpolation et l’extrapolation sont des méthodes qui consistent à estimer une valeur inconnue dans une série statistique - Pour une interpolation le calcul est réalisé dans le domaine d'étude fourni par les valeurs de la série - Pour une extrapolation le calcul est réalisé en dehors du domaine d'étude

Cours V : Analyse numérique Interpolation et Résolution d

Définition : L'interpolation polynômiale consiste à approcher une fonction f dont on connaît n points par un polynôme de degré (n-1) Exemple : Le chiffre d’affaire annuel d’une entreprise est donné dans le tableau suivant: Rang de l’année 1 2 3 CA en millions d’euros 20 24 36 Déterminer le polynôme d'interpolation de cette

Searches related to interpolation entre deux valeurs filetype:pdf

Interpolation avec une echelle logarithmique Il faut faire attention quand on interpole a l’aide d’une echelle logarithmique La fraction lue a l’oeil ou avec une r egle est le logarithme de la fraction de l’unit e et non la fraction elle-m^eme Par exemple a la gure ci-dessous on utilise une unit e de 10 avec echelle

Quelle est la différence entre un point et une interpolation ?

Chaque point correspond à une valeur tandis que les interpolations permettent de saisir la perception de l'évolution des effectifs que les déclarations rétrospectives pouvaient occasionner. Genèses, 2015, Émilien Ruiz (Cairn.info)

Pourquoi utiliser une fonction d’interpolation?

Une fonction d’interpolation ne sert pas juste à reconstruire la fonction entre des points où on connait la valeur. ou pour une intégrale Ceci nous donne des formules très utiles, qui constituent le point de départ d’un très grand nombre de méthodes numériques utilisées en physique pour résoudre des EDO, EDP, équation intégrales ...

Quels sont les différents types d’interpolation?

L’interpolation la plus simple est une interpolation bilinéaire mais elle ne tient pas compte de la forme des objets et peut provoquer des artefacts couleur en par- ticulier des moirages. Des interpolations plus évoluées existent comme l’interpo-

Quelle est la différence entre le polynôme d’interpolation de Lagrange et la fonction interpolation?

Il est assez naturel de penser que le polynˆome d’interpolation de Lagrange approche d’autant mieux la fonction interpol´ee que le nombre de points d’interpolation est grand. Cette id´ee reste correcte pour une grande classe de fonctions et pour des points d’interpo- lation correctement choisis, mais elle est fausse en g´en´eral.

Chapitre IIInterpolation et ApproximationProbl`eme de l'interpolation :on recherche des fonctions "simples" (polynˆomes, polynˆomes par

morceaux, polynˆomes trigonom´etriques) passant par (ou proche) des points donn´es (x0,y0),(x1,y1),...,(xn,yn),(0.1) c.-`a-d., on cherchep(x)avecp(xi) =yipouri= 0,1,...,n. Si les valeurs deyisatisfontyi=

f(xi)o`uf(x)est une fonction donn´ee, il est alors int´eressant d'´etudier l'erreur de l'approximation

f(x)-p(x) = ?(0.2)

Bibliographie de ce chapitre

J.H. Ahlberg, E.N. Nilson & J.L. Walsh (1967):The Theory of Splines and Their Applications.

Academic Press, New York. [MA 65/4]

C. de Boor (1978):A Practical Guide to Splines. Springer-Verlag. [MA 65/141] G.D. Knott (2000):Interpolating Cubic Splines.Birkh¨auser. [MA 65/431] H.J. Nussbaumer (1981):Fast Fourier Transform and Convolution Algorithms. Springer-Verlag. H. Sp¨ath (1995):One Dimensional Spline Interpolation.AK Peters. [MA 65/362]

II.1 Diff

´erences divis´ees et formule de Newton

``...tho' I will not undertake to prove it to others." (Newton, letter to Collins, Nov. 8, 1676 ; publ. Cotes 1711, p. 38) Probl `eme (Newton 1676).´Etant donn´es lesn+ 1points (0.1), chercher un polynˆome p(x) =axn+bxn-1+cxn-2+...(1.1) de degr´enqui satisfasse p(xi) =yipouri= 0,1,...,n.(1.2)

Pour un exemple voir la fig.II.1.

Interpolation et Approximation25

2 4 6 8 10

-50510 p(x) FIG. II.1:Polynˆome d'interpolation de degr´e5 Solution.En ins´erant les conditions (1.2) dans (1.1), le probl`eme se transforme en un syst`eme lin´eaire (`a matrice du type Vandermonde; ici ´ecrit pourn= 2) c+bx0+ax20=y0 c+bx1+ax21=y1 c+bx2+ax22=y2soustraire et diviserb+a(x1+x0) =y1-y0 x1-x0 b+a(x2+x1) =y2-y1 x2-x1(1.3) et, si on soustrait et divise une deuxi`eme fois, on trouve a=1 x2-x0? y2-y1x2-x1-y1-y0x1-x0?.(1.4)

Le mˆeme calcul a ´et´e effectu´e pourn= 4dans un manuscript de Newton datant de 1676; comme `a

l'accoutum´ee, Newton refusa de le publier (voir citation). Cotes le publia comme dernier chapitre

Methodus differentialisdu livreAnalysis per quantitatum series, fluxiones, ac differentias, Londini

1711 (voir fac-simil´e en figure II.2

1). FIG. II.2:Fac-simil´e du calcul de Newton pour le probl`eme de l'interpolation Dans tous ces calculs apparaissent les "diff´erences divis´ees" :

1On peut observer que Newton maˆıtrise les ´eliminations de variables dans un syst`eme lin´eaire avec brio ; plus tard,

toute la gloire pour cette m´ethode reviendra `a Gauss.

26Interpolation et Approximation

D ´efinition 1.1 (diff´erences divis´ees)Pour(xi,yi)donn´es (xidistincts) on d´efinit y[xi] :=yi

δy[xi,xj] :=y[xj]-y[xi]

xj-xi

2y[xi,xj,xk] :=δy[xj,xk]-δy[xi,xj]

xk-xi

3y[xi,xj,xk,xl] :=δ2y[xj,xk,xl]-δ2y[xi,xj,xk]

xl-xietc. tion (voir citation) : Th ´eor`eme 1.2 (formule de Newton)Le polynˆome d'interpolation de degr´enqui passe par les n+ 1points(x0,y0),(x1,y1),...,(xn,yn), o`u lesxisont distincts, est unique et donn´e par p(x) =y[x0] + (x-x0)δy[x0,x1] + (x-x0)(x-x1)δ2y[x0,x1,x2] +...+ (x-x0)(x-x1)·...·(x-xn-1)δny[x0,x1,...,xn].(1.5) D

´emonstration.Nous utilisons deux id´ees :

1. On proc

`ede par r´ecurrence.Pourn= 1, et en tenant compte des premiers deux points, nous avons p(x) =y0+ (x-x0)y1-y0 x1-x0.(1.6)

Il s'agit d'une formule bien connue des G´eom`etres (voirΓ?ωμ?τρ´ια, figure II.1.8).

Puis, pourn= 2, en rajoutant le point(x2,y2), on essaie de bˆatir l`a dessus un polynˆome de degr´e 2, qui ne change plus les valeurs dey0et dey1. Il est donc de la forme p(x) =y0+ (x-x0)y1-y0 x1-x0+a·(x-x0)(x-x1) 2 405 (1.7)

o`u le coefficientaest `a d´eterminer. Mais il s'agit du coefficient dex2dep(x): nous savons d´ej`a

(voir (1.4)) que celui-ci est la deuxi`eme diff´erence divis´eeδ2y[x0,x1,x2]. Pour d´emontrer le cas g´en´eral, nous supposons que p

1(x) =y[x0] + (x-x0)δy[x0,x1] +...+ (x-x0)·...·(x-xn-2)δn-1y[x0,x1,...,xn-1]

soit le polynˆome unique de degr´en-1qui passe par(xi,yi)pouri= 0,1,...,n-1. Alors, comme auparavant, le polynˆomep(x)a n´ecessairement la forme p(x) =p1(x) +a·(x-x0)(x-x1)·...·(x-xn-1), o`uaest d´etermin´e parp(xn) =yn.

2.L'id

´eedeAitken-Neville.Pourmontrerquea=δny[x0,x1,...,xn], cequiach`evelad´emonstra- tion, nous consid´erons ´egalement le polynˆome de degr´en-1 p

2(x) =y[x1] + (x-x1)δy[x1,x2] +...+ (x-x1)·...·(x-xn-1)δn-1y[x1,x2,...,xn],

Interpolation et Approximation27

2 4 6 8 10

-10-50510 p(x) p 2(x)p 1(x) FIG. II.3:Les polynˆomesp1(t),p2(t)etp(t)de l'algorithme d'Aitken-Neville qui passe par(xi,yi)pouri= 1,...,n(voir figure II.3). Ensuite, on pose (Aitken - Neville, 1929, 1932
2) p(x) =1 xn-x0?(xn-x)p1(x) + (x-x0)p2(x)?.(1.8)

Il s'agit d'un polynˆome de degr´en, qui satisfait la condition (1.2) pour le pointx0(ici, le facteur

(x-x0)est nul), pour le pointxn(ici, le facteur(x-xn)est nul), et pour les pointsx1,...,xn-1

(ici, les deux polynˆomesp1etp2sont ´egaux `ayi). Le polynˆome d´esir´e est donc trouv´e.

En consid´erant le coefficient dexndans (1.8), nous obtenons a=1 ce qui d´emontre la formule (1.5). TAB. II.1:Diff´erences divis´ees pour les donn´ees de la fig.II.1 xiyiδy δ2y δ3y δ4y δ5y

0-1121 3/85/2-77/12046-17/6 167/960-6 3/4-287/960050 5/3-1/82/3-1/482 1/63/2105

Exemple 1.3Pour les donn´ees de la fig.II.1, les diff´erences divis´eessont pr´esent´ees dans le

tableau II.1. Le polynˆome d'interpolation est alors donn´e par p(x) =-1 +x+x(x-2)3 -x(x-2)(x-4)(x-5)(x-8)287 9600.
ou mieux encore pour la programmation (ou le calcul `a la main) p(x) =-1 +x?1 + (x-2)?3

8+ (x-4)?-77120+ (x-5)?167960-(x-8)2879600????.

2Il fallait plus de deux si`ecles pour avoir cette id´ee !...

28Interpolation et Approximation

Remarque.L'ordre des{xi}n'a aucune importance pour la formule de Newton (1.5). Si l'on

permute les donn´ees(xi,yi), on obtient ´evidemment le mˆeme polynˆome. Pour l'exempleci-dessus

et pour les{xi}choisis dans l'ordre{4,5,2,8,0,10}, on obtient ainsi p(x) = 6 + (x-4)?-6 + (x-5)?-17

6+ (x-2)?34+ (x-8)?167960-x2879600????.

En observant queδny[xi0,...,xin]est une fonction sym´etrique de ses arguments (par exemple,

2y[x2,x3,x1] =δ2y[x1,x2,x3], voir exercices), on peut utiliser les valeurs calcul´ees dans le

tableau II.1. Sixest entre4et5, les deux facteursx-4etx-5dans laformulepr´ec´edente sont relativement petits, ce qui favorise la diminution des erreurs d'arrondi.

II.2 Erreur de l'interpolation

Supposons que les points(xi,yi)soient sur le graphe d'une fonctionf: [a,b]→IR, c.-`a-d., y i=f(xi), i= 0,1,...,n,(2.1)

´etudions alors l'erreurf(x)-p(x)du polynˆome d'interpolationp(x). Deux exemples sont donn´es

dans la fig.II.4. A gauche, on voit un polynˆome d'interpolation pour la fonctionf(x) = sinx, et

`a droite pour la fonction1/(1 +x2). Pour mieux rendre visible l'erreur, on a dessin´e la fonction

f(x)en une courbe pointill´ee.

0 2 4 6 8

-101 -4 -2 0 2 401 f(x) = sinxf(x) =11 +x2 FIG. II.4:Polynˆome d'interpolation poursinx(gauche) et pour1/(1 +x2)(droite) Lesr´esultatssuivantssontdus `aCauchy(1840,Surlesfonctionsinterpolaires,C.R. XI,p. 775-789,

Oeuvresser. 1, vol. V, p. 409-424). Commenc¸ons par une relation int´eressante entre les diff´erences

divis´ees pour (2.1) et les d´eriv´ees de la fonctionf(x). Lemme 2.1Soitf(x)n-fois diff´erentiable etyi=f(xi)pouri= 0,1,...,n(xidistincts). Alors, il existe unξ?(minxi,maxxi)tel que ny[x0,x1,...,xn] =f(n)(ξ) n!.(2.2) D ´emonstration.Soitp(x)le polynˆome d'interpolation de degr´enpassant par(xi,yi)et notons d(x) =f(x)-p(x). Par d´efinition dep(x), la diff´erenced(x)s'annule enn+ 1points distincts : d(xi) = 0pouri= 0,1,...,n.

Interpolation et Approximation29

Commed(x)est diff´erentiable, on peut appliquernfois le th´eor`eme de Rolle (voir le cours d'Analyse I) et on en d´eduit que d ?(x)anz´eros distincts dans(minxi,maxxi).

Le mˆeme argument appliqu´e `ad?(x)donne

d ??(x)an-1z´eros distincts dans(minixi,maxixi), et finalement encore d (n)(x)a1z´ero dans(minixi,maxixi).quotesdbs_dbs2.pdfusesText_4

[PDF] Chapitre II Interpolation et Approximation

Quelle est la différence entre un point et une interpolation ?

Pourquoi utiliser une fonction d’interpolation?

Quels sont les différents types d’interpolation?

Quelle est la différence entre le polynôme d’interpolation de Lagrange et la fonction interpolation?

Bibliographie de ce chapitre

Academic Press, New York. [MA 65/4]

II.1 Diff

´erences divis´ees et formule de Newton

Pour un exemple voir la fig.II.1.

Interpolation et Approximation25

2 4 6 8 10

1711 (voir fac-simil´e en figure II.2

1On peut observer que Newton maˆıtrise les ´eliminations de variables dans un syst`eme lin´eaire avec brio ; plus tard,

26Interpolation et Approximation

δy[xi,xj] :=y[xj]-y[xi]

2y[xi,xj,xk] :=δy[xj,xk]-δy[xi,xj]

3y[xi,xj,xk,xl] :=δ2y[xj,xk,xl]-δ2y[xi,xj,xk]

´emonstration.Nous utilisons deux id´ees :

1. On proc

1(x) =y[x0] + (x-x0)δy[x0,x1] +...+ (x-x0)·...·(x-xn-2)δn-1y[x0,x1,...,xn-1]

2.L'id

2(x) =y[x1] + (x-x1)δy[x1,x2] +...+ (x-x1)·...·(x-xn-1)δn-1y[x1,x2,...,xn],

Interpolation et Approximation27

2 4 6 8 10

0-1121 3/85/2-77/12046-17/6 167/960-6 3/4-287/960050 5/3-1/82/3-1/482 1/63/2105

8+ (x-4)?-77120+ (x-5)?167960-(x-8)2879600????.

2Il fallait plus de deux si`ecles pour avoir cette id´ee !...

28Interpolation et Approximation

6+ (x-2)?34+ (x-8)?167960-x2879600????.

2y[x2,x3,x1] =δ2y[x1,x2,x3], voir exercices), on peut utiliser les valeurs calcul´ees dans le

II.2 Erreur de l'interpolation

0 2 4 6 8

Interpolation et Approximation29

Le mˆeme argument appliqu´e `ad?(x)donne