Cours de Methodes Numeriques-BAC 2 TS ESI UNILU 2016-2017 Revu [PDF]

Zitiervorschau

UNIVERSITE DE LUBUMBASHI ECOLE SUPERIEURE DES INGENIEURS INDUSTRIELS Département de Science de base

METHODES NUMERIQUES Notes de cours destinées aux étudiants de 2ème Bachelier Ingénieur Industriel

Prof. Dr. Ir. Gustave MUKOKO K. Docteur en Sciences de l’Ingénieur/ Génie Civil

Appartenant à………………………………………….

Année Académique.2016 - 2017

BAC II Génie Civil

COURS DE METHODES NUMERIQUES ANIMATEURS Responsable académique: Prof. Dr. Ir. Gustave MUKOKO K. Phd en Sciences de l’Ingénieur/ Génie Civil et Environnemental Collaborateurs: Ass. Ir. Eddy BILITU Ir. Ind. en Electromécanique I. PRE-REQUIS: • Algèbre linéaire; • Analyse mathématique; • Informatique : Programmation. II. OBJECTIF L'objet du cours est:  d'introduire le concept de solution numérique approchée de problèmes en physique et mathématique dont la solution analytique n'est pas disponible ou difficile à obtenir. Il s'agit de présenter rigoureusement les fondements des méthodes numériques et de développer une méthodologie scientifique. On insiste aussi sur la complémentarité entre l'approche numérique et analytique. III. CONTENU        

Analyse d'erreur : erreurs de modélisation, de troncature, convergence et ordre d'approximation, arithmétique en virgule flottante; Approximation et interpolation : polynômes de Lagrange, polynômes orthogonaux, bornes d'erreur et convergence; Intégration et différentiation numériques : méthodes à pas égaux et inégaux, différences centrés et décentrées, techniques récursives et adaptatives; Résolution d'équations différentielles ordinaires (EDO) : méthodes de Taylor et de Runge-Kutta, méthodes à pas multiples, conditions de stabilité; Résolution d'équations linéaires : méthodes directes et itératives, notions de complexité, calcul de valeurs propres; Résolution d'équations non-linéaires : méthodes d'encadrement et de Newton-Raphson, application à des problèmes d'optimisation; Résolution d'équations aux dérivées partielles (EDP): équation de la diffusion, équation de Laplace et équation des ondes, différences finies et schémas explicites. Laboratoires utilisant Matlab

IV. REFERENCES BIBLIOGRAPHIQUES: • • • • •

F. FILBET. Analyse numérique – Algorithme et étude mathématique. Dunod, 2009. P. LASCAUX et R. THÉODOR. Analyse numérique matricielle appliquée à l’art de l’ingénieur. 1. Méthodes directes. Dunod, 2000. P. LASCAUX et R. THÉODOR. Analyse numérique matricielle appliquée à l’art de l’ingénieur. 2. Méthodes itératives. Dunod, 2000. A. QUARTERONI, R. SACCO et F. SALERI. Méthodes numériques. Algorithmes, analyse et applications. Springer, 2007. DOI : 10.1007/978-88-470-0496-2. Franck Jedrzejewski- Introduction aux méthodes numériques. © Springer-Verlag France, Paris 2005, deuxième édition. ISBN-13 : 978-2-287-25203-7 Paris Berlin Heidelberg New York

BAC II Génie Civil

Cours de Méthodes Numériques Introduction aux méthodes numériques

V. METHODES PEDAGOGIQUES   

30 heures de cours théorique avec remise d’un support de cours (exposé magistral avec diapos); 20 heures de travaux pratiques dirigés (exercices, laboratoires); 25 heures de travaux pratiques encadrés (exercices sur études de cas concrets, sous forme de projet en groupe)

VI. EVALUATION  

Théorique:  deux interrogations 20 %  examen 30 % Pratique:  exercices notés 20 %  laboratoire 15 %  compte-rendu de travaux pratiques 15 %.

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 3 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

SOMMAIRE COURS DE METHODES NUMERIQUES ........................................................................................................ 2 1.

INTRODUCTION AUX METHODES NUMERIQUES ................................................................... 6 1.1. INTRODUCTION

6

1.2. DESASTRES ET CALCUL NUMERIQUE

6

1.3. PROBLEMES NUMERIQUES

6

Définition de calcul numérique

7

Généralités sur l’analyse numérique et le calcul scientifique

7

Différentes sources d’erreur dans une méthode numérique

8

1.4. NOTIONS D’ERREUR ABSOLUE ET RELATIVE Evaluation de l’erreur

9

Propriétés de l’erreur

9

1.5. LA MEMOIRE DE L’ORDINATEUR: LE STOCKAGE DES NOMBRES.

9

1.6. LES REGLES DE BASE DU MODELE.

11

1.7. CONDITIONNEMENT ET STABILITE NUMERIQUE.

11

1.7.1. Notion de conditionnement d’un problème.

11

1.7.2. Notion de stabilité numérique.

11

1.8. QUELQUES NOTIONS D’ALGORITHMIQUE

2.

8

11

1.8.1. Algorithme

11

1.8.2. Codage

12

1.8.3. Efficacité et complexité 13 RESOLUTION D’UNE EQUATION f(x) = 0 .................................................................................. 14 2.1. INTRODUCTION

14

2.2. ÉQUATIONS ALGEBRIQUES

15

2.3. LES ALGORITHMES CLASSIQUES

16

2.3.1 Localisation des racines

16

2.3.2 Approximations successives

17

2.3.3 Méthodes d’encadrement 17 2.3.3.1 Méthode de la bissection ou méthode de dichotomie .................................................. 18 2.3.3.2 Méthode de la fausse position ..................................................................................... 19 2.3.4 Méthode ou Théorèmes de points fixes 20 2.3.4.1 Méthode de Newton-Raphson ..................................................................................... 20 2.3.4.2 Méthode de Steffensen ................................................................................................ 22 2.3.5 Méthode de la sécante et variantes 22 2.3.5.1 Méthode de la sécante ................................................................................................. 22 2.3.5.2 Méthode de Müller ...................................................................................................... 23 3.

INTERPOLATION POLYNOMIALE ............................................................................................... 24 3.1. INTRODUCTION

24

3.2. METHODE DIRECTE BASEE SUR LA RESOLUTION D’UN SYSTEME LINEAIRE

25

3.3. INTERPOLATION DE LAGRANGE: UNE METHODE ITERATIVE

25

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 4 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

4.

5.

3.3.1 Interpolation Linéaire:

25

3.3.2 Interpolation Parabolique:

26

3.3.3 Interpolation de Lagrange:

27

INTERPOLATION DE D’HERMITE

30

3.4. INTERPOLATION DE TCHEBYCHEV

31

3.5. DIFFERENCES DIVISEES

33

3.6. EXERCICES 38 DÉRIVATION ET INTÉGRATION NUMERIQUE ........................................................................ 39 4.1. INTRODUCTION

39

4.2. DERIVATION

39

4.3. METHODES NUMERIQUES D’INTEGRATION.

43

4.3.1 Principes généraux

43

4.3.2 Méthode des rectangles

49

4.3.3 Méthode des trapèzes

51

4.3.4 Méthode de Simpson

52

4.3.5 Méthode de Newton-Côtes

53

4.3.6 Méthode de Poncelet 54 ÉQUATIONS ET SYSTÈMES D’ÉQUATIONS DIFFÉRENTIELLES ....................................... 56 5.1. INTRODUCTION

56

5.2. EXISTENCE ET UNICITE DES SOLUTIONS

56

5.3. RESOLUTION NUMERIQUE DES EQUATIONS DIFFERENTIELLES ORDINAIRES

57

5.3.1. La méthode d’Euler

58

5.3.2. Méthodes de Runge-Kutta

59

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 5 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

1. INTRODUCTION AUX METHODES NUMERIQUES 1.1. INTRODUCTION A l'issue de cet enseignement, les étudiants pourront répondre aux questions suivantes:  Comment approximer ou interpoler une fonction ?  Comment trouver un minimum (ou un maximum) numériquement ?  Comment trouver la solution d'un problème linéaire ou non-linéaire ?  Comment intégrer ou dériver numériquement une fonction ?  Comment résoudre numériquement une équation différentielle ordinaire ?  Comment résoudre numériquement une équation aux dérivées partielles ?  Comment calculer les valeurs propres d'une matrice ? Comment estimer et mesurer la qualité d'une solution numérique ? L'objectif général du cours est l'acquisition de compétences de base en simulation numérique. Cela comporte trois aspects : 1. la maîtrise de méthodes numériques de base, accompagnée d'une compréhension des principes sous-jacents; 2. l'aptitude à l'esprit de rigueur afin de pouvoir valider et estimer la fiabilité d'un résultat numérique; 3. l'implémentation d'une méthode numérique. A l'issue de cet enseignement, les étudiants seront capables de:  distinguer entre réalité physique, modèle mathématique et solution numérique;  comprendre les méthodes numériques et leurs propriétés: précision, convergence, stabilité;  choisir une méthode en tenant compte d'exigences de précision et de complexité;  mettre en œœuvre une méthode numérique;  interpréter de manière critique des résultats obtenus sur un ordinateur. Le cheminement proposé insiste sur le caractère fortement multidisciplinaire des méthodes numériques: analyse, algèbre, algorithmique et implémentation informatique. Face à un problème concret, l'étudiant doit être à même de déterminer s'il convient d'utiliser une méthode numérique. Il doit aussi pouvoir choisir celle qui convient le mieux : conditions de convergence, caractéristiques de coût, de complexité et de stabilité. Il doit être capable d'utiliser ou de programmer des méthodes simples avec des logiciels numériques tels que MATLAB. 1.2. DÉSASTRES ET CALCUL NUMÉRIQUE Voici quelques exemples. de désastres qui ont eu pour cause une mauvaise compréhension et utilisation des algorithmes de calcul numérique. (extrait de la page web http://www.ima.umn.edu/∼arnold/disasters/)  L’erreur de fonctionnement du missile Patriote à Dharan, Arabie Saoudite, le 25 février 1991 qui a causé la mort de 28 soldats américains était la conséquence d’une erreur numérique.  L’explosion de la roquette Ariane 5 juste après son décollage en Guyane, le 4 juin 1996, fut la conséquence d’une erreur d’overflow.  L’échouement de la plate-forme pétrolière en Norvège le 23 août 1991, qui eut pour conséquence une perte d’un milliard de dollars, fut le résultat d’une simulation numérique imprécise.

1.3. PROBLÈMES NUMÉRIQUES L’analyse numérique traite de nombreux problèmes de sciences physiques, biologiques, technologiques ou des problèmes issus de modèles économiques et sociaux. Elle intervient dans le développement de codes de calcul (météorologie, physique des particules...), mais aussi dans les problèmes de simulations (aéronautique, industrie nucléaire...) ou d’expérimentations mathématiques. Elle entretient des liens étroits avec l’informatique. Si sa partie théorique relève plus des mathématiques, sa mise en pratique aboutit généralement à l’implémentation d’algorithmes sur ordinateur. Ses méthodes se fondent à la fois sur la recherche de solutions exactes comme dans le cas de l’analyse matricielle ou du calcul symbolique, sur des solutions approchées qui résultent le plus souvent de processus de Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 6 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

discrétisation comme dans le traitement des équations différentielles. Récemment, l’analyse numérique s’est enrichi des techniques probabilistes comme les méthodes de Monte-Carlo Définition de calcul numérique Nous proposons une définition formelle de calcul numérique basée sur la définition de Nick Trefethen (Oxford University):  

Le calcul numérique est une discipline qui traite de 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. Cette définition s’appuie sur plusieurs notions, comme celle de modèle, de problème et d’algorithme.

L’utilisation d’un modèle pour la résolution d’un problème pratique passe à travers la résolution d’un problème mathématique. Les modèles mathématiques continus prennent typiquement la forme d’un ensemble d’équations (algébriques ou différentielles) et/ou inéquations avec paramètres (connus et/ou inconnus) Généralités sur l’analyse numérique et le calcul scientifique L’analyse numérique (numerical analysis) est une branche des mathématiques appliquées s’intéressant au développement d’outils et de méthodes numériques pour le calcul d’approximations de solutions de problèmes de mathématiques qu’il serait difficile, voire impossible, d’obtenir par des moyens analytiques. Analyse numérique c’est l’étude et la construction d’algorithmes de résolution numérique d’un problème donné. En pratique, l’Analyse Numérique se propose d’étudier les propriétés mathématiques des algorithmes et leur mise en œuvre (programmation). Son objectif est notamment d’introduire des procédures calculatoires détaillées susceptibles d’être mises en œuvre par des calculateurs (électroniques, mécaniques ou humains) et d’analyser leurs caractéristiques et leurs performances, autrement dit, l’objectif de l’analyse numérique est de concevoir et d’e´tudier des me´thodes de re´solution de certains proble`mes mathe´matiques (en ge´ne´ral issus de la mode´lisation de proble`mes ‘re´els’), et dont on cherche a` calculer la solution ou son approximation a` l’aide d’un ordinateur. L’enjeu de l’analyse nume´rique est de re´soudre des proble`mes : – que l’on ne sait pas re´soudre autrement – ’mieux’ qu’on ne le faisait avant : – plus pre´cise´ment, – moins cher... – Plus vite :  complexite´ des algorithmes;  complexite´ des proble`mes – Plus pre´cis :  erreur d’arrondi (lie´es a` la machine);  erreur d’approximation (lie´es a` l’algorithme) – Plus fiable :  stabilite´ d’un algorithme – Facile a` programmer :  comprendre pour mieux réitiliser En Conclusion : l a confiance aveugle dans ce que l’on appelle les re´sultats fournis par l’ordinateur peut eˆtre la cause d’erreurs qui peuvent couˆ ter tre`s che`res Alors que faire ?

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 7 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

Différentes sources d’erreur dans une méthode numérique Les solutions de problèmes calculées par une méthode numérique sont affectées par des erreurs que l’on peut principalement classer en trois catégories :  les erreurs d’arrondi dans les opérations arithmétiques, qui proviennent des erreurs de représentation dues au fait que tout calculateur travaille en précision finie, c’est-à-dire dans un sous-ensemble discret du corps des réels R, l’arithmétique naturelle étant alors approchée par une arithmétique de nombres à virgule flottante; Les erreurs d’arrondi sont imposées par le calculateur, ces erreurs peuvent induire des problèmes de précision.  les erreurs sur les données, imputables à une connaissance imparfaite des données du problème que l’on cherche à résoudre, comme lorsqu’elles sont issues de mesures physiques soumises à des contraintes expérimentales ;  les erreurs de troncature, d’approximation ou de discrétisation, introduites par les schémas de résolution numérique utilisés (Erreur due à la méthode : algorithme). Comme par exemple:  le fait de tronquer le développement en série infinie d’une solution analytique pour permettre son évaluation;  Le fait d’arrêter un processus itératif dès qu’un itéré satisfait un critère donné avec une tolérance prescrite;  ou encore le fait d’approcher la solution d’une équation aux dérivées partielles en un nombre fini de points.  Si une fonction est approchée par son développement de Taylor, l’erreur de troncature sera obtenue par une évaluation du reste du développement.  Au voisinage d’un point a, si une fonction 𝑓 admet un développement de Taylor de la forme:

On peut également envisager d’ajouter à cette liste les erreurs qualifiées d’« humaines », telles:  les erreurs de programmation;  ou causées par des dysfonctionnements des machines réalisant les calculs. Le présent chapitre est en grande partie consacré aux erreurs d’arrondi, aux mécanismes qui en sont à l’origine, à leur propagation, ainsi qu’à l’analyse de leurs effets sur le résultat d’une suite de calculs. L’étude des erreurs de troncature, d’approximation ou de discrétisation constitue pour sa part un autre sujet majeur traité par l’analyse numérique. Si sophistiqué qu’il soit, un calculateur ne peut fournir que des réponses approximatives. Les approximations utilisées dépendent à la fois des contraintes physiques (espace mémoire, vitesse de l’horloge...) et du choix des méthodes retenues par le concepteur du programme. Le but de ce chapitre est de prendre connaissance de l’impact de ces contraintes et de ces choix méthodologiques. Dans certains cas il doit être pris en compte dans l’analyse des résultats dont une utilisation erronée pourrait être coûteuse. La première contrainte est que le système numérique de l’ordinateur est discret, c’est-à- dire qu’il ne comporte qu’un nombre fini de nombres; il en découle que tous les calculs sont entachés d’erreurs. 1.4. NOTIONS D’ERREUR ABSOLUE ET RELATIVE Pour mesurer l’erreur entre la solution fournie par une méthode numérique et la solution du problème que l’on cherche à résoudre (on parle encore d’estimer la précision de la méthode), on introduit les notions d’erreur absolue et relative. Soit 𝑥̂ une approximation d’un nombre réel x. On définit l’erreur absolue entre ces deux scalaires par |𝑥 − 𝑥̂|, et, lorsque x est non nul, l’erreur relative par

|𝑥 −𝑥̂| |𝑥|

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 8 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

De ces deux quantités, c’est souvent la seconde que l’on privilégie pour évaluer la précision d’un résultat, en raison de son invariance par changement d’échelle : la mise à l’échelle x → 𝛼x et 𝑥̂→𝛼𝑥̂, 𝛼 ≠ 0, laisse en effet l’erreur relative inchangée. Evaluation de l’erreur Rappelons d’abord quelques notions de base: −Si X est une quantité à calculer et X* la valeur calculée, on dit que : X−X* est l’erreur et |E|=|X −X*| est l’erreur absolue. Exemple : Si X = 2,224 et X* = 2,223, alors l’erreur absolue |E|=|X −X*| = 2,224 −2,223 = 0,001 Erreur relative 𝐸𝑟 =

|𝑋 −𝑋 ∗ | 𝑋𝑟

est l’erreur relative, avec Xr ≠ 0.

Xr est une valeur de référence pour X. En général, on prend Xr = X. Exemple : Si X = 2,224 et X* = 2,223 alors, si on prend Xr = X, l’erreur relative est: |𝑋 − 𝑋 ∗ | |𝑋 − 𝑋 ∗ | 0,001 𝐸𝑟 = = = = 4,496 ∗ 10−4 𝑋𝑟 𝑋𝑟 2,224 Cependant, si X est la valeur d’une fonction F(t) avec a ≤ t ≤ b, on choisira parfois une valeur de référence globale pour toutes les valeurs de t. Exemple : Si 𝑋 = 𝑠𝑖𝑛⁡(𝑡) avec 0 ≤ 𝑡 ≤ 𝜋⁄4 , on pourra prendre 𝑋𝑟 = √2⁄2 = 𝑠𝑢𝑝⁡𝑠𝑖𝑛⁡(𝑡)0 ≤ t ≤ π/4 . En général, on ne connait pas le signe de l’erreur de sorte que l’on considère les erreurs absolues et les erreurs relatives absolues. Propriétés de l’erreur Les opérations élémentaires propagent des erreurs. Dans la pratique, on considère que : 2. L’erreur absolue sur une somme est la somme des erreurs absolues; 3. L’erreur relative sur un produit ou un quotient est la somme des erreurs relatives. On peut estimer l’effet d’une erreur E sur l’argument x d’une fonction f (x) au moyen de la dérivée de f (x). En effet: 𝑓(𝑥 + 𝐸) ≅ 𝑓 (𝑥) + 𝐸𝑓′(𝑥) Exemple: Calculer la valeur de (11111111)2 La valeur fournie par une petite calculatrice à cinq chiffres est de 1,2345x1014 Mais la réponse exacte est 123456787654321. La machine a donc tronqué le résultat à 5 chiffres et l’erreur absolue est de 6∗109 L’erreur relative est de 0,005% L’exemple ci-haut montre qu’il faut établir clairement l’objectif visé. Cet objectif est double: 4. Nous voulons un bon ordre de grandeur (ici 1014) et avoir le maximum de décimales exactes; 5. Ce maximum ne peut excéder la longueur des mots permis par la machine et dépend donc de la machine 1.5. LA MÉMOIRE DE L’ORDINATEUR: LE STOCKAGE DES NOMBRES. • • •

La mémoire d’un ordinateur est formée d’un certain nombre d’unités adressables appelées OCTETS; Un ordinateur moderne contient des millions voir des milliards d’octets. Les nombres sont stockés dans un ordinateur comme ENTIERS ou REELS

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 9 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

Les nombres réels sont les éléments d’un corps archimédien complet totalement ordonné noté 5 ℝ, constitué de nombres dits rationnels, comme 76 ou − , et de nombres dits irrationnels, comme √2 4 ou 𝜋. On peut les représenter grâce à un système de numération positionnel relatif au choix d’une base.  Les nombres entiers :  sont ceux que l’on utilise d’habitude sauf que le plus grand nombre représentable dépend du nombre d’octets utilisés : - avec deux (2) octets, on peut représenter les entiers compris entre −32768 et 32767; - avec quatre (4) octets on peut représenter les entiers compris entre −2147483648 et 2147483647  Les nombres réels. - dans la mémoire d’un ordinateur, les nombres réels sont représentés en notation flottante; - cette notation a été introduite pour garder une erreur relative à peu près constante ; quel que soit l’ordre de grandeur du nombre qu’on manipule. - en notation flottante, un nombre a la forme :

𝑥 = ±𝑌 × 𝑏 𝑒 b est la base du système numérique utilisé Y est la mantisse : une suite de s entier 𝑦1 , 𝑦2 … 𝑦𝑆 avec 𝑦1 ≠ 0 𝑠𝑖 𝑥 ≠ 0 𝑒𝑡 0 ≤ 𝑦𝑖 ≤ (𝑏 − 1) 𝑒 est l’exposant (un nombre entier relatif) La norme choisie est celle où la mantisse est comprise entre 0 et 1 et où le premier chiffre après la virgule est différent de zéro La mise en œuvre d’une méthode numérique sur une machine amène un certain nombre de difficultés d’ordre pratique, qui sont principalement liées à la nécessaire représentation approchée des nombres réels en mémoire. Avant de décrire plusieurs des particularités de l’arithmétique à virgule flottante (floating-point arithmetic en anglais) en usage sur la majorité des ordinateurs et calculateurs actuels, les principes de représentation des nombres réels et de leur stockage en machine sont rappelés. Dans le système de numération, la représentation d’un nombre peut posséder une infinité de termes non triviaux, c’est notamment le cas pour les nombres irrationnels pour lesquels la representation est qualifiée d’infinie. Une telle représentation ne pouvant être écrite, on a coutume d’indiquer les chiffres omis par des points de suspension, par exemple 𝜋 = 14159265358979323846 …10 (en base 10). Par ailleurs, la représentation d’un nombre rationnel dans une base donnée est dite périodique lorsque l’écriture contient un bloc de chiffres se répétant à l’infini. On a, par exemple : 1 1 1 = 0,3333333333 …10 ;⁡⁡⁡ = 0,142857142857 …10 ⁡;⁡⁡⁡ = 0,5833333333333 …10 3 7 12 Il est possible de noter cette répétition de chiffres à l’infini en plaçant des points de suspension après plusieurs occurrences du bloc en question, comme on l’a fait ci-dessus. Cette écriture peut paraître claire lorsqu’une seule décimale est répétée une dizaine de fois, mais d’autres notations, plus explicites, font le choix de placer, de manière classique, la partie entière du nombre rationnel à gauche du séparateur et la partie fractionnaire non périodique suivie du bloc récurrent de la partie fractionnaire périodique, marqué d’un trait tiré au-dessus ou au-dessous ou bien placé entre crochets, à droite du séparateur. On a ainsi, pour les exemples précédents,

 En base 10, 𝑥 = 1/15 = 0,066666666 … - Dans le cas d’une représentation tronquée nous aurons, pour s = 5, 𝒇𝒍(𝒙) = 𝟎, 𝟔𝟔𝟔𝟔𝟔 ∗ 𝟏𝟎−𝟏 - Remarquez comment nous avons modifié l’exposant afin de respecter la règle qui veut que le premier chiffre de la mantisse ne soit pas nul. - Dans ce cas, l’erreur absolue 𝑋 − 𝑓𝑙(𝑋)𝑒𝑠𝑡 𝑑𝑒 6 × 10−7 L’erreur relative est de l’ordre de 10−5 Dans une représentation tronquée à ‘’s’’ chiffres, l’erreur relative maximale est de l’ordre de 10−s Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 10 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

• • -

Dans une représentation arrondie, lorsque la 1 ère décimale négligée est > 5, on ajoute 1 à la dernière décimale conservée. Exemple : En base 10, 𝑥 = 1/15 = 0,066666666 … Nous écrirons 𝒇𝒍(𝒙) = 𝟎, 𝟔𝟔𝟔𝟔𝟕 ∗ 𝟏𝟎−𝟏 L’erreur absolue serait alors 3,333 × 10−7 et l’erreur relative serait 5 × 10−5 .

En général, l’erreur relative dans une représentation arrondie à ‘’s’’ chiffres est de 6 × 10−(𝑠+1) soit la moitié de celle d’une représentation tronquée. 1.6. LES RÈGLES DE BASE DU MODÈLE. Pour effectuer une opération sur deux nombres réels, on effectue l’opération sur leurs représentations flottantes et on prend ensuite la représentation flottante du résultat. • l’addition flottante: 𝑥 ⊕ 𝑦 = 𝑓𝑙 (𝑓𝑙(𝑥) + 𝑓𝑙(𝑦)) • • •

la soustraction flottante: 𝑥 ⊝ 𝑦 = 𝑓𝑙(𝑓𝑙(𝑥) − 𝑓𝑙(𝑦)) la multiplication flottante: 𝑥 ⊗ 𝑦 = 𝑓𝑙(𝑓𝑙(𝑥) × 𝑓𝑙(𝑦)) la division flottante: 𝑥 ÷ 𝑦 = 𝑓𝑙(𝑓𝑙(𝑥)/𝑓𝑙(𝑦))

Chaque opération intermédiaire dans un calcul introduit une nouvelle erreur d’arrondie ou de troncature.  Quelques remarques sur ce modèle. • l’addition flottante n’est pas associative : x + (y + z) peut être différent de (x + y) + z. Exemple : Pour 4 chiffres significatifs (s = 4), on a : (1 + 0,0005) + 0,0005 = 1,000 car 0,1 × 101 + 0,5 ×10-3 = 0,1×101 + 0,00005×101 = 0,1×101 +0,0000 ×101 = 0,1×101 et 1 + (0,0005 + 0,0005) = 1 .001 On constate aussi que si y est très petit par rapport à x, l’addition de x et y donnera seulement x 1.7. CONDITIONNEMENT ET STABILITÉ NUMÉRIQUE. 1.7.1. Notion de conditionnement d’un problème. Le fait que certains nombres ne soient pas représentés de façon exacte dans un ordinateur entraine que l’introduction même de donnée d’un problème en machine modifie quelque peu le problème initial; Il se peut que cette petite variation des données entraine une variation importante des résultats On dit qu’un problème est bien (ou mal) conditionné, si une petite variation des données entraine une petite (une grande) variation sur les résultats. 1.7.2. Notion de stabilité numérique. Un problème peut être bien conditionné et la méthode utilisée pour le résoudre peut être sujette à une propagation importante des erreurs numériques La notion de conditionnement: liée au problème mathématique et indépendante de la méthode utilisée pour le résoudre tandis que la notion de stabilité numérique est liée à la méthode de résolution. 1.8. QUELQUES NOTIONS D’ALGORITHMIQUE Une méthode numérique repose sur l’emploi d’un (ou de plusieurs) algorithme(s) 1.8.1. Algorithme De manière informelle, on peut définir un algorithme comme un énoncé décrivant, à l’aide d’un enchaînement déterminé d’opérations élémentaires (par exemple arithmétiques ou logiques), une démarche systématique permettant la résolution d’un problème donné en un nombre fini ou infini d’étapes

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 11 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

Un exemple d’algorithme : l’algorithme d’Euclide, cet algorithme permet de déterminer le plus grand commun diviseur de deux entiers naturels. Il est basé sur la propriété suivante: on suppose que 𝑎⁡ ≥ ⁡𝑏 et on note ‘’r’’ le reste de la division euclidienne de a par b ; alors le plus grand commun diviseur de a et b est le plus grand commun diviseur de b et r. En pratique, on divise le plus grand des deux nombres entiers par le plus petit, puis le plus petit des deux par le reste de la première division euclidienne. On répète ensuite le procédé jusqu’à ce que le reste de la division, qui diminue sans cesse, devienne nul. Le plus grand commun diviseur cherché est alors le dernier reste non nul (ou le premier diviseur, si le premier reste est nul). La description d’un algorithme fait intervenir différentes structures algorithmiques, qui peuvent être des structures de contrôle relatives à l’enchaînement des opérations élémentaires (comme des instructions d’affectation ou conditionnelles, des boucles, des appels de fonctions, des commandes de saut, de sortie ou d’arrêt, etc...), ou bien des structures de données, qui vont contenir et organiser les données (sous forme de listes, de tableaux, d’arbres, de piles ou de files selon le problème considéré) afin d’en permettre un traitement efficace. Un algorithme est dit séquentiel lorsque les instructions qui le forment sont exécutées les unes après les autres. Il est dit parallèle lorsqu’elles s’exécutent concurremment. 1.8.2. Codage Le codage (on utilise aussi souvent l’anglicisme implémentation) d’un algorithme consiste en l’écriture de la suite d’opérations élémentaires le composant dans un langage de programmation. Une première étape en vue de cette tâche est d’écrire l’algorithme en pseudo-code, c’est-à-dire d’en donner une description compacte et informelle qui utilise les conventions structurelles des langages de programmation tout en s’affranchissant de certains détails techniques non essentiels à la bonne compréhension de l’algorithme, tels que la syntaxe, les déclarations de variables, le passage d’arguments lors des appels à des fonctions ou des routines externes, etc... À ce titre, les algorithmes 1 et 2 ci-après proposent deux manières de calculer un produit de matrices rectangulaires compatibles. Algorithme 1: Algorithme pour le calcul du produit C = AB des matrices A de Mm,p (ℝ) et B de Mp,n (ℝ) Entrée(s) : les tableaux contenant les matrices A et B. Sortie(s) : le tableau contenant la matrice C. pour 𝑖⁡ = ⁡1⁡à⁡𝑚 faire pour j = 1 à n faire 𝐶(𝑖, 𝑗) ⁡ = ⁡0 pour 𝑘⁡ = ⁡1⁡à⁡𝑝 faire 𝐶(𝑖, 𝑗) ⁡ = ⁡𝐶(𝑖, 𝑗) ⁡ + ⁡𝐴(𝑖, 𝑘) ⁡ ∗ ⁡𝐵(𝑘, 𝑗) fin fin fin N.B.: On notera en particulier que le signe = en pseudo-code ne représente pas l’égalité mathématique, mais l’affectation de la valeur d’une variable à une autre. Pour chaque problème posé de façon mathématique, il peut exister plusieurs algorithmes le résolvant. Certains se distinguent par la nature et/ou le nombre des opérations élémentaires qui les constituent, alors que d’autres vont au contraire effectuer strictement les mêmes opérations élémentaires en ne différant que par la façon d’enchaîner ces dernières. Afin d’illustrer ce dernier point, comparons les algorithmes1et 2. On remarque tout d’abord qu’ils ne se différencient que par l’ordre de leurs boucles, ce qui ne change évidemment rien au résultat obtenu. D’un point de vue informatique cependant, on voit qu’on accède aux éléments des matrices A et B selon leurs lignes ou leurs colonnes, ce qui ne se fait pas à la même vitesse selon la manière dont les matrices sont stockées dans la mémoire. En particulier, la boucle interne de l’algorithme1 correspond à un produit scalaire entre une ligne de la matrice A et une colonne de la matrice B. Dans chacun de ces deux algorithmes présentés, on peut encore modifier l’ordre des boucle en i et j pour obtenir d’autres implémentations parmi les six qu’il est possible de réaliser.

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 12 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

Algorithme 2: Algorithme pour le calcul du produit C = AB des matrices A de Mm,p (ℝ) et B de Mp,n (ℝ) Entrée(s) : les tableaux contenant les matrices A et B. Sortie(s) : le tableau contenant la matrice C. pour 𝑖⁡ = ⁡1⁡à⁡𝑚 faire pour j = 1 à n faire 𝐶(𝑖, 𝑗) ⁡ = ⁡0 fin fin pour 𝑘⁡ = ⁡1⁡à⁡𝑝 faire pour 𝑖⁡ = ⁡1⁡à⁡𝑚 faire pour j = 1 à n faire 𝐶(𝑖, 𝑗) ⁡ = ⁡𝐶(𝑖, 𝑗) ⁡ + ⁡𝐴(𝑖, 𝑘) ⁡ ∗ ⁡𝐵(𝑘, 𝑗) fin fin fin 1.8.3.

Efficacité et complexité

Tout calculateur est soumis à des limitations physiques touchant à sa capacité de calcul, c’està-dire le nombre maximal d’opérations élémentaires, arithmétiques ou logiques, pouvant être effectuées à chaque seconde, ainsi qu’à la mémoire disponible, c’est-à-dire la quantité d’information à disposition ou à laquelle il est possible d’accéder à tout moment en un temps raisonnable. Typiquement, le temps d’exécution d’un algorithme mis en œuvre sur une machine informatique pour la résolution d’un problème dépendra : - de la qualité du codage de l’algorithme dans un langage de programmation et de l’optimisation du code en langage machine du programme exécutable généré par le compilateur à partir de l’analyse du code source; - de l’organisation et de l’architecture des unités de calcul, ainsi que de la répartition de la mémoire de la machine; - des données du problème; - de la complexité de l’algorithme. Pour mesurer l’efficacité d’un algorithme en s’affranchissant des facteurs matériels et de l’instance du problème considéré, on a coutume d’utiliser sa seule complexité. Celle-ci est le plus souvent donnée par le nombre d’opérations de base que l’on doit effectuer (on parle alors de complexité temporelle) et la quantité de mémoire requise (on parle dans ce cas de complexité spatiale) pour résoudre un problème dont les données sont de taille fixée. Évidemment, le type des opérations de base peut varier d’un problème à l’autre; par exemple, ce seront essentiellement des opérations arithmétiques (addition, soustraction, multiplication, division, etc...), pour des applications en calcul scientifique, mais, comme pour un tri de données, il pourra aussi s’agir d’une comparaison ou d’un déplacement d’éléments. De la même manière, la mesure de la taille des données doit refléter la quantité, la nature et la structure de l’information manipulée. Par exemple, pour des opérations sur les matrices, on emploie le (ou les) entier(s) donnant la taille des matrices en jeu; dans le cas d’un graphe, ce sont les nombres de sommets ou de nœuds et d’arêtes ou d’arcs que l’on utilise.

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 13 / 63

Cours de Méthodes Numériques Introduction aux méthodes numériques

2. RESOLUTION D’UNE EQUATION f(x) = 0 2.1. INTRODUCTION Si une équation algébrique ou transcendante est suffisamment complexe, il est relativement rare qu’on obtienne ses racines avec précision. D’autre part, dans certains cas les coefficients de l’équation ne sont connus qu’approximativement et par conséquent, le problème de la détermination précise des racines proprement dit perd son sens. C’est pourquoi les méthodes de la recherche approchée des racines et l’estimation du degré de leur précision s’avèrent indispensables. Soit f une fonction numérique d’une variable réelle. On cherche les racines simples de l’équation 𝑓 (𝑥) = 0 (1) où la fonction 𝑓(𝑥) est définie dans un certain intervalle fini ou infini 𝑎 < 𝑥 < 𝑏 ou 𝑎 ≤ 𝑥 ≤ ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝑏  Séparation des racines Toute valeur « 𝑟 » qui annule la fonction 𝑓(𝑥) c’est-à-dire 𝑓(𝑟) = 0 s’appelle racine de l’équation (1) ou zéro de la fonction 𝑓(𝑥). Supposons aussi que la fonction 𝑓(𝑥) = 0 n’admet que des racines isolées, c’est-à-dire pour chaque racine de l’équation, il existe un voisinage qui ne contient pas d’autres racines de cette équation. • Isoler les racines, c’est-à-dire trouver un intervalle [a, b] dans lequel « 𝑟 » est l’unique racine réelle de (1). • Pour trouver cet intervalle, on recourt au théorème des valeurs intermédiaires : – Si 𝑓(𝑎) ∗ 𝑓(𝑏) < 0: 𝑓 admet un nombre impair de racines; – Si 𝑓(𝑎) ∗ 𝑓(𝑏) > 0: 𝑓 admet un nombre pair de racines.  La recherche approchée des racines réelles isolées de l’équation 𝑓 (𝑥) = 0 se fait en général en deux étapes : 1. Séparation des racines : elle consiste à établir des segments [α,] les plus serrés possibles contenant une et seulement une racine de l’équation (1); y 𝑦⁡ = ⁡𝑓(𝑥)

𝑎

r2

r1 𝑎1

𝑏1

𝑎2

r3 𝑏2

𝑎3

x 𝑏3

𝑏

2. Amélioration de la précision ou mise au point des racines approchées, c’est-à-dire l’obtention de leur précision imposée. Exemple : 𝑓 ′ (𝑥) = 1 +

2𝑒 𝑥 (𝑒 𝑥 −2)2

donc 𝑓 ′ (𝑥) > 0 pour tout x.

L’´équation a donc 2 racines simples situées de chaque côté de ln(2) On vérifie sans problème qu’une première racine appartient à [-1, 0] et la deuxième à [1, 2] On supposera donc désormais avoir trouvé un intervalle [a, b] où 𝑓 admet une unique racine simple et on supposera que 𝑓 est définie, continue, et autant de fois continument dérivable que nécessaire. DEFINITION 1. Nous appellerons algorithme toute méthode de résolution d’un problème donné. Pour tout problème, nous avons des données et des résultats. – Les données sont appelées paramètres d’entrée (input) Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 14 / 63

Cours de Méthodes Numériques Résolution d’une équation f(x)=0

– les résultats paramètres de sortie (output). Ils constituent l’interface de l’algorithme. Les algorithmes classiques que nous allons étudier sont les suivants : (1) Méthodes d’encadrement: méthode de la dichotomie et méthode regula falsi ; (2) Méthodes du point fixe: méthode de Newton-Raphson et méthode de Steffensen ; (3) Méthodes de la sécante et variantes: méthode de la sécante et méthode de Muller. (4)

2.2. ÉQUATIONS ALGÉBRIQUES La théorie des équations algébriques repose sur le théorème fondamental de l’algèbre qui assure l’existence de solutions. Ce théorème encore appelé théorème de d’Alembert affirme que l’équation algébrique 𝑃(𝑥) ⁡ = ⁡0 où P est un polynôme de degré 𝑛 admet exactement 𝑛 racines distinctes ou non, réelles ou complexes, et dans le cas complexe, deux à deux conjuguées. Depuis l’Antiquité, l’homme a cherché des formules explicites donnant les valeurs des racines en

𝑥 2 − 𝑝𝑥 + 𝑞 = 0 qui admet si 𝑝2 − 4𝑞 > 0, 2 racines réelles 𝑥1 ⁡𝑒𝑡⁡⁡𝑥2 vérifiant 𝑝 = 𝑥1 + ⁡⁡ 𝑥2 et 𝑞 = 𝑥1 ∗ ⁡ 𝑥2 fonction des coefficients du polynôme 𝑃(𝑥) à l’image de l’équation du second degré

L’équation générale du troisième degré exprimée sous forme alternée : 𝑥 3 − 𝑎𝑥 2 + 𝑏𝑥 − 𝑐 = 0 admet dans certains cas trois racines 𝑥1 , 𝑥2 , 𝑥3 qui vérifient 𝑎 = 𝑥1 + ⁡⁡ 𝑥2 + 𝑥3 , 𝑏 = 𝑥1 𝑥2 + ⁡⁡𝑥2 𝑥3 + 𝑥1 𝑥3 et 𝑐 = 𝑥1 𝑥2 𝑥3 . On démontre que cette équation se ramène par un changement de variable (⁡𝑋⁡ = 𝑥⁡– ⁡𝑎/3) à une équation du type

𝑥 3 + 𝑝𝑥 + 𝑞 = 0

∆= 4𝑝3 + 27𝑞 2 est positif, trois racines distinctes données par les formules de Cardan 1 1 1 𝑥1 = (𝑢 + 𝑣)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝑥2 = (𝑗𝑢 + 𝑗 2 𝑣)⁡⁡⁡⁡𝑒𝑡⁡⁡⁡𝑥3 = (𝑗 2 𝑢 + 𝑗𝑣) 3 3 3 avec 𝑗 2 = 1 et 𝑢 et 𝑣 étant données par Elle admet si

Si ∆⁡> 0, alors 𝐴 = √∆⁡ 𝜇 est différent de 𝑣. Les racines𝑥2⁡ et 𝑥3⁡ sont imaginaires conjuguées. 𝑥1⁡ est la seule racine réelle qui s’exprime à l’aide de radicaux réels. En revanche, si ∆⁡< 0, alors 𝐴 = 𝑖√−∆⁡, 𝜇 = 𝑣̅ . Les 3 racines sont réelles, mais l’expression qui est sous la racine cubique est complexe. Dans ce cas, il est important d’exprimer les racines de l’équation sous forme de radicaux réels. C’est Girolamo Cardano (Cardan) qui donna en 1545 les formules de résolution de cette équation L’équation du quatrième degré a été résolue par Luigi Ferrari, un disciple de Cardan. Exprimée sous forme alternée, l’équation ⁡ 𝑥4 − 𝑎𝑥3 + 𝑏𝑥2 − 𝑐𝑥 + 𝑑 = 0

Cette équation se résout comme une équation du second degré lorsque 𝑞 = 0. Dans le cas contraire, Ferrari propose de l’exprimer sous la forme: 1 1 (𝑥 2 + 𝑦)2 = (𝑦 − 𝑝)𝑥 2 − 𝑞𝑥 + 𝑦 2 − 𝑟 2 4

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 15 / 63

Cours de Méthodes Numériques Résolution d’une équation f(x)=0

Et de déterminer y de telle sorte que le deuxième membre soit un carré du type (𝑚𝑥 + 𝑛)2 . Pour cela, on démontre 1 qu’il faut et il suffit que le discriminant 𝑞 2 − 4 ( 𝑦 2 − 𝑟) soit nul, autrement dit que 𝑦 vérifie l’équation du 4 troisième degré, appelée résolvante. 𝑦 3 − 𝑝𝑦 2 − 4𝑟𝑦 + 4𝑝𝑟 − 𝑞 2 = 0 Ainsi, la résolution d’une équation du quatrième degré se ramène à la résolution d’une équation du troisième degré. L’équation générale de degré supérieur ou égal à 5 n’est pas résoluble par radicaux. 2.3. LES ALGORITHMES CLASSIQUES 2.3.1 Localisation des racines En pratique, la mise en œuvre d’un algorithme de recherche de solution d’équations suppose que nous connaissons une région dans laquelle se trouve cette solution. La théorie donne quelques critères de localisation lorsque l’équation est une équation polynomiale. Le théorème de Rolle (1690) affirme qu’entre deux racines de l’équation 𝑃(𝑥) = 0 où 𝑃 est un polynôme, il existe au moins une racine de l’équation dérivée 𝑃’(𝑥) = 0. La règle de Descartes affirme que le nombre de racines positives d’un polynôme: 𝑃(𝑥) = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑛 𝑥 𝑛 est inférieur au nombre de changements de signes de la suite (𝑎0 , 𝑎1 , 𝑎2 , … , 𝑎𝑛 ) Le théorème de Sturm (1829) donne un algorithme pour déterminer le nombre de racines d’un polynôme entre deux réels. Soit 𝑎 et 𝑏 deux nombres réels 𝑎 < 𝑏 et 𝑃 un polynôme de degré 𝑛 n’ayant que des racines simples. On note 𝑃0⁡ = ⁡𝑃, 𝑃1 = ⁡𝑃’, 𝑃2⁡ = ⁡𝑄2𝑃1 − 𝑃0 l’opposé du reste de la division euclidienne de 𝑃0 par 𝑃1, ..., et 𝑃𝑖 + 2⁡ = ⁡𝑄𝑖 + 2⁡𝑃𝑖 + 1⁡– 𝑃𝑖 l’opposé du reste de la division euclidienne de⁡𝑃𝑖 par 𝑃𝑖 + 1. On considère 𝑃𝑖⁡(𝑎) la suite 𝑃0(𝑎)⁡𝑃1(𝑎), … , 𝑃𝑛(𝑎) et 𝑃𝑖⁡(𝑏) la suite 𝑃0(𝑏)⁡𝑃1(𝑏), … , 𝑃𝑛(𝑏) et on suppose que 𝑃0(𝑎) ≠ 0, 𝑃1(𝑎) ≠ 0. Le nombre de racines réelles de P(x) comprises entre 𝑎 et 𝑏 est égal au nombre de changements de signes que présente la première suite diminué de celui que présente la deuxième suite. Ce nombre est égal à l’indice de 𝑃’/𝑃 entre 𝑎 et 𝑏. 2 𝑏 ′′ 𝑃′ 𝑃 𝑃 − 𝑃′ 𝑃′ (𝑏) 𝑃′ (𝑎) −𝜋𝐼 ( , 𝑎, 𝑏) = ∫ 𝑑𝑥 − 𝐴𝑟𝑐𝑡𝑔 ( ) + 𝐴𝑟𝑐𝑡𝑔 ( ) ′2 2 𝑃 𝑃(𝑏) 𝑃(𝑎) 𝑎 𝑃 +𝑃 Exemple. Soit 𝑃(𝑥) = 𝑥 3 − 𝑥 un polynôme de degré 3. 𝑃 admet trois racines distinctes (𝑥⁡ = ⁡1, 0, 1). Cherchons le nombre de racines de 𝑃 dans l’intervalle [−2, 2]. La suite de Sturm s’écrit 𝑃0 (𝑥) = 𝑥 3 − 2 𝑥, 𝑃1 (𝑥) = 3𝑥 2 − 1, 𝑃2 (𝑥) = 𝑥 et 𝑃3⁡(𝑥) = 1 Les différentes valeurs de 𝑃𝑖(𝑥) aux points 𝑎⁡ = ⁡ −⁡2 et 3 𝑏 = 2⁡sont résumées dans le tableau suivant : 𝑥 3 − 𝑥⁡ 3𝑥 2 − 1 1 1 − (𝑥 3 − 𝑥)⁡ 𝑥 3

3

2

− 𝑥 = Reste de la division euclidienne de 3

3𝑥 2 − 1⁡ ⁡−(3𝑥 3 − 0)⁡

2 3 9 2

𝑃0 par 𝑃1 et son opposé vaut 𝑃2 (𝑥) = 23 𝑥

𝑥 𝑥

−1 = Reste de la division euclidienne de x -2 2

P0 -6 6

𝑃1 par 𝑃2 et son opposé vaut 𝑃3 (𝑥) = 1 P1 11 11

P2 -4/3 4/3

P3 1 1

La suite 𝑃𝑖(−2) change trois fois de signe et la suite 𝑃𝑖(2) reste constante. L’indice est donc égal à 3⁡ − ⁡0 = 3. Le polynôme 𝑃(𝑥) admet donc trois racines réelles dans l’intervalle [−2⁡2]. Ce calcul peut aussi s’effectuer en intégrant l’expression ci-dessus, soit : −𝜋𝐼 (

𝑃′ 3𝑏 2 − 1 3𝑎2 − 1 , 𝑎, 𝑏) = 𝑢(𝑏) − 𝑢(𝑎) − 𝐴𝑟𝑐𝑡𝑔 ( 3 ) + 𝐴𝑟𝑐𝑡𝑔 ( 3 ) 𝑃 𝑏 −𝑏 𝑎 −𝑎

avec Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 16 / 63

Cours de Méthodes Numériques Résolution d’une équation f(x)=0 3

7

25

1

1

𝑢(𝑡) = 𝐴𝑟𝑐𝑡𝑔 (11𝑡 3 + 𝑡 5 − 𝑡) − 𝐴𝑟𝑐𝑡𝑔 ( 𝑡 + 𝑡 3 ) − 𝐴𝑟𝑐𝑡𝑔 ( 𝑡) 2 2 6 2 3 En remplaçant 𝑎 et 𝑏 par leurs valeurs, on retrouve la valeur précédente 𝐼 = 3. 2.3.2 Approximations successives Une des méthodes, parmi les plus importantes, de résolution numérique des équations est la méthode des approximations successives dite également méthodes des itérations. Dans les méthodes d’approximations successives, l’équation 𝑓(𝑥) = 0 est remplacée par l’étude d’une suite numérique convergente: 𝑥𝑛+1 = 𝜑(𝑥𝑛 ) qui permet d’obtenir en un nombre fini d’itérations une solution approchée de l’équation. En général, on prend 𝜑(𝑥𝑛 ) = 𝑥 − 𝑐𝑓(𝑥). Dans la méthode de Lagrange, on remplace la fonction par le segment de droite passant par les points (𝑎, 𝑓(𝑎)) et (𝑏, 𝑓(𝑏)) 𝑥−𝑎 𝜑(𝑥𝑛 ) = 𝑎 − 𝑓(𝑎) 𝑓(𝑥) − 𝑓(𝑎) Dans la méthode de Newton, on remplace la fonction 𝑓 entre les points d’abscisse a et b par la tangente à la courbe en ces points 𝑓(𝑥) 𝜑(𝑥𝑛 ) = 𝑥 − 𝑓′(𝑥) 2.3.3 Méthodes d’encadrement Cette première classe de méthodes repose sur la propriété fondamentale suivante, relative à l’existence d’un zéro pour une application d’une variable réelle à valeurs réelles. THEOREME: (existence d’un zéro d’une fonction à valeurs réelles continue) Soit [𝑎, 𝑏] un intervalle non vide de ℝ et 𝑓 une application continue de [𝑎, 𝑏] dans ℝ vérifiant⁡𝑓(𝑎)𝑓(𝑏) ⁡ < ⁡0. Alors il existe 𝜉 ∈ ]𝑎, 𝑏[ tel que 𝑓(𝜉) ⁡ = ⁡0. CONVERGENCE ET ORDRE DE CONVERGENCE.  Convergence d’une méthode itérative Afin de pouvoir évaluer à quelle « vitesse» la suite construite par une méthode itérative converge vers sa limite (ce sera souvent l’un des critères discriminants pour le choix d’une méthode), il nous faut introduire quelques définitions. DEFINITION 1: Soit 𝐷 une partie de ℝ et 𝐹 une application de 𝐷 dans 𝐷. On dit que la fonction 𝐹 est contractante si ∀𝑥, 𝑦 ∈ 𝐷, ⁡𝑘 ∈ [0, 1[ tel que ⃓𝐹(𝑥) − 𝐹(𝑦)⃓ ≤ 𝑘⃓𝑥 = 𝑦⃓ 𝑘 est le coéfficient de contraction ou de Lipschitz de 𝐹. THEOREME 1: Considérons le segment 𝑆⁡ = ⁡ [𝑥0 − ⁡𝑎, 𝑥0 + ⁡𝑎] ⁡ ⊂ ⁡𝐷; si 𝐹 est contractante sur 𝑆 et si |⁡𝐹(𝑥0)⁡– 𝑥0| ≤ ⁡ (1⁡ − ⁡𝑘)⁡𝑎, alors l’itération 𝑥𝑛 + 1 = ⁡𝐹(𝑥𝑛) de point initial 𝑥0, converge vers l’unique point fixe 𝑥⁡ ∈ ⁡𝑆 de 𝐹. THEOREME 2: Si 𝐹 est différentiable au voisinage d’un point fixe 𝑥 et si |⁡𝐹’(𝑥)⁡| < ⁡1 alors: ∃𝑉 voisinage de 𝑥 tels que 𝑥0⁡ ∈ ⁡𝑉 et 𝑥𝑛 + 1 = ⁡𝐹(𝑥𝑛)⁡converge vers 𝑥.  Ordre de convergence d’une méthode itérative DEFINITION 2: Considérons une suite {xn} convergeant vers x et posons en = xn - x. On dit dans le cas 𝑒 où {| 𝑛 |} converge, que la suite xn converge linéairement vers x ou encore que la méthode est du 𝑒𝑛−1

𝑒𝑛 𝑘 𝑛−1 )

premier ordre. Si on a {|(𝑒

|} converge, alors la convergence est dite d’ordre k

Soit une suite (𝑥𝑛)𝑛∈ℕ de réels convergeant vers une limite 𝜉. On dit que cette suite est convergente d’ordre 𝑟⁡ ≥ 1, s’il existe deux constantes 0⁡ < ⁡ 𝐶1 ⁡ ≤ 𝐶2 < +∞ et un entier naturel 𝑛0 tels que |𝑥𝑛+1 − 𝜉| ∀𝑛 ∈ ℕ, 𝑛 ≥ 𝑛0 ⇒ 𝐶1 ≤ ≤ 𝐶2 |𝑥𝑛 − 𝜉|𝑟

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 17 / 63

Cours de Méthodes Numériques Résolution d’une équation f(x)=0

Par extension, une méthode itérative produisant une suite convergente vérifiant les relations ci-dessus sera également dite d’ordre r. DEFINITION 3: Soit une suite (𝑥𝑛 )𝑛∈ℕ de réels convergeant vers une limite 𝜉. On dit que cette suite est convergente d’ordre 𝑟⁡ > 1) vers 𝜉 s’il existe un réel 𝑢 > 0, appelé constante asymptotique d’erreur, tel que: |𝑥𝑛+1 − 𝜉| lim =𝜇 𝑥→+∞ |𝑥𝑛 − 𝜉|𝑟 Dans le cas particulier où r = 1, on dit que la suite converge linéairement si |𝑥𝑛+1 − 𝜉| lim = 𝜇, 𝑎𝑣𝑒𝑐⁡𝜇 ∈ ]0,1[ 𝑥→+∞ |𝑥𝑛 − 𝜉|𝑟 et super-linéairement (respectivement. sous-linéairement) si l’égalité ci-dessus est vérifiée avec 𝜇⁡ = ⁡0 (respectivement. 𝜇⁡ = ⁡1) 2.3.3.1 Méthode de la bissection ou méthode de dichotomie Dans la méthode de dichotomie ou méthode de la bissection ou de la bipartition (une des méthodes d’encadrement), l’intervalle de recherche de la solution est coupé en deux à chaque pas d’itération. On détermine progressivement un intervalle de plus en plus fin dans lequel se trouve la solution cherchée. Soit 𝑓 une fonction numérique strictement monotone sur un intervalle [𝑎, 𝑏]. On suppose que l’équation 𝑓(𝑥) ⁡ = ⁡0 n’a qu’une et une seule solution dans cet intervalle. On se propose de déterminer cette valeur 𝑢 avec une précision donnée. Soit [𝑎0 , 𝑏0 ]⁡un intervalle dans lequel 𝑓(𝑎0 )𝑓(⁡𝑏0 ) < 0. On note 𝑐0 = (𝑎0 + ⁡ 𝑏0 )/2⁡ le centre de l’intervalle. Si 𝑓(⁡𝑐0 )𝑓(𝑎0 ) < 0 alors la racine 𝑢 appartient à l’intervalle [𝑎0 , 𝑐0 ]. On reprend le procédé avec 𝑎1 = 𝑎0 ⁡𝑒𝑡⁡𝑏1 = ⁡ 𝑐0 . Sinon, c’est-à-dire si 𝑓(⁡𝑐0 )𝑓(𝑎0 ) > 0 on pose 𝑎1 = 𝑐0 ⁡𝑒𝑡⁡𝑏1 = ⁡ 𝑏0 . On construit ainsi une suite d’intervalles emboîtés [𝑎𝑛 , 𝑏𝑛 ] de longueur (𝑎0 + ⁡ 𝑏0 )/2𝑛 Les suites 𝑎𝑛 et ⁡𝑏𝑛 ⁡sont adjacentes et convergent vers 𝑢. Fig.: Construction des premiers itérés de la méthode de dichotomie : illustration de la construction des approximations du zéro produites par cette méthode.

Bref, il faut : 1. localiser ou chercher un intervalle [a, b] dans lequel la fonction change de signe; 𝑎+𝑏 2. on pose 𝑐⁡ = ; 2 - si f(a) * f(c) < 0 on remplace b par c ; - sinon on remplace a par c ; 3. on continue cette opération jusqu’à ce qu’on trouve la racine 𝑢 avec la précision demandée.

Le but de la méthode est de trouver une approximation de la solution de f(x) = 0 dans [a, b]. En construisant une suite d’intervalles ([𝑎𝑛 ⁡ + ⁡ 𝑏𝑛 ]) contenant la racine et tels que 𝑎𝑛 ⁡𝑜𝑢⁡𝑏𝑛 est le milieu de l’intervalle [𝑎𝑛−1 ⁡ + ⁡ 𝑏𝑛−1 ] ALGORITHME.3 : Entrée(s) : a, b, , N0. Sortie(s) : la valeur approchée 𝑢:⁡𝑓(𝑢) ⁡ = ⁡0. (1) si 𝑓(𝑎) ⁡ = ⁡0 imprimer la solution est 𝑎. Si 𝑓(𝑏) ⁡ = ⁡0 imprimer la solution est 𝑏, aller à 10 (2) si 𝑓(𝑏) ⁡ ∗ ⁡𝑓(𝑎) ⁡ > ⁡0, imprimer (pas de changement de signe). Aller `a 10 (3) poser N = 1 (4) Tant que N < N0, faire les étapes 5 à 8 𝑎+𝑏 (5) poser 𝑢⁡ = 2

𝑏−𝑎

(6) Si 𝑓(𝑝) ⁡ = ⁡0 ou ≤∈, imprimer p. Aller à 10 2 (7) poser N = N + 1 (8) Si 𝑓(𝑎) ∗ ⁡𝑓(𝑝) ⁡ > ⁡0, alors poser 𝑎⁡ = ⁡𝑝, sinon poser 𝑏⁡ = ⁡𝑝 (9) Imprimer après N0 itérations l’approximation obtenue est p et l’erreur maximale est (10)Fin Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

𝑏−𝑎 2

Page 18 / 63

Cours de Méthodes Numériques Résolution d’une équation f(x)=0

 (la précision désirée) et N0 (le nombre maximum d’itérations) Exemple d’application de la méthode de dichotomie. On utilise la méthode de dichotomie pour approcher la racine du polynôme 𝑓(𝑥) = ⁡ 𝑥 3 + 2𝑥 2 − 3𝑥 − 1 contenue dans l’intervalle [1, 2] (on a en effet 𝑓(1) = ⁡ −1 et 𝑓(2) ⁡ = ⁡9),avec une précision égale à 10-4. Le tableau ci-dessous donne les valeurs respectives des bornes 𝑎𝑛 de 𝑏𝑛 l’intervalle d’encadrement, de l’approximation 𝑥(𝑛) de la racine et de 𝑓(𝑥𝑛 ) en fonction du numéro n de l’itération. Concernant la convergence de la méthode de dichotomie, on a le résultat suivant, dont la preuve est laissée en exercice. Soit [𝑎, 𝑏] un intervalle non vide de ℝ et 𝑓 une fonction réelle continue sur [𝑎, 𝑏], vérifiant 𝑓(𝑎)𝑓(𝑏) < 0 et possédant un unique zéro 𝜉⁡dans ]𝑎, 𝑏[. Alors, la suite (𝑥𝑛 )𝑛∈ℕ construite par la méthode de dichotomie converge vers 𝜉 et on a l’estimation: 𝑏−𝑎 ∀𝑛⁡ ∈ ℕ, |𝑥𝑛 − 𝜉| ≤ 𝑛+1 2 TABLE: Tableau récapitulatif du déroulement de la méthode de dichotomie pour l’approximation (avec une précision égale à 10-4 ) de la racine du polynôme 𝑓(𝑥) = ⁡ 𝑥 3 + 2𝑥 2 − 3𝑥 − 1 contenue dans [1, 2]. n 𝑎𝑛 𝑏𝑛 𝑥𝑛 𝑓(𝑥𝑛 ) 0 1 2 1,5 2,375 1 1 1,5 1,25 0,328125 2 1 1,25 1,125 - 0,419922 3 1,125 1,25 1,1875 - 0,067627 4 1,1875 1,25 1,21875 - 0,124725 5 1,1875 1,21875 1,203125 0,02718 6 1,1875 1,203125 1,195312 - 0,020564 7 1,195312 1,203125 1,199219 0,003222 8 1,195312 1,199219 1,197266 - 0,008692 9 1,197266 1,199219 1,198242 - 0,00274 10 1,198242 1,199219 1,19873 0,000239 11 1,198242 1,19873 1,198486 - 0,001251 12 1,198486 1,19873 1,198608 0,000506 13 1,198608 1,19873 1,198609 - 0,000133 Il ressort de cette proposition que la méthode de dichotomie converge de manière certaine: c’est une méthode globalement convergente. L’estimation d’erreur fournit par ailleurs directement un critère d’arrêt pour la méthode, puisque, à précision ‘𝜀′ donnée, cette dernière permet d’approcher 𝜉 en un nombre prévisible d’itérations. On voit en effet que, pour avoir |𝑥𝑛 − 𝜉| ≤ 𝜀, il faut que: 𝑏−𝑎 𝑙𝑛 ( ) 𝑏−𝑎 𝜀 ∀𝑛⁡ ∈ ℕ, ≤ 𝜀 ⇔ 𝑛 ≥⁡ −1 𝑛+1 2 𝑙𝑛2 2.3.3.2 Méthode de la fausse position La méthode de la fausse position (false-position method en anglais), encore appelée méthode regula falsi, est une méthode d’encadrement combinant les possibilités de la méthode de dichotomie avec celles de la méthode de la sécante. L’idée est d’utiliser l’information fournie par les valeurs de la fonction 𝑓⁡aux extrémités de l’intervalle d’encadrement pour améliorer la vitesse de convergence de la méthode de dichotomie (cette dernière ne tenant compte que du signe de la fonction). Cette méthode suppose connus deux points a et b vérifiant 𝑓(𝑎)𝑓(𝑏) ⁡ < ⁡0 et servant d’initialisation à la suite d’intervalles [𝑎𝑛 ; ⁡𝑏𝑛 ], 𝑛⁡ ≥ ⁡0, contenant un zéro de la fonction 𝑓. Le procédé de construction des intervalles emboîtés est alors le même pour la méthode de dichotomie, à l’exception du choix de 𝑥𝑛 , qui est à présent donné par l’abscisse du point d’intersection de la droite passant par les points (𝑎, 𝑓(𝑎)) et (𝑏, 𝑓(𝑏)) avec l’axe des abscisses, c’est-à-dire

𝑥𝑛 = 𝑎𝑛 −

𝑎𝑛 − 𝑏𝑛 𝑏𝑛 − 𝑎𝑛 𝑓(𝑎𝑛 )𝑏𝑛 − 𝑓(𝑏𝑛 )𝑎𝑛 𝑓(𝑎𝑛 ) = 𝑏𝑛 − 𝑓(𝑏𝑛 ) = 𝑓(𝑎𝑛 ) − 𝑓(𝑏𝑛 ) 𝑓(𝑏𝑛 ) − 𝑓(𝑎𝑛 ) 𝑓(𝑎𝑛 ) − 𝑓(𝑏𝑛 )

La détermination de l’approximation du zéro à chaque étape repose donc sur un procédé d’interpolation linéaire de la fonction 𝑓⁡entre les bornes de l’intervalle d’encadrement. Par conséquent, le zéro est obtenu après une seule itération si 𝑓 est une fonction affine, contre a priori une infinité pour la méthode de dichotomie.

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 19 / 63

Cours de Méthodes Numériques Résolution d’une équation f(x)=0

THEOREME Soit [𝑎, 𝑏] un intervalle non vide de ℝ et 𝑓 une application continue de [𝑎, 𝑏] dans ℝ vérifiant⁡𝑓(𝑎)𝑓(𝑏) ⁡ < ⁡0. et possédant un unique zéro 𝜉 dans ]a; b[. Supposons de plus que 𝑓⁡est continûment dérivable sur ]a; b[ et convexe ou concave dans un voisinage de 𝜉. Alors, la suite (𝑥𝑛 )𝑛∈ℕ construite par la méthode de la fausse position converge au moins linéairement vers 𝜉.

Par définition de la méthode, on a, ∀𝑛⁡ ∈ ℕ, 𝑎𝑛+1 = 𝑥𝑛 , 𝑏𝑛+1 = 𝑏⁡si 𝑓(𝑥) < 0, le point (𝑥𝑛+1 ) étant alors donné par la formule : 𝑏 − 𝑥𝑛 ∀𝑛⁡ ∈ ℕ, 𝑥𝑛+1 = 𝑥𝑛 − 𝑓(𝑥𝑛 ) 𝑓(𝑏) − 𝑓(𝑥𝑛 ) 2.3.4 Méthode ou Théorèmes de points fixes Les méthodes d’approximation de zéros introduites dans la suite de ce paragraphe sont plus générales au sens où elles se passent de l’hypothèse de changement de signe de f en ξ et ne consistent pas en la construction d’une suite d’intervalles contenant le zéro de la fonction ; bien qu’étant aussi des méthodes itératives, ce ne sont pas des méthodes d’encadrement. Soit une application d’un ensemble 𝐸 dans lui-même. On appelle point fixe d’une application 𝑓 tout élément 𝑢⁡ ∈ ⁡𝐸 tel que 𝑓(𝑢) = 𝑢. On voit que résoudre ce type d’équation est un cas particulier des équations numériques ℎ(𝑢) = 𝑓(𝑢) − 𝑢 = 0. De nombreux résultats affirment l’existence de points fixes. Lorsque l’ensemble 𝐸 est un espace de Banach (c’est-à-dire un espace vectoriel normé complet), toute application contractante (i.e. toute application lipchitzienne de rapport 𝑘 < 1) de 𝐸 dans lui-même admet un et un seul point fixe 𝑢 tel que: ∀𝑥 ∈ 𝐸,⁡⁡⁡⁡⁡⁡⁡⁡⁡𝑢 = lim 𝑓 𝑛 (𝑥) 𝑛

Par exemple, la fonction 𝑓(𝑥) = 𝑎𝑥 + 𝑏, avec |𝑎| ⁡ < ⁡1 conduit à: 1 − 𝑎𝑛 𝑓 𝑛 (𝑥) = 𝑎𝑛 𝑥 + 𝑏 1−𝑎 𝑏 Le point fixe de 𝑓⁡est donné par 𝑢⁡ = ⁡𝑙𝑖𝑚𝑓 𝑛 (𝑥) = 1−𝑎

Nous

verrons

que

la

méthode

de

Newton

peut s’interpréter 𝑓(𝑥) 𝑔(𝑥) = 𝑥 − 𝑓′(𝑥)

comme

𝑥𝑛+1 = 𝑔(𝑥𝑛 )

où

Maintenant, si la fonction 𝑔(𝑥) est continue et si l’algorithme converge (c’est-à-dire 𝑥𝑛 ⟶ 𝑥), on tire de 𝑥𝑛+1 = 𝑔(𝑥𝑛 ) que 𝑥 satisfait l’équation 𝑥⁡ = ⁡𝑔(𝑥); on dit que x est un point fixe de 𝑔. 2.3.4.1 Méthode de Newton-Raphson La méthode de Newton-Raphson, encore appelée méthode des tangentes a été exposée par Newton vers 1669 et complétée par Joseph Raphson (1648-1715) en 1690. C’est une méthode par approximations successives fondée sur le théorème suivant: −1

𝑥𝑛+1 = 𝑥𝑛 − (𝑑𝑓(𝑥𝑛 )) 𝑓(𝑥𝑛 )

Pr. Dr. Ir. Gustave. Mukoko

∀𝑛⁡ ∈ ℕ

BAC II Génie Industriel

Page 20 / 63

Cours de Méthodes Numériques Résolution d’une équation f(x)=0

converge vers l’unique solution de l’équation 𝑓(𝑥) = 0 ; l’initialisation 𝑥0 étant donnée. La formule de récurrence offre une formule itérative qu’on initialise à partir d’un point arbitraire suffisamment voisin de la racine que l’on cherche à déterminer. Lorsque 𝑓 est une fonction à variable réelle, la formule donnant 𝑥𝑛+1 est l’intersection de la tangente passant par le point (𝑥𝑛 , 𝑓(𝑥𝑛 )) avec l’axe des abscisses 𝑓(𝑥𝑛 ) 𝑥𝑛+1 = 𝑥𝑛 − 𝑓′(𝑥𝑛 ) Lorsque la racine est double, on se ramène à une racine simple en remplaçant la fonction 𝑓 par la fonction (𝑓(𝑥𝑛 ))/(𝑓′(𝑥𝑛 )). On arrête l’itération lorsque la différence entre deux pas consécutifs est inférieure à la précision souhaitée |𝑥𝑛+1 − 𝑥𝑛 | ⁡0 donné, il existe un polynôme 𝑃𝑛 de degré 𝑛 tel que: Max |𝑓(𝑥) − 𝑃𝑛 (𝑥)| < 𝜖 𝑎≤𝑥≤𝑏

(1) L’interpolation polynômiale est un outil pour la construction des méthodes d’intégration numérique ou des méthodes d’approximation des équations différentielles. (2) L’interpolation par les fonctions splines est largement utilisée dans tous les programmes de dessin assisté par ordinateur, conception assistée par ordinateur ou plus généralement de graphisme. (3) Les séries de Fourier et leur analogue discret, la transformation de Fourier discrète : Elles sont un moyen très utile pour l’approximation des fonctions périodiques. Remarque : - Pour les équations aux dérivées partielles, la méthode des éléments finis, un des outils de base de l’ingénierie moderne, utilise de façons essentielle l’interpolation multidimensionnelle; - Une façon naturelle d’approcher les fonctions périodiques est d’utiliser les polynômes trigonométriques. Nous nous limiterons dans ces pages à des problèmes d’interpolation polynomiale, ce qui signifie que la courbe que l’on cherche à obtenir est le graphe d’une fonction polynomiale (éventuellement par morceaux). Ce choix n’est, de loin, pas le seul possible : l’interpolation trigonométrique, basée sur les polynômes trigonométriques, est en effet largement utilisée pour l’interpolation des fonctions périodiques et la mise en œuvre de techniques en lien avec l’analyse de Fourier, l’interpolation rationnelle se sert de quotients de polynômes, etc... L’interpolation polynomiale est un outil numérique de premier ordre pour l’approximation polynomiale des fonctions réelles d’une variable réelle. Elle consiste à déterminer un polynôme 𝑃𝑛 (𝑥) de degré 𝑛 qui puisse remplacer lors des applications la fonction 𝑓(𝑥). De plus, c’est un outil efficace pour : - Calculer, pour x donné, une approximation de 𝑓(𝑥). en calculant 𝑃𝑛 (𝑥) ; Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 24 / 63

Cours de Méthodes Numériques Interpolation polynômiale

-

Construire : (1) des méthodes d’intégration numérique ; (2) des méthodes de différentiation ; (3) des méthodes d’approximation des équations différentielles ; (4) …

Le principe est simple, le procédé est le suivant : – On choisit (ou on se donne) (𝑛⁡ + ⁡1) points 𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 . – On calcule 𝑦0 = 𝑓(𝑥𝑛 ), … , 𝑦𝑛 = 𝑓(𝑥𝑛 ), ou on se donne (𝑥𝑖 , 𝑦𝑖 )𝑖 = 0, 1, …⁡, 𝑛 ; – On cherche un polynôme de degré 𝑛 tel que 𝑃𝑛 (𝑥𝑖 ) = 𝑦𝑖 , 𝑖 = 0, … , 𝑛 Remarque : (1) Les points (𝑥𝑖 , 𝑦𝑖 )𝑖 = 0, 1, …⁡, 𝑛 ⁡sont appelés points d’interpolation: (2) Si la fonction 𝑓 est connue seulement par ses valeurs en quelques points, les (𝑛⁡ + ⁡1) points 𝑥1 , 𝑥2 , … , 𝑥𝑛 . sont fixés ; (3) Si on veut que 𝑃𝑚 (𝑥𝑖 ) = 𝑓(𝑥𝑖 ) et 𝑃′𝑚 (𝑥𝑖 ) = 𝑓 ′ (𝑥𝑖 )⁡𝑖 = 0, 1, …⁡, 𝑛 , on obtient l’interpolation dite d’Hermite Il existe plusieurs techniques pour calculer 𝑃𝑛 (𝑥). Les plus connues sont celles de Lagrange et de Newton-Côtes. Nous allons en fait le faire de deux façons : (1) Une méthode directe basée sur la résolution d’un système linéaire ; (2) Une méthode itérative due à Lagrange ; (3) Une méthode iterative d’Hermite. 3.2. MÉTHODE DIRECTE BASÉE SUR LA RÉSOLUTION D’UN SYSTÈME LINÉAIRE – – –

On se donne (𝑛⁡ + ⁡1) points 𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑛 ⁡ On calcule 𝑦0 = 𝑓(𝑥𝑛 ), … , 𝑦𝑛 = 𝑓(𝑥𝑛 ), ou on se donne (𝑥𝑖 , 𝑦𝑖 )𝑖 = 0, 1, …⁡, 𝑛 ; On cherche un polynôme de degré 𝑛 tel que 𝑃𝑛 (𝑥𝑖 ) = 𝑦𝑖 , 𝑖 = 0, … , 𝑛

Ecrivons explicitement 𝑃𝑛 (𝑥𝑖 ) = 𝑦𝑖 𝑎𝑛 𝑥𝑖𝑛 + 𝑎𝑛−1 𝑥𝑖𝑛−1 + ⋯ + 𝑎1 𝑥𝑖 + 𝑎0 = 𝑦𝑖 ,⁡⁡⁡⁡⁡𝑖 = 0,1, …,

On a 𝑑𝑒𝑡 ≠ 0 si tous les 𝑥𝑖 sont distincts. On peut donc trouver un unique vecteur de coefficients (𝑎𝑛 , … , 𝑎0 ) résolvant le problème. 3.3. INTERPOLATION DE LAGRANGE: UNE MÉTHODE ITÉRATIVE Interpolation Linéaire: On considère deux points (𝑥0, 𝑦0), (𝑥1, 𝑦1)⁡avec : 𝑥0 ≠ 𝑥1 , { 𝑦0 = 𝑓(𝑥0 )⁡𝑒𝑡⁡𝑦1 = 𝑓(𝑥1 )⁡ Pour déterminer le polynôme 𝑃1 (𝑥) = 𝑎𝑥 + 𝑏 qui passe par deux points distincts (𝑥0 , 𝑦0 ), (𝑥1 , 𝑦1 )⁡(𝑥0 ≠ ⁡ 𝑥1 ), On peut :

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 25 / 63

Cours de Méthodes Numériques Interpolation polynômiale 𝑦 −𝑦

𝑎 =⁡ 1 0 𝑎𝑥0 + 𝑏 = ⁡ 𝑦0 ′ 𝑥1 −𝑥0 1) Résoudre le système d’équations :⁡{ ⁡𝑑 𝑜ù⁡ { 𝑥 𝑦 −𝑥 𝑦 𝑎𝑥1 + 𝑏 = ⁡ 𝑦1 𝑏 = ⁡ 𝑦0 − 𝑎𝑥0 = 1 0 0 1 On a :⁡𝑃1 (𝑥) = ⁡

2) Poser : {

𝑦1 −𝑦0 𝑥1 −𝑥0

𝐿0 (𝑥) = ⁡ 𝐿1 (𝑥) = ⁡

𝑥+

𝑥−𝑥1 𝑥0 −𝑥1 𝑥−𝑥0 , 𝑥1 −𝑥0

𝑥1 𝑦0 −𝑥0 𝑦1 𝑥1 −𝑥0

𝑥1 −𝑥0

et 𝑃1 (𝑥0 ) = 𝑦0 , 𝑃1 (𝑥1 ) = 𝑦1

0⁡⁡𝑠𝑖⁡⁡𝑖 ≠ 𝑘 on a :⁡𝐿𝑘 (𝑥𝑖 ) = { . 1⁡⁡𝑠𝑖⁡⁡𝑖 = 𝑘

Ainsi :⁡𝑃1 (𝑥) = ⁡ 𝑦0 𝐿0 (𝑥) + 𝑦1 𝐿1 (𝑥) (𝑥 − 𝑥1 ) 𝑥 − 𝑥0 ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= 𝑦0 + 𝑦1 ⁡( ) (𝑥0 − 𝑥1 ) 𝑥1 − 𝑥0 𝑦1 − 𝑦0 𝑥1 𝑦0 − 𝑥0 𝑦1 ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= 𝑥+ 𝑥1 − 𝑥0 𝑥1 − 𝑥0 0⁡⁡𝑠𝑖⁡⁡𝑖 ≠ 𝑘 1⁡⁡𝑠𝑖⁡⁡𝑖 = 𝑘 Ces deux procédés déterminent évidemment le même polynôme de degré 1 (la même droite). Si maintenant, on veut déterminer le polynôme de degré 2 qui passe par trois (3) points distincts alors : i) la première expression de 𝑃(𝑥) est inadéquate (il faut refaire les calculs) ; ii) la deuxième expression se prête assez facilement à une généralisation par récurrence. On a :⁡𝑃1 (𝑥0 ) = 𝑦0 et 𝑃1 (𝑥1 ) = 𝑦1 car 𝐿𝑘 (𝑥𝑖 ) = {

Exemple : Déterminer le polynôme d’interpolation 𝑃1 (𝑥) de degré 1 tel que 𝑃1 (𝑥𝑖 ) = 𝑓(𝑥𝑖 ), 𝑖 = 0, 1 avec 𝑦𝑖 ⁡ = ⁡𝑓(𝑥𝑖 ), 𝑖⁡ = ⁡0, 1⁡, (𝑥0 , 𝑦0 ) = ⁡ (0, 1), (𝑥1 , 𝑦1 ) ⁡ = ⁡ (2, 5) D’après la méthode de Lagrange, 𝑃1 (𝑥) = ⁡ 𝑦0 𝐿0 (𝑥) + 𝑦1 𝐿1 (𝑥) (𝑥 − 𝑥1 ) 𝑥 − 𝑥0 ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= 𝑦0 + 𝑦1 ⁡( ) (𝑥0 − 𝑥1 ) 𝑥1 − 𝑥0 (𝑥 − 2) (𝑥 − 0) ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= 1 +5 (0 − 2) (2 − 0) (𝑥 − 2) (𝑥) ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= 1 +5 = 2𝑥 + 1 (−2) (2) Interpolation Parabolique: 𝑥0 ≠ 𝑥1 , 𝑥0 ≠ 𝑥2 ⁡⁡⁡𝑒𝑡⁡𝑥1 ≠ 𝑥2 𝑦0 = 𝑓(𝑥0 ), 𝑦1 = 𝑓(𝑥1 )⁡𝑒𝑡⁡𝑦2 = 𝑓(𝑥2 ) Pour déterminer le polynôme 𝑃2 (𝑥) de degré 2, d’équation 𝑦 = 𝑎𝑥 2 + 𝑏𝑥 + 𝑐 qui passe par trois points distincts (𝑥0 , 𝑦0 ), (𝑥1 , 𝑦1 )⁡𝑒𝑡⁡(𝑥2 , 𝑦2 ) , il suffit de poser : (𝑥−𝑥1 )(𝑥−𝑥2 ) 𝐿0 (𝑥) = ⁡ On considère trois points (𝑥0 , 𝑦0 ), (𝑥1 , 𝑦1 )⁡𝑒𝑡⁡(𝑥2 , 𝑦2 ) avec :⁡{

(𝑥0 −𝑥1 )(𝑥0 −𝑥2 ) (𝑥−𝑥0 )(𝑥−𝑥2 )

: 𝐿1 (𝑥) = ⁡ (𝑥

1 −𝑥0 )(𝑥1 −𝑥2 )

, on a on a :⁡𝐿𝑘 (𝑥𝑖 ) = {

(𝑥−𝑥 )(𝑥−𝑥 )

0⁡⁡𝑠𝑖⁡⁡𝑖 ≠ 𝑘 1⁡⁡𝑠𝑖⁡⁡𝑖 = 𝑘

0 1 {𝐿2 (𝑥) = ⁡ (𝑥2 −𝑥0 )(𝑥2 −𝑥1 ) Ainsi :⁡𝑃2 (𝑥) = ⁡ 𝑦0 𝐿0 (𝑥) + 𝑦1 𝐿1 (𝑥) + 𝑦2 𝐿2 (𝑥) (𝑥 − 𝑥0 )(𝑥 − 𝑥2 ) (𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) (𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) ⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡= 𝑦0 + 𝑦1 ⁡ + 𝑦2 (𝑥0 − 𝑥1 )(𝑥0 − 𝑥2 ) (𝑥1 − 𝑥0 )(𝑥1 − 𝑥2 ) (𝑥2 − 𝑥0 )(𝑥2 − 𝑥1 )

est le polynôme d’interpolation polynômiale associé.

Exemple : Déterminer le polynôme d’interpolation 𝑃2 (𝑥) de degré 2 tel que 𝑃2 (𝑥𝑖 ) = 𝑓(𝑥𝑖 ), 𝑖 = 0, 1⁡𝑒𝑡⁡2 avec 𝑦𝑖 ⁡ = ⁡𝑓(𝑥𝑖 ), 𝑖⁡ = ⁡0, 1⁡𝑒𝑡⁡2, ⁡(𝑥0 , 𝑦0 ) = ⁡ (0, 1), (𝑥1 , 𝑦1 ) = ⁡ (1, 2)⁡𝑒𝑡(𝑥2 , 𝑦2 ) ⁡ = ⁡ (2, 5) D’après la méthode de Lagrange,

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 26 / 63

Cours de Méthodes Numériques Interpolation polynômiale

Remarque : (1) Pour calculer 𝑃2(𝑥), on n’a pas utilisé le polynôme 𝑃1(𝑥) calculé dans l’exemple précédent et pourtant on avait deux points communs. (2) 𝐿𝑖 (𝑥), 𝑖 = 0, 1, 2 sont des polynômes de degré 2 :

L’approximation polynomiale, fondée en général sur le développement en série de Taylor, permet d’approcher une fonction 𝑓 suffisamment régulière par un polynôme de degré 𝑛. Interpolation de Lagrange: -

On choisit 𝑛 + 1 points 𝑥0 , 𝑥1 , … , 𝑥𝑛 ; On calcul 𝑦0 = 𝑓(𝑥0 ), … , 𝑦𝑛 = 𝑓(𝑥𝑛 ) ; On cherche un polynôme de degré 𝑛 tel que 𝑃𝑛 (𝑥𝑖 ) = 𝑦𝑖 , 𝑖 = 0, … , 𝑛

On introduit les coefficients d’interpolation de Lagrange

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 27 / 63

Cours de Méthodes Numériques Interpolation polynômiale

Remarque: 1. En pratique, on utilise l’interpolation polynômiale avec des polynômes de degré 𝑛 assez grand ou l’interpolation polynômiale par morceaux. Ainsi dans l’exemple précédent, il faut augmenter le nombre de points d’interpolations. 2. Si les valeurs 𝑦𝑛 sont des valeurs expérimentales. L’interpolation polynomiale est une technique peu appropriée pour de telles situations. Les polynômes de degré ´élevé sont sensibles à la perturbation des données. 3. La méthode de Lagrange s’adapte mal au changement du nombre de points (𝑥𝑖 , 𝑦𝑖 ). On ne peut utiliser les coefficients de Lagrange si on passe de 𝑛 à (𝑛⁡ + ⁡1) points.

On démontre le résultat suivant : toute fonction continue sur un intervalle borné et connue en (n + 1) points distincts peut être approchée par un polynôme qui coïncide avec cette fonction en ces (n + 1) points. Si 𝑓 :⁡[𝑎, 𝑏] → 𝑅 est une fonction continue et si 𝑥0 , 𝑥1 , … , 𝑥𝑛 sont (n + 1) points distincts de l’intervalle [a, b], alors il existe un unique polynôme 𝑃𝑛 de degré 𝑛 appelé polynôme d’interpolation de Lagrange, dont la valeur coïncide avec 𝑓 aux points 𝑥1 , c’est-à-dire vérifiant 𝑃𝑛 (𝑥) = 𝑓(𝑥𝑖 ) et qui est donné par la formule: Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 28 / 63

Cours de Méthodes Numériques Interpolation polynômiale

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 29 / 63

Cours de Méthodes Numériques Interpolation polynômiale

INTERPOLATION DE D’HERMITE

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 30 / 63

Cours de Méthodes Numériques Interpolation polynômiale

L’interpolation de Lagrange, qui fournit facilement un polynôme prenant des valeurs données, présente l’inconvénient dans certains cas de donner une qualité m´médiocre : entre les points d’interpolation la différence entre une fonction et son polynôme d’interpolation peut être grande, même si le nombre de points tend vers l’infini (phénomène dit de Runge). Pour remédier à cela on peut essayer d’utiliser non seulement les valeurs d’une fonction mais aussi celles de ses d´dérivées : c’est l’interpolation d’Hermite. On se donne (𝑥𝑖 , 𝑓(𝑘)⁡(𝑥𝑖)), pour 𝑖⁡ = ⁡0, . . . , 𝑛, 𝑘⁡ = ⁡0, . . . , 𝑚𝑖 où 𝑚𝑖 ∈ N. En posant 𝑁⁡ = ∑𝑛𝑖=0(𝑚𝑖 + 1), on peut montrer que si les nœuds 𝑥𝑖 sont distincts, il existe un unique polynôme ℍ𝑁−1 ∈ ℙ𝑁−1 , appelé polynôme d’interpolation d’Hermite, Interpolation d’Hermite, cas où k = 1. En définissant les polynômes

3.4. INTERPOLATION DE TCHEBYCHEV

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 31 / 63

Cours de Méthodes Numériques Interpolation polynômiale

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 32 / 63

Cours de Méthodes Numériques Interpolation polynômiale

3.5. DIFFÉRENCES DIVISÉES Ce sont les méthodes de calcul d’interpolation à l’aide des différences finies développées par Thomas Harriot (1560-1621), Henry Briggs (1561-1630), James Gregory (1638-1675) et Isaac Newton (16421727).

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 33 / 63

Cours de Méthodes Numériques Interpolation polynômiale

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 34 / 63

Cours de Méthodes Numériques Interpolation polynômiale

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 35 / 63

Cours de Méthodes Numériques Interpolation polynômiale

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 36 / 63

Cours de Méthodes Numériques Interpolation polynômiale

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 37 / 63

Cours de Méthodes Numériques Interpolation polynômiale

3.6. EXERCICES

Pr. Dr. Ir. Gustave. Mukoko

BAC II Génie Industriel

Page 38 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

4. DÉRIVATION ET INTÉGRATION NUMERIQUE 4.1. INTRODUCTION

R(h) est la somme de Riemann avec ℎ =

𝑏−𝑎 𝑛

𝑠𝑖𝑛𝑥

- Il existe des fonctions simples comme ⁡𝑜𝑢⁡√𝑐𝑜𝑠 2 𝑥 + 3𝑠𝑖𝑛2 𝑥 qui n’ont pas de primitive connue. 𝑥 - 𝑓⁡peut-être connue seulement en quelques points et sa formule est inconnue. Comment peut-on intégrer de telles fonctions entre a et b ? Si 𝑃(𝑥) est une approximation de 𝑓 dans l’intervalle [a, b], nous nous proposons d’étudier les approximations : 𝑏

𝑏

𝑓 ′ (𝑦) ≈ 𝑃′ (𝑦)⁡⁡⁡⁡⁡⁡⁡⁡⁡⁡𝑦 ∈ [𝑎, 𝑏]⁡⁡⁡⁡⁡⁡⁡⁡𝑒𝑡⁡⁡⁡⁡ ∫ 𝑓(𝑥)𝑑𝑥 ≈ ∫ 𝑃(𝑥)𝑑𝑥 𝑎

𝑎

4.2. DÉRIVATION 4. 2.1. Dérivée première. La dérivation numérique nous permet de trouver une estimation de la dérivée ou de la pente d’une fonction, en utilisant seulement un ensemble discret de points. Soit 𝑓 une fonction connue seulement par sa valeur en (n + 1) points donnés 𝑥𝑖 ⁡𝑎𝑣𝑒𝑐⁡𝑖⁡ = ⁡0, 1, . . . , 𝑛 distincts. On suppose connue la valeur de la fonction en 𝑥1−1 , 𝑥𝑖 et 𝑥1+1 ; on pose 𝑓⁡(𝑥𝑖−1 ) ⁡ = ⁡ 𝑦𝑖−1 , 𝑓⁡(𝑥𝑖 ) ⁡ = ⁡ 𝑦𝑖 et 𝑓⁡(𝑥𝑖+1 ) = ⁡ 𝑦𝑖+1 . Si on suppose que l’espace entre deux points successifs est constant, donc on pose ℎ⁡ = ⁡ 𝑥𝑖 − 𝑥𝑖−1 ⁡ = ⁡ 𝑥𝑖+1 − 𝑥𝑖 . Alors les formules standarts en deux points sont :  Formule de difference progressive :



Formule de différence régressive :



Formule de différence centrale :

39

Gustave MUKOKO/ Dr. en Génie Civil

Page 39 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

40

Gustave MUKOKO/ Dr. en Génie Civil

Page 40 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

41

Gustave MUKOKO/ Dr. en Génie Civil

Page 41 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

42

Gustave MUKOKO/ Dr. en Génie Civil

Page 42 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

4.3. MÉTHODES NUMÉRIQUES D’INTÉGRATION. Les méthodes d’intégration numérique, interviennent essentiellement lorsque une primitive de 𝑓⁡est d’expression assez compliquée ou inconnue, ou lorsque 𝑓 n’est connue que par points, par exemple si elle résulte de mesures physiques, on peut l’approcher alors par interpolation, puis on intègre numériquement l’interpolée. On traitera seulement les intégrales du type :

Principes généraux

43

Gustave MUKOKO/ Dr. en Génie Civil

Page 43 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

44

Gustave MUKOKO/ Dr. en Génie Civil

Page 44 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

K(t) désigne le noyau de Peano associé à la méthode numérique. Si K garde un signe constant sur [a, b], alors il existe 𝑐 ∈ [𝑎, 𝑏] tel que :

la fonction

où 𝑝𝑘 est un polynôme de degré inférieur ou égal à 𝑘. Comme la méthode est d’ordre 𝑘, l’erreur 𝑒(𝑝𝑘 ) = 0 est nulle. Par conséquent

d'où

soit finalement

Supposons que K soit de signe constatant, appliquons la deuxième formule de la moyenne

en introduisant la fonction 𝑟𝐾 pour laquelle

45

Gustave MUKOKO/ Dr. en Génie Civil

Page 45 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

46

Gustave MUKOKO/ Dr. en Génie Civil

Page 46 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

47

Gustave MUKOKO/ Dr. en Génie Civil

Page 47 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

48

Gustave MUKOKO/ Dr. en Génie Civil

Page 48 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

Méthode des rectangles  Méthodes des Rectangles supérieurs et inférieurs

 Méthodes des Rectangles points-milieux

49

Gustave MUKOKO/ Dr. en Génie Civil

Page 49 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

50

Gustave MUKOKO/ Dr. en Génie Civil

Page 50 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

Méthode des trapèzes

51

Gustave MUKOKO/ Dr. en Génie Civil

Page 51 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

Méthode de Simpson

52

Gustave MUKOKO/ Dr. en Génie Civil

Page 52 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

Méthode de Newton-Côtes

53

Gustave MUKOKO/ Dr. en Génie Civil

Page 53 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

Méthode de Poncelet

54

Gustave MUKOKO/ Dr. en Génie Civil

Page 54 / 63

Cours de Méthodes Numériques Dérivation et intégration numérique

55

Gustave MUKOKO/ Dr. en Génie Civil

Page 55 / 63

Cours de Méthodes Numériques Équations et systèmes d’équations différentielles

5. ÉQUATIONS ET SYSTÈMES D’ÉQUATIONS DIFFÉRENTIELLES 5.1. INTRODUCTION Ce chapitre concerne la résolution numérique approchée d’équations, et de systèmes d’équations, différentielles ordinaires. De telles équations interviennent dans de nombreux problèmes issus de la modélisation mathématique de phénomènes physiques et se rencontrent par conséquent dans des disciplines aussi variées que l’ingénierie, la mécanique ou l’économie. Dans le traitement numérique des équations différentielles, on distingue les méthodes à pas séparés (ou à un seul pas) qui permettent de calculer𝑦𝑛+1 ⁡ à partir de la seule connaissance de 𝑦𝑛 ⁡ et les méthodes à pas liés (ou à pas multiples) qui nécessitent la connaissance de 𝑦𝑛 ⁡, 𝑦𝑛−1 ⁡, … , 𝑦𝑛−𝑝 ⁡pour calculer 𝑦𝑛+1 ⁡. Les méthodes numériques de résolution (dites à différences finies) sont fondées sur le développement de Taylor. 5.2. EXISTENCE ET UNICITÉ DES SOLUTIONS

56

Gustave MUKOKO/ Dr. en Génie Civil

Page 56 / 63

Cours de Méthodes Numériques Équations et systèmes d’équations différentielles 5.3. RÉSOLUTION NUMÉRIQUE DES ÉQUATIONS DIFFÉRENTIELLES ORDINAIRES  Rappels sur les équations différentielles ordinaires Une EDO est un lien entre la dérivée et valeur de la fonction f ' ( x)  F ( f ( x)) • « Ordinaires » : fonction d’une variable • Différent des EDP – Équations aux Dérivées Partielles – Fonction de plusieurs variables Forme générique ODE premier degré:

dy (t )  f  y (t ), t  dt y:R  R n f : Rn  R   R n •

Notes: – t représente le temps – f variable en fonction du temps – Parfois X au lieu de Y, parfois y au lieu de t,… – Souvent Y=(x,y)

(5.1)

(5.2)

57

Gustave MUKOKO/ Dr. en Génie Civil

Page 57 / 63

Cours de Méthodes Numériques Équations et systèmes d’équations différentielles

(5.3)

 Méthodes numériques de résolution 5.3.1.

La méthode d’Euler

La méthode d’Euler est la plus ancienne et certainement la plus simple des méthodes numériques de résolution des équations différentielles ordinaires.

58

Gustave MUKOKO/ Dr. en Génie Civil

Page 58 / 63

Cours de Méthodes Numériques Équations et systèmes d’équations différentielles

5.3.2.

Méthodes de Runge-Kutta

59

Gustave MUKOKO/ Dr. en Génie Civil

Page 59 / 63

Cours de Méthodes Numériques Équations et systèmes d’équations différentielles

60

Gustave MUKOKO/ Dr. en Génie Civil

Page 60 / 63

Cours de Méthodes Numériques Équations et systèmes d’équations différentielles

61

Gustave MUKOKO/ Dr. en Génie Civil

Page 61 / 63

Cours de Méthodes Numériques Équations et systèmes d’équations différentielles

62

Gustave MUKOKO/ Dr. en Génie Civil

Page 62 / 63

Cours de Méthodes Numériques Équations et systèmes d’équations différentielles

63

Gustave MUKOKO/ Dr. en Génie Civil

Page 63 / 63