Remerciez-le!

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

Généré le 21 avril 2022 à 12:24:17 Analyse numérique Abdoulaye Samaké ∗ DER de

Généré le 21 avril 2022 à 12:24:17 Analyse numérique Abdoulaye Samaké ∗ DER de Mathématiques et Informatique Faculté des Sciences et Techniques (FST) Université des Sciences, des Techniques et des Technologies de Bamako (USTTB) École Normale Supérieure (ENSup) Licence mathématiques (S5) ∗. E-mail : abdoulaye.samake@usttb.edu.ml BP : E 3206, Bamako, Mali Abdoulaye Samaké (USTTB/FST) Analyse numérique 1 / 104 Outline 1 Introduction Généralités Typologie des problèmes Résolution des problèmes Typologie des algorithmes 2 Analyse d’erreurs Estimation des erreurs Réprésentation des nombres en machine 3 Méthodes directes de résolution des systèmes linéaires Systèmes linéaires Analyse de stabilité des systèmes linéaires Résolution des systèmes triangulaires Méthode d’élimination de Gauss Factorisation LU Factorisation de Cholesky Abdoulaye Samaké (USTTB/FST) Analyse numérique 2 / 104 Introduction Introduction Abdoulaye Samaké (USTTB/FST) Analyse numérique 3 / 104 Introduction Généralités Modélisation Mathématique Les systèmes et phénomènes physiques les plus remarquables de la vie réelle sont également les plus complexes à comprendre et à étudier. Les méthodes mathématiques de plus en plus sophistiquées sont utilisées dans le traitement de ces problèmes issus de la science de l’ingénieur, de sciences physiques et biologiques, technologiques, économiques et sociales. La modélisation mathématique consiste à la description d’un phénomène observé par le biais d’équations mathématiques, généralement sous la forme d’Équations aux Dérivées Partielles (EDP) et d’Équations aux Diﬀérentielles Ordinaires (EDO). Le problème mathématique issu de cette modélisation est appelé un modèle mathématique. Il doit contenir les informations nécessaires, qui peuvent être qualitatives ou quantitatives, sur le phénomène réel qu’il représente. La modélisation mathématique a lieu en étroite collaboration avec les scientiﬁques des disciplines applicatives concernées. Les modèles issus de la modélisation mathématique n’admettent en général pratiquement pas de solutions analytiques (exactes), établies explicitement à l’aide des outils mathématiques classiques. Il devient par conséquent nécessaire de faire recours aux méthodes numériques pour calculer des solutions approchées. Abdoulaye Samaké (USTTB/FST) Analyse numérique 4 / 104 Introduction Généralités Analyse numérique Déﬁnition (Nick Trefethen, Oxford) L’analyse numérique est une discipline qui traite de la déﬁnition, 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. L’analyse numérique s’intéresse au développement d’outils et de méthodes numériques pour le calcul d’approximations de la solution des modèles mathématiques continus. Elle est à l’interface entre l’informatique, les mathématiques et les autres disciplines scientiﬁques. Elle permet d’établir des procédures calculatoires détaillées, c’est à dire des algorithmes, susceptibles d’être mises en œuvre sur les ordinateurs. Un modèle étant une abstraction d’un phénomène réel, ne peut par conséquent le décrire exactement tel qu’il est. Il devient ainsi nécessaire d’associer une incertitude à l’étude du modèle. L’incertitude d’une grandeur modélisée peut être déﬁnie comme une valeur associée au résultat du modèle. Cette valeur caractérise la dispersion des valeurs qui pourraient raisonnablement être attribuées à la valeur exacte de la grandeur modélisée. L’incertitude associée à une grandeur peut être évaluée en utilisant l’analyse des incertitudes. Cette représentation permet de bien préciser la signiﬁcation du concept “sources d’erreurs”. Abdoulaye Samaké (USTTB/FST) Analyse numérique 5 / 104 Introduction Généralités Analyse numérique L’analyse numérique se caractérise par une triple adéquation entre : Le problème et le modèle La solution du problème La résolution du problème (méthode et algorithme) Étapes (niveaux) Conception Analyse Implémentation Outils classiques Les matrices et les systèmes linéaires Les équations diﬀérentielles (ordinaires et partielles) Abdoulaye Samaké (USTTB/FST) Analyse numérique 6 / 104 Introduction Typologie des problèmes Typologie des problèmes On distingue : Problèmes qualitatifs et quantitatifs Problèmes implicites et explicites Problèmes bien/mal posés Problèmes bien/mal conditionnés Problémes qualitatifs Comportement des solutions : analyse de stabilité Comportement asymptotique : conclusions globales, comportement à long terme Problémes quantitatifs calcul détaillé d’une solution (numérique) : conclusions spéciﬁques Problémes sous forme explicite et implicite Forme explicite : x = F(d) Forme implicite : F(x, d) = 0 Abdoulaye Samaké (USTTB/FST) Analyse numérique 7 / 104 Introduction Typologie des problèmes Typologie des problèmes Problèmes bien/mal posés La notion de problème bien/mal posé a été introduite par Hadamard en 1923. Le problème mathématique x = F(d) est bien posé si : La solution x existe La solution x est unique La solution x dépend continûment des données d. Autrement, le problème est dit mal posé. Abdoulaye Samaké (USTTB/FST) Analyse numérique 8 / 104 Introduction Typologie des problèmes Conditionnement d’un problème conditionnement Le conditionnement d’un problème bien posé de la forme x = F(d) mésure la sensibilité de la solution x du problème au changement des données d. Soient δd une perturbation admissible des données et δx la modiﬁcation induite sur la solution du problème x = F(d), c’est à dire : δx = F(d + δd) −F(d) On appelle conditionnement relatif de ce problème, la quantité déﬁnie par : κ(d) = lim |D|→0 sup δd∈D ∥δx∥/ ∥x∥ ∥δd∥/ ∥d∥= lim |D|→0 sup δd∈D ∥F(d + δd) −F(d)∥/ ∥F(d)∥ ∥δd∥/ ∥d∥ sup dénote la borne supérieure et D désigne la norme vectorielle (ou matricielle) Si d = 0, le conditionnement relatif est 0 Si x = 0, le conditionnement relatif est ∞ Dans le cas où d = 0 ou x = 0, on introduit le conditionnement absolu déﬁni par : κabs(d) = lim |D|→0 sup δd∈D ∥δx∥ ∥δd∥ Abdoulaye Samaké (USTTB/FST) Analyse numérique 9 / 104 Introduction Typologie des problèmes Conditionnement d’un problème conditionnement On considère le problème sous la forme explicite x = F(d). Si la fonction F est diﬀérentiable en d et si on note F ′(d) = lim δd→0 ∥δx∥ ∥δd∥sa dérivée, le conditionnement relatif peut s’écrire comme suit : κ(d) = lim δd→0 ∥δx∥/ ∥x∥ ∥δd∥/ ∥d∥= lim δd→0 ∥δx∥∥d∥ ∥δd∥∥x∥= F ′(d) ∥δd∥ ∥δx∥== F ′(d) ∥d∥ ∥F(d)∥ Si d ∈Rp et x = F(d) ∈Rq, la dérivée F ′(d) correspond à la matrice jacobienne Si q = 1, la matrice jacobienne est le gradient ∇F(d) Abdoulaye Samaké (USTTB/FST) Analyse numérique 10 / 104 Introduction Typologie des problèmes Conditionnement d’un problème Quelques propriétés Un problème peut avoir un petit conditionnement pour certaines valeurs de d et un grand conditionnement pour d’autres valeurs de d Si κ(d) est grand pour toute donnée admissible d, le problème est dit mal conditionné Un problème mal posé est mal conditionné, mais mal conditionné ne veut pas dire mal posé Le conditionnement associé à un problème est un indicateur de la diﬃculté de résolution numérique du problème Le fait d’être bien conditionné est une propriété du problème qui est indépendante de l’algorithme choisi pour le résoudre. Abdoulaye Samaké (USTTB/FST) Analyse numérique 11 / 104 Introduction Résolution des problèmes Résolution d’un problème Pour résoudre un problème mathématique, deux approches peuvent être envisagées : Résolution analytique (ou symbolique) Cette approche utilise les propriétés analytiques et mathématiques du problème pour en dériver la solution x. Malheureusement, une solution analytique n’est pas calculable pour tous les problèmes. Résolution numérique Cette approche fait recours à une méthode numérique pour déterminer la solution x pour une valeur d donnée. Quelques avantages d’une approche numérique Une solution numérique peut être obtenue même si aucune solution analytique n’est disponible (calculable) Une méthode numérique est décomposée en une série d’opérations arithmétiques élémentaires adaptées pour un ordinateur. Abdoulaye Samaké (USTTB/FST) Analyse numérique 12 / 104 Introduction Typologie des algorithmes Typologie des algorithmes Déﬁnition Un algorithme est une suite ﬁnie d’instructions indiquant la démarche à suivre pour résoudre un problème donné. Complexité d’un algorithme La complexité d’un algorithme peut être caractérisée par les mésures suivantes : Le nombre d’étapes Le temps d’éxécution L’occupation de l’espace mémoire Des mesures dépendantes de l’architecture du processeur Il est souvent intéressant d’avoir une idée qualitative du comportement de l’algorithme plutôt que de chercher á calculer le nombre exact d’opérations. Par conséquent, la notion de complexité (asymptotique), qui consiste à déﬁnir une mésure de complexité comme une fonction de la taille n des données du problème. En général, la complexité d’un problème est déﬁnie comme étant la complexité de l’algorithme ayant la plus petite complexité parmi ceux qui résolvent le problème. Abdoulaye Samaké (USTTB/FST) Analyse numérique 13 / 104 Introduction Typologie des algorithmes Ordre de complexité Soient n la taille des données d’un problème et C(n) la complexité d’un algorithme de résolution de ce problème. La complexité C(n) est dite d’ordre f(n) s’il exite deux constantes réelles α et β telles que : C(n) ≤βf(n), pour tout n ≥α. Elle est notée C(n) = O(f(n)). Ordre Classe de complexité O(1) constante O(log(n)) logarithmique O(n) linéaire O(n2) quadratique O(n3) cubique O(np), p ∈N polynomiale O(cn), c constante exponentielle O(n!) factorielle Abdoulaye Samaké (USTTB/FST) Analyse numérique 14 / 104 Introduction Typologie des algorithmes Algorithmes numériques Déﬁnition (Algorithme numérique) On considère un problème bien posé F(x, d) = 0. L’algorithme numérique pour la résolution du problème F est déﬁni par la suite suivante de problèmes approchés : F1(x(1), d(1)), F2(x(2), d(2)), . . . , Fn(x(n), d(n)), où n est un paramètre L’idée sous-jacente à la décomposition en sous-problèmes est la résolution des problèmes Fn est plus simple que celle de F. Diﬀérents algorithmes peuvent être utilisés pour résoudre le même problème numérique. Il est par conséquent nécessaire de choisir ce uploads/Management/ lecture-ensup-1.pdf