PROGRAMMATION SCIENTIFIQUE EN C

PRO-1027

Interpolation de fonctions

Introduction Méthode de Gregory-Newton Méthode de Lagrange Travail pratique 3 a)

– Affichage de 2 courbes avec xgraph

Introduction

Dans plusieurs problèmes nous avons en main un ensemble de mesures discrètes

Nous voulons souvent connaître le comportement du phénomène mesuré entre chaque mesure discrète

Nous devons alors interpoler les intervalles de valeurs entre chaque mesure discrète à l’aide de fonctions de degré quelconque

Introduction

Si nous avons un polynôme d’interpolation f(x) de degré n:

nnxbxbxbbxf 2

210)(

Les coefficients du polynôme sont déduits à partir des points de contrôle (mesures)

Introduction

Interpolation linéaire

xbbxf 10)(

Deux points de contrôle (mesures) sont nécessaires pour déduire les coefficients inconnus

Introduction

Interpolation linéaire

Introduction

Interpolation linéaire– Par la loi des triangles semblables nous savons:

i

i

ii

ii

xx

xfxf

xx

xfxf

)()()()(

1

1

– Si f(x) est mis en évidence:

iii

iii xx

xx

xfxfxfxf

1

1 )()()()(

PENTEDÉVIATION PAR RAPPORT à xi

Introduction

Interpolation linéaire– Ce type d’interpolation peut causer des erreurs

importantes lorsque le polynôme réel est d’ordre supérieur au polynôme d’interpolation (Voir l’intervalle [2,3])

– Pour améliorer la précision de l’interpolation nous devons utiliser des polynômes de degrés supérieurs

Introduction

Interpolation non linéaire– Prenons par exemple un polynôme de degré 2

2210)( xbxbbxf

– Nous devons alors utiliser 3 points de contrôle pour dé- duire les valeurs des coefficients

– Si nous généralisons cette approche, nous pouvons alors utiliser un polynôme d’interpolation de degré n avec n+1 coefficients et qui requière n+1 points de con- trôle pour déduire les valeurs des coefficients

Méthode de Gregory-Newton

Cette méthode permet de déduire un polynôme d’interpolation de degré n sans avoir à résoudre un système d’équations linéaires

Le polynôme déduit par cette méthode est de la forme

)())(()())((

))()(())(()()(

211121

3214213121

nnnn

n

xxxxxxaxxxxxxa

xxxxxxaxxxxaxxaaxf

Les n valeurs de xi et f(xi) sont connues, les n+1 valeurs des coefficients ai sont inconnues et doivent être déduites

Méthode de Gregory-Newton

Si les valeurs de x sont en ordre croissant nous pouvons alors déduire les coefficients ai par

))((

)(

))((

)()(

)()()(

)(

))(()()()(

)()()(

)()(

2313

13213

2313

1321323

12

12

12

1021

12

1212

1101

2313313213323

12212212

11101

xxxx

xxaay

xxxx

xxaaxfa

xx

yy

xx

xfxf

xx

axfa

yxfa

xxxxaxxaayxfxf

xxaayxfxf

ayxfxf

n

n

n

Nous répétons ces calculs pour les n+1 coefficients ai.

Méthode de Gregory-Newton

Le polynôme de Gregory-Newton sous sa forme généralisée

12)())()((

)(

011)(

)()(

1321

1

11

1

1

1

1

1

1

nixxxxxxxx

xfya

ya

ixx

xxaxf

iiiii

iiii

j

i

j

j

i

j

n

iin

Méthode de Gregory-Newton

Le polynôme de Gregory-Newton sous sa forme généralisée (calcul des coefficients ai)

12)(

)(

)()(

1

1

1

1101

nixx

xfya

yxfxfa

j

i

j

iiii

n

Méthode de Gregory-Newton

Le polynôme de Gregory-Newton sous sa forme généralisée

)())(())(()()(

))(()()(

)()(

)(

211213121

2131212

1211

10

nnn xxxxxxaxxxxaxxaaxf

xxxxaxxaaxf

xxaaxf

axf

Méthode de Gregory-Newton

Le polynôme de Gregory-Newton sous sa forme généralisée (forme récursive)

)())(()()(

))(()()(

)()()(

)(

2111

21312

1201

10

nnnn xxxxxxaxfxf

xxxxaxfxf

xxaxfxf

axf

Méthode de Lagrange

Lorsque les intervalles en x sont inégaux il faut utiliser une autre forme de polynôme d’interpola-tion

Le polynôme de Lagrange de degré n-1 est utilisée dans ces circonstances. Sa forme générale est donnée par

n

iii

nn

yxlxf

ylylylylxf

1

332211

)()(

)(

Méthode de Lagrange

Les fonctions cardinales li(x) sont données par

ki

kixl

xx

xxxl

ki

ji

jn

ijj

i

1

0)(

)(1

jn

jn

njj

n

j

jn

jj

j

jn

jj

ji

jn

ijj

i

xx

xxxl

xx

xxxl

xx

xxxl

xx

xxxl

1

221

2

111

1

1

)(

)(

)(

)(

Méthode de Lagrange

Les fonctions cardinales li(x) sont données par (n = 3)

))((

))(()(

))((

))(()(

))((

))(()(

2313

21

3

3

31

3

3212

31

2

3

21

2

3121

32

1

3

11

1

xxxx

xxxx

xx

xxxl

xxxx

xxxx

xx

xxxl

xxxx

xxxx

xx

xxxl

j

j

jj

j

j

jj

j

j

jj

Méthode de Lagrange

Les fonctions cardinales li(x1) sont données par (n = 3)

0))((

))(()(

0))((

))(()(

1))((

))(()(

2313

2111

3

13

31

13

3212

3111

2

13

21

12

3121

3121

1

13

11

11

xxxx

xxxx

xx

xxxl

xxxx

xxxx

xx

xxxl

xxxx

xxxx

xx

xxxl

j

j

jj

j

j

jj

j

j

jj

Méthode de Lagrange

Les fonctions cardinales li(x1) sont données par (n = 3)

13322111)( yylylylxf

Méthode de Lagrange

AlgorithmeLire les xi

Lire les yi

Pour m valeurs de x dans l’intervalle [minx, maxx] FAIRE

Calculer

Écrire x et f(x) dans un fichier

FIN POUR

n

iii yxlxf

1

)()(

Travail pratique 3 a)

Recherche du chemin interpolant un ensemble de points (exemple du taxi)