Remerciez-le!

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

Cours Calcul Matriciel Numérique A. Taakili Calcul numérique approché ▶Introduc

Cours Calcul Matriciel Numérique A. Taakili Calcul numérique approché ▶Introduction ▶Représentation des nombres entiers et réels ▶Erreur absolue et erreur relative ▶Relation entre erreur relative et chiﬀre signiﬁcatif ▶Problèmes numérique Résolution des systèmes linéaires : Méthodes directes ▶Matrices triangulaire ▶Méthode de Gauss ▶Méthode de Gauss-Jordan ▶Décomposition LU, LLT , LDLT , QR ▶Application au calcul de la matrice inverse et du déterminant ▶Etude de la complexité Résolution des systèmes linéaires : Méthodes itératives ▶Méthode de Jacobi ▶Méthode de Gauss-Seidel ▶Méthode de relaxation ▶Etude de la convergence Conditionnement d’un système linéaire Calcul des valeurs et vecteurs propres pour les matrices réelles symétriques ▶Introduction ▶Méthode de la puissance itérée ▶Méthode de la puissance itérée inverse ▶L’algorithme QR. Chap. 1 : Introduction au calcul numérique approché A. Taakili 1 / 47 Introduction Le problème consiste à trouver une fonction θ(t) pour t ∈]t0, T] vériﬁant : ( θ′′(t) + ω2 sin(θ(t)) = 0, t ∈]t0, T] θ(0) = θ0, θ′(0) = v. (1) Solution analytique (Calcul formel ou symbolique) Solution approchée (Calcul numérique) A. Taakili Introduction 2 / 47 Calcul formel Déﬁnition Le calcul formel (ou calcul symbolique) est une discipline qui s’intéresse à la manipulation symbolique d’expressions mathématiques. Il traite des calculs avec paramètres, des polynômes, des fractions Example 1. Simpliﬁcation : √ 5+2 √ 5−2 = 9 + 4 √ 5 Primitives : R cos(x) exp(−3x)dx Dérivation Avantage : échapper aux erreurs et à la propagation d’erreurs Inconvenients : algorithmes plus longues à exécutés, l’éventail des poblèmes résolus est très réduit A. Taakili Introduction 3 / 47 Calcul numérique Déﬁnition Le calcul numérique est un ensemble de calculs qui sont réalisés sur ordinateur à traves un langage interprétable par ce dernier. Domaines d’application : la conception de structures (CAO, dynamique des ﬂuide,...), les prévisions numériques du temps, la conception d’objets chimiques, les statistiques appliquées, l’analyse ﬁnancière ou boursière, etc. ; ... autant de domaines pour lesquels le calcul à la main peut être diﬃcille et très couteux. A. Taakili Introduction 4 / 47 Pourquoi le calcul numérique? Le problème ( θ′′(t) + ω2 sin(θ(t)) = 0, t ∈]t0, T] θ(0) = θ0, θ′(0) = v. (2) admet une unique solution (Cauchy-Lipschitz) La solution existe, peut-on la calculer? Pour θ(t) petit, sin(θ(t)) ≃θ(t), la solution analytique est θ(t) = θ0 cos(ωt) + v ω sin(ωt) Pour θ(t) grand, il n’y a pas de méthodes analytiques. Il faut donc résoudre le problème par la voie numérique A. Taakili Introduction 5 / 47 Calcul numérique Le calcul numérique s’intéresse à la conception, l’analyse et l’implémentation d’algorithmes pour la résolution numérique des problèmes mathématiques continus qui proviennent de la modélisation des phénomènes réels. Avantages : L’éventail des problèmes résolus est très large Les algorithmes sont en générale plus eﬃcaces Inconvénients : La solution est approchée. Propagation de l’erreur A. Taakili Introduction 6 / 47 Projet de calcul scientiﬁque Modélisation physique : Modèle physique ou continu : très souvent consiste en un jeu d’équations aux dérivées partielles (EDP) →physicien ou ingénieur Étude mathématique : identiﬁer le cadre mathématique dans lequel on a existence et unicité, au moins pour un modèle simpliﬁé →mathématicien Modèle discret →numéricien ▶Solution exacte du modèle continu appartient souvent à un espace de dimension inﬁnie, ▶Pour résoudre le problème sur ordinateur, on doit se ramener à un problème de dimension ﬁnie, ▶"modèle numérique" ou "modèle discret" qui approche l’EDP (et les CL/CI) dans un certain sens Aspect logiciel et adaptation aux architéctures →informaticien A. Taakili Introduction 7 / 47 Exemple d’un projet de calcul scientiﬁque Stockage géologique du CO2 Ecoulement monophasique Réactions chimiques (instantanées ou lentes) Transport des espèces aqueuses Précipitation-dissolution des minéraux A. Taakili Introduction 8 / 47 Objet d’analyse numérique Des problèmes mathématique impossible à les résoudre directement. La nécessité des calcul purement numériques (solution approchées.) L’objet de l’Analyse numérique est de concevoir et étudier des méthodes de résolution de certains problèmes physiques dont on cherche à calculer une solution approchée à l’aide d’un ordinateur. De telles méthodes méthodes passent souvent par la résolution de systèmes linéaire AX = b. A. Taakili Introduction 9 / 47 Méthodes de résolution Méthode de Cramer, il faut calculer n + 1 déterminants,(n + 1)! opérations. La résolution à la main d’un système de 12 équations à 12 inconnues par la méthode de Cramer nécessiterait ? années si on suppose qu’on ait capable d’eﬀectuer une opération arithmétique en une seconde. Ce qui est extrêmement rapide. La résolution d’un système de 100 équations à 100 inconnues nécessiterait environ (101)! ≃10160 opérations arithmétiques. Aujourd’hui l’ordinateur le plus puissant eﬀectue 1017 opérations par seconde. ? Années pour résoudre un telle système avec la méthode de Cramer sur un superordinateur. Même travail peut être eﬀectué en moins d’une seconde en utilisant une “bonne” méthode numérique. La méthode d’élimination de Gauss, nécessite seulement (2/3)n3 opérations arithmétiques. Pour un système de taille n = 100, la méthode d’élimination de Gauss, nécessite 6.66 ∗10−10 secondes sur un superordinateur. A. Taakili Introduction 10 / 47 Représentation des nombres entiers Pour représenter un nombre, aussi grand soit-il, nous disposons d’une série de 10 signes qui s’appellent les chiﬀres 0, 1, 2, 3, 4, 5, 6, 7, 8 et 9. Lorsque nous écrivons un nombre en mettant certains de ces chiﬀres les uns derrière les autres, l’ordre dans lequel nous mettons les chiﬀres est capital. ▶4025 est diﬀérent de 2045 C’est la position des chiﬀres dans le nombre qui donne sa valeur. ▶2025 = 2 ∗1000 + 0 ∗100 + 2 ∗10 + 5 = 2 ∗103 + 0 ∗102 + 2 ∗101 + 5 ∗100 A. Taakili Représentation des nombres entiers et réels 11 / 47 Représentation des nombres entiers Les ordinateurs utilisent un système de représentation à deux chiﬀres : 0 et 1. Les informations sont manipulées par paquets de 0 et de 1. La taille de ces paquets a été ﬁxée à 8 informations binaires. Ce sont les octets. Une information binaire s’appelle un bit (en anglais bit, pour binary digit). Un groupe de huit bits s’appelle un octet (en anglais, byte). Codage binaire : 2025 = (11111101001)2. A. Taakili Représentation des nombres entiers et réels 12 / 47 Représentation des nombres entiers Conversion décimal vs binaire 2025 = 2 × 1012 + 1 1012 = 2 × 506 + 0 506 = 2 × 253 + 0 253 = 2 × 126 + 1 126 = 2 × 63 + 0 63 = 2 × 31 + 1 31 = 2 × 15 + 1 15 = 2 × 7 + 1 7 = 2 × 3 + 1 3 = 2 × 1 + 1 1 = 2 × 0 + 1 A. Taakili Représentation des nombres entiers et réels 13 / 47 Représentation des nombres entiers Conversion binaire vs décimal 0 11111101001 0 × 2 + 1 =1 1111101001 1 × 2 + 1 =3 111101001 3 × 2 + 1 =7 11101001 7 × 2 + 1 =15 1101001 15 × 2 + 1 =31 101001 31 × 2 + 1 =63 01001 63 × 2 + 0 =126 1001 126 × 2 + 1 =253 001 253 × 2 + 0 =506 01 506 × 2 + 0 =1012 1 1012 × 2 + 1 =2025 A. Taakili Représentation des nombres entiers et réels 14 / 47 Représentation des nombres entiers Dans un ordinateur, les entiers sont représentés à l’aide de bits (1 bit = un caractère 0 ou 1). Typiquement, on utilise 32 ou 64 bits pour les représenter 1 des bits est uniquement dedié au signe de l’entier (0 = +, 1 = −) Exemple : sur 32 bits, les entiers peuvent prendre une valeur comprise entre −2 147 483 648 et 2 147 483 647. Exercice Montrer que 4325 s’écrit bien (1000011100101)2 en base 2 puis reconvertir (1000011100101)2 en base 10. Si on dispose de 6 bits (bit de signe compris), quelles valeurs peuvent prendre les entiers? Ecrire (34)10 et (27)10 en binaire puis eﬀectuer l’opération en binaire (34)10 + (27)10. Déterminer le nombre de bit nécessaire pour représenter un entier non nul N en base 2. A. Taakili Représentation des nombres entiers et réels 15 / 47 La représentation des nombres négatifs est réalisé grâce au bit de poids fort "bit de gauche". On parle également d’entiers signés. Nombres positifs →le bit de poids fort est 0 Nombres négatifs →le bit de poids fort est 1 Les autres bits contiennent la valeur absolue du nombre Exemple sur un octet Inconvénient: Pour réaliser des opérations entre nombres signés, il faut faire un traitement particulier du bit de signe. Le résultat ﬁnal ne pouvant être obtenu de façon simple (addition ou soustraction des deux nombres). D’où l’utilisation du complément à 2. A. Taakili Représentation des nombres entiers et réels 16 / 47 Représentation par le complément à 1 Le complément à 1 (noté C1) est également appelé complément logique, il consiste à inverser chaque bit (0 →1 et 1 →0) Représentation par le complément à 2 Le complément à 2 (noté C2) est également appelé uploads/s3/ cmn-22-23-chapter1.pdf