Remerciez-le!

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

Chapitre 1 Représentation des nombres sur ordinateur ENSAM-Meknès Université Mo

Chapitre 1 Représentation des nombres sur ordinateur ENSAM-Meknès Université Moulay Ismail - Meknès 2018/2019 Maths-Info (ENSAM) CMN 1 / 51 1 Introduction 2 Représentation des nombres sur ordinateur 3 Arithmétique ﬂottante Maths-Info (ENSAM) CMN 2 / 51 Introduction Analyse numérique L ’Analyse Numérique est une spécialité "récente" des mathématiques. Elle s’est développée avec l’apparition des ordinateurs. Son objet essentiel est d’écrire les programmes permettant d’effectuer les opérations nécessaires pour résoudre numériquement un problème donné. Les méthodes ont un "coût", lié d’une part au temps de calcul, c’est à dire au nombre d’opérations élémentaires (additions, soustractions, multiplications et divisions) à faire, et d’autre part à l’espace mémoire nécessaire pour stocker les données et les résultats. L ’ordinateur ne fait pas de calculs exacts (à cause du mode de représentation des nombres). Ceci constitue un inconvénient car cela provoque des erreurs d’arrondis et de troncature. Maths-Info (ENSAM) CMN 3 / 51 Introduction Analyse numérique 23 août 1991, Gandsfjorden, Norvège Une plate-forme de forage de plus de cent mille tonnes coule suite à la rupture de la paroi des ballasts, provoquant un séisme de magnitude 3 sur l’échelle de Richter; le coût de la plate-forme est estimé à 700 millions de dollars. Les experts remontent les causes de la catastrophe jusqu’au logiciel de calcul des éléments ﬁnis utilisé pour le dessin des ballasts. Une approximation de calcul dans ce logiciel a conduit à une sous-estimation de la taille des parois du balast de 47%. Compte-tenu de cette sous-estimation, les experts estiment la rupture probable à partir de 62 m de profondeur. La catastrophe s’est produite à une profondeur de 65 m. Maths-Info (ENSAM) CMN 4 / 51 Introduction Analyse numérique 25 février 1991, Dahran, Arabie Saoudite Un missile Scud irakien détruit un baraquement américain; 28 morts et 100 blessés. En raison d’une erreur d’arrondi sur le calcul du temps (au 24ème bit), la batterie de missiles "Patriot" supposée protéger la base déviait de 0,34 secondes. La vitesse d’un Scud étant de 1676 m/s, l’erreur commise sur la position était donc de plus de 500 m. Cette distance est sufﬁsante pour que le missile Scud soit hors de la "fenêtre d’interception" que le missile Patriot poursuivait. Aucun missile anti-Scud n’a été lancé. Le bug avait été détecté le 11 février. Le correctif est arrivé à Dahran le 26. Maths-Info (ENSAM) CMN 5 / 51 Introduction Analyse numérique 4 juin 1996, Kourou, Guyane Française Après 39 secondes de vol, la fusée Ariane 5 s’auto-détruit avec son chargement (coût estimé : 500 millions de dollars). La commission d’enquête a rendu son rapport au bout de deux semaines. L ’autodestruction a été provoquée suite à une correction de l’angle de vol après qu’une vitesse horizontale importante ait été signalée par le Système de Référence Inertielle (SRI). En pratique, la vitesse était normale mais une conversion de "double" (ﬂoating point, 64 bits) en "short" (integer, 16 bits) avait provoquée un dépassement de capacité. Maths-Info (ENSAM) CMN 6 / 51 Introduction Analyse numérique Pour un grand nombre de problèmes, le seul moyen de calculer la solution, si elle existe, est de l’approcher numériquement. Un algorithme c’est une démarche pour obtenir une solution (impliquant des simpliﬁcations, ajout/retrait d’hypothèses sur le modèle, etc) l’implémentation sur ordinateur de cette démarche. Objectifs de l’analyse numérique : proposer et développer des algorithmes (méthodes d’approximation) pour calculer une solution approchée, contrôler les diverses sources d’erreurs, propres à l’approximation numérique, évaluer la pertinence et la valeur de différents algorithmes (estimer leurs performances) pouvant être utilisés pour résoudre le même problème aﬁn de sélectionner les meilleurs . Maths-Info (ENSAM) CMN 7 / 51 Introduction Analyse numérique Quelques problèmes typiques Interpolation - Extrapolation. Résolution de systèmes linéaires. Résolution de systèmes non-linéaires. Intégration et différentiation numérique. Résolution de systèmes d’équations différentielles. Résolution de systèmes d’EDP . Analyse statistique. Transformée de Fourier. Diagonalisation. Calcul de valeurs propres. item Calcul de vecteurs propres. . . . Maths-Info (ENSAM) CMN 8 / 51 Introduction Analyse numérique Langages de programmation Fortran : Idéal pour le calcul intensif. C : le plus proche du "hardware". IDL : Courant en astrophysique. Java : Indépendant de la machine (portabilité). Shell : Scripting de base. Autre : C++, python, Mathematica, etc . . . . A choisir en fonction de la tache à réaliser, et non en fonction des habitudes. Maths-Info (ENSAM) CMN 9 / 51 Introduction Sources d’erreurs Qu’est-ce qu’un bon algorithme? Aﬁn de choisir le meilleur algorithme possible, il faut pouvoir les comparer. Un bon algorithme est : le moins coûteux possible en place mémoire, le moins coûteux possible en temps de calcul : c’est-à-dire qui minimise le nombre d’opérations nécessaires. C’est ce qu’on appelle un problème de complexité. le plus stable possible, ie le moins sensible aux erreurs d’arrondi que nous venons d’évoquer, le plus précis possible : la solution approchée obtenue est-elle proche ou loin de la solution exacte. C’est ce qu’on appelle l’estimation d’erreur. Maths-Info (ENSAM) CMN 10 / 51 Introduction Sources d’erreurs Exemple : Calcul du déterminant d’une matrice N × N La méthode mathématique de Cramer nécessite N × N! opérations élémentaires (N! additions et (N −1) × N! multiplications). Prenons N = 50, sachant que 50 × 50! = 15.1065, et qu’un ordinateur peut faire environ 20 GFlops (ie 20 milliards d’opérations à la seconde), il faudrait quand même environ 1050 ans pour faire ce calcul. Maths-Info (ENSAM) CMN 11 / 51 Introduction Sources d’erreurs Les quatre principales sources d’erreurs : erreurs de modélisation, erreurs sur les données, erreurs dues à la représentation des nombres sur ordinateur, erreurs de troncature ou de discrétisation. Exemple 1 Soit la suite déﬁnie par : xn+1 = 4xn(1 −xn) On peut la programmer de deux façons : x1 = 4 ∗x1 ∗(1.0 −x1); x2 = 4 ∗x2 −4 ∗x2 ∗x2 ; "Normalement", on doit trouver la même chose "mathématiquement", mais les opérations ne sont pas faites dans le même ordre en machine. Maths-Info (ENSAM) CMN 12 / 51 Introduction Sources d’erreurs Exemple 2 Soit à résoudre l’équation : x2 + 2bx −1 = 0 Où b peut être "très grand". On demande de calculer la solution positive : x+ = −b + √ b2 + 1 Comment faut-il la programmer? La aussi, deux possibilités : x = −b + √ b ∗b + 1.0; x = 1.0 b+ √ b∗b+1. Équivalentes mathématiquement. Maths-Info (ENSAM) CMN 13 / 51 Introduction Sources d’erreurs Exemple 3 Soit à calculer, pour n ﬁxé : Sn = Pn i=1 1 i Il y a (au moins) deux façons d’écrire la boucle : for (i=1; i<=n; i++) x = x + 1.0/i; for (i=n; i>=1; i–) x = x + 1.0/i; Sans oublier d’initialiser x à 0 évidemment. Ici aussi les mathématiques sont équivalentes. Maths-Info (ENSAM) CMN 14 / 51 Introduction Erreurs de modélisation La modélisation c’est : L ’identiﬁcation des différents facteurs agissant dans le phénomène (physique, biologique, économique , etc) à l’étude. L ’identiﬁcation et réprésentation mathématique des relations entre les facteurs : écriture des “formules/équations” représentants ces relations. Les erreurs de modélisation peuvent provenir de l’étape de "mathématisation" i.e. simpliﬁcation ou mauvaise description de la relation entre différents facteurs lors de la mise en équations pour réduire le degré de complexité d’un phénomème physique, on est souvent amené à simpliﬁer le système d’équations, ce qui revient à négliger certaines composantes de la réalité physique. Solution : Un choix convenable du modèle mathématique. Maths-Info (ENSAM) CMN 15 / 51 Introduction Erreurs sur les données Les erreurs sur les données proviennent généralement de l’imprécision des mesures physiques qui sont utilisées dans l’algorithme. Solution : Ces erreurs peuvent généralement être réduites en améliorant la précision des mesures. Remarque Il est possible d’étudier l’inﬂuence de ces erreurs sur le résultat ﬁnal, par exemple à l’aide de la notion de conditionnement (sensibilité aux erreurs). Dans la suite de ce cours, nous ne nous intéresserons pas aux erreurs de modélisation ni à celles sur les données. Maths-Info (ENSAM) CMN 16 / 51 Représentation des nombres sur ordinateur Erreur relative et erreur absolue Déﬁnition 1 Soit x un nombre réel et ˜ x une approximation de x. L ’erreur absolue : ∆x = |x −˜ x| (mesure de l’erreur) L ’erreur relative : ∆x |x| (importance de l’erreur). Déﬁnition 2 Si m est le plus petit entier signé tel que ∆x ≤0.5 × 10m alors le chiffre correspondant à la mième puissance de 10 (et tous ceux à sa gauche jusqu’au dernier non-nul) sont dit signiﬁcatifs. Exception : si le chiffre correspondant est nul ainsi que tous ceux à sa gauche on dit qu’il n’y a pas de chiffre signiﬁcatif. Nombre à N chiffres signiﬁcatifs : compter vers la droite jusqu’à N à partir du premier non-nul à gauche. L ’erreur absolue est inférieure à la moitié de la puissance de 10 du dernier chiffre signiﬁcatif. Exemple Si ˜ d’ ù 2 2 D l Maths-Info (ENSAM) CMN 17 / 51 Représentation des nombres sur ordinateur Erreurs de représentation des nombres L ’ordinateur doit représenter les nombres dans un système qui lui permette uploads/Management/ chapitre-1cmn.pdf