Approximation De Fonction ( Cours Math 4 Usthb )

Analyse Numérique Problèmes Pratiques

Approximation de fonctions

Introduction

1/2

❚ Dans différentes disciplines scientifiques, besoin de résoudre de nombreux problèmes numériques : ❙ … ❙ …

❚ Résolution de ces problèmes ❙ mise sous forme matricielle ❙ résolution de systèmes linéaires de n équations à n inconnues ❙ besoin d'inverser des matrices Ph. Leray

Analyse Numérique

1

1

Introduction

2/2

❚ Quelques problèmes abordés dans ce cours : ❙ ❙ ❙ ❙ ❙ ❙

approximation de fonctions optimisation résolution de f(x)=0 intégration et dérivation résolution d'équations différentielles transformée de Fourier

Ph. Leray

Analyse Numérique

2

Approximation de fonctions

1/2

❚ Soit une fonction f (inconnue explicitement) ❙ connue seulement en certains points x0,x1…xn ❙ ou évaluable par un calcul coûteux.

❚ Principe : ❙ représenter f par une fonction simple, facile à évaluer

❚ Problème : ❙ il existe une infinité de solutions ! 2 1 0 -1 -2 -3 -4 0

Ph. Leray

0.2

0.4

Analyse Numérique

0.6

0.8

1

1.2

1.4

1.6

1.8

3

2

Approximation de fonctions

2/2

❚ Il faut se restreindre à une famille de fonctions ❙ polynômes, ❙ exponentielles, ❙ fonctions trigonométriques…

2 1 0 -1 -2 -3 -4 0

Ph. Leray

0.2

0.4

0.6

0.8

1

1.2

1.4

1.6

1.8

Analyse Numérique

4

Quelques méthodes d'approximation ❚ Interpolation polynomiale ❙ polynômes de degré au plus n ❘ polynômes de Lagrange ❘ différences finies de Newton

❚ Interpolation par splines cubiques ❙ polynômes de degré 3 par morceaux

❚ Interpolation d'Hermite ❙ informations sur les dérivées de la fonction à approcher

❚ … Ph. Leray

Analyse Numérique

5

3

Interpolation polynomiale : Lagrange ❚ Théorème ❙ Soient n+1 points distincts xi réels et n+1 réels yi, il existe un unique polynôme p ∈ Pn tel que p(xi) = yi pour i = 0 à n

❚ Démonstration par construction n ❙ p( x ) = ∑ y i Li ( x ) i =0

avec Li polynôme de Lagrange

n

Li ( x ) = ∏ j =0 j ≠i

❙ Propriétés de Li

(x − x ) (x − x ) j

i

j

❘ Li polynôme de degré n ❘ Li(xi)=1 Li(xj)=0 (j ≠ i) Ph. Leray

Analyse Numérique

6

Lagrange : exemple n°1 ❚ Exemple avec n=1 ❙ on connaît 2 points (x0,y0) et (x1,y1) ❙ on cherche la droite y=ax+b (polynôme de degré 1) qui passe par les 2 points : ❘ y 0 = a x0 + b a = (y0 - y1) / (x0 - x1) y1 ❘ y 1 = a x1 + b

❙ y=

y0 − y1 x y − x1 y 0 x+ 0 1 x 0 − x1 x0 − x1

y = y0

Ph. Leray

b = (x0 y1 - x1 y0) / (x0 - x1)

y0 x0

x1

x − x0 x − x0 x − x1 x − x1 − y1 = y0 + y1 x0 − x1 x0 − x1 x0 − x1 x1 − x 0 L0(x) L1(x) Analyse Numérique

7

4

Lagrange : exemple n°2

1/2

❚ Exemple avec n=2 ❙ on connaît 3 points (0,1), (2,5) et (4,17) ❙ polynômes de Lagrange associés : L0 ( x ) =

(x − 2 )(x − 4 ) 8

x(x − 4 ) −4

L1 ( x ) =

L2 ( x ) =

x (x − 2 ) 8

-

0

Ph. Leray

2

4

0

2

4

0

2

4

Analyse Numérique

8

Lagrange : exemple n°2

2/2

❙ calcul du polynôme d'interpolation 30

25

❘

p(x)=L0(x) + 5 L1(x) + 17 L2(x) 20

15

10

5

0 -1

0

1

2

3

4

5

❘ en simplifiant, on retrouverait p(x)=x2+1

Ph. Leray

Analyse Numérique

9

5

Lagrange : exemple n°3

1/2

❚ Exemple avec n=2

(fonction à approcher y=ex) ❙ on connaît 3 points (0,1), (2,7.3891) et (4,54.5982) ❙ Polynôme d'interpolation ❘ p(x) =L0(x) + 7.3891 L1(x) + 54.5982 L2(x) 60

50

40

30

20

10

0

-10 -1

Ph. Leray

0

1

2

3

Analyse Numérique

4

5

10

Lagrange : exemple n°3

2/2

❙ Erreur d'interpolation e(x) = f(x) - p(x) 60

50

40

30

20

10

0

-10

-20 -1

Ph. Leray

0

1

2

Analyse Numérique

3

4

5

11

6

Lagrange : erreur d'interpolation ❚ Théorème : ❙ si f est n+1 dérivable sur [a,b], ∀ x ∈ [a,b], notons : ❘ I le plus petit intervalle fermé contenant x et les xi ❘ φ(x)=(x-x0)(x-x1)…(x-xn) ( n +1 )

❙ alors, il existe ξ ∈ I tel que e(x ) =

(ξ )φ (x ) (n + 1)!

f

❙ NB : ξ dépend de x

❚ Utilité ❙ contrôle de l’erreur d’approximation ❙ « réglage » de la qualité de l’approximation Ph. Leray

Analyse Numérique

12

Lagrange : choix de n ❚ Supposons que l'on possède un nb élevé de points pour approcher f … faut-il tous les utiliser ? ❙ (calculs lourds)

❚ Méthode de Neville : ❙ on augmente progressivement n ❙ on calcule les Li de manière récursive ❙ on arrête dès que l'erreur est inférieure à un seuil (d’où l’utilité du calcul de l’erreur)

Ph. Leray

Analyse Numérique

13

7

Lagrange : l’algorithme

1/2

❚ Méthode de Neuville (approche récursive) ❙ Soient xj et xk deux points où la fonction est connue ❘ on a

p( x ) =

(x − x j )Q j (x )− (x − xk )Q k (x ) (xk − x j )

❘ avec Qj(x) (resp. Qk(x)) polynôme d’interpolation obtenu avec tous les points sauf xj (resp. xk)

❙ Soit Qjk(x) le polynôme d’interpolation de degré k obtenu avec les points xj-k à xj ❘ on a p(x) = Qii(x) polynôme d’interpolation de degré i

Ph. Leray

Analyse Numérique

Lagrange : l’algorithme

14

2/2

❚ Interpolation en 1 point x : Pour i allant de 1 à n Pour j allant de 1 à i Q ij ( x ) =

(x − xi− j )Q i , j −1 (x ) − (x − xi )Q i−1, j −1 (x ) (xi − xi− j )

FinPour Approximation de degré i = Qii(x) FinPour

❚ Complexité du calcul : n2 Ph. Leray

Analyse Numérique

15

8

Interpolation polynomiale : Newton ❚ Polynômes de Newton : ❙ base = {1, (x-x0), (x-x0)(x-x1), …, (x-x0)(x-x1)…(x-xn-1)} ❙ on peut ré-écrire p(x) : p(x)=a0 + a1(x-x0) + a2(x-x0)(x-x1)+…+ an(x-x0)(x-x1)…(x-xn-1) ❙ calcul des ak : méthode des différences divisées

Ph. Leray

Analyse Numérique

Newton : différences divisées

16

1/3

❚ Définition : ❙ Soit une fonction f dont on connaît les valeurs en des points distincts a, b, c, … ❙ On appelle différence divisée d’ordre 0, 1, 2,...,n les expressions définies par récurrence sur l’ordre k : ❙ k=0 f [a] = f (a) ❙ k=1 f [a,b] = ( f [b] - f [a] ) / ( b - a ) ❙ k=2 f [a,b,c] = ( f [a,c] - f [a,b] ) / ( c - b ) ❙ … Ph. Leray

f [X,a,b] = ( f [X,b] - f [X,a] ) / ( b - a ) a∉X, b∉X, a≠b Analyse Numérique

17

9

Newton : différences divisées

2/3

❚ Théorèmes : ❙ détermination des coefficients de p(x) dans la base de Newton : avec k = 0 … n

f [x0, x1,…, xk] = ak ❙ erreur d'interpolation :

e(x) = f [x0, x1,…, xn, x] φ(x)

Ph. Leray

Analyse Numérique

18

Newton : différences divisées

3/3

❚ Calcul pratique des coefficients : a0

x0 f [x0] x1 f [x1] x2 f [x2] … … … … xn

f [xn]

Ph. Leray

a1

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

f [x0, x1, x2] ... f [xn-3, xn-2, xn-1]

f [xn-1, xn]

f [xn-2, xn-1, xn]

a2

Analyse Numérique

an

…

f [x0, ..., xn]

19

10

Newton : exemple ❚ (ex. n°2) : n=2

(0,1), (2,5) et (4,17)

a0

0

f [x0]=1

2

f [x1]=5

4

f [x2]=17

a1 f [x0, x1] =(1-5)/(0-2)=2 f [x1, x2] =(5-17)/(2-4)=6

(et on retombe sur p(x) = 1 + x2)

p(x)=1 + 2x + x(x-2) Ph. Leray

f [x0, x1, x2] a2 = (2-6)/(0-4)=1

Analyse Numérique

20

Newton : l’algorithme ❚ Interpolation en 1 point x : Pour i allant de 1 à n Pour j allant de 1 à i Fi , j =

Fi , j −1 − Fi −1, j −1 xi − xi − j

FinPour ai = Fi,i FinPour

❚ Complexité du calcul : n2 Ph. Leray

Analyse Numérique

21

11

A bas les polynômes ❚ Ex : y=2(1+tanh(x)) - x/10 avec 9 points ❙ entre les points, le polynôme fait ce qu'il veut… et plus son degré est élevé plus il est apte à osciller ! 6

4

2

0

-2

-4

-6 -6

Ph. Leray

-4

-2

0

2

4

6

Analyse Numérique

22

Interpolation par splines cubiques ❚ Principe : ❙ on approche la courbe par morceaux (localement) ❙ on prend des polynômes de degré faible (3) pour éviter les oscillations

❚ Cas particulier des splines

Ph. Leray

Analyse Numérique

23

12

Splines cubiques : définition ❚ Définition : ❙ On appelle spline cubique d’interpolation une fonction notée g, qui vérifie les propriétés suivantes : ❘ g ∈ C2[a;b] (g est deux fois continûment dérivable), ❘ g coïncide sur chaque intervalle [xi; xi+1] avec un polynôme de degré inférieur ou égal à 3, ❘ g(xi) = yi pour i = 0 … n

❚ Remarque : ❙ Il faut des conditions supplémentaires pour définir la spline d’interpolation de façon unique ❙ Ex. de conditions supplémentaires : spline naturelle.

❘ g"(a) = g"(b) = 0 Ph. Leray

Analyse Numérique

Splines cubiques : détermination

24

1/4

❚ Détermination de la spline d’interpolation ❙ g coïncide sur chaque intervalle [xi; xi+1] avec un polynôme de degré inférieur ou égal à 3 ➨ g" est de degré 1 et est déterminé par 2 valeurs: ❘ mi = g"(xi) et mi+1 = g"(xi+1)

(moment au noeud n°i)

❙ Notations : ❘ hi = xi+1 - xi pour i = 0 … n-1 ❘ δi= [xi; xi+1] ❘ gi(x) le polynôme de degré 3 qui coïncide avec g sur l’intervalle δi

Ph. Leray

Analyse Numérique

25

13

Splines cubiques : détermination

2/4

❙ g"i(x) est linéaire :

x − xi x −x + mi i +1 hi hi x − xi )2 (x − x )2 + a ( g i′ (x ) = mi +1 − mi i +1 i 2 hi 2 hi

g i′′(x ) = mi +1

❘ ∀ x ∈ δi

❘ on intègre (ai constante)

❘ on continue g i (x ) = mi +1 (bi constante)

❙ gi(xi) = yi ❙ gi(xi+1) = yi+1

Ph. Leray

yi =

(x − xi )3 + m (xi +1 − x )3 + a (x − x ) + b i

6 hi

mi hi 2 + bi 6

1

y i +1 =

6 hi

i

mi +1hi 2 + ai hi + bi 6

i

i

2

Analyse Numérique

26

Splines cubiques : détermination

3/4

i i −1 ❙ g'(x) est continue : g i′ (xi ) = −mi 2 + ai = mi 2 + ai −1 = g i′−1 (xi ) 3

h

❙ 1 et 2

ai =

h

1 (yi +1 − yi ) − hi (mi +1 − mi ) hi 6

❙ on remplace les ai dans 3 : 4

 1 1 (yi − yi −1 ) hi −1 mi −1 + 2(hi + hi −1 )mi + hi mi +1 = 6  (yi +1 − yi ) − h h i −1   i

❙ Rappel : on cherche les mi (n+1 inconnues) ➨ on a seulement n-1 équations grâce à 4 ➨ il faut rajouter 2 conditions, par exemple ➨ m0 = mn =0 Ph. Leray

(spline naturelle) Analyse Numérique

27

14

Splines cubiques : détermination

4/4

 1 1 hi −1 mi −1 + 2(hi + hi −1 )mi + hi mi +1 = 6  (yi +1 − yi ) − (yi − yi −1 ) hi −1   hi

4

❙ Ex de résolution avec hi = xi+1 - xi constant : ❘

mi −1 + 4 mi + mi +1 =

1

h2

( y i −1 − 2 y i + y i +1 ) =

4 ❘ forme matricielle :  1  Tm=f    

1 4 Ο

1 Ο 1

Ο 4 1

fi

0  m1   f 1           Λ  =  Λ         1      4  mn −1   f n −1 

❘ T inversible (tridiagonale) Ph. Leray

Analyse Numérique

28

Splines cubiques : l’algorithme ❚ Calcul des moments par résolution d’un système linéaire tridiagonal ❚ Algorithme = factorisation de Crout (LU « tridiagonal ») ❚ Complexité du calcul : n

Ph. Leray

Analyse Numérique

29

15

Splines cubiques : exemple ❚ Ex : y=2(1+tanh(x)) - x/10 avec 9 points 6

4

spline

2

0

-2

-4

-6 -6

polynôme de degré 8 -4

Ph. Leray

-2

0

2

4

6

Analyse Numérique

30

Conclusion ❚ Interpolation polynomiale ❙ évaluer la fonction en un point : polynôme de Lagrange ➨ méthode de Neville ❙ compiler la fonction (calcul des coefficients du polynôme) : polynôme de Newton

❚ Interpolation polynomiale par morceau : splines ❙ ❙ ❙ ❙ Ph. Leray

spline cubique d’interpolation spline cubique d’approximation (on régularise) b spline spline généralisée : splines gaussiennes Analyse Numérique

31

16