Analyse Numérique

(Pour Génie Informatiqe)

n©N

Présenté par:
A. Laghrib
[email protected]

2024

ENSA Khouribga, Université Sultan Moulay Slimane

Analyse Numérique

1 Introduction

2 Analyse de l’erreur
Erreurs dues à la représentation
Norme IEEE-754
Arithmétique flottante

3 Résolution numérique de f (x) = 0

Méthode de la dichotomie
La méthode de point fixe
La méthode de Newton
Vitesse de convergence de la méthode de point fixe et de Newton
Méthode de la corde (Newton-Corde)
Méthode de sécante

4 Résolution des équations différentielles

A. Laghrib | c b n a 2 / 133
Analyse Numérique | Introduction

Contents

1 Introduction

2 Analyse de l’erreur
Erreurs dues à la représentation
Norme IEEE-754
Arithmétique flottante
3 Résolution numérique de f (x) = 0
Méthode de la dichotomie
La méthode de point fixe
La méthode de Newton
Vitesse de convergence de la méthode de point fixe et de Newton
Méthode de la corde (Newton-Corde)
Méthode de sécante
4 Résolution des équations différentielles

A. Laghrib | c b n a 3 / 133
Analyse Numérique | Introduction

Introduction général

Introduction
Dans les différents applications, les méthodes classiques utilisées en
mathématiques sont très limitées pour résoudre tous les problèmes. On ne
sait pas, par exemple, donner une formule pour calculer exactement les
racines des équations de degré 5 ou plus ; on ne sait pas non plus trouver la
solution analytique de certaines équations différentielles ni calculer
certaines intégrales définies. On remplace alors la résolution mathématique
exacte du problème par sa résolution numérique qui est, en général,
approchée.

A. Laghrib | c b n a 4 / 133
Analyse Numérique | Introduction

Introduction général

Exemples
On considère l’équation différentielle suivante :
1
(E) y ′ + y = , y(1) = 2.
1 + t2
La primitive suivante ne peut pas être explicité par des fonctions
usuelles :
et
Z
c(t) = dt
1 + t2
La résolution de l’équation non-linéaire suivante :

exp(x2 ) + ln(x + 1) − x = 0.

A. Laghrib | c b n a 5 / 133
Analyse Numérique | Introduction

Introduction général

L’analyse numérique
L’analyse numérique est considérée comme un outil puissant d’analyse
quantitative et qualitative. Ceci est accompagné par l’évolution extrême des
ordinateurs et logiciels. Parmi ces logiciel on trouve "Matlab".

A. Laghrib | c b n a 6 / 133
Analyse Numérique | Introduction

Introduction général

L’analyse numérique
Sur ordinateur, approximer une solution x par x∗ génère des erreurs. Il faut
donc calculer ces erreurs pour mesurer la précision des méthodes utilisées.
Voici les deux erreurs qu’il faut connaitre :
L’erreur absolue est définie par :

∆x = |x − x∗ |.

L’erreur relative est définie par :

|x − x∗ |
Er = .
|x|

A. Laghrib | c b n a 7 / 133
Analyse Numérique | Introduction

Introduction général

L’analyse numérique
L’erreur absolue donne une mesure quantitative de l’erreur commise et
l’erreur relative en mesure l’importance.

Exemple
si l’on fait usage d’un chronomètre dont la précision est de l’ordre du
dixième de seconde, l’erreur absolue est bornée par

∆x = |x − x∗ | ≤ 0.1.

Dans le contexte d’un marathon

Dans le contexte d’une course de 100 mètres.

A. Laghrib | c b n a 8 / 133
Analyse Numérique | Introduction

Introduction général

L’analyse numérique
Ce cours est réparti en cinq chapitres :
Analyse de l’erreur sur ordinateur ;
La résolution des equations non-linéaires (dimension supérieure) ;
L’interpolation numérique ;
Résolution des systèmes Ax = b : méthodes itératives ;
Résolution des équations différentielles.
On commence par le premier chapitre.

A. Laghrib | c b n a 9 / 133
Analyse Numérique | Analyse de l’erreur

Contents

1 Introduction

2 Analyse de l’erreur
Erreurs dues à la représentation
Norme IEEE-754
Arithmétique flottante
3 Résolution numérique de f (x) = 0
Méthode de la dichotomie
La méthode de point fixe
La méthode de Newton
Vitesse de convergence de la méthode de point fixe et de Newton
Méthode de la corde (Newton-Corde)
Méthode de sécante
4 Résolution des équations différentielles

A. Laghrib | c b n a 10 / 133
Analyse Numérique | Analyse de l’erreur

Analyse de l’erreur

L’analyse numérique
Une partie importante de l’analyse numérique consiste donc à contenir les
effets des erreurs ainsi introduites, qui proviennent de trois sources
principales :
les erreurs de modélisation ;
les erreurs de représentation sur ordinateur ;
les erreurs de troncature.
On s’intéressera dans la suite aux erreurs sur ordinateur.

A. Laghrib | c b n a 11 / 133
Analyse Numérique | Analyse de l’erreur

Analyse de l’erreur

Représentation des nombres sur ordinateur

La structure interne de la plupart des ordinateurs s’appuie sur le système
binaire. L’unité d’information ou bit prend la valeur 0 ou 1.
Pour transformer un entier positif N dans sa représentation binaire
habituelle, il faut déterminer les ai tels que :

(N )10 = (an−1 an−2 an−3 . . . a2 a1 a0 )2

Conversion d’une fraction décimale en valeur binaire. Soit F , une

fraction décimale comprise entre 0 et 1. Il faut donc trouver les di tels
que :

(F )10 = (0, d1 d2 d3 . . .)2 = d1 × 2−1 + d2 × 2−2 + . . .

A. Laghrib | c b n a 12 / 133
Analyse Numérique | Analyse de l’erreur

Analyse de l’erreur

Représentation des entiers signés

Pour les entiers signés, il faut tenir compte du signe de l’entier. Nous
étudierons la représentation en complément à 2 :
La représentation en complément à 2 est très fréquemment utilisée.
C’est le cas pour le langage Java qui l’utilise pour les entiers signés. Si
l’on dispose de n bits pour exprimer l’entier N , on pose :

(N )10 = (−an−1 an−2 an−3 . . . a2 a1 a0 )2

c-à-s que :

N = −an−1 × 2n−1 + an−2 × 2n−2 + an−3 × 2n−3 +

. . . a2 × 22 + a1 × 21 + a0 × 20 .

A. Laghrib | c b n a 13 / 133
Analyse Numérique | Analyse de l’erreur

Analyse de l’erreur

Représentation des entiers signés

Il faut remarquer le signe négatif devant le terme an−1 . On constate
facilement que tous les entiers positifs vérifient :

an−1 = 0

Exemples
La représentation en complément à 2 sur 4 bits de 0101 vaut :

−0 × 23 + 1 × 22 + 0 × 21 + 1 × 20 .

Quelle est la représentation des nombres −9 et −23 ?

A. Laghrib | c b n a 14 / 133
Analyse Numérique | Analyse de l’erreur

Analyse de l’erreur

Représentation des nombres réels

La tâche de représentation est plus complexe dans le cas des nombres réels.
En effet, dans le système décimal, nous avons l’habitude de représenter un
nombre x sous la forme :

x = ±m × 10r .

où m est la mantisse.
r est l’exposant, et 10 est la base.

A. Laghrib | c b n a 15 / 133
Analyse Numérique | Analyse de l’erreur

Analyse de l’erreur
Représentation des nombres réels
Généralement, pour une base quelconque b, on écrit :

x = ±m × br .

On appelle cette représentation la notation flottante.

La forme générale de la mantisse est la suivante :

m = 0, d1 d2 d3 . . . dn . . .

ce qui donne :

m = d1 × b−1 + d2 × b−2 + . . . dn × b−n + . . .

Pour problème de mémoire, on ce contente des n premiers termes :

m = d1 × b−1 + d2 × b−2 + . . . dn × b−n .

A. Laghrib | c b n a 16 / 133
Analyse Numérique | Analyse de l’erreur

Analyse de l’erreur

Représentation des nombres réels

Les di vérifient :

1 ≤ d1 ≤ b − 1 et 0 ≤ di ≤ b − 1, i = 2...n

La mantisse est normalisée, c’est-à-dire que son premier chiffre est

toujours différent de 0.
La normalisation permet d’assurer l’unicité de la représentation.

0, 1030 × 102 et 0, 0103 × 103

A. Laghrib | c b n a 17 / 133
Analyse Numérique | Analyse de l’erreur

Analyse de l’erreur

Représentation des nombres réels

pour représenter le nombre 10, 3 dans la base 10 et n = 4 chiffres dans la
mantisse. Ainsi, la mantisse satisfait toujours :
1
≤ m < 1.
b

Il faut trouver une représentation de la mantisse dans la base de 2.

Les calculatrices de poche se distinguent des ordinateurs
principalement par le fait qu’elles utilisent la base 10 (b = 10).

A. Laghrib | c b n a 18 / 133
Analyse Numérique | Analyse de l’erreur | Erreurs dues à la représentation

Analyse de l’erreur

Erreurs dues à la représentation

Le fait d’utiliser un nombre limité de bits pour représenter un nombre réel a
des conséquences importantes. Ainsi, la représentation en virgule flottante
induit une erreur relative aux
nombre de bits de la mantisse ;
l’utilisation de la troncature ;
Le nombre qu’on veut représenter.

A. Laghrib | c b n a 19 / 133
Analyse Numérique | Analyse de l’erreur | Erreurs dues à la représentation

Analyse de l’erreur

Erreurs dues à la représentation

Soit la suite définie par :

xn+1 = 3xn (2 − xn )

On peut la programmer de deux façons :

x1 = 3 × x1 × (2 − x1 ) ;
x2 = 6 × x2 − 3 × x2 × x2 ;
On doit trouver la même chose "mathématiquement", mais les opérations
ne sont pas faites dans le même ordre sur machine.

A. Laghrib | c b n a 20 / 133
Analyse Numérique | Analyse de l’erreur | Erreurs dues à la représentation

Analyse de l’erreur

Erreurs dues à la représentation

L’intervalle entre les nombres représentables varie en longueur selon
l’exposant devant la mantisse.

Définition
La précision machine ϵm est la plus grande erreur relative que l’on puisse
commettre en représentant un nombre réel sur ordinateur en utilisant la
troncature.

A. Laghrib | c b n a 21 / 133
Analyse Numérique | Analyse de l’erreur | Erreurs dues à la représentation

Analyse de l’erreur
Erreurs dues à la représentation
On a un résultat important sur la précision machine.

Theorème
La précision machine ϵm vérifie :

ϵm ≤ b1−n .

où b est la base utilisée et n le nombre de chiffres (bits si b = 2) de la

mantisse.
b1−n est la borne supérieure pour la précision machine. On peut montrer
que cette borne est presque atteinte pour tous les nombres x de
développement en base b de la forme :

x = 0, 100 . . . 0(b − 1)(b − 1) . . . × br .

A. Laghrib | c b n a 22 / 133
Analyse Numérique | Analyse de l’erreur | Norme IEEE-754

Analyse de l’erreur

Norme IEEE-754
Norme visant à standardiser la représentation des nombres sur les
ordinateurs. En particulier elle impose le nombre de bits pour la mantisse,
et l’exposant pour les nombres reels à 32 bits (simple precision) et les reels
64 bits (double precision). Fait en sorte que l’on peut determiner la precision
machine ainsi que le plus grand et plus petit reels (simple et double
precision) représentable indépendemment de l’ordinateur.

A. Laghrib | c b n a 23 / 133
Analyse Numérique | Analyse de l’erreur | Norme IEEE-754

Analyse de l’erreur

Format simple précision

Un nombre flottant simple précision est stocké dans un nombre de 32 bit : 1
bit de signe, 8 bits pour l’exposant et 23 pour la mantisse. L’exposant est
donc décalé de 28−1 − 1 = 127 dans ce cas. L’exposant −127 (qui est
décalé vers la valeur 0) est réservé pour zéro et les nombres dénormalisés,
tandis que l’exposant 128 (décalé vers 255) est réservé pour coder les infinis
et les NaNs.

A. Laghrib | c b n a 24 / 133
Analyse Numérique | Analyse de l’erreur | Norme IEEE-754

Analyse de l’erreur

Format simple précision

La norme IEEE-754 en simple précision est basée sur la représentation :

(d1 d2 . . . d32 )10 = (−1)d1 2d2 d3 ...d9 2−127 × (1, d10 . . . d32 )2

Exemple
Les 32 bits suivants (en simple précision) :

1110 0001 1110 0100 0000 0000 0000 0000

Codez le nombre −118, 625 en utilisant IEEE 754. La réponse est :

1100 0010 1110 1101 0100 0000 0000 0000

A. Laghrib | c b n a 25 / 133
Analyse Numérique | Analyse de l’erreur | Norme IEEE-754

Analyse de l’erreur

Exercice
Donner la representation flottante du nombe 85.125 en simple
précision.
Donner la representation flottante du nombe 23.255 en simple
précision.
Codez le nombre 0.2 en utilisant IEEE 754.

A. Laghrib | c b n a 26 / 133
Analyse Numérique | Analyse de l’erreur | Norme IEEE-754

Analyse de l’erreur

Norme IEEE-754
Le format double précision est identique au simple précision, mis à part le
fait que les champs sont plus grands. En effet, il possède 52 bits de
mantisse, et 11 bits d’exposant. La mantisse est très élargie, alors que
l’exposant est peu élargi. Ceci est dû au fait que, selon les créateurs du
standard, la précision est plus importante que l’amplitude. Les NaNs et les
infinis sont représentés en mettant tous les bits de l’exposant à 1 (2047).
Pour les nombres normalisés, le décalage de l’exposant est +1023.

A. Laghrib | c b n a 27 / 133
Analyse Numérique | Analyse de l’erreur | Norme IEEE-754

Analyse de l’erreur

Format simple précision

La norme IEEE-754 en double précision est basée sur la représentation :

(d1 d2 . . . d64 )10 = (−1)d1 × 2d2 d3 ...d1 2 2−1023 × (1, d13 . . . d64 )2

A. Laghrib | c b n a 28 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur
Arithmétique flottante
Afin de simplifier l’exposé, nous utilisons le système décimal, mais les effets
décrits valent également pour les autres bases. Tout nombre réel x s’écrit
sous la forme :

x = ±(0, d1 d2 . . . dn dn+1 . . .) × 10r

Définition
Soit x, un nombre réel. On note f l(x) sa représentation en notation
flottante à n chiffres définie par :

f l(x) = ±(0, d1 d2 . . . dn ) × 10r

La convention IEEE-754 impose l’utilisation de l’arrondi dans la

représentation binaire des nombres réels.
A. Laghrib | c b n a 29 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Exemples
Si l’on choisit n = 4, alors on a :
f l(π) = 0, 3142 × 101 .
f l(14, 4771) = 0, 1448 × 102 .
f l(exp) = 0, 2719 × 101 .
f l(1/7) = 0, 1429 × 100

A. Laghrib | c b n a 30 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur

Opérations élémentaires
Les opérations élémentaires sont l’addition, la soustraction, la
multiplication et la division. Soit x et y, deux nombres réels. On effectue ces
opérations en arithmétique flottante de la façon suivante :

x + y → fl(fl(x) + fl(y))
x − y → fl(fl(x) − f(y))
x ÷ y → fl(fl(x) ÷ fl(y))
x × y → fl(fl(x) × fl(y))

A. Laghrib | c b n a 31 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur

Exemples
Si l’on prend n = 4, alors on a :
1 1
   
× 3 → fl fl × fl(3)
3 3
   
= fl 0, 3333 × 100 × 0, 3000 × 101
 
= fl 0, 09999000 × 101
= 0, 9999 × 100

On remarque une légère perte de précision par rapport à la valeur exacte de

cette opération qui est 1.

A. Laghrib | c b n a 32 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur

Remarque
Il faut bien remarquer que des opérations mathématiquement équivalentes
ne le sont pas forcément en arithmétique flottante. L’ordre des opérations
est très important.

Exemple
La propriété de distributivité de la multiplication sur l’addition n’est pas
toujours respectée en arithmétique flottante (voir Fortin et Pierre, réf. [18]).
En effet, en arithmétique exacte :

122 × (333 + 695) = (122 × 333) + (122 × 695) = 125416

A. Laghrib | c b n a 33 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur

Exemple
En arithmétique flottante avec n = 3, on obtient d’une part :
h   i
122 × (333 + 695) = fl 0, 122 × 103 × fl 0, 333 × 103 + 0, 695 × 103
h   i
= fl 0, 122 × 103 × fl 1, 028 × 103
h   i
= fl 0, 122 × 103 × 0, 103 × 104
 
= fl 0, 012566 × 107
= 0, 126 × 106

A. Laghrib | c b n a 34 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur

Exemple
En arithmétique flottante avec n = 3, on obtient d’une part :
h  
122 × 333 + 122 × 695 = fl fl 0, 122 × 103 × 0, 333 × 103
 i
+ fl 0, 122 × 103 + 0, 695 × 103
h    i
= fl fl 0, 040626 × 106 + fl 0, 08479 × 106
h i
= fl 0, 406 × 105 + 0, 848 × 105
 
= fl 1, 254 × 105
= 0, 125 × 106

A. Laghrib | c b n a 35 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur

Attention
Il existe d’autre part, un certain nombre d’opérations risquées. Soustraire
deux nombres presque identiques :
√ √
7001 − 7000 = 0, 8367 × 102 − 0, 8367 × 102
= 0, 000100 si n = 4
√ √
7001 − 7000 = 0, 83672 × 102 − 0, 83666 × 102
= 0, 6 × 10−2 si n = 5

A. Laghrib | c b n a 36 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur

Alternative
Dans ce cas-ci on peut remédier à cette difficulté en évitant la soustraction
des racines :
√ √ x−y
x− y = √ √
x+ y
et on trouve 0,5977 10-2 au lieu de 0 pour n = 4.

A. Laghrib | c b n a 37 / 133
Analyse Numérique | Analyse de l’erreur | Arithmétique flottante

Analyse de l’erreur

Conclusion
L’ordre dans lequel on fait les opérations et le nombre d’opérations ont un
impact important sur la précision du résultats. Ainsi on devrait ”toujours“ :
éviter les opérations avec des nombres très différents en ordre de
grandeurs.
éviter si possibles les soustractions avec des nombre relativement
proche,
on devrait faire les sommes en ordre décroissant.

A. Laghrib | c b n a 38 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Contents

1 Introduction

2 Analyse de l’erreur
Erreurs dues à la représentation
Norme IEEE-754
Arithmétique flottante
3 Résolution numérique de f (x) = 0
Méthode de la dichotomie
La méthode de point fixe
La méthode de Newton
Vitesse de convergence de la méthode de point fixe et de Newton
Méthode de la corde (Newton-Corde)
Méthode de sécante
4 Résolution des équations différentielles

A. Laghrib | c b n a 39 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Introduction
Dans plusieurs application on est toujours amené à résoudre des equation
de type :
f (x) = 0.
Des equations sont simples à résoudre tel que

ax + b = 0

D’autres sont assez compliquées et impossible à résoudre analytiquement,

comme :
3x5 − exp(x2 ) + x + 1 = 0

A. Laghrib | c b n a 40 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Question
Quelle est donc la solution ?

Réponse
Utiliser des approximation numérique de la solution !

Objectif
L’objectif est de chercher les solutions possibles (les zéros ou racines de f )

A. Laghrib | c b n a 41 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Définition
Soit f : I ⊂ R → R une fonction bien définie. On dit que f admet un zero
α ∈ I si :
f (α) = 0.
On dit que α est une racine de f .

A. Laghrib | c b n a 42 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Méthodologie
Les méthodes numériques pour approcher α consistent à :
Localiser où les zéros de f existent (intervalle).
Construire à partir d’une donnée initial α0 , une suite (αn )n∈N∗ telle
que :
lim αn = α.
n→+∞

On dit alors que α est une racine de f et que la méthode est

convergente.

A. Laghrib | c b n a 43 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Méthodologie
Dans la suite on va étudier quelques méthodes classiques pour approximer
de tels solutions. Ça dépend en fait de la convergence des méthodes
utilisées et les données disponibles.

Définition
On dit que la suite (αn )n∈N∗ converge vers α avec un ordre p s’il existe
une constante C telle que :

|αn+1 − α|
≤ C.
|αn − α|p

A. Laghrib | c b n a 44 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Définition
Si p = 1 (et C < 1), on dit alors que la convergence est linéaire.
Si p = 2, on dit alors que la convergence est quadratique.
Si p = 3 alors on parle de convergence cubique.
Si p = 1 (et C = Cn ), où Cn dépend de n et limn→+∞ Cn = 0, on dit
alors que la convergence est surlinéaire.
On dit que p est l’ordre de convergence.

A. Laghrib | c b n a 45 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Remarques
En général le choix de la donnée initial α0 affecte la convergence de la
méthode itérative utilisée.
On a souvent des convergences locales, c-à-d α0 au voisinage de α.
Pour la convergence globale, il faut montrer la convergence ∀α0 ∈ R.
Dans ce qui suit, nous présentons plusieurs techniques de résolution,
chacune ayant ses avantages et ses inconvénients.

A. Laghrib | c b n a 46 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Définition
Supposons que {βn }∞ ∞
n=1 est une suite qui converge vers zero et {αn }n=1
converge vers α. S’il existe une constante positive K tel que

|αn − α| ≤ K |βn | , for large n,

alors on dit que {αn }∞

n=1 converge vers α avec un taux, ou ordre, de
convergence O (βn ). On écrit alors αn = α + O (βn ).

A. Laghrib | c b n a 47 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Remarque
La définition précédente permet de comparer {αn }∞
n=1 à une suite
arbitraire {βn }∞
n=1 , on a alors en général :

1
βn = ,
np
pour p > 0. On est généralement intéresses à la plus grande valeur de p
avec αn = α + O (1/np )

A. Laghrib | c b n a 48 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

exemple
Supposons que, pour n ≥ 1,
n+1 n+3
αn = et α̂n = .
n2 n3
Les deux limites limn→∞ αn = 0 et limn→∞ α̂n = 0, mais la suite {α̂n }
converge vers cette limite plus rapidement que la suite {αn }.

A. Laghrib | c b n a 49 / 133
Analyse Numérique | Résolution numérique de f (x) = 0

Résolution numérique de f (x) = 0

Définition
Supposons que limh→0 G(h) = 0 et limh→0 F (h) = L. S’il existe une
constante positive K tel que |F (h) − L| ≤ K|G(h)|, pour h assez petit,
on a alors F (h) = L + O(G(h)).

Exercice
Montrer que :
1
cos(h) + h2 = 1 + O(h4 ).
2

A. Laghrib | c b n a 50 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie
On veut résoudre f (x) = 0, où f est une fonction de I dans R non linéaire
(sinon c’est évident !).
On recherche donc un nombre réel x∗ tel que f (x∗ ) = 0. Comme pour
toute méthode itérative, on va donc construire une suite de nombres réels
x(0) , x(1) , ..., x(n) , ... qui converge vers x∗ . Puisqu’ici les termes de la suite
sont des nombres réels, on les notera plus simplement

x0 , x1 , ..., xn , ...

A. Laghrib | c b n a 51 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie
Le principe de la dichotomie se base sur le théorème des valeurs
intermédiaires (TVI). On suppose que f : [a, b] −→ R est continue et que
f (a)f (b) < 0, c’est-à-dire qu’il y a au moins une racine réelle de f dans
]a, b[. On prend alors le milieu de l’intervalle c = a+b
2 .

A. Laghrib | c b n a 52 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie
Si f (c) = 0 (ou numériquement très proche de 0), on considère que
l’on a résolu le problème.
Autrement, deux cas peuvent se présenter :
1 si f (a)f (c) < 0, alors f a une racine réelle dans [a, c] (au moins une, en
tous cas, un nombre impair de racines),
2 autrement, f (a)f (c) > 0, donc f (a)f (b)f (a)f (c) < 0, ce qui donne
f (b)f (c) < 0 et f a une racine réelle dans [c, b].
On itère alors le processus avec l’intervalle qui contient au moins une
racine.

A. Laghrib | c b n a 53 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie
La méthode de dichotomie s’écrit de la manière suivante :
On pose :

a0 + b0
a0 = a, b0 = b, I0 = [a0 , b0 ], et x0 = .
2
Pour n ≥ 1, on construit le sous-intervalle In = [an , bn ] à partir de
l’intervalle In−1 = [an−1 , bn−1 ] de la façon suivante :

A. Laghrib | c b n a 54 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie
an−1 +bn−1
a) soit xn−1 = 2
b) si f (xn−1 ) = 0 alors x⋆ = xn−1 et la méthode termine.
c) si f (xn−1 ) ̸= 0, alors :
si f (an−1 ).f (xn−1 ) < 0, on pose :

an = an−1 , bn = xn−1 ;

si f (xn−1 ).f (bn−1 ) < 0, on pose :

an = xn−1 ; bn = bn−1 ;

d) on définit In = [an , bn ] ; on augmente n de 1 et on recommence du

point a).

A. Laghrib | c b n a 55 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie
Exemple :
Résoudre l’équation x3 + x − 1 = 0 par l’algorithme de dichotomie sur
l’intervalle [0, 2].

A. Laghrib | c b n a 56 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie
Il est clair qu’à chaque itération la longueur ln de l’intervalle de localisation
de la racine x∗ est divisée par 2. On sait de plus que |xn − x∗ | ≤ ln , d’où le
résultat de convergence de la suite (xn ) vers x∗ si on montre que ln tend
vers 0.

A. Laghrib | c b n a 57 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie

Proposition
La suite de segments In = ([an , bn ])n≥0 est telle que :

b−a
ln = |bn − an | = , n ≥ 1.
2n

Cette proposition est utile sur le plan numérique, en effet elle renseigne sur
le nombre minimal d’itérations nécessaires pour calculer la racine à ϵ près,
ϵ > 0 étant une précision fixée à l’avance par l’utilisateur (test d’arrêt).

A. Laghrib | c b n a 58 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Méthode de la dichotomie
En effet, on peut montrer que ce nombre n doit vérifier :
b − a
n ≥ log2
ϵ
La méthode donne une solution avec la précision
 ϵ avec un nombre
d’itération n = E log2 (b − a) − log2 (ϵ) + 1.

A. Laghrib | c b n a 59 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Exemple
Si [a, b] = [0, 1], pour obtenir une précision |xn − x∗ | ≤ 10−6 , il faut 19
itérations, quelque soit la fonction f .

A. Laghrib | c b n a 60 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Résultat de convergence
Soit [a0 , b0 ], [a1 , b1 ]; . . . [an , bn ] les intervalles générés par la méthode de
dichotomie et soit :
an + bn
xn =
2
alors on a :
b−a
|xn − x∗ | ≤ n+1
2
∗
où x est la racine de f . De plus :

lim xn = lim an = lim bn = x∗ .

n→+∞ n→+∞ n→+∞

A. Laghrib | c b n a 61 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Algorithme

A. Laghrib | c b n a 62 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Test d’arrêt
On peut utiliser trois tests d’arrêts pour les méthodes itératives, à savoir :

|xn+1 − xn | < ϵ,
|xn+1 − xn |
< ϵ, xn ̸= 0, ou
|xn |
|f (xn )| < ϵ.

Meilleur choix
Lequel il faut choisir ?

A. Laghrib | c b n a 63 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Test d’arrêt
Pour |xn+1 − xn | < ϵ, on considère l’exemple de la serie Harmonique :
n
X 1
xn = .
k=1
k

Pour |f (xn )| < ϵ, on considère l’exemple suivant :

Soit f (x) = (x − 1)10 , x∗ = 1, et xn = 1 + 1/n. Montrer que
|f (xn )| < 10−3 pour n > 1 mais que |x∗ − xn | < 10−3 est vérifiée
lorsque n > 1000.

A. Laghrib | c b n a 64 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Illustration graphique

A. Laghrib | c b n a 65 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Remarques
La méthode de bissection est toujours convergente mais elle est très
lente.
On parle alors de méthode fermée, car on travaille dans un intervalle
fermé.
Elle n’a pas d’ordre de convergence.
La méthode ne garentie pas la réduction de l’erreur absolue. On n’a
pas :
|xn+1 − x∗ | ≤ Cn |xn − x∗ | avec : Cn < 1.
C’est une méthode qui peut être utilisée seulement pour s’approcher
de la racine.

A. Laghrib | c b n a 66 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Remarques
Les cas où la méthode de bissection ne marche pas !

A. Laghrib | c b n a 67 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Exercices d’applications
Soit la fonction f (x) = x2 sin(x) − 4, 1.
a) Faire 3 itérations de la méthode de la bissection pour la fonction f à
partir de l’intervalle [a0 , b0 ] = [0, 4].
b) Estimer l’erreur absolue à l’itération n = 20.
c) Déterminer le nombre d’itérations nécessaires pour obtenir une erreur
absolue inférieure ou égale à 10−3 .

A. Laghrib | c b n a 68 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la dichotomie

Résolution numérique de f (x) = 0

Exercices d’application
On considère la fonction h(x) = x3 − x2 − 1.
a) Vérifier que la fonction h possède une et une seule racine r dans
l’intervalle [1, 2].
b) Déterminer le nombre d’itérations de la méthode de bissection qui
seront nécessaires pour obtenir une approximation de r avec une
erreur absolue inférieure ou égale à 10−10 .

A. Laghrib | c b n a 69 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

La méthode de point fixe

Pour résoudre f (x) = 0, on peut se ramener à un problème équivalent de la
forme g(x) = x (par exemple en posant g(x) = f (x) + x). Mais il y a
beaucoup de choix possibles pour définir g !
La résolution de g(x) = x s’appelle recherche des points fixes de g.

L’intérêt
L’intérêt de cet algorithme réside dans sa généralité et dans la relative
facilité avec laquelle on peut en faire l’analyse de convergence.

A. Laghrib | c b n a 70 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Définition (Point fixe)

Un point fixe d’une fonction f est une valeur de x qui reste invariante pour
cette fonction :
f (x) = x

A. Laghrib | c b n a 71 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Le choix de la fonction g
Par exemple pour calculer la racine carrée d’un nombre réel a > 0, on
résout x2 = a . Il existe alors différentes manières de se ramener à un
problème de point fixe :
1 x = xa , et g1 (x) = xa ,
a a a
2 2x = x + x soit x = 2x − x et g2 (x) = 2x − x
x a x a
3 x= 2 + 2x et g3 (x) = 2 + 2x

A. Laghrib | c b n a 72 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Itération de point fixe

Les méthodes dites de point fixe, consistent à construire la suite
x0 , x1 , ..., xn , ... de la façon suivante :
(
x0 donné
(1)
xn+1 = g(xn ), n > 0

Si la suite (xn ) converge, la continuité de g implique qu’elle converge vers

un point fixe x∗ de g. En effet

x∗ = lim xn+1 = g( lim xn ) = g(x∗ ).

n→∞ n→∞

A. Laghrib | c b n a 73 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Remarque
l’algorithme des points fixes, selon le choix de la fonction itérative g(x),
converge vers l’une ou l’autre des racines et peut même diverger
complètement dans certains cas. Il faut donc une analyse plus fine afin de
déterminer dans quelles conditions la méthode des points fixes est
convergente.
Des conditions sur g ?

A. Laghrib | c b n a 74 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Résultat de convergence 1
Définition
Soit I un intervalle de R, g est une contraction sur I, si ∃K ∈ [0, 1[ tel que :

|g(x) − g(y)| ≤ K|x − y|, ∀x, y ∈ I.

Proposition
Soit I un intervalle de R, g est une fonction de classe C 1 sur I, si

|g ′ (x)| ≤ K < 1 ∀x ∈ I.

alors :
|g(x) − g(y)| ≤ K|x − y|, ∀x, y ∈ I.

A. Laghrib | c b n a 75 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Résultat de convergence 1
Théorème
Soit I un intervalle fermé de R et g : I ⊂ R une fonction donnée. Si g
satisfait les deux propriétés suivantes :
g(I) ⊂ I (∀x ∈ I on a g(x) ∈ I) ;
g est une contraction sur I.
Alors g admet un et un seul point fixe x∗ sur I. De plus, pour tout x0 ∈ I, la
suite récurrente xn+1 = g(xn ) converge vers un unique x∗ . La convergence
est linéaire.

A. Laghrib | c b n a 76 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Résultat de convergence 1
Exemple
On applique le théorème précédent pour résoudre l’équation suivante sur
[0, 1] :
cos x − x = 0.

A. Laghrib | c b n a 77 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Résultat de convergence 2
Théorème
Soit une fonction g : R −→ R continûment dérivable et soit x∗ un point
fixe de g, si
|g ′ (x∗ )| ≤ k < 1
Alors ∃ϵ > 0 tel que si x0 satisfait |x∗ − x0 | < ϵ. De plus, la suite
récurrente xn+1 = g(xn ) converge vers un unique x∗ .

A. Laghrib | c b n a 78 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Résultat de convergence 3
Proposition
Soit une fonction g : [a, b] −→ [a, b] continûment dérivable sur [a, b] et
supposons que :
|g ′ (x)| ≤ k < 1, ∀x ∈ [a, b].
Alors g possède un point fixe unique x∗ ∈ [a, b] et la suite :
(
x0 donné
(2)
xn+1 = g(xn ), n > 0

converge vers x∗ .

A. Laghrib | c b n a 79 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

La méthode de point fixe

Dans la proposition précédente, on a supposé que la valeur absolue de la
dérivée était majorée par 1 sur l’intervalle [a, b] tout entier. Si l’on considère
l’exemple de la racine carrée d’un nombre réel traité dans le paragraphe
précédent, on a décrit trois fonctions g pour lesquelles le point fixe x∗
correspond à cette racine carrée.
Calculons les dérivées correspondantes aux points fixes x∗ ( dans notre cas :
2
x∗ = a) :
−a
1 g1 (x) = xa , g1′ (x) = x2
et g1′ (x∗ ) = −1
2 g2 (x) = 2x − xa , g2′ (x) = 2 + a
x2
et g2′ (x∗ ) = 3
g3 (x) = x a ′ 1
− a
et g3′ (x∗ ) = 0
3 2 + 2x , g3 (x) = 2 2x2

A. Laghrib | c b n a 80 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

La méthode de point fixe

Définition
Le taux de convergence d’une méthode des points fixes est donné par
|g ′ (x∗ )|.

Plus le taux de convergence est petit, plus la convergence est rapide. Le cas
limite est celui où g ′ (x∗ ) = 0.

A. Laghrib | c b n a 81 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Ordre de convergence
Définition
On dit qu’une méthode des points fixes converge à l’ordre p si :

|en+1 | = C|en |p

où C est une constante. La convergence d’ordre 1 est également dite

linéaire, tandis que celle d’ordre 2 est dite quadratique.

A. Laghrib | c b n a 82 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

La méthode de point fixe

Remarques
Si |g ′ (x∗ )| < 1 et |g ′ (x∗ )| =
̸ 0, la méthode des points fixes converge à
l’ordre 1.
Si |g ′ (x∗ )| = 0 et |g ′′ (x∗ )| =
̸ 0, on a une convergence quadratique.
Si |g ′ (x∗ )| = g ′′ (x∗ )| = 0 et g ′′′ (x∗ ) ̸= 0, la convergence est d’ordre 3
et ainsi de suite.

A. Laghrib | c b n a 83 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Algorithme

A. Laghrib | c b n a 84 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Graphiquement

A. Laghrib | c b n a 85 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

Graphiquement

A. Laghrib | c b n a 86 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

La méthode de point fixe

La condition de convergence

A. Laghrib | c b n a 87 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

Résolution numérique de f (x) = 0

La méthode de point fixe

Remarque
La convergence d’une méthode des points fixes est également reliée au
choix de la valeur initiale x0 . En effet, un mauvais choix de x0 peut résulter
en un algorithme divergent même si la condition de convergence est
vérifiée.

A. Laghrib | c b n a 88 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de point fixe

Résolution numérique de f (x) = 0

Exercices d’applications
x∗ de l’équation x3 + 4x2 − 10 = 0 sur l’intervalle
Pour calculer la racineq
10
[1, 2], on pose g(x) = 4+x afin d’appliquer la méthode du point fixe
g(x) = x.
a) Montrer que la suite xn+1 = g(xn ) avec x0 ∈ [1, 2] converge vers un
unique point fixe x∗ ∈ [1, 2].
1
b) Montrer que |xn+1 − xn | ≤ K n |x1 − x0 | avec K = √
5 2
.
c) En déduire que, pour p > n, |xp − xn | ≤ (K p−1 + · · · + K n )|x1 − x0 |.
Kn
d) Montrer alors que |xn − x∗ | ≤ 1−K |x1 − x0 |.
e) Pour x0 = 23 , calculer le nombre d’itérations de la méthode du point
fixe nécessaire pour obtenir une erreur absolue inférieure ou égale à
ϵ = 10−3 .

A. Laghrib | c b n a 89 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

Résolution numérique de f (x) = 0

La méthode de Newton
La méthode de Newton s’utilise pour calculer une racine de f (x) = 0, où f
est une fonction deux fois continûment dérivable de [a, b] dans R.

A. Laghrib | c b n a 90 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

Le principe
Soit f : R → R une fonction de classe C 1 et soit x∗ une racine simple de f
(f (x∗ ) = 0 et f ′ (x∗ ) ̸= 0). A partir d’une valeur initial x0 de la solution, on
cherche une correction ∆x tel que :

f (x0 + ∆x) = 0

A. Laghrib | c b n a 91 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

Le principe
En faisant un développement de Taylor autour de x = 0, on trouve :

f ′′ (x0 )
0 = f (x0 + ∆x) = f (x0 ) + f ′ (x0 )∆x + ∆x2 + o(∆x)2 .
2
On néglige alors les termes d’ordre supérieur ou égal à 2 en ∆x, on trouve
alors :
f (x0 )
∆x = − ′ .
f (x0 )

A. Laghrib | c b n a 92 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

Le principe
Donc le point corrigé noté x1 est donné par :

f (x0 )
x1 = x0 + ∆x = x0 − .
f ′ (x0 )

On recommence le processus en cherchant à corriger x1 d’une nouvelle

quantité ∆x. On obtient alors à l’itération n la suite de Newton :

f (xn )
xn+1 = xn − f ′ (xn ) ̸= 0, ∀n ∈ N.
f ′ (xn )

A. Laghrib | c b n a 93 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

L’idée de l’algorithme
Soit f : R → R une fonction de classe C 1 et soit x∗ une racine simple de f
(f (x∗ ) = 0 et f ′ (x∗ ) ̸= 0). Si on suppose que l’on connait une valeur plus
proche de x∗ , notée par xn . Pour calculer xn+1 nous prenons l’intersection
de la droite (Ox) avec la droite tangente à f passant par le point
(xn , f (xn )).

A. Laghrib | c b n a 94 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

L’idée de l’algorithme

A. Laghrib | c b n a 95 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

L’algorithme
L’algorithme de Newton pour résoudre une équation f (x) = 0 est le
suivant : 
 x0 donné
f (xn ) (3)
 xn+1 = xn − f ′ (xn ) , n ≥0

Il s’agit donc d’une méthode de point fixe xn+1 = g(xn ) pour laquelle la
fonction g : g(x) = x − ff′(x)
(x) .

A. Laghrib | c b n a 96 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

Remarque
La méthode de Newton est une méthode de point fixe telle que g ′ (x∗ ) = 0
c’est-à-dire que la dérivée s’annule au point fixe de la fonction g.

A. Laghrib | c b n a 97 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

Convergence 1
Soit f une fonction deux fois continûment dérivable sur [a, b] et x∗ ∈ [a, b]
tel que f (x∗ ) = 0 et f ′ (x∗ ) ̸= 0. Alors il existe α > 0 tel que la suite
générée par la méthode de Newton :

f (xn )
xn+1 = xn −
f ′ (xn )

converge vers x∗ pour tout x0 ∈ [x∗ − α, x∗ + α].

A. Laghrib | c b n a 98 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

Convergence 1
Comme il s’agit d’une méthode de point fixe de la fonction
g(x) = x − ff′(x)
(x) , on calcule la dérivée de cette fonction au point fixe :

f ′ (x)2 − f ” (x) ∗ f (x) f ” (x) ∗ f (x)

g ′ (x) = 1 − =
f ′ (x)2 f ′ (x)2

et puisque f (x⋆ ) = 0., on a g ′ (x⋆ ) = 0. On peut donc appliquer la

proposition qui montre l’existence de α tel que la suite xn+1 = g(xn )
converge vers le point fixe x0 ∈ [x⋆ − α, x⋆ + α].

A. Laghrib | c b n a 99 / 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

Convergence 2
Soit f une fonction deux fois continûment dérivable et supposons que x∗
est tel que f (x∗ ) = 0 et f ′ (x∗ ) ̸= 0. Alors il existe ϵ > 0 tel que si
x0 ∈ [x∗ − α, x∗ + α] la suite générée par la méthode de Newton :

f (xn )
xn+1 = xn −
f ′ (xn )

converge vers x∗ . De plus la convergence est quadratique.

100 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | La méthode de Newton

La méthode de Newton

Remarque
Cette proposition donne une condition suffisante de convergence
mais heureusement la méthode de Newton converge souvent même
si l’on part loin de la solution.

101 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Vitesse de convergence de la méthode de point fixe et de Newton

La méthode de Newton

Proposition
Soit g une fonction deux fois continûment dérivable de [a, b] dans [a, b], soit
x∗ ∈ [a, b] tel que g(x∗ ) = x∗ et g ′ (x∗ ) = 0, soit x0 ∈ [a, b], on définit
xn+1 = g(xn ), alors :

M
|xn+1 − x∗ | ≤ |xn − x∗ |2
2
′′
où M = maxx∈[a,b] |g (x)|.

102 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Vitesse de convergence de la méthode de point fixe et de Newton

La méthode de Newton

Proposition
Démonstration : D.T au point x⋆ donne :

(xn − x⋆ )2
g(xn ) = g(x⋆ ) + (xn − x⋆ )g ′ (x⋆ ) + g”(ϵ)
2
avec ϵ est strictement compris entre xn et x⋆ , d’où le résultat.

103 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la corde (Newton-Corde)

La méthode de la corde

Intérêt
Cette méthode permet d’éviter le calcul de la dérivée à chaque itération. En
effet, on va se contenté du calcul de la quantité f ′ (x0 ) seulement. Cette
méthode consiste à remplacer f ′ (xn ) par f ′ (x0 ) dans l’itération de Newton.
Ce qui conduit à l’itération de la corde suivante :

f (xn )
xn+1 = xn − , n ∈ N.
f ′ (x0 )

104 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la corde (Newton-Corde)

La méthode de la corde
Interprétation géométrique

105 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de la corde (Newton-Corde)

La méthode de la corde

Convergence
Soit f une fonction deux fois continûment dérivable et supposons que x∗
est tel que f (x∗ ) = 0 et f ′ (x∗ ) ̸= 0. Alors il existe ϵ > 0 tel que si
x0 ∈ [x∗ − ϵ, x∗ + ϵ] la suite générée par la méthode de la Corde :

f (xn )
xn+1 = xn −
f ′ (x0 )

converge vers x∗ . De plus la convergence est quadratique.

106 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de sécante

La méthode de sécante

Le principe
Éviter le calcul de la dérivée à chaque itération.

Pour cela on contourne cette difficulté en remplaçant le calcul de la pente

f ′ (xn ) de la droite tangente à la courbe par l’expression suivante :

f (xn ) − f (xn−1 )
f ′ (xn ) =
xn − xn−1

Cela revient à utiliser la droite sécante passant par les points (xn , f (xn )) et
(xn−1 , f (xn−1 )).

107 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de sécante

La méthode de sécante

Remarques
La dérivée de f n’apparaît plus dans l’algorithme.
Il faut fournir au départ 2 valeurs initiales. C’est ce qu’on appelle un
algorithme à deux pas.
On choisit les valeurs initiales le plus près possible de la racine
recherchée.

108 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de sécante

La méthode de sécante
Interprétation géométrique

109 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de sécante

La méthode de sécante

Convergence
Soit f une fonction deux fois continûment dérivable et supposons que x∗
est tel que f (x∗ ) = 0 et f ′ (x∗ ) ̸= 0. Alors il existe ϵ > 0 tel que si
x0 ∈ [x∗ − ϵ, x∗ + ϵ] et x1 ∈ [x∗ − ϵ, x∗ + ϵ] la suite (xn ) générée par la
méthode de la sécante :
xn − xn−1
xn+1 = xn − f (xn )
f (xn ) − f (xn−1 )
√
1 + 5
converge vers x∗ . De plus la convergence est d’ordre (le nombre
2
d’or).

110 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution numérique de f (x) = 0 | Méthode de sécante

La méthode de sécante

Exemple
Résoudre l’équation :

exp(−x2 ) − x + 1 = 0.

par la méthode de sécante avec x0 = 0 et x1 = 1.

111 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Contents

1 Introduction

2 Analyse de l’erreur
Erreurs dues à la représentation
Norme IEEE-754
Arithmétique flottante
3 Résolution numérique de f (x) = 0
Méthode de la dichotomie
La méthode de point fixe
La méthode de Newton
Vitesse de convergence de la méthode de point fixe et de Newton
Méthode de la corde (Newton-Corde)
Méthode de sécante
4 Résolution des équations différentielles

112 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Résolution des equations de premier ordre

Le problème consiste à déterminer une fonction y(t) solution de

y ′ (t) = f (t, y(t)) t0 < t ≤ T
y(t ) = y .
0 0

113 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Résolution des equations de premier ordre

Le problème consiste à déterminer une fonction y(t) solution de

y ′ (t) = f (t, y(t)) t0 < t ≤ T
y(t ) = y .
0 0

114 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Exemple :
Soit l’équation différentielle où y(t) solution de

y ′ (t) = ty(t) t0 < t ≤ T
y(1) = 2.

On doit d’abord séparer les variables en écrivant par exemple :

dy dy
= ty(t), ce qui donne : = tdt
dt dy

115 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Exemple :
Les variables étant séparées, on peut maintenant faire l’intégration :
!
(t2 − 1)
y(t) = 2 exp .
2

116 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Approximation de la solution analytique

On note y(tn ) la solution analytique de l’équation différentielle en t = tn .
On note yn la solution approximative en t = tn obtenue à l’aide d’une
méthode numérique.

117 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Méthode d’Euler explicite

La méthode d’Euler explicite est de loin la méthode la plus simple de
résolution numérique d’équations différentielles ordinaires.
On subdivise l’intervalle [t0 , T ] en N sous-intervalles de longueur :

T − t0
h= . (4)
N
Pour tn = t0 + nh, on cherche yn la valeur approchée de y(tn ) tel que :

y(tn ) ≈ yn .

118 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Méthode d’Euler explicite

Pour calculer yn on utilise l’approximation de la dérivée

y(tn+1 ) − y(tn ) yn+1 − yn

y ′ (tn ) ≃ ≃
tn+1 − tn h

On déduit alors la relation suivante :

yn+1 − yn
= f (tn , yn ). (5)
h

119 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Méthode d’Euler explicite

Les solution yn pour n = 0, . . . , N sont donc exprimés par :

y0 = y(t0 ),
y
n+1 = yn + hf (tn , yn ), pour n = 0 . . . N − 1.

120 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Méthode d’Euler explicite

121 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Méthode d’Euler explicite

122 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Ordre de convergence
Une méthode de résolution d’équations différentielles est dite à un pas si
elle est de la forme :

yn+1 = yn + hϕ(tn , yn , h).

où ϕ est une fonction quelconque. Une telle relation est appelée équation
aux différences.

123 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Méthode d’Euler explicite

On dira qu’un schéma à un pas converge à l’ordre p si :

max |y(tn ) − yn | = o(hp ).

1≤n≤N

où N est le nombre total de pas de temps.

124 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

l’erreur de troncature locale

L’erreur de troncature locale au point t = tn est définie par :

y(tn+1 ) − y(tn )
τn+1 = − ϕ(tn , y(tn ), h).
h
L’erreur de troncature locale mesure la précision avec laquelle la solution
analytique vérifie l’équation de dépard.

125 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Méthodes de Runge-Kutta
Il serait avantageux de disposer de méthodes d’ordre de plus en plus élevé.
On propose la forme :

y(tn+1 ) = y(tn ) + a1 hf (tn , y(tn )) + a2 hf (tn + a3 h, y(tn ) + a4 h)

126 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Méthodes de Runge-Kutta
En faisant la correspondance avec la formule de Taylor on trouve



 a1 + a2 = 1,

1
a2 a3 = 2 ,


a a = f (tn ,y(tn )

2 4 2

127 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Théorème d’équivalence de Lax-Richtmyer

Soit l’équation différentielle :

y ′ = f (x, y)

avec f continue de [x0 , x0 + a] × Rn dans Rn , Lipschitzienne par rapport à

y, et le schéma à un pas

yk+1 = yk + hΦ (xk , yk , h)

avec Φ continue de [x0 , x0 + a] × Rn × [0, h0 ] dans Rn . Si le schéma est

stable et consistant il est convergent.

128 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Theorème de consistance
Soit l’équation différentielle y ′ = f (x, y) avec f continue de
[x0 , x0 + a] × Rn dans Rn , Lipschitzienne par rapport à y, et le schéma à
un pas yk+1 = yk + hΦ (xk , yk , h) avec Φ continue de
[x0 , x0 + a] × Rn × [0, h0 ] dans Rn . Le schéma est consistant si et
seulement si :

Φ(x, y, 0) = f (x, y), ∀x ∈ [x0 , x0 + a] , ∀y ∈ Rn

129 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Theorème de stabilité
Soit le schéma à un pas yk+1 = yk + hΦ (xk , yk , h), une condition
suffisante de stabilité est donnée par : Il existe une constante Λ,
indépendante de h, telle que

∥Φ(x, y, h) − Φ(x, z, h)∥ ≤ Λ∥y − z∥

∀x ∈ [x0 , x0 + a] , ∀y, z ∈ Rn , ∀h ∈ [0, h0 ]

130 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Ordre de convergence
La méthode à un pas

yk+1 = yk + hΦ (xk , yk , h)

de discrétisation de l’équation y ′ = f (x, y) est d’ordre p si :

y (xk+1 ) − y (xk )
max − Φ (xk , y (xk ) , h) ≤ Khp
0≤k≤N h

pour toute solution y(x) de l’EDO assez continument différentiable. La

constante K ne dépendant que de y et de Φ.

131 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Theorème de l’ordre de convergence

p
Si f ∈ C p ([x0 , x0 + a] × Rn , Rn ) et Φ, ∂Φ ∂ Φ
∂h , · · · , ∂hp sont continues sur
[x0 , x0 + a] × Rn × [0, h0 ], alors la méthode à un pas

yk+1 = yk + hΦ (xk , yk , h)

est d’ordre p si et seulement si, ∀x, y ∈ [x0 , x0 + a] × Rn :



 Φ(x, y, 0) = f (x, y)

 ∂Φ (x, y, 0) = 1 f (1) (x, y)


∂h 2



···
 ∂ p−1 Φ

(x, y, 0) = p1 f (p−1) (x, y)

∂hp−1

132 /
A. Laghrib | c b n a 133
Analyse Numérique | Résolution des équations différentielles

Résolution des équations différentielles

Ordre de convergence
On a alors dans la définition de l’ordre :
1 1 ∂pΦ
K= max f (p) (x, y(x)) + max (x, y(x), h)
(p + 1)! x∈[x0 ,x0 +a] p! x∈[x0 ,x0 +a] ∂hp
h∈[0,h00 ]

133 /
A. Laghrib | c b n a 133