[PDF] [PDF] Chapitre 1 : Introduction à LAnalyse Numérique

532ejmj2e253'1016

1Représentation des réels sur l"ordinateur

2Conditionnement, stabilité et complexité

14/18Conditionnement d"un problème numérique

Definition

On dit qu"un problème est

15/18Conditionnement des opérations arithmétiques

élémentairesSoitf2 C2(Rn;R). Quel est le conditionnement def?D"après le développement de Taylor def,

16/18Stabilité d"un algorithme

Definition

d"éventuels écarts, à la précision des résultats obtenus.Exemple : l"algorithme qui calcule les racines du polynôme

1=b+pb

24ac2a;x2=bpb

24ac2a

Proposer un autre algorithme plus stable

17/18Complexité algorithmique

Definition (Coût algorithmique)

O(an)!coût exponentiel

O(n!)!coût factoriel

18/18Complexité algorithmique

Exemple : Evalutation du polynômep(x) =Pn

Chapitre 2 : Interpolation et approximation

A partir d"un ensemble de points(xi;yi)

Rég ressionlinéaire ,quadr atique

1Interpolation polynomiale

2Interpolation polynomiale par morceaux

3Approximation au sens des moindres carrés

5/41Interpolation polynomiale :

Définition

On note P

Il existe un unique polynôme p

6/41Polynôme d"interpolation de Vandermonde :

2(1) =2,p2(0) =3 etp2(1) =6. Alors

8>>>>><>>>>>:p

2(1) =2

2(0) =3

2(1) =6=)8

0a1+a2=2

0+a1+a2=6=)8

La solution du problème est doncp2(x) =3+2x+x2

7/41Polynôme d"interpolation de Vandermonde :

8>>>>>>>>><>>>>>>>>>:p

0+a1x0+a2x2

0+:::+anxn

0+a1x1+a2x2

1+:::+anxn

1=y1:::

0+a1xn+a2x2n+:::+anxnn=yn

8/41Polynôme d"interpolation de Vandermonde :

BBBBBBBBBBBBBBB@1x0x2

01x1x2

1xnx2nxnn1

CCCCCCCCCCCCCCCA0

BBBBBBBBBBBBBBB@a

CCCCCCCCCCCCCCCA=0

BBBBBBBBBBBBBBB@y

CCCCCCCCCCCCCCCA

Le déterminant de la matrice B vérifie

0i

9/41Polynôme d"interpolation de Vandermonde :

Le polynôme d"interpolationpns"obtient donc par la résolution du système

linéaireBa=y! Mais en pratiqueBest une matrice mal conditionnée !Coût de la résolution du système linéaire enO(n3)!

Idée :Exprimer le polynômepndans une autre base dePnet pour laquelle, la décomposition depnest explicite !

10/41Polynôme d"interpolation de Lagrange

On souhaite trouver le polynôme d"interpolation associé aux noeuds (1;2);(0;3);(1;6). On introduit alors les trois polynômesL0,L1etL2définis par L

0(x) =12

x(x1);L1(x) =1x2;etL2(x) =12 x(1+x);qui vérifient

8>>>>><>>>>>:L

0(1) =1;L0(0) =0;L0(1) =0;

L

1(1) =0;L1(0) =1;L1(1) =0;

L

2(1) =0;L2(0) =0;L2(1) =1;Exercice

Montrer que la famille

fL0;L1;L2gest libre et expliciter la décomposition de p

2dans cette base

11/41Polynôme d"interpolation de Lagrange

Plus généralement, on introduit une base dePnnotéenLn ko k=0:n, où les polynômesLn ksont définis par la propriété suivante : L n k(xi) =8 >><>>:1 sik=i

0 sinonExercice

Montrer que le polynômeLn

ks"explicite sous la forme L n k(x) =Q n i=0;i,k(xxi)Q n i=0;i,k(xkxi):Exercice

Montrer que le polynôme d"interpolation p

nau noeuds(xi;yi) i=0:nvérifie p n=n X i=0y iLn i 12/41 fig: Inter polationpolynomiale de la f onctionf(x) =11+x2sur[1;1]avec respectivementn=6,n=14 etn=24fig:Inter polationpolynomiale de la f onctionf(x) =11+x2sur[5;5]avec respectivementn=6,n=14 etn=24

13/41Erreur d"interpolation

On suppose quef: [a;b]!Rest une fonction suffisamment régulière. On vient d"expliquer comment obtenir le polynôme d"interpolationpnau noeuds(xi;f(xi)) i=0:n. On souhaite maintenant donner une estimation de l"erreurE(x)commise entrepnetf:

E(x) =f(x)pn(x):

14/41Erreur d"interpolation

Théorème

Soit f2Cn+1[a;b]avec a=x015/41Erreur d"interpolation

Montrer le résultat précédent

16/41Noeuds d"interpolation de tchebychev