Embed Size (px)
DESCRIPTION
cours de element methode univesité ibn tofail (prof:abu shabaka) (etudiant: fatima zara motia)
Citation preview
Traitement numérique des données
Pierre HérouxUniversité de Rouen
2 TABLE DES MATIÈRES
Table des matières
1 Représentation des données numériques 31.1 Nombres entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Nombres réels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Virgule flottante binaire . . . . . . . . . . . . . . . . . . . 31.2.2 Capacité (en valeur absolue) . . . . . . . . . . . . . . . . 41.2.3 Précision . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.4 Principe des opérations en virgule flottante . . . . . . . . 4
2 Rappels d’algorithmique 62.1 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.2 Théorème de structure . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 La simple séquence d’instruction . . . . . . . . . . . . . . 62.2.2 L’itération canonique . . . . . . . . . . . . . . . . . . . . . 62.2.3 La structure alternative . . . . . . . . . . . . . . . . . . . 6
2.3 Notion de bloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4 L’opération d’affectation . . . . . . . . . . . . . . . . . . . . . . . 72.5 Exercice :Calcul du PGCD de deux entiers M et N . . . . . . . . 72.6 Extension aux autres instructions de base . . . . . . . . . . . . . 7
2.6.1 Instruction de répétition . . . . . . . . . . . . . . . . . . . 72.6.2 Boucle pour . . . . . . . . . . . . . . . . . . . . . . . . . 72.6.3 Extension de l’alternative :l’aiguillage . . . . . . . . . . . . 82.6.4 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Programmation des séries 93.1 Première approche . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.3 À faire en travaux pratiques . . . . . . . . . . . . . . . . . . . . . 103.4 Principe de programmation des séries . . . . . . . . . . . . . . . 103.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.5.1 Série de Leibnitz . . . . . . . . . . . . . . . . . . . . . . . 103.5.2 Autres résultats . . . . . . . . . . . . . . . . . . . . . . . . 11
4 Résolution d’équations 134.1 Équation du type f(x) = 0 . . . . . . . . . . . . . . . . . . . . . 13
4.1.1 Méthode de dichotomie . . . . . . . . . . . . . . . . . . . 134.1.2 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . 13
4.2 Équation du type f(x) = x - Méthode du point fixe . . . . . . . . 144.2.1 Principe de la méthode . . . . . . . . . . . . . . . . . . . 14
TABLE DES MATIÈRES 3
4.2.2 Algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . 144.2.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5 Interpolation polynomiale 165.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165.2 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . 165.3 Polynôme de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . 175.4 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195.6 Deux algorithmes de calcul . . . . . . . . . . . . . . . . . . . . . 19
5.6.1 Algorithme d’Aitken . . . . . . . . . . . . . . . . . . . . . 195.6.2 Méthode barycentrique . . . . . . . . . . . . . . . . . . . 20
6 Intégration 226.1 Méthode des rectangles médians . . . . . . . . . . . . . . . . . . 226.2 Méthode des trapèzes . . . . . . . . . . . . . . . . . . . . . . . . 236.3 Méthode de Simpson . . . . . . . . . . . . . . . . . . . . . . . . . 24
7 Résolution des systèmes linéaires 277.1 Méthodes directes . . . . . . . . . . . . . . . . . . . . . . . . . . 27
7.1.1 Méthodes de Cramer . . . . . . . . . . . . . . . . . . . . . 277.1.2 Méthodes de Gauss . . . . . . . . . . . . . . . . . . . . . . 27
7.2 Méthodes itératives . . . . . . . . . . . . . . . . . . . . . . . . . . 297.2.1 Méthode de Jacobi . . . . . . . . . . . . . . . . . . . . . . 297.2.2 Méthode de Gauss-Seidel . . . . . . . . . . . . . . . . . . 30
8 Méthode des moindres carrés 318.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . 318.2 Critère des moindres carrés . . . . . . . . . . . . . . . . . . . . . 318.3 Exercice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
9 Résolution numériques des équations différentielles 339.1 Position du problème . . . . . . . . . . . . . . . . . . . . . . . . . 339.2 Méthode d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . 339.3 Méthode de Runge-Kutta à pas unique . . . . . . . . . . . . . . . 34
9.3.1 Méthode de Runge-Kutta à l’ordre 2 . . . . . . . . . . . . 349.3.2 Méthode de Runge-Kutta à l’ordre 4 . . . . . . . . . . . . 35
9.4 Formules d’Adams ouvertes . . . . . . . . . . . . . . . . . . . . . 359.4.1 Formules d’Adams à l’ordre 1 . . . . . . . . . . . . . . . . 359.4.2 Formules d’Adams à l’ordre 2 . . . . . . . . . . . . . . . . 369.4.3 Formules d’Adams d’ordre plus élevé . . . . . . . . . . . . 36
4 CHAPITRE 1. REPRÉSENTATION DES DONNÉES NUMÉRIQUES
Chapitre 1
Représentation des donnéesnumériques
1.1 Nombres entiers
Un entier est codé par défaut sur un mot machine, le plus souvent sur 32bits, dont un bit de signe. Lorsque le bit de signe vaut 0, l’entier représenté estun nombre positif ou nul. Quand le bit de signe est à 1, l’entier est négatif. Pourun entier positif ou nul, sa représentation est binaire pure (avec le bit de signeà 0).ExempleLa représentation en machine de l’entier +5 est la suivante :s 31 bits0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
Conséquence : le plus grand entier représentable est 231 − 1.Pour les entier négatifs, la représentation la plus couramment employée uti-
lise une convention de complémentation. En conséquence, la plus petit entierreprésentable est −231. Les entiers machine signés représentent donc la partiede l’ensemble Z des entiers relatifs allant de −231 à 231 − 1.
La représentation est exacte et toutes les règles de l’arithmétique entière sontrespectées à condition que les résultats appartiennent au domaine des nombresentiers représentables en machine.
1.2 Nombres réels
Soit X un nombre quelconque. Il est toujours possible d’écrire X = m.2e.Il existe une infinité de couples (m,e) vérifiant cette équation. m est appelé lamantisse et e est appelé l’exposant (e est entier).Exemplex = 5 peut s’écrire x = 5.20, x = 2,5.21, x = 10.2−1, . . .
1.2.1 Virgule flottante binaire
Parmi tous les couples (m,e), un seul possède la caractéristique suivante :
1.2. NOMBRES RÉELS 5
12≤ m < 1
On a alors une virgule flottante dite normalisée. Un réel machine simpleprécision est codé sur 32 bits en virgule flottante normalisée. La mantisse occupe24 bits et l’exposant occupe 8 bits.
1.2.2 Capacité (en valeur absolue)
Xmax ' 2127 ' 1038
Xmin = 0,5.2−128 ' 10−39
1.2.3 Précision
2−23 ' 10−7. Ceci implique que les réels machines sont donnés avec 7 chiffressignificatifs.
– Ces réels machine sont en fait des éléments de l’ensemble Q des nombresrationnels.
– L’écart relatif entre 2 réels consécutifs, lorsque l’exposant est égal pour lesdeux, vaut 2−23. En revanche, l’écart absolu entre deux réels consécutifsdépend de la valeur de l’exposant.
Soient X et XS deux réels dont les représentations en machine sont exacteset consécutives. Soient y et z deux nombres proches de X+XS
2 tels que y < X+XS
2
et z > X+XS
2 . En machine, y est représenté par X et z par XS . Le calcul dez − y donnera XS −X alors qu’il devrait tendre vers 0.
– En arithmétique réelle, en machine, compte-tenu des arrondis et autresopérations dues aux problèmes de représentations, on a aucune chance detrouver un résultat égal à une valeur donnée. Ainsi, on prendra garde dene jamais tester l’égalité d’un résultat issu de l’arithmétique réelle avecune valeur donnée. On préférera comparer l’écart (absolu ou relatif) de cerésultat à la valeur à ε (souvent pris égal à 10−6 ou 10−7).
– Il convient d’être prudent car les règles de l’arithmétique classique ne sontplus respectées.
1.2.4 Principe des opérations en virgule flottante
Soient deux nombres flottants X1 = m12e1 et X2 = m12e2 .
Multiplication
X1.X2 = m1m22e1+e2
Pour effectuer la multiplication X1.X2, on procède au produit des mantisseset à la somme des exposants. Si la mantisse résultat est inférieure à 0,5, oneffectue un recadrage en décalant la mantisse d’un position vers la gauche et endiminuant l’exposant d’une unité.
6 CHAPITRE 1. REPRÉSENTATION DES DONNÉES NUMÉRIQUES
Addition
L’addition X1+X2 n’est possible au niveau des mantisses que si les exposantsont égaux (e1 = e2).
– Si e1 = e2, on ajoute m1 et m2. Le résultat donne une mantisse supérieureà 1. Il faut donc effectuer un recadrage en décalant la mantisse vers ladroit et en augmentant l’exposant d’une unité.
– Si e1 6= e2, on aligne min(e1,e2) sur max(e1,e2) et on décale la mantissedu nombre le plus faible en valeur absolue de |e1 − e2| bits vers la droite.Cette opération entraîne une perte de précision car des bits sont perdulors du décalage. Les exposants sont maintenant égaux, il ne reste plusqu’à additionner les mantisses et à effectuer le recalage.
ExempleSoient X1 = 3,875 et X2 = 12,25. On utilise une représentation sur 12 bits, lamantisse étant codée sur 8bits dont un bit de signe et l’exposant étant codé sur4 bits.
X1 = (11,111)2 = (0,11111)2.22
X2 = (1100,01)2 = (0,110001)2.24
L’exposant de X2 est plus grand que celui X1. Il faut donc dénormaliser X1
en décalant sa mantisse de 2 positions vers la droite.L’addition se présente comme suit :s 2−1 2−2 2−3 2−4 2−5 2−6 2−7 exposant0 0 0 1 1 1 1 1 0 1 0 00 1 1 0 0 0 1 0 0 1 0 01 0 0 0 0 0 0 1 0 1 0 0
Le bit de report signale que la mantisse est supérieure à 1. Il faut recadrerle résultat en décalant la mantisse d’une position vers la droite (perte d’un bità 1) et en augmentant l’exposant d’une unité, d’où le résultat :
0 1 0 0 0 0 0 0 0 1 0 1Multiplication X1.X2
La multiplication des mantisses est illustrée si dessous :1 1 1 1 1 0 01 1 0 0 0 1 0
1 1 1 1 1 0 01 1 1 1 1 0 0
1 1 1 1 1 0 01 0 1 1 1 1 0 1 1 1 1 0 0 0
De cette multiplication, on ne conserve que les bits les plus significatifs, cequi fait que 7 bits de poids faible sont perdus. Là encore, l’arithmétique n’estpas respectée.
L’addition des exposants donne e1 + e2 = 6 = (110)2.Parmi les bits éliminés lors de la multiplication des mantisses, celui dont le
poids est le plus fort est un 1. Pour l’arrondi, on ajoutera 1 en septième positionde la mantisse, d’où le résultat final :
0 1 0 1 1 1 1 1 0 1 1 0Ce nombre en virgule flottant représente 47,5 alors que le résultat exact du
produit vaut 47,46 875.
7
Chapitre 2
Rappels d’algorithmique
2.1 AlgorithmeUn algorithme est une suite finie d’instructions élémentaires constituant le
schéma de résolution d’un problème.Les données sont initialisées par des instructions d’entrée (Lire). Les résultats
sont restitués par des instruction de sortie (Écrire).
2.2 Théorème de structureTout programme linéaire peut s’exprimer à l’aide de trois seules instructions
de base plus celles relatives au entrée/sortie. Les trois instructions sont :– la simple séquence ;– l’itération canonique ;– la structure alternative.
2.2.1 La simple séquence d’instruction
Si S1 et S2 sont deux blocs d’instructions, la séquentialité de S1;S2 signifieque le bloc d’instruction S1 sera exécuté et immédiatement suivi de l’exécutiondu bloc S2.
2.2.2 L’itération canonique
Soient α une proposition logique (à valeur booléenne) et S une suite d’ins-tructions. L’itération canonique se traduit par la formule :
tant que α faire S
2.2.3 La structure alternative
Soient α une proposition logique, S1 et S2 deux blocs d’instructions. Lastructure alternative s’exprime par :
si α alors S1 sinon S2
NB : Si le bloc d’instruction S2 est vide, l’alternative se simplifie par :si α alors S1
8 CHAPITRE 2. RAPPELS D’ALGORITHMIQUE
2.3 Notion de blocUn bloc d’instructions est une suite d’instructions dépendant d’un même
mot-clé. On le délimite par les mots début et fin . Lorsqu’un bloc est vide ou s’iln’est composé que d’une seule instruction, les mots début et fin sont facultatifs.
2.4 L’opération d’affectationL’opération d’affectation a un rôle essentiel car c’est l’opération qui permet
de modifier les valeurs des variables contenues en mémoire. Elle est symboliséepar←. Ainsi, on note l’incrémentation de la valeur d’une variable i d’une unité :i← i + 1.
L’affectation est toujours de la forme :
nom_identificateur_de_variable← expression
2.5 Exercice : Calcul du PGCD de deux entiersM et N
Le PGCD s’obtient par l’algorithme d’Euclide dont le principe est le suivant.On divise M par N . Si N est diviseur de M alors N est le PGCD et l’algorithmeest terminé. Dans le cas contraire, on donne à M la valeur de N , puis on donne àN la valeur du reste de la division précédente et on recommence à le processus.
2.6 Extension aux autres instructions de base
2.6.1 Instruction de répétitionOn trouve dans certains langages des structures telles que faire (ou répéter)
S tant que α. Cette instruction est équivalente à S ; tant que α faire Sfaire (ou répéter) S jusqu’à α est équivalente à S ; tant que non α faire S
2.6.2 Boucle pour
Soient i une variable de type entier et α une condition dans laquelle i inter-vient sous la forme d’une limite à ne pas dépasser (par exemple i ≤ n, où n estune valeur définie).
La séquence qui suit peut s’exprimer par une boucle pour.i← 1tant que i ≤ n fairedébut
S /* S est une suite d’instructions quelconque */i← i + 1
finLa boucle pour correspondante est la suivante :
pour i variant de 1 à n par pas de 1 faire Si est appelé indice de boucle. Lorsque le pas vaut 1, il est possible de ne
pas le préciser. Les valeurs initiale et finale de l’indice de boucle peuvent bienentendu être modifiées.
2.6. EXTENSION AUX AUTRES INSTRUCTIONS DE BASE 9
2.6.3 Extension de l’alternative : l’aiguillageL’aiguillage est équivalent à une suite d’instruction alternatives en cascade.
Soient ch une expression, V1, . . . ,Vn des valeurs constantes du même type quech, et S1, . . . ,Sn,Sd sont des blocs d’instructions.selon la valeur de ch
V1 faire S1...Vn faire Sn
par défaut faire Sd
2.6.4 ExerciceUn nombre est dit parfait s’il est égal à la somme de ses diviseurs (1 compris
et lui-même exclus). Les nombres qui possèdent cette propriété sont très rares.Écrire un algorithme qui affiche tous les nombre parfaits compris entre 2 et10 000. On admettra que tous les nombres parfaits sont pairs.
10 CHAPITRE 3. PROGRAMMATION DES SÉRIES
Chapitre 3
Programmation des séries
ExempleOn veut obtenir une table de la fonction cos(x) pour x variant de 0 à π par pasde π
12 en utilisant la formule :
cos(x) = 1− x2
2!+
x4
4!+ · · ·+ (−1)p x2p
(2p)!+ · · · =
∞∑p=0
(−1)p x2p
(2p)!
La précision souhaitée est 10−6.
3.1 Première approcheL’énoncé impose une boucle.
pour x variant de 0 à π par pas de π12 faire
débutCalculer cos(x) à 10−6 près par la formuleÉcrire x et la valeur calculée e cos(x)
finSoit tp = (−1)p x2p
(2p)! . Le calcul de tp à chaque itération serait d’une extrêmemaladresse car beaucoup trop coûteux en temps de calcul. Faisons apparaîtreune récurrence. {
tp = (−1)p x2p
(2p)!
tp−1 = (−1)p−1 x2p−2
(2p−2)!
tp = tp−1x2
(2p− 1)(2p)avec t0 = 1 et p ≥ 1
3.2 Algorithmex réelp entier : rang du terme calculét réel : terme calculés réel : somme de terme jusqu’au rang p
3.3. À FAIRE EN TRAVAUX PRATIQUES 11
débutpour x variant de 0 à π par pas de π
12 fairedébut
x2 ← x ∗ xp← 0s← 1t← 1tant que précision non atteinte fairedébut
p← p + 1t← −t x2
(2p−1)(2p)s← s + t
finÉcrire x et s
finfin
On prendra comme condition relative à la précision∣∣ ts > 10−6
∣∣.3.3 À faire en travaux pratiques
Programmer cet algorithme.Modifier cet algorithme de telle sorte qu’il effectue une tabulation de cos(x)
pour x variant de 0 à π par pas de πn où n est un entier strictement positif saisi
par l’utilisateur.Que constate-t-on pour certaines valeurs de n?Quelle est la cause de l’anomalie mise en évidence?Comment y remédier de façon rigoureuse?Reprogrammer l’algorithme en conséquence?
3.4 Principe de programmation des sériesPour programmer une série, si le terme général est très simple, on peut le
calculer directement, sinon, il faut essayer de faire apparaître une récurrence.Parmi les variables figurent généralement le terme calculé, la somme des termeet le rang du terme courant. Il peut également y avoir une variable représentantle signe du terme au rang considéré. Les termes sont calculés et ajoutés à lasomme jusqu’à ce que la précision soit atteinte.
3.5 Exercices
3.5.1 Série de Leibnitz
π
4= 1− 1
3+
15− 1
7+ · · · =
∞∑n=0
(−1)n 12n + 1
Cette série converge très lentement.Programmer le calcul de cette série à 10−6 près.
12 CHAPITRE 3. PROGRAMMATION DES SÉRIES
Pour cette série, le terme est simple. On procède donc au calcul dirent duterme avec une variable auxiliaire représentant le signe.
On peut appliquer à cette série des techniques de convergence, par exemple :
π
4=
(1− 1
3
)+
(15− 1
7
)+ · · ·
=∞∑
n=0
(1
4n + 1− 1
4n + 3
)
=∞∑
n=0
2(4n + 1)(4n + 3)
(3.1)
Programmer cette série et donnez la valeur de n correspondant à une préci-sion de 10−6.
On peut également appliquer la formule suivante :
π
4= 1−
(13− 1
5
)−
(17− 1
9
)− · · ·
= 1−∞∑
n=0
(1
4n + 3− 1
4n + 5
)
= 1−∞∑
n=0
2(4n + 3)(4n + 5)
(3.2)
On peut également sommer les équations (3.1) et (3.2) pour calculer π2 .
π
2= 1 +
∞∑n=0
(2
(4n + 1)(4n + 3)− 2
(4n + 3)(4n + 5)
)
= 1 + 2∞∑
n=0
4(4n + 1)(4n + 3)(4n + 5)
= 1 + 8∞∑
n=0
1(4n + 1)(4n + 3)(4n + 5)
3.5.2 Autres résultats
π2
6=
∞∑n=1
1n2
π4
90=
∞∑n=1
1n4
π6
945=
∞∑n=1
1n6
Les produits suivants donnent également des approximations de π.
3.5. EXERCICES 13
π
2=
21
23
43
45
65
67
87
89· · · =
∞∏n=1
4n2
(2n− 1)(2n + 1)
2π
=√
22
√2 +√
22
√2 +
√2 +√
22
14 CHAPITRE 4. RÉSOLUTION D’ÉQUATIONS
Chapitre 4
Méthodes usuelles derésolution d’équations
4.1 Équation du type f(x) = 0
4.1.1 Méthode de dichotomie
Hypothèse : la fonction f est connue par son expression mathématique. Elleest définie et continue sur [a,b], intervalle donné. f possède une racine uniqueappartenant à ]a,b[ et s’annule en changeant de signe.
Principe de la méthode
On se place au point d’abscisse x = a+b2 et on cherche à quel demi-intervalle
[a,x] ou [x,b] appartient la racine. On restreint alors l’intervalle de rechercheau demi-intervalle déterminé lors de l’étape précédente et on recommence lemême processus jusqu’à obtention d’un encadrement suffisamment restreint dela racine.
Donner l’algorithme de cette méthode.On choisira de préférence pour l’arrêt des itérations un test relatif, par
exemple,∣∣x−a
a
∣∣ < ε, plutôt écrit |x− a| < ε |a| afin d’éviter la division parzéro.
Remarque : la méthode de dichotomie est de convergence lente.Appliquer la méthode de dichotomie à f(x) = e−
x10 − x sur l’intervalle [0,1].
Vérification des hypothèses : f est monotone décroissante sur [0,1]. f(0) = 1et f(1) < 0. Ceci implique que f a une racine unique sur l’intervalle [0,1].
4.1.2 Méthode de Newton
Hypothèses : f et f ′ sont connues par leur expression mathématique. Ellessont définies partout sur l’intervalle d’étude. Soit x0 donné.
Principe de la méthode
On mène la tangente à la courbe y = f(x) au point d’abscisse x0. Cettetangente coupe l’axe des abscisses au point d’abscisse x1. En x1, on recommence
4.2. ÉQUATION DU TYPE F (X) = X - MÉTHODE DU POINT FIXE 15
le même processus, on obtient le point x2 et ainsi de suite. Ainsi, on construitune suite xi qui, dans de bonnes conditions, converge rapidement vers la racinecherchée.
Recherchons la relation liant xi+1 à xi.
tan(α) = f ′(xi)tan(α) = f(xi)
xi−xi+1
}⇒ xi+1 = xi −
f(xi)f ′(xi)
Conséquence : f ′ ne doit pas s’annuler en un point xi.Il faut être vigilant dans le choix de x0. En effet, la tangente de la courbe en
xi doit couper l’axe des abscisses dans le domaine de définition de la fonction fet dans la partie continue contenant la racine recherchée.
Généralement, on choisit x0 pas trop éloigné de la racine cherchée.
Algorithme
À chercher.
4.2 Équation du type f(x) = x - Méthode dupoint fixe
Hypothèse : f est définie partout sur l’intervalle d’étude.
4.2.1 Principe de la méthode
On construit une suite xi définie par xi = f(xi−1).La suite converge si et seulement si |f ′(r)| < 1 où r est la racine cherchée. r
est appelé le point fixe.La méthode, s’il y a convergence, est plus rapide que la dichotomie mais un
peu moins que la méthode de Newton.
4.2.2 Algorithme
À chercher
4.2.3 Exercice
On considère la fonction F définie par :
F (x) =13x3 − 2x2 + 3x− 5
2(4.1)
1. Par une étude analytique de F , montrer que l’équation
F (x) = 0 (4.2)
admet une racine unique a et montrer que celle-ci appartient à un intervalle]k,k + 1[ où k ∈ N.
16 CHAPITRE 4. RÉSOLUTION D’ÉQUATIONS
2. Montrer que l’équation (4.2) peut se mettre sous l’une quelconque desdeux formes suivantes :
x = f(x) où f(x) = −19x3 +
23x2 +
56
(4.3)
x = g(x) où g(x) =
√16x3 +
23x− 5
4(4.4)
Les méthodes d’approximation de la forme xn+1 = f(xn) et xn+1 = g(xn)convergent-t-elles?
3. Pour résoudre l’équation (4.2), on décide d’appliquer la méthode de New-ton à partir de x0 donné. Comment choisir x0 pour obtenir une conver-gence dans de bonnes conditions? Calculer x1, x2 et x3 avec quatre dé-cimales exactes ainsi que F (x3) dans les deux cas suivants : x0 = 5 etx0 = 2,5.
17
Chapitre 5
Interpolation polynomiale
5.1 IntroductionSupposons connues n + 1 valeurs y0,y1,. . . ,yn correspondant aux n + 1 abs-
cisses x0,x1,. . . ,xn. Il peut s’agir, par exemple, de valeur relevées expérimenta-lement ou prises par un fonction f aux abscissesx0,x1,. . . ,xn.
Le procédé d’interpolation polynomiale consiste à construire un polynômeP de degré minimal prenant pour chaque valeur xi la valeur yi, donc tel queP (xi) = yi,∀i = 0,1, . . . ,n.
Ceci peut servir à obtenir de nouvelles valeurs calculées en d’autres abscisseset aussi à obtenir une expression analytique représentant la collection des va-leurs initiales. Ce second aspect est important car il est à la base des méthodesclassiques d’intégration.
5.2 Position du problèmeOn recherche un polynôme de degré minimal prenant aux points x0,x1,. . . ,xn
les valeurs y0,y1,. . . ,yn. Il y a n + 1 points, le polynôme recherché sera donc dedegré inférieur ou égal à n. Il y a donc n+1 coefficients a0,a1,. . . ,an à déterminerpour obtenir P (x) = a0 + a1x + · · ·+ anxn.En x0, on a a0 + a1x0 + · · ·+ anxn
0 = y0
En x1, on a a0 + a1x1 + · · ·+ anxn1 = y1
· · ·En x0, on a a0 + a1xn + · · ·+ anxn
n = yn
Ces n + 1 équations constituent un système linéaire de n + 1 équations àn + 1 inconnues.
xn0 xn−1
0 · · · x0 1xn
1 xn−11 · · · x1 1
......
......
...xn
n xn−1n · · · xn 1
︸ ︷︷ ︸
matrice carrée d’ordre n+1
an
an−1
...a0
︸ ︷︷ ︸inconnues
=
yn
yn−1
...y0
Ce système est mal conditionné. Les résolutions par les méthodes classiqueséchouent numériquement dès que n est un peu élevé.
18 CHAPITRE 5. INTERPOLATION POLYNOMIALE
Une solution plus élégante est fournie par les polynômes de Lagrange.
5.3 Polynôme de Lagrange
Les polynômes de Lagrange construits sur les n + 1 abscisses x0,x1,. . . ,xn
sont les n+1 polynômes Li, de degré n, qui vérifient pour i et j entiers comprisentre 0 et n :
Li(xi) = 1,∀i = 0,1, . . . ,n
Li(xj) = 0,sij 6= i 0 ≤ j ≤ n
Li(x) =(x− x0)(x− x1) · · · (x− xi−1)(x− xi+1) · · · (x− xn)
(xi − x0)(xi − x1) · · · (xi − xi−1)(xi − xi+1) · · · (xi − xn)
Soit
Li(x) =n∏
j=0j 6=i
x− xj
xi − xj)
Ces n+1 polynômes Li, forment une base de l’espace des polynômes de degréinférieur ou égal à n. Dans cette base, le polynôme d’interpolation prenant auxpoints xi les valeurs yi (i ∈ N,0 ≤ i ≤ n) s’écrit :
P (x) = y0L0(x) + y1L1(x) + · · ·+ ynLn(x)
=n∑
i=0
yiLi(x)
Interprétation : quand on écrit le polynôme P cherché dans la base canonique1,x, . . . ,xn, les coefficients de P dans cette base sont solution du système linéairede n+1 équations à n+1 inconnues précédent (qu’on ne sait pas bien résoudrenumériquement). En revanche, les coefficients de P dans la base des polynômesde Lagrange sont les yi. En d’autres termes, le changement de base à diagonaliséla matrice du système.
5.4 Exemples
Soient 3 points de coordonnées (x0,y0), (x1,y1), (x2,y2), le polynôme d’in-terpolation de Lagrange P (x), basé sur les 3 abscisses x0, x1, x2.
Li(x) =n∏
j=0j 6=i
(x− xj)(xi − xj)
Donc :
5.4. EXEMPLES 19
L0(x) =(x− x1)(x− x2)
(x0 − x1)(x0 − x2)
L1(x) =(x− x0)(x− x2)
(x1 − x0)(x1 − x2)
L2(x) =(x− x0)(x− x1)
(x2 − x0)(x2 − x1)
1. Déterminer P (x) dans le cas suivant
x0 = −1 x1 = 0 x2 = 1y0 = 1 y1 = 0 y2 = 2
Puisque y1 = 0, le calcul de L1 est inutile
L0(x) = (x−0)(x−1)(−1−0)(−1−1) = x(x−1)
2
L2(x) = (x+1)(x−0)(1+1)(1−0) = x(x+1)
2
P (x) =x(x− 1)
2+ 2
x(x + 1)2
=32x2 +
12x
2. Calcul de la valeur approchée de sin(
π5
)sachant que
sin(0) = 0
sin(π
6
)=
12
sin(π
4
)=√
22
Les abscisses de base sont 0, π6 et π
4 . Les valeurs de yi sont 0, 12 et
√2
2 .Puisque y0 = 0, le calcul de L0 est inutile.
L1(x) =(x−0)(x−π
4 )(π
6−0)(π6−
π4 ) =
x(x−π4 )
−π6
π12
L2(x) =(x−0)(x−π
6 )(π
4−0)(π4−
π6 ) =
x(x−π6 )
π4
π12
Or,
P (x) =12L1(x) +
√2
2L2(x)
Donc,
P (x) =x
(x− π
4
)−π
3π12
+
√2x
(x− π
6
)π2
π12
P(
π5
)est une valeur approchée de sin
(π5
).
20 CHAPITRE 5. INTERPOLATION POLYNOMIALE
P(π
5
)=
15
(15 −
π4
)−π
3π12
+
√2 1
5
(15 −
π6
)π2
π12
=− 1
100
− 136
+√
21
150124
=925
+√
2425
' 0,58626
D’autre part,
sin(π
5
)' 0,5877
5.5 Exercices
1. Écrire le polynôme d’interpolation de Lagrange P (x) de la fonction cosinusaux points −π
2 , 0 et π2 . Calculer P
(π4
)et comparer le résultat à cos
(π4
).
2. Écrire le polynôme d’interpolation de Lagrange P (x) d’une fonction f ,construit sur les points−1,− 1
3 , 13 et 1. En déduire une expression approché
de sin(
π4
)par interpolation de la fonction
R → Rx 7→ f(x) = sin
(πx
2
)
5.6 Deux algorithmes de calcul
Rappel : On recherche les valeurs numériques prises par le polynôme d’in-terpolation en certains points et non son expression analytique. L’utilisationdirecte de la formule de Lagrange P (x) =
∑ni=0 yiLi(x) pour déterminer P (α)
nécessite le calcul pour chacun des polynômes Li des n fractions α−xj
xi−xjpuis
leur produit pour déterminer Li(α), enfin une multiplication yiLi(α). En négli-geant les additions dans le décompte des opérations, on aura pour chaque pointα(n + 1)2 multiplication et n(n + 1) divisions. On donne ici deux algorithmesplus intéressants.
5.6.1 Algorithme d’Aitken
Cet algorithme construit une suite de polynômes réalisant l’interpolation deLagrange sur un nombre de plus en plus élevé de points de base xj . Plus préci-sément, cet algorithme calcule P (α) en utilisant successivement les polynômesde degré 0,1, . . . ,n construits respectivement sur 1,2 . . . ,n + 1 points de base xj
parmi les abscisses xi données. Le calcul peut être présenté sous la forme d’untableau triangulaire.
5.6. DEUX ALGORITHMES DE CALCUL 21
y0
y1 P1,1(α)y2 P2,1(α) P2,2(α)y3 P3,1(α) P3,2(α) P3,3(α)...
......
. . .yk Pk,1(α) Pk,2(α) · · · Pk,k(α)...
......
. . .yn Pn,1(α) Pn,2(α) · · · · · · Pn,n(α)
P1,1 réalise l’interpolation sur la base des points x0, x1
P2,1 réalise l’interpolation sur la base des points x0, x2
Pk,1 réalise l’interpolation sur la base des points x0, xk
Pn,1 réalise l’interpolation sur la base des points x0, xn
Pk,k réalise l’interpolation sur la base des points x0, x1,. . . ,xk−1,xk
Pn,k réalise l’interpolation sur la base des points x0, x1,. . . ,xk−1,xn
Pn,n réalise l’interpolation sur la base des points x0, x1,. . . ,xn−1,xn
Chaque colonne est déterminée à partir de la précédente par la formule
Pk,j+1(α) =(α− xj)Pk,j(α)− (α− xj)Pj,j(α)
xk − xj
On montre que pour obtenir Pn,n(α), polynôme réalisant l’interpolation deLagrange sur les n+1 points, il faut n(n+1) multiplications et n(n+1)
2 divisionspour chaque point α. Ceci ne représente pas un gain énorme par rapport aucalcul direct, cependant, on constate fréquemment qu’on obtient un résultatsatisfaisant pour un degré k inférieur à n et en s’arrêtant au calcul de Pk,k.
5.6.2 Méthode barycentrique
On montre que le polynôme d’interpolation de Lagrange peut s’écrire
P (x) =
∑ni=0 yi
Ai
x−xi∑ni=0
Ai
x−xi
avec
Ai =1
(xi − x0) · · · (xi − xi−1(xi − xi+1 · · · (xi − xn)
=1∏n
j=0j 6=i
(xi − xj)
=n∏
j=0j 6=i
1(xi − xj)
Le calcul de Ai nécessite n divisions et n multiplications en effectuant lecalcul par la dernière expression. Le calcul de P (alpha) nécessite donc (n + 1)2
multiplications et (n + 1)2 divisions. L’avantage de cette méthode ne se faitsentir que si on doit effectuer le calcul en plusieurs valeurs αk. En effet, le calculdes Ai est indépendant de α et sera donc effectué une fois pour toutes.
22 CHAPITRE 5. INTERPOLATION POLYNOMIALE
Exercice
Écrire l’algorithme de cette méthode
23
Chapitre 6
Intégration
Soit à calculer I =∫ b
af(x) dx, avec a et b réels donnés et f une fonction
réelle.
6.1 Méthode des rectangles médians
On subdivise l’intervalle [a,b] en n intervalle élémentaires de même amplitudeet on pose
h =b− a
n
Sur chaque intervalle élémentaire, on se place au milieu xm de l’intervalle eton interpole la fonction f par la droite d’équation y = f(xm).
Soient x0 = a et xn = b.Sur l’intervalle [xi,xi+1] on a xm = xi+xi+1
2 .Sur l’intervalle [x0,x1] on a xm = x0+x0+h
2 = x0 + h2 .
Sur l’intervalle [x1,x2] on a xm = x0+h+x0+2h2 = x0 + 3h
2 .Sur l’intervalle [xi,xi+1] on a xm = x0 + 2i+i
2 h.On a donc y = f
(x0 + 2i+i
2 h).
Sur l’intervalle [xi,xi+1], l’aire Ai du rectangle Ri est
Ai =∫ xi+1
xi
f
(x0 +
2i + i
2h
)dx
= f
(x0 +
2i + i
2h
)[x]xi+1
xi
= (xi+1 − xi)f(
x0 +2i + i
2h
)= hf
(x0 +
2i + i
2h
)I∗R =
∑n−1j=0 Ai est l’approximation de I par la méthode des rectangles mé-
dians.
24 CHAPITRE 6. INTÉGRATION
I∗R =n−1∑j=0
hf
(x0 +
2i + i
2h
)
= hn−1∑j=0
f
(x0 +
2i + i
2h
)
= hn−1∑j=0
f
(a +
2i + i
2h
)
6.2 Méthode des trapèzes
L’intervalle [a,b] est subdivisé en n intervalles de même amplitude h = b−an .
On pose x0 = a et xn = b. Sur un intervalle [xi,xi+1] la fonction f est interpoléepar la droite passant par les points (xi,f(xi)) et (xi+1,f(xi+1)).
Soit Ai l’aire du trapèze Ti.
A0 =12
(f(x0) + f(x0 + h))h
A1 =12
(f(x0 + h) + f(x0 + 2h))h
......
An−1 =12
(f (x0 + (n− 1)h) + f(x0 + nh))h
Donc
Ai =12
(f (x0 + ih) + f (x0 + (i + 1)h))h, ∀i ∈ N,0 ≤ i < n
I∗T =∑n−1
j=0 Ai est l’approximation de I par la méthode des trapèzes.
I∗T =n−1∑j=0
Ai
=n−1∑j=0
12
(f (x0 + ih) + f (x0 + (i + 1)h))h
= h
[12f(x0) + f(x0 + h) + · · ·+ f (x0 + (n− 1)h) +
12f(x0 + nh)
]= h
[f(x0) + f(xn)
2+
n−1∑i=1
f(x0 + ih)
]
= h
[f(a) + f(b)
2+
n−1∑i=1
f(a + ih)
]
6.3. MÉTHODE DE SIMPSON 25
6.3 Méthode de Simpson
On procède toujours de la même manière. [a,b] est subdivisé en n intervallesde même amplitude h = b−a
2 . On pose x0 = a et xn = b. Sur un intervalle[xi−1,xi+1] la fonction f est interpolée par la parabole passant par les points(xi−1,f(xi−1)), (xi,f(xi)) et (xi+1,f(xi+1)).
On travaille sur une suite d’intervalles d’amplitude 2h, ce qui implique quen doit être pair. On pose n = 2p.
Donnons tout d’abord l’équation de la parabole passant par les 3 points decoordonnées (xi−1,f(xi−1)), (xi,f(xi)) et (xi+1,f(xi+1)).
Écrivons les polynômes de Lagrange basés sur les abscisses xi−1, xi et xi+1.
L0(x) =(x− xi)(x− xi+1)
(xi−1 − xi)(xi−1 − xi+1)
=(x− xi)(x− xi+1)
2h2
=x2 − x(xi−1 + xi+1) + xixi+1
2h2
=x2 − x(2xi + h) + xi(xi + h)
2h2
L1(x) =(x− xi−1)(x− xi+1)(xi − xi−1)(xi − xi+1)
=(x− xi−1)(x− xi+1)
−h2
= −x2 − x(xi−1 + xi+1) + xi−1xi+1
h2
= −x2 − x(2xi) + x2i − h2
h2
L2(x) =(x− xi−1)(x− xi)
(xi+1 − xi−1)(xi+1 − xi)
=(x− xi−1)(x− xi)
2h2
=x2 − x(xi−1 + xi) + xixi−1
2h2
=x2 − x(2xi − h) + xi(xi − h)
2h2
La parabole Pi d’interpolation de f sur [xi−1,xi+1] a donc pour équation :
Pi = f(xi−1)L0(x) + f(xi)L1(x) + f(xi+1)L2(x)
26 CHAPITRE 6. INTÉGRATION
α =1h2
(f(xi−1)
2− f(xi) +
f(xi+1)2
)β =
1h2
(−f(xi−1)
2(2xi + h) + 2xif(xi)−
f(xi+1)2
(2xi − h))
γ =1h2
(f(xi−1)
2xi(xi + h)− f(xi)(x2
i − h2)− f(xi+1)2
xi(xi − h))
Soient α le coefficient en x2 de Pi(x), β le coefficient en x de Pi(x) et γ leterme constant de Pi(x). On a alors
∫ xi+1
xi−1
Pi(x) dx =∫ xi+1
xi−1
(αx2 + βx + γ) dx
=[13αx3 +
12βx2 + γx
]xi+1
xi−1
=13α(x3
i+1 − x3i−1) +
12β(x2
i+1 − x2i−1) + γ(xi+1 − xi−1)
= (xi+1 − xi−1)[13α(x2
i+1 + xi+1xi−1 + x2i−1)
+12β(xi+1 + xi−1) + γ
]= 2h
[13α
((xi+1 + xi−1)2)− xi+1xi−1
)+
12β(xi+1 + xi−1) + γ
]= 2h
[13α(4x2
i − x2i + h2) + βxi + γ
]= 2h
[13α(3x2
i + h2) + βxi + γ
]
En reportant les expressions de α, β et γ, on obtient finalement :
∫ xi+1
xi−1
Pi(x) dx =h
3(f(xi−1) + 4f(xi) + f(xi+1))
Soit I∗S , la valeur approchée de I =∫ b
aPi(x) dx par la méthode de Simpson.
I∗S =p∑
i=1
∫ xi+1
xi−1
Pi(x) dx
Notons Ai =∫ xi+1
xi−1Pi(x) dx
6.3. MÉTHODE DE SIMPSON 27
A1 =h
3(f(x0) + 4f(x1) + f(x2))
A2 =h
3(f(x2) + 4f(x3) + f(x4))
......
Ap =h
3(f(xn−2) + 4f(xn−1) + f(xn))
D’où la formule
I∗S =h
3
[f(x0) + f(xn) + 2
p−1∑i=1
f(x0 + 2ih) + 4p−1∑i=1
f (x0 + (2i− 1)h)
]
28 CHAPITRE 7. RÉSOLUTION DES SYSTÈMES LINÉAIRES
Chapitre 7
Méthodes de résolution dessystèmes linéaires de néquations à n inconnues
Soit le système S suivant :
a1,1x1 + a1,2x2 + · · ·+ a1,nxn = b1
a2,1x1 + a2,2x2 + · · ·+ a2,nxn = b2
...an,1x1 + an,2x2 + · · ·+ an,nxn = bn
On note souvent le système sous sa forme matricielle a~x = ~b.
7.1 Méthodes directes
7.1.1 Méthodes de Cramer
Soit xi = ∆i∆ où ∆ est le déterminant de a et ∆i est le déterminant obtenu
en remplaçant la ième colonne de a par le vecteur ~b. Le calcul de ~x nécessite doncle calcul de n + 1 déterminants d’ordre n. Ceci s’avère inapplicable en pratique.
7.1.2 Méthodes de Gauss
Cette méthode consiste à transformer le système S en un système équivalentS′ que l’on sait résoudre, par exemple un système triangulaire ou diagonal.
Pour ce faire, les opérations permises sont la permutation d’équation dusystème ou la combinaison linéaire d’équations.
La méthode de triangulation avec pivot maximum partiel est la plus cou-rante sur les méthodes numériques. Le système S est transformé en un systèmetriangulaire supérieur.
7.1. MÉTHODES DIRECTES 29
a′1,1 a′1,2 · · · a′1,n
a′2,2 · · · a′2,n
. . ....
a′n,n
x′1x′2...
x′n
=
b1
b2
...bn
Pour obtenir un système triangulaire, il faut traiter les colonnes de la matrice
a depuis la première colonne jusqu’à la (n−1)ème. Ceci implique que l’algorithmede résolution devra comporter une boucle d’index j variant de 1 à n− 1.Algorithme de principe de la triangulationdébutpour j variant de 1 à n− 1
Rechercher parmi les valeurs aj,j , aj+1,j ,..., an,j celle qui a la plus grande
valeur absolue.Soit ap,j cet élément. Il est appelé pivot (la méthode échoue si le pivot
est nul).si p 6= i alors on permute les équations d’indice p et jpour i variant de j + 1 à n
début z ← − ai,j
aj,j
Les nouveaux éléments de l’équation i sont obtenus en leur ajou-tant le produit par z des éléments de même rang dans l’équation j
finfin
Une fois le système triangularisé, on le résout facilement par remontée.a1,1x1 + a1,2x2 + · · · + a1,nxn = b1
a2,2x2 + · · · + a2,nxn = b2
. . ....
...an,nxn = bn
La dernière équation donne directement xn = bn
an,n. La valeur de xn est alors
portée dans la (n − 1)ème équation, d’où on tire xn−1 et ainsi de suite jusqu’àx1.
La ième équation est :
ai,ixi + ai,i+1xi+1 + · · ·+ ai,nxn = bn
On en déduit
xi =bi −
∑nj=i+1 ai,jxj
ai,i
Écrire l’algorithme de la procédure remontée dont les arguments sont :
– n entier, ordre du système ;– a matrice carrée triangulaire d’ordre n ;– b vecteur de n éléments ;– x vecteur de n éléments, solutions du système.
30 CHAPITRE 7. RÉSOLUTION DES SYSTÈMES LINÉAIRES
Écrire l’algorithme de l’algorithme triangulation dont les arguments sont :
– n entier, ordre du système ;– a matrice carrée triangulaire d’ordre n ;– b vecteur de n éléments ;
Écrire l’algorithme du programme principal.
7.2 Méthodes itérativesDans ce type de méthodes, on ne modifie pas le système. On par d’un vecteur
arbitraire ~x(0) (par exemple ~x(0) = ~0) et on construit une suite de vecteurs ~x(k)
qui, sous certaines conditions, converge vers la solution ~x du système.
7.2.1 Méthode de JacobiExempleSoit le système de 3 équations à 3 inconnues :
a1,1x1 + a1,2x2 + a1,3xn = b1 (7.1)a2,1x1 + a2,2x2 + a2,3xn = b2 (7.2)a3,1x1 + a3,2x2 + a3,3xn = b3 (7.3)
Partant de valeurs arbitraires x(0)1 , x
(0)2 , x
(0)3 , on résout l’équation (7.1) en
x1.
x1 =b1 − a1,2x2 − a1,3x3
a1,1
Soit en tenant compte des valeurs initiales :
x(1)1 =
b1 − a1,2x(0)2 − a1,3x
(0)3
a1,1
De même, on résout les équation (7.2) et (7.3) et on obtient :
x(1)2 =
b2 − a2,1x(0)1 − a2,3x
(0)3
a2,2
x(1)3 =
b1 − a3,1x(0)2 − a3,2x
(0)3
a3,3
On obtient ainsi les composantes du vecteur ~x(1), on recommence le processuset on obtient ~x(2) et ainsi de suite jusqu’à un rang n tel que ~x(n) = ~x(n−1) à ~εprès.
Une condition suffisante mais pas nécessaire de convergence est que la ma-trice a du système soit diagonale strictement dominante, c’est-à-dire :
∀i ∈ N,1 ≤ i ≤ n, |ai,i| >n∑
j=1j 6=i
|ai,i|
7.2. MÉTHODES ITÉRATIVES 31
7.2.2 Méthode de Gauss-SeidelPartant comme la méthode de Jacobi, on utilise systématiquement les valeurs
actuelle des composantes du vecteur ~x et non les valeurs du rang précédent.Ainsi, on a :
x(i+1)1 =
b1 − a1,2x(i)2 − a1,3x
(i)3
a1,1(7.4)
x(i+1)2 =
b2 − a2,1x(i+1)1 − a2,3x
(i)3
a2,2(7.5)
x(i+1)3 =
b3 − a3,1x(i+1)1 − a3,2x
(i+1)2
a3,3(7.6)
Ceci assure une convergence plus rapide que la méthode de Jacobi.Ces méthodes échouent si un pivot est nul.On arrêtera les itérations quand
∑ni=1
∣∣∣x(k)i − x
(k−1)i
∣∣∣ < nε
Écrire l’algorithme de la procédure de résolution d’un système d’équationspar la méthode de Gauss-Seidel et l’algorithme d’une fonction permettant detester si la matrice a est diagonale strictement dominante.
32 CHAPITRE 8. MÉTHODE DES MOINDRES CARRÉS
Chapitre 8
Lissage d’un ensemble depoints par une fonctionpolynôme - Méthode desmoindres carrés
8.1 Position du problèmeOn a relevé expérimentalement Nexp valeurs y0,y1, . . . ,yNexp
pour Nexp abs-cisses x0,x1, . . . ,xNexp
. On cherche le Polynôme P (x) de degré N (N < Nexp)qui représente au mieux les Nexp points (xi,yi).
P (x) = C0 + C1x + C2x2 + · · ·+ CNxN
8.2 Critère des moindres carrésLe critère des moindres carrés consiste à choisir les coefficients Cj du poly-
nôme P (x) de façon à minimiser l’expression
ω =Nexp∑i=0
(yi − P (xi))2
En expriment ∂ω∂Cj
= 0 pour j variant de 1 à N , on trouve que les coefficients
Cj doivent être solution d’un système linéaire de N + 1 inconnues A.~C = ~B
où ~C est un vecteur à N + 1 dimensions qui sont les inconnues du système etsont donc les coefficients du polynôme à déterminer. A est une matrice carréed’ordre N + 1 telle que :
Ai,j =Nexp−1∑
k=0
xi+jk ,∀(i,j) ∈ N,0 ≤ i ≤ N,0 ≤ j ≤ N
~B est un vecteur de dimension N + 1 tel que :
8.3. EXERCICE 33
Bi =Nexp−1∑
k=0
xikyk,∀i ∈ N2,0 ≤ i ≤ N
Le système obtenu est mal conditionné, mais en pratique N est souvent prisfaible (N ≤ 2) et sa résolution ne pose pas de problème.
8.3 ExerciceÉtablir les formules dans le cas où N = 1 (équation de la droite des moindres
carrés).Appliquer les formules trouvées à l’ensemble des points suivants :xi -2 -1 0 1 2 3yi 0 0,5 1 2 4 6
Écrire l’algorithme de la procédure permettant de déterminer les coefficientsde la droite des moindres carrés.
34CHAPITRE 9. RÉSOLUTION NUMÉRIQUES DES ÉQUATIONS DIFFÉRENTIELLES
Chapitre 9
Résolution numériques deséquations différentielles
9.1 Position du problème
Soit l’équation différentielle du second ordre avec conditions initiales suivantesuivante :
Ad2ydt2 + B dy
dt + Cy = Dy(0) = y0(dydt
)0
= V0
En posant z = dydt , le système précédent devient
dzdt = −B
Az − CAy + D
Ay(0) = y0
z(0) = V0
On peut généraliser le raisonnement aux équations différentielles d’ordren avec conditions initiales. Ainsi, toute équation différentielle d’ordre n avecconditions initiales peut se ramener à un système de n équations diférentiellescouplées du premier ordre.
Dans le cas général, un problème aux conditions intiales est de la forme{d~ydt = ~f(~y,t)
~y(0) = y0
avec{
~y = y1,y2, . . . ,yn
~f = f1,f2, . . . ,fn
9.2 Méthode d’Euler
Soit l’équation différentielle suivante :{ dydy = f(y,t)
y(0) = y0
9.3. MÉTHODE DE RUNGE-KUTTA À PAS UNIQUE 35
Si on suppose la fonction y connue à l’instant t, on peut déduire sa valeuren l’instant t + ∆t grâce au développement en série de Taylor.
y(t + ∆t) = y(t) + ∆tdy
dt+
(∆t)2
2!d2y
dt2+
(∆t)3
3!d3y
dt3+ · · ·
À l’ordre 1 de ce développement on obtient :
y(t + ∆t) ' y(t) + ∆tdy
dt= y(t) + ∆tf(y,t)
Si ∆t est constant, on peut écrire
yi+1 = yi + ∆tf(yi,ti)
Exemple Soit à résoudre le système suivant :{dydt + y2 = 0
y(0) = 1
La solution exacte de ce système est y = 1t+1 .
Appliquons la méthode d’Euler
f(y,t) = −y2
yi+1 = yi + ∆tf(yi,ti) = yi −∆ty2
Si on fixe ∆t = 0.1, on obtient les valeurs suivantes :
i ti yi exact yi donné par erreur relativela méthode d’Euler en %
1 0,1 0,90909091 0,90000000 1,002 0,2 0,83333333 0,81900000 1,723 0,3 0,76923077 0,75192390 2,254 0,4 0,71428571 0,69538494 2,655 0,5 0,66666667 0,64702892 2,957 0,7 0,58823529 0,56854190 3,259 0,9 0,52631579 0,50746495 3,5811 1,1 0,47619048 0,45850815 3,71
Tab. 9.1 – Comparaison entre les valeurs données par la méthode d’Euler et lesvaleurs de la solution analytique de l’équation différentielle
On constate que l’erreur augmente au fur et à mesure que i augmente. Laméthode d’Euler est peu précise.
9.3 Méthode de Runge-Kutta à pas unique
9.3.1 Méthode de Runge-Kutta à l’ordre 2Cette méthode est obtenue en prenant les différences centrées au premier
ordre.
36CHAPITRE 9. RÉSOLUTION NUMÉRIQUES DES ÉQUATIONS DIFFÉRENTIELLES
yi+1 − yi = ∆tf(y1+ 12,ti+ 1
2)
Or y1+ 12
est inconnu. On le remplace donc par une valeur estimée notéey1+ 1
2. On obtient le système suivant :
yi+1 = yi + ∆tf(y1+ 12,ti+ 1
2)
y1+ 12
= yi + ∆t2 f(yi,ti)
ti+ 12
= ti + ∆t2
Pour évaluer yi+1, il faut calculer 2 fois la fonction f . C’est pour cette raisonque cette méthode est dite d’ordre 2.
9.3.2 Méthode de Runge-Kutta à l’ordre 4Le système à calculer est le suivant :
yi+1 = yi + ∆t
6
(f(yi,ti) + 2f(yi+ 1
2,ti+ 1
2) + 2f(y′i+ 1
2,ti+ 1
2) + f(yi+1,ti+1)
)yi+ 1
2= yi + ∆t
2 f(yi,ti)y′i+ 1
2= yi + ∆t
2 f(yi+ 12,ti+ 1
2)
yi+1 = yi + ∆tf(y′i+ 12,ti+ 1
2)
9.4 Formules d’Adams ouvertesSoit l’équation différentielle suivante :{
dydt = f(y,t)
y(0) = y0
Le développement en série de Taylor autour de t donne :
y(t + ∆t) = y(t) + ∆tdy
dt+
(∆t)2
2!d2y
dt2+
(∆t)3
3!d3y
dt3+ · · ·+ (∆t)n
n!dny
dtn
L’équation différentielle se transforme de la façon suivante :dydt = y′(t) = f(y,t)
d2ydt2 = y′′(t) = f ′(y,t)
...dnydtn = y(n)(t) = f (n−1)(y,t)
où yi+1 = yi + ∆tfi + (∆t)2
2! f ′i + (∆t)n
n! f(n−1)i .
9.4.1 Formules d’Adams à l’ordre 1Si dans l’équation précédente, on regarde uniquement les 2 premiers termes,
on obtient
yi+1 = yi + ∆tfi
C’est la méthode d’Euler.
9.4. FORMULES D’ADAMS OUVERTES 37
9.4.2 Formules d’Adams à l’ordre 2En utilisant les 3 premiers termes, on obtient la formule d’Adams à l’ordre
2 :
yi+1 = yi + ∆tfi +(∆t)2
2!f ′i
Or,
f ′i =fi − fi−1
∆t
Donc,
yi+1 = yi + ∆tfi +(∆t)2
2!fi − fi−1
∆t
= yi + ∆tfi +(∆t)
2(fi − fi−1)
= yi +∆t
2(3fi − fi−1)
Pour calculer yi+1, il faut connaître yi et yi−1, ce qui interdit l’utilisation dela méthode pour calculer y1. On utilisera alors la méthode de Runge-Kutta.
9.4.3 Formules d’Adams d’ordre plus élevéOn peut bien évidemment utiliser les ordres plus élevés en généralisant le
raisonnement précédent.
Index
addition, 6affactation, 8algorithme, 7algorithme d’Aitken, 20alternative, 7
bloc, 8boucle, 7
début, 8dichotomie, 14
entier, 4exposant, 4
faire tant que, 8fin, 8
intégration, 23interpolation, 17itération, 7
méthode barycentrique, 21méthode de Cramer, 28méthode de Gauss, 28méthode de Jacobi, 30méthode de Newton, 14méthode de Seidel, 31méthode de Simpson, 25méthode des moindres carrés, 32méthode des rectangles médians, 23méthode des trapèzes, 24mantisse, 4multiplication, 5
point fixe, 15polynôme de Lagrange, 18pour, 8
réel, 4répéter jusqu’à, 8répéter tant que, 8
série, 10si alors sinon, 7système linéaire, 28
tant que faire, 7test, 7
virgule flottante, 4
38
