Ecole Centrale de Nantes D´ept. Info/Math Ann´ee universitaire 2011-2012 EI 1 ANALYSE NUMERIQUE Mazen SAAD [email protected] i ii ` TABLE DES MATIERES Introduction....................................................................... 1 1. Alg`ebre lin´eaire................................................................ 3 1.1. Arithm´etique flottante........................................................ 3 1.2. Un peu de calcul matriciel.................................................... 6 2. R´esolution des grands syst`emes lin´eaires creux............................. 9 2.1. Exemple 1. Equation de la chaleur............................................ 9 2.2. Exemple 2. Probl`emes de r´eseaux............................................. 12 2.3. Graphe associ´e `a une matrice et inversement.................................. 13 2.4. Les matrices irr´eductibles..................................................... 15 2.5. Localisation des valeurs propres............................................... 16 2.6. M´ethodes directes pour la r´esolution de syst`emes lin´eaires..................... 20 3. M´ethodes it´eratives............................................................ 25 3.1. M´ethodes it´eratives classiques................................................. 27 3.2. M´ethodes de gradients........................................................ 29 3.3. Calcul de valeurs propres et de vecteurs propres............................... 30 4. Interpolation et Approximation.............................................. 37 4.1. Introduction.................................................................. 37 4.2. Interpolation de Lagrange..................................................... 38 4.3. Polynˆome d’interpolation de Newton.......................................... 41 4.4. Interpolation de Hermite...................................................... 42 4.5. Interpolation locale........................................................... 44 4.6. Meilleure approximation (projection orthogonale)............................. 45 4.7. Polynˆomes orthogonaux....................................................... 47 4.8. Approximation au sens des moindres carr´es discrets........................... 48 5. Int´egration num´erique......................................................... 51 5.1. M´ethode composite........................................................... 51 5.2. Formulation de quadrature de type interpolation.............................. 52 iv TABLE DES MATIE`RES 5.3. Formule d’int´egration classique............................................... 52 5.4. Les formule de Gauss......................................................... 55 5.5. Int´egration num´erique d’une fonction en 2D................................... 57 6. R´esolution num´eriques des edo............................................... 61 6.1. Le probl`eme de Cauchy....................................................... 61 6.2. Approximation num´erique des ´equations diff´erentielles d’ordre 1............... 62 6.3. Sch´emas classiques............................................................ 63 6.4. Etude des m´ethodes `a un pas................................................. 65 6.5. M´ethodes `a pas multiple...................................................... 69 7. Travaux Dirig´es................................................................ 71 7.1. Syst`emes lin´eaires creux...................................................... 71 7.2. M´ethodes it´eratives .......................................................... 75 7.3. Interpolation et approximation................................................ 77 7.4. Int´egration num´erique........................................................ 79 7.5. Equations diff´erentielles....................................................... 82 7.6. TA – 2007 avec correction.................................................... 86 7.7. TA-2008...................................................................... 93 8. Devoir surveill´e d’Analyse Num´erique (2010) et son corrig´e.............. 97 Exercice 1......................................................................... 97 Exercice 2......................................................................... 97 Exercice 3......................................................................... 99 Corrig´e exercice 1.................................................................100 Corrig´e exercice 2.................................................................101 Corrig´e exercice 3.................................................................104 9. Devoir surveill´e d’Analyse Num´erique (2011)..............................107 Exercice 1.........................................................................107 Exercice 2.........................................................................107 Exercice 3.........................................................................108 10. Travaux sur ordinateur Initiation `a Matlab...........................................................111 10.1. La commande;..............................................................112 10.2. Variables sp´eciales...........................................................112 10.3. Nombres complexes..........................................................113 10.4. Affichage....................................................................114 10.5. Les commentaires............................................................114 10.6. Vecteurs - Matrices..........................................................114 10.7. Cr´eation de matrices.........................................................117 10.8. Op´erations sur les matrices..................................................117 10.9. M-Files ou scripts...........................................................118 10.10. Fonctions...................................................................119 TABLE DES MATIE`RES v 10.11. HELP......................................................................120 10.12. Boucles et contrˆole .........................................................120 10.13. Graphismes................................................................121 10.14. tic toc......................................................................122 10.15. Fonctions math´ematiques...................................................122 11. Travaux sur ordinateur Equation de la chaleur en 1D...............................................123 11.1. Equation de la chaleur.......................................................123 11.2. Flambage d’une barre (facultatif) ...........................................127 Bibliographie......................................................................129 INTRODUCTION Les math´ematiques appliqu´ees et le calcul scientifique jouent un rˆole croissant dans la conception de produits industriels; ce n’est cependant qu’un maillon d’une longue chaˆıne qui mobilise des ressources intellectuelles nombreuses et vari´ees pour arriver `aconcevoir, au mieux dans des d´elais impartis le produit d´esir´e. On peutrepr´esenter tr`es sch´ematiquement un processus d’´etude et de conception par le diagramme suivant : Physique m´ecanique, mod´elisation m´ecanique (a´erodynamique, thermique, structure, • ...) Mod´elisation math´ematique (E.D.P.) • Approximation : El´ements finis, volumes finis... • Algorithme num´erique, m´ethodes num´eriques pour la r´esolution de syst`emes lin´eaires • et non lin´eaires, optimisation Calcul informatique ... • Exp´erimentation • Exploitation des produits • La mod´elisation et l’approximation num´erique voient leurs applications dans diff´erents domaines, `a titre d’exemples : Conception d’avions (a´erodynamique, mat´eriaux composites ...) • Conception de voitures (a´erodynamique, ´ecoulement dans les moteurs, crache tests, • commande optimale, structure (pneus, carrosserie, ) .... Ing´enierie p´etroli`ere : comprendre la migration des hydrocarbures, am´eliorer la pro- • duction des gisements p´etroliers, .... Biologie math´ematiques : propagation d’´epid´emie, mod`ele math´ematique en cardio- • logie, cancer, tissus dentaire, pneumologie, ... Gestion des stocks, finance, trafic routier • Environnement : pollution air, eau, sol • M´et´eo : mod´eliser le monde • Et bien d’autres applications ... • 2 INTRODUCTION Dansce cours, nous nousint´eressons `a l’analyse num´erique; cette discipline elle-mˆeme peut ˆetre consid´er´ee comme partag´ee en deux grands th`emes : Approximation num´erique des EDP (El´ements finis, volumes finis, m´ethodes spec- • trales, ...) Algorithmes num´eriques : r´esolution de grands syst`emes lin´eaires creux, int´egration • num´erique, r´esolution num´erique des EDO, optimisation L’objet de ce cours est de d´eterminer des m´ethodes pour calculer la valeur num´erique (exacte ou approch´ee) de la solution d’une ´equation ou d’un syst`eme d’´equations; en par- ticulier `a l’aide d’un ordinateur. CHAPITRE 1 ` ´ ALGEBRE LINEAIRE 1.1. Arithm´etique flottante Il est important de se pr´eoccuper de la mani`ere dont sont repr´esent´es et manipul´es les nombres dans une machine. Un nombre est repr´esent´e par un nombre finis de caract`eres, fix´e `a l’avance, qui d´epend de l’architecture de la machine. Ainsi tous les nombres entiers ou r´eels ne peuvent pas ˆetre repr´esent´es. Les cons´equences en sont tr`es importantes, en particulier dans la pr´ecision des r´esultats lors de calculs. Comment sont repr´esent´es et manipul´es les nombres sur un ordinateur? La m´emoire centrale est un ensemble de ’positions binaires’ nomm´ees bits. Les bits sont g´en´eralement regroup´esenoctets(8bits)etchaqueoctetestrep´er´eparsonadresse.Chaque information devra ˆetre cod´ee sous cette forme binaire. En informatique, le kilo vaut 1K = 210 = 1024 le m´ega vaut 1M = 220 = 1048576 le giga vaut 1G = 230 = 1073741824 On distingue : –Les nombres entiersdontlarepr´esentationetlamanipulationsontcellesdel’arithm´etique usuel. Il existe un plus grand entier repr´esent´e en machine. Les entiers relatifs cod´es sur n chiffres binaires ont pour valeur dans [ 2n 1,2n 1 1]. − − − − Ainsi les entiers cod´es sur 16 bits (=2 octets) correspond `a des entiers en simple pr´ecision ont pour valeur dans [ 215,215 1] = [ 32K,32K 1] − − − − 32 bits (=4 octets) correspond `a des entiers en double pr´ecision ont pour valeur dans [ 231,231 1] = [ 2G,2G 1]. − − − − 4 CHAPITRE 1. ALGE`BRE LINE´AIRE – Les nombres flottants qui repr´esentent les nombres r´eels ou les nombres d´ecimaux. Les nombres r´eels sont repr´esent´es de fac¸on approximative en m´emoire (repr´esentation en virgule flottante), avec la convention standardis´ee de la forme m 2e, ou` m est la mantisse × 1 m 2 et e l’exposant. ≤ ≤ On utilise p chiffres binaires pour les d´ecimaux binaires de m et q chiffres binaires pour l’exposant. Repr´esentation en simple pr´ecision. Sur 32 bits (4 octets), on a p = 23, q = 8 (1 bit pour le signe) ce qui permet de repr´esenter des nombres compris, en valeur absolue, entre 2 128 10 38 et 2128 1038 car 128 = 2q = 28. La pr´ecision machine est de 7 chiffres − − ≈ ≈ d´ecimaux significatifs car 223 = 107. Repr´esentation en double pr´ecision. Sur 64 bits (8 octets), on a p = 52, q = 11 et les r´eels en valeur absolue appartiennent [2 1024,21024] [10 308,10308] avec 15 chiffres − − ≈ d´ecimaux significatifs (car 252 1015). ≈ La repr´esentation exacte en machine est sous forme binaire (comme on a vu), pour l’ana- lyse que nous voulons faire ici une repr´esentation d´ecimale est suffisante et plus intuitive. On consid`ere un nombre flottant de la forme a10q avec ± a est la mantisse de la forme 0.d d d , d = 0 1 2 t 1 ··· 6 q est l’exposant (entier relatif) Bien suˆr, l’entier q est soumis `a la restriction : M q M (ou` M d´epend de la machine). − ≤ ≤ Cette repr´esentation des nombres r´eels entraˆıne les cons´equences suivantes : Il existe un plus petit nombre flottant (= z´ero). Le z´ero machine en valeur absolue • 6 vaut = 0.10 10 M. − ··· Il existe un plus grand nombre flottant, l’infinie machine vaut = 0.99 910M. • ··· Tous les nombres r´eels n’admettent de repr´esentation exacte : • √2 est repr´esent´e par 0.14142143 10+1 × π est repr´esent´e par 0.314... 10+1 × Toute op´eration ´el´ementaire (+, , /) est en g´en´eral entach´ee d’une erreur. • ∗ Une op´eration peut avoir un r´esultat non repr´esentable : • Si pour le r´esultat q > M (OVERFLOW ou d´epassement de capacit´e.) Si pour le r´esultat q < M (UNDERFLOW). − Larepr´esentationflottanted’unnombrepeutˆetreobtenue`apartirdesarepr´esentation • d´ecimale par – la troncature (on garde les t premiers d´ecimaux) – l’arrondi : le ti`eme chiffre de la mantisse est choisi au plus pr`es.