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

View - Download Chapitre 1 : Introduction à LAnalyse Numérique

Previous PDF

Next PDF

1/18 Chapitre 1 : Introduction à L"Analyse Numérique 2/18

1Définition

L"analyse numérique est la conception et l"étude d"algorithmes pour obtenir des solutions à des ensembles d"équations issus de modèles issus de la physique, de la biologie, de la finance ...2Motivations : Recherche et développement : études expérimentales coûteuses Les modèles considérés sont composés d"ensemble d"équations dont

on ne sait pas déterminer de solutions explicitesProposer une solution approchée, calculée à l"aide de l"ordinateur.

3Développer des algorithmes efficaces

Convergence et stabilité de la méthode numérique

Coût algorithmique

3/18 Plan du cours1Introduction à l"analyse numérique

2Interpolation et approximation

3Intégration numérique

4Résolution de systèmes linéaires

5Equations non linéaires

6Equations différentielles ordinaires

7Equations aux dérivées partielles

4/18Quelques exemples

Mouvement du penduleθl

mg

Equation

8

00(t) +gl

sin((t)) =0; (0) =0;0(0) =1Solution exacte ?

Solution approchée pour <<1

8>>><>>>:

00(t) +gl

(t) =0; (t) =0cos qg l t +ql g 1sin qg l tUtiliser une approximation numérique de la solution !

5/18Quelques exemples

Calculer les racines du polynômep(x) =ax2+bx+c

6/18Quelques exemples

Temps de calcul pour l"inversion d"une matrice

7/18

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

2Conditionnement, stabilité et complexité

8/18Représentation des réels en basebTous nombre réelxpeut être représenté sous la forme

x=m be;avecb2:avec la mantissem: m=m1b1+m2b2+:::;etmi2 f0;1;:::;b1get l"exposante: e=e0b0+e1b1+:::es1bs1;avec s2NReprésentation unique ?

Ordinateur : mémoire finie !

La mantisse est tronquée au bout derchiffres,Valeur maximale pours

9/18Le standard IEE (754-1985)

Float double précision : utilisation de 8 octets ( 64 bits ),b=2e : 11 bitsm : 52 bitsSigne: 1 bitPour la mantisse : utilisation de 52 bits

m=21+m222+m323+:::+m53253;Pour l"exposant : 11 bits :e2[1022;1025]avec e=c020+c121+:::+c102101022;avecci2 f0;1gLes valeurse=1022 ete=1025 sont réservées à la représentation de 0 et de InfOn appelleFl"ensemble fini de ces nombres

10/18Exercices

Exercice

Calculer x

maxle nombre le plus grand deFet xposmin, le nombre positif le plus petit deFExercice Proposer deux algorithmes pour déterminer respectivement une approximation numérique de x maxet xposmin

11/18Erreur d"arrondi

Seuls les éléments deFsont autorisésUn nombre réelxm2e,m=0:1m2m3:::pourxposmin><>>:0:1m2:::m532esim54=0; (0:1m2:::m53+253)2esim54=1;Exercice Calculer le nombre le plus petit tel que rd(x+1)>1et proposer un algorithme pour retrouver numériquement ce nombre

12/18Erreur arrondi

Sixposmin2532e:L"erreur d"arrondi relative est xrd(x)x 12 2

532ejmj2e253'1016

13/18

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

2Conditionnement, stabilité et complexité

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

Definition

Le conditionnement représente la sensibilité du résultat par rapport à de petites variations des données ...

On dit qu"un problème est

-bien conditionnési une petite variation des données entraîne une petite variation du résultat -mal conditionnési une petite variation des données entraîne une grande variation du résultatExemple : soitf:R!RDéveloppement de Taylor f(x+x) =f(x) +f0(x)x+o(x) f:=f(x+x)f(x)'f0(x)xConditionnement k=ffx x'xf0(x)f(x)

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,

f=f(x+dx)f(x) =n X i=1@f@xixi+0(jxj2):Le conditionnement est donc déterminé par les nombres k i=@f@xix if(x):Exercice Calculer le conditionnement de l"addition et de la multiplication

16/18Stabilité d"un algorithme

Definition

La stabilité d"un algorithme se réfère à la propagation des erreurs au cours des étapes du calcul, à la capacité de l"algorithme de ne pas trop amplifier

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

p(x) =ax2+bx+cbasé sur les formules x

1=b+pb

24ac2a;x2=bpb

24ac2a

s"avère instable en pratique : exemple aveca=1020;b=1;c=1Exercice

Proposer un autre algorithme plus stable

17/18Complexité algorithmique

Definition (Coût algorithmique)

Nombre d"opérations élémentaires effectuées par l"algorithme (+, *, sqrt, puissance ...)Exemple : Evalutation du polynômep(x) =Pn i=0aixi:Nombre de multiplications : Pn i=0i=n(n+1)2 Nombre d"additions :nCoût algorithmique!O(n2)Definition8 >>>>><>>>>>:O(nk)!coût polynomial

O(an)!coût exponentiel

O(n!)!coût factoriel

18/18Complexité algorithmique

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

i=0aixi:Schéma de Horner p(x) =a0+x(a1+x(a2+x(:::an)))Coût algorithmique ? 1/41

Chapitre 2 : Interpolation et approximation

2/41

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

i=0:n, on recherche dans un espace de fonctions,Interpolation :une fonctionsqui interpole les noeuds(xi;yi), s(xi) =yi;8i=0:n Approximation au sens des moindres carrés :une fonctionsqui minimise l"énergie, nX i=0jyis(xi)j2 3/41 Exemples d"interpolation :fig:Inter polationpolynomiale ,linéaire par morceaux et spline Exemples d"approximation au sens des moindres carrés : fig:

Rég ressionlinéaire ,quadr atique

4/41

1Interpolation polynomiale

2Interpolation polynomiale par morceaux

3Approximation au sens des moindres carrés

5/41Interpolation polynomiale :

Définition

On note P

nl"ensemble des polynômes réels de degré n P n=np(x) ;p(x) =a0+a1x+a2x2+:::+anxno avec a i2ROn recherche un polynômepn2Pntel que pour touti=0:n, p n(xi) =yi:Théorème

Il existe un unique polynôme p

n2Pnqui interpole les noeuds(xi;yi) i=0:n.

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

On souhaite trouver un polynôme de degré 2 qui interpole les noeuds (1;2);(0;3);(1;6). On cherche le polynômep2sous la formep2(x) =a0+a1x+a2x2tel que p

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

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

2(1) =2

p

2(0) =3

p

2(1) =6=)8

>>>>><>>>>>:a

0a1+a2=2

a 0=3 a

0+a1+a2=6=)8

>>>>><>>>>>:a 0=3 a 1=2 a 2=1

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

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

Plus généralement,Pnest un espace vectoriel dont la base canonique s"écritn1;X;X2;:::;Xnoet p n(x) =n X k=0a kxk:quotesdbs_dbs29.pdfusesText_35

[PDF] TD - corrigé

[PDF] SERIE D 'EXERCICES N° 3 - THEORIE DU CONSOMMATEUR

[PDF] TD Microéconomie - Numilog

[PDF] Statistique descriptive, exercices maths standard secondaire II

[PDF] Les modulations analogiques

[PDF] Eléments de correction TD EDT4 Exercices corrigés

[PDF] Hydraulique industrielle Correction TD 1

[PDF] Exercice sur la variance et l 'écart-type

[PDF] Exercices MS Project - Chamilo

[PDF] Correction - limsi

[PDF] ED Biologie moléculaire - Free

[PDF] Soins et pharmacologie automne 2009 (Corrigé) Exercice : associer

[PDF] Livre du professeur - Le livre du prof

[PDF] Exercice 1 -A : Approche déterministe du calcul des stocks de

[PDF] Exercice 12