Remerciez-le!

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

UNIVERSITE ABDELMALEK ESSADI FACULTE DES SCIENCES DE TETOUAN MASTER MECATRONIQU

UNIVERSITE ABDELMALEK ESSADI FACULTE DES SCIENCES DE TETOUAN MASTER MECATRONIQUE Module MO1: Méthodes numériques et probabilités 2008-2009 Abdellatif Khamlichi 0 UNIVERSITE ABDELMALEK ESSADI FACULTE DES SCIENCES DE TETOUAN MASTER GENIE ENERGETIQUE ET ENVIRONNEMENT Module M7: Méthodes numériques et optimisation Elément : Méthodes numériques 2008-2009 Abdellatif Khamlichi 1 Sommaire Chapitre1: Les concepts rattachés au calcul numérique...................................................................4 Chapitre 2: Résolution numérique des équations non linéaires.........................................................14 Chapitre 3: Interpolation et approximation........................................................................................22 Chapitre 4: Résolution numérique des systèmes d'équations linéaires............................................34 Chapitre 5: Méthodes de calcul numérique des valeurs propres et des vecteurs propres...............45 Chapitre 6: Programmation linéaire....................................................................................................50 Chapitre 7: Equations différentielles aux dérivées partielles.............................................................54 2 Bibliographie  1 D. M. Young, R. T. Gregory "A survey of numerical mathematics", Volume I, Dover Publications, New York, 1988.  2 D. M. Young, R. T. Gregory "A survey of numerical mathematics", Volume II, Dover Publications, New York, 1988.  3 P. G. Ciarlet " Introduction à l'analyse numérique matricielle et à l'optimisation", Dunod, Paris, 1998.  4 P. G. Ciarlet, B. Miara, J. M. Thomas "Exercices d'analyse numérique matricielle et d'optimisation avec solutions", 2ième édition, Masson, Paris, 1986.  5 A. Magnus "Analyse numérique 1a et 2", Cours Université Catholique de Louvain, 2005. [6] M. Crouzeix, A.L. Mignot "Analyse numérique des équations différentielles", Masson, Paris, 1984. [7] M. Minoux "Programmation mathématique: théorie et algorithmes - Tome 1", CNET-ENST, Collection Technique et Scientifique des Télécommunications, Dunod, paris, 1983. [8] J.C. Strikwerda "Finite difference schemes and partial differential equations", Wadsworth & Brooks/ Cole, Mathematics Series, California 1989. 3 CHAPITRE 1: Les concepts rattachés au calcul numérique 1. Introduction L'objet de l'analyse numérique est l'application des mathématiques afin de développer des algorithmes et des méthodes capables de construire des solutions numériques aux différents problèmes rencontrés dans la pratique. Très souvent les théorèmes d'existence permettent d'établir que certaines classes de problèmes admettent des solutions mais ne donnent aucune information concernant comment calculer effectivement la solution. Dans d'autres cas des solutions analytiques existent mais ne peuvent pas être utilisées telles qu'elles sont pour obtenir des résultats numériques. Voici quelques exemples: (1) comment résoudre le système linéaire n ij j i j 1 a x b i 1,2, n     L , où les ij a et i b sont des réels donnés? (2) comment évaluer 746 e ? (Matlab donne par exemple exp( 746) 0   et -324 exp( 745) 4.9407 10    ) (3) comment résoudre automatiquement l'équation du second degré 2 ax bx c 0    ? 2. Précision numérique d'un algorithme L'un des problèmes majeurs auxquels le numéricien est confronté est le contrôle de la précision des résultats des calculs effectués. Il convient pour cela d'utiliser des algorithmes numériques fiables et économiques. Le numéricien ne peut pas ignorer l'aspect mathématique qui recouvre le choix d'un algorithme numérique afin de résoudre un problème donné. Considérons à titre d'exemple le problème de l'évaluation de la fonction f(x) tan x sin x   en x 0.1250  . Supposons que nous souhaitions obtenir un résultat à 4 chiffres significatifs, ce qui signifie une précision relative de 1/10000 . Deux méthodes aux moins peuvent être envisagées. 4 Méthode 1: Nous effectuons les calculs intermédiaires en retenant 4 chiffres significatifs; tan(0.1250) 0.1257  , sin(0.1250) 0.1247  ; par soustraction il vient f(x) 0.0010  qui est un résultat à deux chiffres significatifs; une perte de précision est constatée. Méthode 2: Nous développons tan x et sin x en série de Taylor. On obtient ainsi 3 5 7 1 2 17 tan x x x x x 3 15 315     L et 3 5 7 1 1 1 sin x x x x x 6 120 5040     L ; d'où 3 5 7 1 1 13 f(x) x x x 2 8 240    L ; si nous utilisons cette formulation tronquée aux trois premiers termes, on obtient f(0.1250) 0.0009804  et le résultat est précis à 4 chiffres significatifs. L'exemple précédent montre qu'il est nécessaire d'envisager une reformulation mathématique adéquate du problème afin de sauvegarder la précision des résultats. Autrement, des pertes de précision accompagneront le résultat de tout calcul où interviennent par exemple des soustractions. Lorsqu'un algorithme est appliqué en pratique, il y a des considérations qui doivent être prises en compte et qui dépassent le cadre mathématique ordinaire. Ces considérations supplémentaires sont nécessaires à cause du fait que les opérations de calcul sont effectuées sur un calculateur numérique automatique (ordinateur). Ce qui signifie que notre univers mathématique est constitué seulement d'un sous ensemble fini de l'ensemble des nombres rationnels Q . Cet ensemble est appelé espace des nombres représentés par la machine. Il a plein de défauts: il ne contient pas par exemple la fraction 1/3 et il est instable vis à vis des opérations arithmétiques. Les nombres pouvant être pris en compte effectivement forment l'ensemble élargi des nombres dits représentables sur la machine en considérant des approximations de ces derniers par les nombres représentés. Il s'ensuit alors des erreurs d'arrondis. Par ailleurs, les opérations ne sont pas effectuées en général de manière exacte et d'autres erreurs d'arrondis affectent les résultats de calcul. Par conséquent les propriétés habituelles algébriques telles que par exemple la commutativité et l'associativité ne peuvent plus être garanties de sorte que les relations suivantes a(b / c) b(a / c) (ab)/ c   ne peuvent pas toujours avoir lieu. 5 3. Instabilités numériques et problèmes mal conditionnés Il faut distinguer entre les difficultés propres associées à la résolution d'un problème donné et les difficultés qui sont liées à l'algorithme numérique utilisé pour calculer numériquement une solution de ce problème. Considérons le problème de résolution du système algébrique linéaire suivant où 0 1  2 2x y 2 3 1 x y 1 3                  Supposons que 10 10  . Le calcul analytique nous conduit à l'unique solution: x 1  et y 0  . Si la perturbation  est nulle, on obtient une infinité de solutions: x 1 k /3  et y k  . Ce qu'il faut remarquer ici c'est qu'une petite perturbation 10 10  affectant un seul coefficient du système est capable de modifier de manière considérable la nature du résultat. C'est une propriété mathématique du système qui ne dépend pas de l'algorithme utilisé pour le résoudre. Si un problème est tel qu'une petite perturbation dans les données ne produise qu'une petite perturbation au niveau de la solution mathématique, le problème est bien conditionné. Si au contraire une petite perturbation au niveau des données produit une grande perturbation au niveau du résultat, le problème est mal conditionné. Cette notion de conditionnement du problème mathématique peut être transcrite aux algorithmes numériques qui sont envisagés pour le résoudre. Nous disons ainsi qu'un algorithme numérique est stable si la solution obtenue en utilisant cet algorithme est proche, en uns sens à préciser (choix d'une norme), de la solution exacte du problème perturbé. Supposons que le symbole D désigne les données et que F représente une fonction mathématique qui permet d'obtenir la solution exacte. F(D) est le processus mathématique qui permet de résoudre le problème. Si les données sont perturbées, on se retrouve avec * D et le processus de résolution conduit à la solution * F(D ) du problème perturbé. Le problème est bien conditionné si * D proche de D entraîne * F(D ) proche de F(D). Soit * F un algorithme numérique permettant de résoudre le problème de manière approchée. Alors par définition * F est un algorithme stable s'il existe une perturbation * D de D telle que * F (D) soit proche de * F(D ) . 6 Remarque On peut trouver dans la pratique les quatre situations suivantes: - problème mal conditionné et algorithme numérique stable; dans cette situation tout ce qu'on peut faire c'est étudier la sensibilité du problème (Chaos par exemple); - problème mal conditionné et algorithme numérique instable; dans ce cas l'outil numérique ne peut servir à rien; - problème bien conditionné et algorithme numérique stable; c'est la situation idéale; - problème bien conditionné et algorithme numérique instable; c'est le cas où le numéricien doit travailler davantage. 4. Problèmes types qui intéressent le numéricien Tout d'abord un numéricien est un mathématicien qui développe, analyse et évalue des algorithmes numériques destinés à obtenir des solutions numériques approchées aux problèmes mathématiques. Beaucoup de ces problèmes apparaissent dans le domaine de la physique et de l'ingénierie. Le numéricien est souvent conduit à développer de nouveaux résultats mathématiques et les adapter afin de les utiliser de manière effective dans le cadre de la programmation sur ordinateur. L'évaluation des algorithmes est conduite par des approches mathématiques et fait appel aussi à des essais numériques (par exemple évaluation de la durée de calcul). L'évaluation des algorithmes est souvent effectuée par résolution de problèmes tests sur ordinateur. Parmi les problèmes types que recouvre le domaine de uploads/Management/ polycopie-methodes-numeriques.pdf