Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

09/10/2022 1 Introduction aux méthodes numériques DOUIMI Mohammed École Nationa

09/10/2022 1 Introduction aux méthodes numériques DOUIMI Mohammed École Nationale Supérieure d’Arts et Métiers - Meknès Quel est le rôle du calcul scientifique ? Alors, il faut résoudre l’équation du pendule : Situation (t) l m À t=0, on a : (0)= 0 et ’(0)=v Problème : Déterminer (t) avec t[0, T] ? ’’(t)+w2sin((t))=0 (0)= 0 et ’(0)=v Calcul scientifique Calcul formel (calcul analytique) Calcul numérique (calcul sur ordinateur) résoudre Modélisation 09/10/2022 2 Calcul formel 2 2 3 1 2 1 2      dx x x ) 5 exp( ) sin( Le calcul formel manipule des symboles (des opérateurs avec une précision infinie) et on doit disposer d’un papier, d’un crayon, des méthodes et sa tête Exemples   3 2 ) cos( ) sin( xy y x y x x     Des logiciels capable de faire du calcul formel ont été développés ces dernières années : Matematica, Maple, … Exercice sur le calcul formel Remarques Le calcul formel nécessite le développement des méthodes de calcul qui manipulent des symboles Calcul numérique Le calcul numérique utilise l’ordinateur (outil centrale et nécessaire), un langage interprétable par l’ordinateur et les algorithmes Exemples Écrire un programme qui calcule 115 Écrire un programme qui calcule sin(x) Remarques Le calcul numérique nécessite le développement des méthodes de calcul qui peuvent être automatisées Des logiciels de calcul numérique ont été développés ces 30 dernières années : Matlab, Scilab, Nag, … Exercice sur le calcul numérique 09/10/2022 3 Pourquoi le calcul numérique ? ’’(t)+w2 sin((t))=0 (0)= 0 et ’(0)=v Le problème : admet une solution unique d’après le théorème de Cauchy-Lipschitz Comment calculer la solution de ce problème ? Si (t) est petit pour t [0, T], on a sin((t)) ≈ (t) D’où le problème devient ’’(t)+w2 (t)=0 (0)= 0 et ’(0)=v admet (t)= 0 cos(wt) + (v/w) sin(wt) comme solution analytique On ne sait pas calculer sous forme analytique (formel) la solution Pour (t) est grand, il n’y a pas de méthodes analytiques. Il faut donc essayer de résoudre le problème par la voie numérique Comparaison : calcul formel et calcul numérique ? Calcul formel Calcul numérique Avantage Inconvénient Donne une solution exacte L’éventail des pbs résolus est très réduit L’éventail des pbs est très large La solution est approchée 09/10/2022 4 C’est quoi l’analyse numérique (AN) ? Définition générale : L’AN est le domaine des mathématiques qui a pour mission première la définition et l’élaboration des processus qui permettent de résoudre des pbs mathématiques par la seule voie numérique Définition mathématique : La mathématique de l’AN est le domaine des maths qui a pour mission : 1. L’étude des conditions d’existence et d’unicité de la solution du pb 2. La construction d’algorithme 3. L’analyse des erreurs incluant la troncature et les erreurs d’arrondis 4. L’étude de la convergence, incluant la vitesse de convergence 5. La comparaison de différents algorithmes dans des situations différentes Quel est le rôle de l’ordinateur ? L’ordinateur est un outil de calcul de plus en plus rapide et nécessite la maîtrise d’un langage interprétable par la machine (par exemple : Langage C, Fortran, Pascal, Matlab, Java, etc) Le nombre et le calcul sont aussi vieux que l’humanité : Histoire UN OS Les opérations arithmétiques mis en jeu sur ordinateur ne sont qu’une approximation des opérateurs mathématiques et c’est de là que provient la différence fondamentale entre le calcul algébrique et le calcul numérique sur ordinateur Que signifie « calcul » ? ! calcul 09/10/2022 5 Représentation des nombres en machine (1/2) Problème 1 : La représentation d’un nombre n’est pas unique En effet, il peut être représenté différemment selon la base de numérotation choisie Exemple : x10 = 425.33 dans la base 10 x6 = 425.33 = 4 62 + 2 61 + 5 60 + 3 6-1 + 3 6-2 Il s’agit de 161.583 dans la base 10 _ Toutes les bases sont équivalentes, d’où la non unicité de la représentation ne pose pas de problème Les ordinateurs utilisent en général la base 2, exceptés certains qui emploient la base 16 (hexadécimal) Représentation des nombres en machine (2/2) Problème 2 : non unicité de l’écriture d’un nombre xIR Exemple : x = 123.45 = 0.12345 103 = 1.2345 10-2 = 12345 10-3 Conséquence : Il va falloir définir un système de représentation standard Soit IN une base fixée avec ≥ 2 et soit x IR comportant un nombre fini de chiffres Le système de représentation en virgule flottante normalisée x= (-1)s 0.a1a2a3 ... at x e avec a1 ≠ 0 et 0 ≤ ak < pour k=1, 2, … , t = (-1)s (ak t-k) e-t k=1 t = (-1)s m e-t s= 0 si x ≥ 0 1 sinon m est la mantisse qui vérifie 0 ≤ m ≤ t - 1 t est le nombre de chiffres significatifs e ]L, U[ est l’exposant avec L < 0 et U > 0 09/10/2022 6 Comment l’ordinateur représente les nombres ? Pour stocker un nombre, l’ordinateur utilise des cases de mémoires (bits) Il y a deux formats disponibles pour les nombres à virgule flottante : La représentation en simple précision (32 bits) s e m 1 bit 8 bits 23 bits La représentation en double précision (64 bits) s e m 1 bit 11 bits 52 bits Format Taille Précision L U Valeur max Simple 32 23bits+1 -126 +127 3,403 … 1038 Double 64 52bits+1 -1022 +1023 1,798 … 10308 Quadruple 128 112bits+1 -16382 +16383 1,190 … 107932 Comment l’ordinateur représente les nombres ? Exemple : Imaginons un ordinateur fictif utilisant la base 10 et la représentation suivante  signe Exposant +50 mantisse Représenter = 3.141592123 et la charge électron -1.59 10-19  + 5 1 3 1 4 5 9 2 3.141592123 ≈ Charge électron - 3 2 1 5 9 0 0 0 = 1 0 09/10/2022 7 Exemples de représentation en format simple Type exposant Mantisse Valeur approchée zéro 0000 0000 000 0000 0000 0000 0000 0000 0,0 PPND 0000 0000 000 0000 0000 0000 0000 0001 1,4×10-45 AND 0000 0000 100 0000 0000 0000 0000 0000 5,9 ×ௗ10−39 PGDN 0000 0000 111 1111 1111 1111 1111 1111 1,175 494 21 ×ௗ10−38 PPNN 0000 0001 000 0000 0000 0000 0000 0000 1,175 494 35 ×ௗ10−38 ANN 0000 0001 111 1111 1111 1111 1111 1111 2,350 988 56 ×ௗ10−38 1 0111 1110 111 1111 1111 1111 1111 1111 0,999 999 94 1 0111 1111 000 0000 0000 0000 0000 0000 1,000 000 00 NS 1 0111 1111 000 0000 0000 0000 0000 0001 1,000 000 12 max 1111 1110 111 1111 1111 1111 1111 1110 3,402 823 26 ×ௗ1038 max 1111 1110 111 1111 1111 1111 1111 1111 3,402 823 46 ×ௗ1038  1111 1111 000 0000 0000 0000 0000 0000 infini NaN 1111 1111 0 Not a Number Conséquences de l’opération de stockage L’ordinateur est incapable de représenter tous les nombres réels. L’ensemble IR est remplacé par : IF(, t, L, U) = {0}{x IR / x = (-1)s e ak -k avec a1 ≠ 0} K=1 t On a donc : xmin = L-1 ≤ |x| ≤ xmax = U(1- -t) x IF(, t, L, U) Et card IF(, t, L, U) = 2(-1) t-1 (U-L+1) + 1 Remarque Dans la passé, IF était spécifique à chaque type d’ordinateur mais à partir de 1985 un standard a été établi par IEEE. Ainsi : • Pour la simple précision : IF(2, 24, -127, 128) • Pour la double précision : IF(2, 53, -1023, 1024) L’ensemble IR (infini, non dénombrable et non borné) est remplacé par un ensemble IF (fini et borné) 09/10/2022 8 Opérations machines en virgule flottante (1/3) Vu que IF(, t, L, U) est inclus strictement dans IR, cela pose plusieurs problèmes pratiques • Erreur d’arrondi si |x| ]xmin, xmax[ alors pour présenter x dans IF il faut l’arrondir c-à-d remplacer x par Fl(x) avec Fl(x) = (-1)s 0.a1a2 ….. at-1at at = at si at+1 < /2 at +1 si at+1 ≥/2 si x ]xmin, xmax[ alors Fl(x) n’est pas définie La définition de Fl(x) découle de la propriété : d(x, Fl(x)) ≤ d(x,y) y IF(, t, L, U) Exemple : Fl(1./3.), Fl(0.123456789) Exemple : Fl(exp(1000.)) Soit x IR ~ ~ Opérations machines en virgule flottante (2/3) • Opérations machines Il est nécessaire de définir sur IF une arithmétique autant que possible analogue à l’arithmétique de IR. Désignons par l’+, l’-, la x ou la / On a : IR x IR IR (x, y) xy : IR x IR IF x y = Fl(Fl(x)Fl(y)) (x, y)  On note par l’opération machine Conserve la cummutativité de la somme ou du produit mais l’associativité de la somme est perdue Faire la + exacte et machine des nombres 0.123456789 ,0.987698765 Calcul exact : 0.123456789 + 0.987698765 = 1.111155554 Calcul machine : 0.123456789 + 0.987698765 =0.1234568 + 0.9876988 =1.1111556 (erreur commise est 0.14 10-6) Exemple : 09/10/2022 9 Opérations machines en virgule flottante (3/3) Exemple de la non associativité uploads/s3/ cmn-3a-imn-ensam2223.pdf