Remerciez-le!

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

SYLLABUS Cours de Calcul Formel et Numérique INFO-F-205 Gianluca Bontempi Ana d

SYLLABUS Cours de Calcul Formel et Numérique INFO-F-205 Gianluca Bontempi Ana da Silva Soares, Martin De Wulf Département d’Informatique, Faculté de Sciences Université Libre de Bruxelles, ULB Belgique 2 Table des matières Index 2 1 Introduction au calcul numérique 3 1.1 Du modèle au problème mathématique . . . . . . . . . . . . . . . . . 3 1.1.1 Problèmes bien/mal posés . . . . . . . . . . . . . . . . . . . . 5 1.1.2 Conditionnement d’un problème . . . . . . . . . . . . . . . . 6 1.2 La résolution d’un problème mathématique . . . . . . . . . . . . . . 7 1.3 Algorithmes et problèmes numériques . . . . . . . . . . . . . . . . . 8 1.3.1 Déﬁnition qualitative d’algorithme . . . . . . . . . . . . . . . 8 1.3.2 Complexité d’un algorithme . . . . . . . . . . . . . . . . . . . 9 1.3.3 Algorithmes numériques . . . . . . . . . . . . . . . . . . . . . 10 1.3.4 Consistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.5 Stabilité d’un algorithme . . . . . . . . . . . . . . . . . . . . 11 1.3.6 Convergence d’un algorithme . . . . . . . . . . . . . . . . . . 13 1.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Analyse d’erreurs 15 2.1 Erreurs absolue et relative . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Sources d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Représentation des nombres en machine . . . . . . . . . . . . . . . . 16 2.3.1 Notation à virgule ﬁxe . . . . . . . . . . . . . . . . . . . . . . 17 2.3.2 Notation à virgule ﬂottante . . . . . . . . . . . . . . . . . . . 18 2.3.3 Répartition des nombres à virgule ﬂottante . . . . . . . . . . 19 2.4 Représentation machine des nombres réels . . . . . . . . . . . . . . . 21 2.4.1 L’erreur d’arrondi . . . . . . . . . . . . . . . . . . . . . . . . 23 2.5 Erreurs d’arrondi et résolution numérique . . . . . . . . . . . . . . . 23 2.5.1 L’erreur de propagation . . . . . . . . . . . . . . . . . . . . . 23 2.5.2 L’erreur de génération . . . . . . . . . . . . . . . . . . . . . . 25 2.6 Opérations machines en virgule ﬂottante . . . . . . . . . . . . . . . . 27 2.6.1 La propagation d’erreurs dans les opération arithmétiques en virgule ﬂottante . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.7 Quelques conseils pour concevoir un algorithme stable . . . . . . . . 30 2.8 Standard IEC/IEEE . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.9 Gestion de la mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.10 L’analyse de stabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.11 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.11.1 Représentation en virgule ﬁxe . . . . . . . . . . . . . . . . . . 32 2.11.2 Représentation en virgule ﬂottante normalisée . . . . . . . . . 32 2.11.3 Erreur d’annulation . . . . . . . . . . . . . . . . . . . . . . . 33 2.11.4 Erreur de génération . . . . . . . . . . . . . . . . . . . . . . . 34 3 4 TABLE DES MATIÈRES 3 Résolution des systèmes linéaires 35 3.1 Exemples et motivations . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 Systèmes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3 Systèmes triangulaires . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.1 Analyse de complexité . . . . . . . . . . . . . . . . . . . . . . 38 3.4 Élimination de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4.1 Description de l’algorithme . . . . . . . . . . . . . . . . . . . 40 3.4.2 Analyse de complexité . . . . . . . . . . . . . . . . . . . . . . 42 3.5 La factorisation LU . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5.1 La méthode de Gauss vs. la factorisation LU . . . . . . . . . 44 3.5.2 Le calcul du déterminant . . . . . . . . . . . . . . . . . . . . 44 3.5.3 Existence et unicité de la factorisation . . . . . . . . . . . . . 45 3.6 Les méthodes directes pour la factorisation . . . . . . . . . . . . . . 45 3.7 La factorisation de Choleski . . . . . . . . . . . . . . . . . . . . . . . 47 3.8 Le calcul de l’inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.9 Les méthodes de changement de pivot . . . . . . . . . . . . . . . . . 49 3.10 L’analyse de stabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.10.1 Le conditionnement d’une matrice . . . . . . . . . . . . . . . 54 3.10.2 L’analyse a priori . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.10.3 L’analyse a posteriori . . . . . . . . . . . . . . . . . . . . . . 58 3.11 Raﬃnement itératif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.12 Les méthodes itératives . . . . . . uploads/Management/ calcul-formel-et-numerique-in-french-handbook-of-the-numerical-analysis-course-of-ulb-computer-science-department.pdf