[PDF] [PDF] Introduction `a lAnalyse Num´erique

View - Download [PDF] Introduction `a lAnalyse Num´erique

Previous PDF

Next PDF

Introduction

a l"Analyse Num

´erique

Ernst Hairer et Gerhard Wanner

Travaux Pratiques

en collaboration avec

Assyr Abdulle

Universit´e de Gen`eveJuin 2005

Section de math´ematiques

Case postale 240

CH-1211 Gen`eve 24

Table de Mati`ere

I Int ´egration Num´erique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1 I.1 Formules de quadrature et leur ordre . . . . . . . . . . . . . . . . .. . . . . . 1 I.2 Etude de l"erreur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 5 I.3 Formules d"un ordre sup´erieur . . . . . . . . . . . . . . . . . . . . .. . . . . . 9 I.4 Polynˆomes orthogonaux de Legendre . . . . . . . . . . . . . . . . .. . . . . . 10 I.5 Formules de quadrature de Gauss . . . . . . . . . . . . . . . . . . . . .. . . . 13 I.6 Un programme adaptatif - TEGRAL . . . . . . . . . . . . . . . . . . . . .. . 15 I.7 L"epsilon-algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 18 I.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 II Interpolation et Approximation . . . . . . . . . . . . . . . . . . . . .. . . . . . . .23 II.1 Diff´erences divis´ees et formule de Newton . . . . . . . . .. . . . . . . . . . . 23 II.2 Erreur de l"interpolation . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 26 II.3 Polynˆomes de Chebyshev . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 28 II.4 Convergence de l"interpolation . . . . . . . . . . . . . . . . . . .. . . . . . . 30 II.5 Influence des erreurs d"arrondi sur l"interpolation . .. . . . . . . . . . . . . . . 34 II.6 Transform´ee de Fourier discr`ete (DFT) . . . . . . . . . . . .. . . . . . . . . . 37 II.7 Transform´ee cosinus discr`ete (DCT) et JPEG . . . . . . . .. . . . . . . . . . . 40 II.8 Transform´ee de Fourier rapide (FFT) . . . . . . . . . . . . . . .. . . . . . . . 43 II.9 Interpolation trigonom´etrique . . . . . . . . . . . . . . . . . .. . . . . . . . . 44 II.10 Interpolation par fonctions spline . . . . . . . . . . . . . . .. . . . . . . . . . 46 II.11 L"erreur du spline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 50 II.12 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 53

III Equations Diff

´erentielles Ordinaires . . . . . . . . . . . . . . . . . . . . . . . . . .57 III.1 Quelques exemples typiques . . . . . . . . . . . . . . . . . . . . . .. . . . . . 58 III.2 M´ethodes de Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 60 III.3 Convergence des m´ethodes de Runge-Kutta . . . . . . . . . .. . . . . . . . . . 63 III.4 Un programme `a pas variables . . . . . . . . . . . . . . . . . . . . .. . . . . . 65 III.5 M´ethodes multipas (multistep methods) . . . . . . . . . . .. . . . . . . . . . . 67 III.6´Etude de l"erreur locale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .71 III.7 Stabilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 72 III.8 Convergence des m´ethodes multipas . . . . . . . . . . . . . . .. . . . . . . . . 73 III.9 Equations diff´erentielles raides (stiff) . . . . . . . .. . . . . . . . . . . . . . . 75

III.10 Int´egration g´eom´etrique . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 80

III.11 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 84

IV Syst

`emes d"Equations Lin´eaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . .87 IV.1 Elimination de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 88 IV.2 Le choix du pivot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 90 IV.3 La condition d"une matrice . . . . . . . . . . . . . . . . . . . . . . . .. . . . 93 IV.4 La stabilit´e d"un algorithme . . . . . . . . . . . . . . . . . . . . .. . . . . . . 95 2 IV.5 L"algorithme de Cholesky . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 98

IV.6 Syst`emes surd´etermin´es - m´ethode des moindres carr´es . . . . . . . . . . . . . 100

IV.7 D´ecomposition QR d"une matrice . . . . . . . . . . . . . . . . . . .. . . . . . 101 IV.8 Etude de l"erreur de la m´ethode des moindres carr´es . .. . . . . . . . . . . . . 104 IV.9 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .109 V Valeurs et Vecteurs Propres . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .113 V.1 La condition du calcul des valeurs propres . . . . . . . . . . . .. . . . . . . . 114 V.2 La m´ethode de la puissance . . . . . . . . . . . . . . . . . . . . . . . . .. . . 118 V.3 Transformation sous forme de Hessenberg (ou tridiagonale) . . . . . . . . . . . 119 V.4 M´ethode de bissection pour des matrices tridiagonales. . . . . . . . . . . . . . 121 V.5 L"it´eration orthogonale . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 124 V.6 L" algorithme QR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .126 V.7 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 VI M ´ethodes It´eratives - Equations Non Lin´eaires . . . . . . . . . . . . . . . . . . . .134 VI.1 M´ethode des approximations successives . . . . . . . . . . .. . . . . . . . . . 134

VI.2 M´ethodes it´eratives pour syst`emes lin´eaires . . . .. . . . . . . . . . . . . . . . 136

VI.3 M´ethode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 138 VI.4 M´ethode de Gauss-Newton . . . . . . . . . . . . . . . . . . . . . . . . .. . . 141 VI.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .146 VII Travaux Pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .147 VII.1 Introduction au FORTRAN 90 . . . . . . . . . . . . . . . . . . . . . . .. . . . 147 VII.2 Int´egration par la r`egle du Trap`eze et Simpson . . . .. . . . . . . . . . . . . . 148 VII.3 Calcul de racines par la m´ethode de la bissection . . . .. . . . . . . . . . . . . 149 VII.4 Wegral: programme d"int´egration d"ordre 8 . . . . . . . .. . . . . . . . . . . . 149 VII.5 Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 151 VII.6 Interpolation et erreur . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 152

VII.7 R´esolution d"´equations diff´erentielles et calcul de la trajectoire des plan`etes . . . 154

VII.8 D´ecomposition LR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 156

VII.9 D´ecomposition QR et trajectoire d"un ast´ero¨ıde . .. . . . . . . . . . . . . . . . 157

VII.10 FORTRAN 90/95 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .160

Avant-propos

(2heures par semaine) donn´e en 2004/2005. Elle est une version corrig´ee et modifi´ee des poly-

copi´es distribu´es en 1991/92 et en 2000/2001. Durant des ann´ees, ce cours a ´et´e donn´e alternative-

ment par les auteurs. En ce lieu, nous aimerions remercier Laurent Jay, Luc Rey-Bellet, St´ephane Cirilli, Pierre Leone, Assyr Abdulle, Michael Hauth, Martin Hairer et des nombreux assistants et ´etudiants soit

pour leur aide dans la pr´eparation des exercices soit pour la correction des erreurs (typographiques

et math´ematiques). OEuvres g´en´erales sur l"analyse num´erique

Il y a un grand assortiment de livres qui introduisent le sujet d"analyse num´erique (voir le rayon

65 `a la biblioth`eque de la section de math´ematiques avec plus de 400 livres). En voici quelques

ref´erences. Les num´eros entre chrochets (p. ex. [MA 65/403]) vous permettent de trouver le livre

facilement `a la biblioth`eque. K.E. Atkinson (1978):An Introduction to Numerical Analysis.John Wiley & Sons. [MA 65/142] W. Boehm & H. Pautzsch (1993):Numerical Methods.AK Peters. [Ma 65/332] G. Dahlquist & A. Bj¨orck (1969):Numeriska Metoder.CWK Gleerup, Bokfoerlag, Lund, Sweden. Traduc- tion anglaise:Numerical Methods.Prentice-Hall, 1974. [MA 65/84]

P. Deuflhard & A. Hohmann (1993):Numerische Mathematik I. Eine algorithmisch orientierte Einf¨uhrung.

Walter de Gruyter & Co. Traduction anglaise:Numerical analysis. A first course in scientific computation.Walter de Gruyter & Co., 1995. [MA 65/301, MA 65/309] G. Evans (1995):Practical Numerical Analysis.John Wiley & Sons. [MA 65/374] W. Gautschi (1997):Numerical Analysis. An Introduction.Birkh¨auser. [MA 65/393] G. H¨ammerlin & K.-H. Hoffmann (1991):Numerische Mathematik.Zweite Auflage. Springer. [MA 65/303] M.J. Maron (1982):Numerical analysis: a practical approach.Macmillan. W.H. Press, B.P. Flannery, S.A. Teukolsky & W.T. Vetterling(1986):Numerical Recipes (FORTRAN). The Art of Scientific Computing.Cambridge Univ. Press. [MA 65/239]

J. Rappaz & M. Picasso (1998):Introduction`a l"analyse num´erique.Presses polytechniques et universitaires

romandes. [MA 65/404] A. Quarteroni, R. Sacco & F. Saleri (2000):Numerical Mathematics.Springer. [MA 65/432]

M.Schatzman (1991):Analyse num´erique:cours etexercices pour lalicence.Paris:InterEditions. [MAE188]

H.R. Schwarz (1986):Numerische Mathematik.B.G. Teubner. [MA 65/249] G.W. Stewart (1996):Afternotes on Numerical Analysis.SIAM. [MA 65/389]

J. Stoer & R. Bulirsch (1972):Einf¨uhrung in die Numerische Mathematik.Heidelberger Taschenb¨ucher,

Springer. Traduction anglaise:Introduction to Numerical Analysis.Springer, 1980. [MA 65/48] Ch. ¨Uberhuber (1995):Computer-Numerik 1 und 2.Springer.

Chapitre IInt´egration Num´erique

Pour ses calculs en physique et en astronomie, Newton est le premier `a utiliser des formules de quadrature, suivi en cela par ses successeurs anglais (Cotes 1711, Simpson 1743). Euler, dans son gigantesque trait´e (Inst. Calculi Integralis1768, 1769, 1770, Opera XI-XIii), met toute son

ing´eniosit´e `a rechercher des primitives analytiques. Cependant, de nombreuses int´egrales r´esistent

encore et toujours `a l"envahisseur (exemples?ex xdx,?dxlogx); de nombreux calculs en astronomie

(perturbations des orbites plan´etaires) contraignent Gauss (1814) `a intensifier la th´eorie des for-

mules de quadrature. Les programmes qui ont tourn´e sur les premiers ordinateurs furent en grande

partie les calculs d"int´egrales: ces probl`emes sont les plus faciles `a programmer. Pour cette mˆeme

raison, nous commenc¸ons par ce sujet. Probl `eme.Etant donn´e une fonction continue sur un intervalle born´e f: [a,b]→IR,(0.1) on cherche `a calculer l"int´egrale ?b af(x)dx.(0.2)

Bibliographie sur ce chapitre

P.J. Davis & P. Rabinowitz (1975):Methods of Numerical Integration.Academic Press, New York. G. Evans (1993):Practical Numerical Integration.John Wiley & Sons. [MA 65/336] V.I. Krylov (1959):Priblizhennoe Vychislenie Integralov. Goz. Izd. Fiz.-Mat. Lit., Moscow. Tra- ductionanglaise:Approximatecalculationofintegrals.Macmillan,1962.[MA 65/185]

R. Piessens, E. de Doncker-Kapenga, C.W.

¨Uberhuber & D.K. Kahaner (1983): QUADPACK.

A Subroutine Package for Automatic Integration.Springer Series in Comput. Math., vol. 1. [MA 65/210] [MA 65/89]

I.1 Formules de quadrature et leur ordre

La plupart des algorithmes num´eriques proc`edent comme suit: on subdivise[a,b]en plusieurs sous-intervalles (a=x0< x1< x2< ... < xN=b) et on utilise le fait que b af(x)dx=N-1? j=0? xj+1 x jf(x)dx.(1.1)

2Int´egration Num´erique

FIG. I.1:Une division d"un intervalle en sous-intervalles

De cette mani`ere, on est ramen´e au calcul de plusieurs int´egrales pour lesquelles la longueur de

l"intervalled"int´egrationestrelativementpetite. Prenons unedeces int´egralesetnotonslalongueur

de l"intervalle parhj:=xj+1-xj. Un changement de variable nous donne alors xj+1 x jf(x)dx=hj? 1

0f(xj+thj)dt.

Notons enfing(t) :=f(xj+thj). Il reste alors `a calculer une approximation de 1

0g(t)dt.(1.2)

Exemples.1. Laformule du point milieu?1

0g(t)dt≈g(1/2).

0 1 2

2. Laformule du trap`eze?1

0g(t)dt≈1

2?g(0) +g(1)?.0 1 2

3. On obtient laformule de Simpsonsi l"on passe une parabole (polynˆome de degr´e2) par les

trois points(0,g(0)),(1/2,g(1/2)),(1,g(1))et si l"on approche l"int´egrale (1.2) par l"aire sous la parabole:?1

0g(t)dt≈1

6?g(0) + 4g(1/2) +g(1)?.0 1 2

4. La “pulcherrima et utilissima regula"de Newton(degr´e3) :?1

0g(t)dt≈1

8?g(0) + 3g(1/3) + 3g(2/3) +g(1)?.0 1 2

5. En g´en´eralisant cette id´ee (passer un polynˆome de degr´es-1par lesspoints ´equidistants

(i/(s-1),g(i/(s-1))),i= 0,...,s-1), on obtient lesformules de Newton-Cotes(Newton 1676, dessin en figure I.2 montre que les poids “explosent" au-del`a des= 10. Si on veut augmenter la pr´ecision, il vaut mieux raffiner les subdivisions en (1.1)qu"augmenter le degr´es. D ´efinition 1.1Une formule de quadrature`as´etages est donn´ee par 1

0g(t)dt≈s?

i=1b ig(ci).(1.3) Lescisont les noeuds de la formule de quadrature et lesbien sont les poids.

Int´egration Num´erique3

TAB. I.1: Formules de Newton-Cotes

sordrepoidsbinom 221

212trap`eze

3 41

64616Simpson

4 41

8383818Newton

5 67

90329012903290790Boole

quotesdbs_dbs7.pdfusesText_13

[PDF] taux de pénetration d'un produit calcul

[PDF] taux de pénetration assurance

[PDF] comment calculer le taux de saturation du marché

[PDF] taux de pénetration économie

[PDF] calcul part de marché marketing

[PDF] taux de saturation définition

[PDF] matrice mc kinsey exercice corrigé pdf

[PDF] matrice bcg 2 pdf

[PDF] matrice bcg exercice corrigé pdf

[PDF] matrice mckinsey cas pratique

[PDF] exercice d'application matrice bcg

[PDF] matrice mc kinsey pdf

[PDF] matrice bcg cas pratique

[PDF] etude de cas matrice bcg

[PDF] rendement système vis écrou