Chapitre 2

Équations non linéaires

2.1 Introduction
Le numéricien est souvent confronté à la résolution d’équations algébriques
de la forme :
f (x) = 0 (2.1)
et ce, dans toutes sortes de contextes. Introduisons dès maintenant la termi-
nologie qui nous sera utile pour traiter ce problème.

Définition 2.1
Une valeur de x solution de f (x) = 0 est appelée une racine ou un zéro de
la fonction f (x) et est notée r.

Nous avons tous appris au secondaire comment résoudre l’équation du second

degré :
ax2 + bx + c = 0
dont les deux racines sont :
√
−b ± b2 − 4ac
2a
Certains ont également vu comment calculer les racines d’une équation du
troisième ordre et se souviennent que la formule est beaucoup plus complexe.
On peut aussi obtenir une formule générale pour le quatrième degré. Par contre,
on ignore souvent qu’il n’existe pas de formule permettant de trouver les racines
des polynômes de degré plus grand ou égal à 5. Non pas que les mathématiciens
ne l’aient pas encore trouvée, mais Abel 1 et par la suite Galois 2 ont démontré
que cette formule n’existe pas.
Puisqu’il n’existe pas de formule générale pour des fonctions aussi simples
que des polynômes, il est peu probable que l’on puisse résoudre analytiquement
l’équation 2.1 dans tous les cas qui nous intéressent. Il faudra donc recourir aux
1. Le mathématicien norvégien Niels Henrik Abel (1802-1829) fut à l’origine de la pre-
mière démonstration de cet important résultat.
2. Le mathématicien Évariste Galois (1811-1832) fut tué dans un duel à l’âge de 21 ans,
non sans avoir eu le temps d’apporter une contribution considérable à la théorie des groupes.
50 Chapitre 2

méthodes numériques. Dans ce qui suit, nous présentons plusieurs techniques de

résolution, chacune ayant ses avantages et ses inconvénients. Nous tâcherons
de les mettre en évidence de façon à tirer le meilleur parti de chacune des
méthodes proposées.
Il faudra également se souvenir des enseignements du chapitre précédent
pour éviter de développer des algorithmes numériquement instables.

2.2 Méthode de la bissection

La méthode de la bissection repose sur une idée toute simple : en général,
de part et d’autre d’une solution de l’équation 2.1, une fonction continue f (x)
change de signe et passe du positif au négatif ou vice versa (fig. 2.1). De toute
évidence, ce n’est pas toujours le cas puisque la fonction f (x) peut aussi être
tangente à l’axe des x Nous reviendrons plus loin sur ces situations particulières
(fig. 2.2).
Supposons pour l’instant qu’il y ait effectivement un changement de signe
autour d’une racine r de f (x). Nous nous occuperons des cas pathologiques
un peu plus tard. Soit [x1 , x2 ], un intervalle ayant un changement de signe,
c’est-à-dire :
f (x1 ) × f (x2 ) < 0 (2.2)
On pose alors :
x1 + x2
xm =
2
qui est bien sûr le point milieu de l’intervalle. Il suffit alors de déterminer, entre
les intervalles [x1 , xm ] et [xm , x2 ], celui qui possède encore un changement
de signe. La racine se trouvera forcément dans cet intervalle. À la première
itération de la figure 2.1, ce serait l’intervalle [xm , x2 ], tandis qu’à la deuxième
itération ce serait [x1 , xm ]. Cela nous amène à l’algorithme suivant.

Algorithme 2.2 : Algorithme de la bissection

1. Étant donné un intervalle [x1 , x2 ] pour lequel f (x) possède un change-
ment de signe
2. Étant donné ϵa , le critère d’arrêt, et N , le nombre maximal d’itérations
3. Poser :
x1 + x2
xm =
2
|x2 − x1 |
4. Si < ϵa :
2|xm |
– convergence atteinte
– écrire la racine xm
– écrire f (xm )
– arrêt
5. Écrire x1 , x2 , xm , f (x1 ), f (x2 ), f (xm )
6. Si f (x1 ) × f (xm ) < 0, alors x2 = xm
7. Si f (xm ) × f (x2 ) < 0, alors x1 = xm
 Équations non linéaires 51

10

-2
-2 -1,5 -1 -0,5 0 0,5 1 1,5 2
x1 xm x2

0,5

-0,5

-1

-1,5

-2
0 0,2 0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 2
x1 xm x2
1
0,8
0,6
0,4
0,2
0
-0,2
-0,4
-0,6
-0,8
0 0,2 0,4 0,6 0,8 1
x1 xm x2
0,2
0,1
0
-0,1
-0,2
-0,3
-0,4
-0,5
-0,6
-0,7
0,5 0,6 0,7 0,8 0,9 1
x1 xm x2

Figure 2.1 – Méthode de la bissection : f (x) = e−x − x

52 Chapitre 2

8. Si le nombre maximal d’itérations N est atteint :

– convergence non atteinte en N itérations
– arrêt
9. Retour à l’étape 3
!

L’expression :
|x2 − x1 |
2|xm |
est une approximation de l’erreur relative. En effet, à l’étape 3 de l’algorithme
de la bissection, la racine recherchée est soit dans l’intervalle [x1 , xm ] ou dans
l’intervalle [xm , x2 ], qui sont tous deux de longueur (x2 −x1 )/2, ce qui constitue
une borne supérieure de l’erreur absolue. En divisant par xm , on obtient une
approximation assez fiable de l’erreur relative.
Remarque 2.3
Dans l’algorithme précédent, il faut prendre garde au cas où la racine recherchée
est 0. Il y a alors risque de division par 0 au cours de l’évaluation de l’erreur
relative. Ce cas est toutefois rare en pratique. "

Remarque 2.4
Il est parfois utile d’introduire un critère d’arrêt sur la valeur de f (x), qui doit
tendre également vers 0. "

Exemple 2.5
La fonction f (x) = x3 + x2 − 3x − 3 possède un zéro dans l’intervalle [1 , 2].
En effet :
f (1) × f (2) = −4,0 × 3,0 = −12,0 < 0
On a alors xm = 1,5 et f (1,5) = −1,875. L’intervalle [1,5 , 2] possède encore
un changement de signe, ce qui n’est pas le cas pour l’intervalle [1 , 1,5]. Le
nouvel intervalle de travail est donc [1,5 , 2], dont le point milieu est xm = 1,75.
Puisque f (1,75) = 0,171 87, on prendra l’intervalle [1,5 , 1,75] et ainsi de suite.
Le tableau suivant résume les résultats.

Méthode de la bissection : f (x) = x3 + x2 − 3x − 3

x1 x2 xm f (x1 ) f (x2 ) f (xm ) Erreur absolue
liée à xm
1,0 2,0 1,5 −4,0 3,0 −1,875 0,5
1,5 2,0 1,75 −1,875 3,0 +0,171 87 0,25
1,5 1,75 1,625 −1,875 0,171 87 −0,943 35 0,125
1,625 1,75 1,6875 −0,943 35 0,171 87 −0,409 42 0,0625
1,6875 1,75 1,718 75 −0,409 42 0,171 87 −0,124 78 0,031 25

#
 Équations non linéaires 53

On remarque aisément que la longueur de l’intervalle entourant la racine est

divisée par deux à chaque itération. Cette constatation permet de déterminer
à l’avance le nombre d’itérations nécessaire pour obtenir une certaine erreur
absolue ∆r sur la racine r. Soit L = x2 − x1 , la longueur de l’intervalle de
départ. Après une itération, le nouvel intervalle est de longueur L2 et après n
itérations la longueur de l’intervalle est L/2n . Si l’on veut connaître la valeur
de n nécessaire pour avoir :
L
< ∆r
2n
il suffit de résoudre cette équation en fonction de n et l’on trouve la condition :
!L"
ln ∆r
n> (2.3)
ln 2
Il est clair que, sur le plan pratique, on doit prendre pour valeur de n le plus
petit entier vérifiant cette condition. On a aussi tout intérêt à bien cerner la
racine recherchée et à prendre, dès le départ, un intervalle de longueur aussi
petite que possible.

Exemple 2.6
Dans l’exemple précédent, L = 2,0 − 1,0. Si l’on veut une erreur absolue plus
petite que 0,5 × 10−2 , ce qui revient à s’assurer que le chiffre des centièmes est
significatif, il faut effectuer au moins :
# $
1 ,0
ln 0,5×10−2
= 7,64 itérations
ln 2
On fera donc 8 itérations pour s’assurer de cette précision. On peut aisément
vérifier qu’après 8 itérations l’erreur maximale liée à xm est de 0,003 906 25 et
que la véritable erreur est 0,001 582. #

Exemple 2.7 √
On souhaite calculer 2 avec une calculatrice dotée seulement des 4 opérations
élémentaires. Cela revient à résoudre :
x2 − 2 = 0
Cette fonction présente un changement de signe dans l’intervalle [1 , 2]. L’al-
gorithme de la bissection donne les résultats suivants.

Méthode de la bissection : f (x) = x2 − 2

x1 x2 xm f (x1 ) f (x2 ) f (xm ) (xm )2
1,0 2,0 1,5 −1,0 2,0 +0,25 1,1
1,0 1,5 1,25 −1,0 0,25 −0,4375 1,01
1,25 1,5 1,375 −0,4375 0,25 −0,1094 1,011
1,375 1,5 1,4375 −0,1094 0,25 +0,066 41 1,0111
1,375 1,4375 1,4062 −0,1094 0,066 41 −0,022 46 1,011 01
1,4062 1,4375 1,4219 −0,022 46 0,066 41 +0,021 73 1,011 011
1,4062 1,4219 1,4141 −0,022 46 0,021 73 −0,000 43 1,011 010 1
54 Chapitre 2

On a arrondi à 5 chiffres les résultats de ce tableau. En√ poursuivant plus

avant les itérations, on se rapprocherait de plus en plus de 2. On peut égale-
ment ajouter une remarque intéressante du point de vue de la représentation
binaire. En effet, l’intervalle de départ étant [1 , 2], chaque itération de la
méthode de la bissection permet de fixer 1 bit de la représentation binaire de
la racine. À la (n + 1)e itération, on est assuré que les n premiers bits de la
mantisse de xm sont exacts. On peut constater ce phénomène à la dernière
colonne du tableau, qui contient la représentation binaire de xm . #
Remarque 2.8
La convergence de la méthode de la bissection n’est pas très rapide, mais elle
est sûre à partir du moment où on a un intervalle avec changement de signe.
On parle alors de méthode fermée, car on travaille dans un intervalle fermé.
C’est également le cas de la méthode de la fausse position (voir les exercices de
fin de chapitre). Les méthodes des sections qui suivent sont dites ouvertes en
ce sens qu’il n’y a pas d’intervalle à déterminer ayant un changement de signe.
Au contraire des méthodes fermées, les méthodes ouvertes ne garantissent nul-
lement la convergence, mais elles présentent d’autres avantages. "
Remarque 2.9
Il existe des cas où la méthode de la bissection ne fonctionne pas. La figure 2.2
illustre certains de ces cas. La première situation critique est celle où la fonction
f (x) est tangente à l’axe des x et ne présente donc pas de changement de signe.
La bissection ne peut alors s’appliquer. Il y a aussi celle où deux racines (ou un
nombre pair de racines) sont présentes dans l’intervalle de départ ; en ce cas,
il n’y a toujours pas de changement de signe. Enfin, si l’intervalle de départ
contient un nombre impair de racines, f (x) change de signe, mais l’algorithme
peut avoir des difficultés à choisir parmi ces racines. On peut assez facilement
éviter ces écueils en illustrant graphiquement la fonction f (x) dans l’intervalle
d’intérêt. "

2.3 Méthodes des points fixes

Avant d’aborder les méthodes des points fixes, il importe de définir ce qu’est
un point fixe d’une fonction.

Définition 2.10
Un point fixe d’une fonction g(x) est une valeur de x qui reste invariante
pour cette fonction, c’est-à-dire toute solution de :

x = g(x) (2.4)

est un point fixe de la fonction g(x).

Il existe un algorithme très simple permettant de déterminer des points

fixes. Il suffit en effet d’effectuer les itérations de la façon suivante :
%
x0 donné
(2.5)
xn+1 = g(xn )
 Équations non linéaires 55

x1 x2

x1 x2

x1 x2

Figure 2.2 – Cas pathologiques pour la méthode de la bissection

56 Chapitre 2

à partir d’une valeur estimée initiale x0 . 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. Il en résulte l’algorithme plus complet suivant.

Algorithme 2.11 : Algorithme des points fixes

1. Étant donné ϵa , un critère d’arrêt
2. Étant donné N , le nombre maximal d’itérations
3. Étant donné x0 , une valeur estimée initiale du point fixe
4. Effectuer xn+1 = g(xn )
|xn+1 − xn |
5. Si < ϵa :
|xn+1 |
– convergence atteinte
– écrire la solution xn+1
– arrêt
6. Si le nombre maximal d’itérations N est atteint :
– convergence non atteinte en N itérations
– arrêt
7. Retour à l’étape 4
!

On peut résoudre des équations non linéaires de la forme f (x) = 0 en

utilisant l’algorithme des points fixes. Il suffit pour ce faire de transformer
l’équation f (x) = 0 en un problème équivalent de la forme x = g(x). L’ennui
est qu’il y a une infinité de façons différentes de le faire. Nous verrons que
certains choix donnent lieu à des algorithmes convergents et d’autres pas.

Exemple 2.12
Commençons par un exemple simple. On cherche à résoudre l’équation du
second degré x2 − 2x − 3 = 0. Il n’est pas nécessaire de recourir aux méthodes
numériques pour résoudre ce problème, dont les deux solutions sont r1 = 3
et r2 = −1. Cet exemple permet cependant de mieux comprendre ce qui se
passe lorsqu’on utilise l’algorithme des points fixes. Puisqu’il y a une infinité
de façons différentes de transformer cette équation sous la forme x = g(x),
nous en choisissons trois au hasard.

√
x = 2x + 3 = g1 (x) (en isolant x2 )

3
x = = g2 (x) (en écrivant x(x − 2) − 3 = 0) (2.6)
x−2

x2 − 3
x = = g3 (x) (en isolant le x de −2x)
2
Si l’on applique l’algorithme des points fixes à chacune des fonctions gi (x) en
partant de x0 = 4, on obtient pour g1 (x) :
 Équations non linéaires 57

√
x1 = g1 (4) = 2×4+3 = 3,316 6248
√
x2 = g1 (3,316 6248) = 2 × 3,316 6248 + 3 = 3,103 7477
√
x3 = g1 (3,103 7477) = 2 × 3,103 7477 + 3 = 3,034 3855
√
x4 = g1 (3,034 3855) = 2 × 3,034 3855 + 3 = 3,011 4402
.. .. .. ..
. . .√ .
x10 = g1 (3,000 0470) = 2 × 3,000 0470 + 3 = 3,000 0157
L’algorithme semble donc converger vers la racine r1 = 3. Reprenons l’exercice
avec g2 (x), toujours en partant de x0 = 4 :

3
x1 = g2 (4) = = 1,5
4−2
3
x2 = g2 (1,5) = = −6,0
1,5 − 2
3
x3 = g2 (−6,0) = = −0,375
−6,0 − 2
3
x4 = g2 (−0,375) = = −1,263 1579
−0,375 − 2
.. .. .. ..
. . . .
3
x10 = g2 (−0,998 9841) = = −1,000 3387
−0,998 9841 − 2
On remarque que, contrairement au cas précédent, les itérations convergent
vers la racine r2 = −1 en ignorant la racine r1 = 3. En dernier lieu, essayons
l’algorithme avec la fonction g3 (x) :
(4)2 − 3
x1 = g3 (4) = = 6,5
2
(6,5)2 − 3
x2 = g3 (6,5) = = 19,625
2
(19,625)2 − 3
x3 = g3 (19,625) = = 191,0703
2
(191,0703)2 − 3
x4 = g3 (191,0703) = = 18 252,43
2
.. .. .. ..
. . . .
Visiblement, les itérations tendent vers l’infini et aucune des deux solutions
possibles ne sera atteinte.
Cet exemple montre clairement que 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. #
58 Chapitre 2

2.3.1 Convergence de la méthode des points fixes

Nous nous intéressons dans cette section au comportement de la méthode
des points fixes pour la résolution de l’équation f (x) = 0. On a d’abord trans-
formé cette équation sous la forme équivalente x = g(x). Soit r, une valeur qui
est à la fois une racine de f (x) et un point fixe de la fonction g(x), c’est-à-dire
qui vérifie f (r) = 0 et :
r = g(r) (2.7)
On définit l’erreur à l’étape n comme étant :
e n = xn − r
On cherche à déterminer sous quelles conditions l’algorithme des points fixes
converge vers la racine r. Ce sera bien sûr le cas si l’erreur en tend vers 0 lorsque
n devient grand. Il est intéressant de suivre le comportement de l’erreur au fil
des itérations. On a en vertu des relations 2.5 et 2.7 :

en+1 = xn+1 − r = g(xn ) − g(r) (2.8)

On constate aisément que :
xn = r + (xn − r) = r + en
et l’on peut alors utiliser un développement de Taylor de la fonction g(x) autour
de la racine r. La relation 2.8 devient alors :
en+1 = g(r + en ) − g(r)
& '
′ g ′′ (r)e2n g ′′′ (r)e3n
= g(r) + g (r)en + + + ··· − g(r)
2! 3!
On en conclut que :
g ′′ (r)e2n g ′′′ (r)e3n
en+1 = g ′ (r)en + + + ··· (2.9)
2 3!
L’étude de la relation 2.9 est fondamentale pour la compréhension de la mé-
thode des points fixes. Au voisinage de la racine r, le premier terme non nul
de l’expression de droite sera déterminant pour la convergence.
Selon l’équation 2.9, si g ′ (r) ̸= 0 et si l’on néglige les termes d’ordre supé-
rieur ou égal à 2 en en , on a :
en+1 ≃ g ′ (r)en (2.10)
On voit que l’erreur à l’étape (n + 1) est directement proportionnelle à l’erreur
à l’étape n. L’erreur ne pourra donc diminuer que si :
|g ′ (r)| < 1 (2.11)
La condition 2.11 est une condition nécessaire de convergence d’une méthode
des points fixes. On remarque également que le signe de g ′ (r) a une influence
sur la convergence. En effet, si :
−1 < g ′ (r) < 0
 Équations non linéaires 59

l’erreur changera de signe à chaque itération en vertu de l’équation 2.10 et les

valeurs de xn oscilleront de part et d’autre de r. La convergence n’en sera pas
moins assurée.
La relation 2.10 donne de plus la vitesse à laquelle l’erreur diminue. En
effet, plus g ′ (r) est petit, plus l’erreur diminue vite et donc plus la convergence
est rapide. Cela nous amène à la définition suivante.

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

Plus le taux de convergence est petit, plus la convergence est rapide. Le

cas limite est celui où g ′ (r) = 0. Dans ce cas, on déduit de l’équation 2.9 que
l’erreur en+1 est proportionnelle à e2n . Cela nous amène à une autre définition.

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

|en+1 | ≃ C |en |p (2.12)

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

tandis que celle d’ordre 2 est dite quadratique.

Remarque 2.15
Si |g ′ (r)| < 1 et |g ′ (r)| = ̸ 0, la méthode des points fixes converge à l’ordre 1.
Si |g (r)| = 0 et |g (r)| ̸= 0, on a une convergence quadratique ; si |g ′ (r)| =
′ ′′

̸ 0, la convergence est d’ordre 3 ; et ainsi de suite. "

|g ′′ (r)| = 0 et |g ′′′ (r)| =

Remarque 2.16
La convergence d’une méthode des points fixes est également assujettie 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 2.11 est respectée. "

Cela nous amène à définir le bassin d’attraction d’une racine r.

Définition 2.17
Le bassin d’attraction de la racine r pour la méthode des points fixes xn+1 =
g(xn ) est l’ensemble des valeurs initiales x0 pour lesquelles xn tend vers r
lorsque n tend vers l’infini.

En d’autres termes, le bassin d’attraction de r comprend tous les points

x0 pour lesquels la méthode des points fixes converge vers r. Pour s’assurer
de la convergence, il faut donc choisir x0 dans le bassin d’attraction de r.
Intuitivement, on choisit x0 aussi près que possible de r en utilisant par exemple
une méthode graphique. Il faut aussi se souvenir que les problèmes rencontrés
proviennent le plus souvent de l’ingénierie et que le numéricien doit utiliser
60 Chapitre 2

ses connaissances pour estimer x0 . Par exemple, si la racine que l’on cherche
correspond à une longueur ou à une concentration, il serait peu raisonnable de
prendre une valeur négative de x0 . Très souvent, le simple bon sens permet de
choisir x0 avec succès.

Définition 2.18
Un point fixe r de la fonction g(x) est dit attractif si :

|g ′ (r)| < 1

et répulsif si :
|g ′ (r)| > 1
Le cas où |g ′ (r)| = 1 est indéterminé.

Exemple 2.19
Considérons la fonction g(x) = x2 qui possède les points fixes x = 0 et x = 1.
Ce dernier est répulsif, car la dérivée de g(x) (2x) vaut 2 en x = 1. Le seul
point fixe intéressant est donc x = 0. La méthode des points fixes engendre, à
partir de la valeur initiale x0 , la suite :
x0 , x20 , x40 , x80 , x16 32
0 , x0 ···
Cette suite convergera vers 0 seulement si x0 ∈ ] − 1 , 1[. Ce dernier intervalle
constitue donc le bassin d’attraction de ce point fixe. Toute valeur de x0 choisie
à l’extérieur de cet intervalle résultera en un algorithme divergent. #

Remarque 2.20
Dans le cas d’un point fixe répulsif, le bassin d’attraction se réduit à peu de
choses, le plus souvent à l’ensemble {r} constitué d’un seul point. "

Le résultat suivant permet dans certains cas de s’assurer de la convergence

(voir Burden et Faires, réf. [5]).

Théorème 2.21
Soit g(x), une fonction continue dans l’intervalle I = [a, b] et telle que g(x) ∈ I
pour tout x dans I. Si de plus g ′ (x) existe et si :
|g ′ (x)| ≤ k < 1
pour tout x dans l’intervalle ouvert (a, b), alors tous les points x0 de l’intervalle
I appartiennent au bassin d’attraction de l’unique point fixe r de I. ⋆

Remarque 2.22
Il est possible que la méthode des points fixes converge dans le cas où :
|g ′ (r)| = 1
 Équations non linéaires 61

Il s’agit d’un cas limite intéressant. Nous verrons plus loin un exemple de cette
situation. La convergence dans ce cas est au mieux extrêmement lente, car le
taux de convergence est près de 1. "

Exemple 2.23
Revenons aux trois fonctions gi (x) de l’exemple précédent. On veut s’assurer
que la condition 2.11 se vérifie à l’une ou l’autre des racines r1 = 3 et r2 = −1.
On doit d’abord calculer les dérivées :
1 −3
g1′ (x) = √ , g2′ (x) = , g3′ (x) = x
2x + 3 (x − 2)2

Les résultats sont compilés dans le tableau suivant.

Taux de convergence
r1 = 3 r2 = −1
′
g1 (r) 0,333 33 1
′
g2 (r) −3 −0,333 33
g3′ (r) 3 −1
Ce tableau aide à comprendre les résultats obtenus précédemment. La
méthode des points fixes appliquée à g1 (x) a convergé vers r1 = 3, puisque
g1′ (3) < 1. De même, avec g2 (x), la méthode des points fixes ne peut converger
vers r1 = 3, car la dérivée de g2 (x) en ce point est plus grande que 1. Les itéra-
tions ignorent r1 et convergent vers r2 , où la valeur de la dérivée est inférieure
à 1.
Enfin, la fonction g3 (x) a également une dérivée plus grande que 1 en
r1 . L’analyse de la convergence autour de r2 = −1 est plus subtile. En effet,
puisque g3′ (x) = x, on constate que la valeur absolue de la dérivée est inférieure
à 1 à droite de r2 et supérieure à 1 à gauche de r2 . De plus, cette dérivée est
négative, ce qui signifie que la méthode des points fixes oscillera de part et
d’autre de la racine. À une itération, la pente g ′ (xn ) sera inférieure à 1 et, à
l’itération suivante, la pente g ′ (xn+1 ) sera supérieure à 1 en valeur absolue.
On en conclut que l’algorithme des points fixes s’approchera légèrement de
r2 à une itération et s’en éloignera à la suivante. En un mot, l’algorithme
piétinera. On peut vérifier ce raisonnement en effectuant les itérations à partir
de x0 = −0,95. On obtient après 10 000 itérations la valeur x10 000 = −0,986 36,
ce qui signifie que la convergence est extrêmement lente. #

Exemple 2.24
Considérons la fonction g(x) = x2 + 14 dont l’unique point fixe est 12 . On a bien
sûr g ′ (x) = 2x, qui vaut précisément 1 en 12 . En partant de x0 = 14 , on obtient
la valeur 0,499 009 5 après 1000 itérations et donc une convergence très lente.
Cela s’explique par le fait que la dérivée de g(x) est légèrement inférieure à 1
pour les valeurs de x inférieures à 12 et que les résultats des itérations restent
toujours inférieurs à 12 . Par contre, en partant de x0 = 0,51, l’algorithme
62 Chapitre 2

diverge violemment après une centaine d’itérations. On constate aisément que

la dérivée de g(x) est supérieure à 1 pour les valeurs de x supérieures à 12 . #

2.3.2 Interprétation géométrique

L’algorithme des points fixes possède une interprétation géométrique très
élégante qui permet d’illustrer la convergence ou la divergence. La figure 2.3
présente les différents cas possibles : 0 < g ′ (r) < 1, −1 < g ′ (r) < 0 et g ′ (r) > 1.
On peut interpréter cette figure de la manière suivante. Les courbes y = x et
y = g(x) sont représentées et les points fixes sont bien entendu à l’intersec-
tion de ces deux courbes. À partir de la valeur initiale x0 , on se rend sur la
courbe y = g(x) au point (x0 , g(x0 )) et, de là, sur la droite y = x au point
(g(x0 ), g(x0 )), qui est en fait (x1 , x1 ). On recommence le même processus à
partir de x1 pour se rendre à (x1 , g(x1 )) et, de là, sur la droite y = x au point
(g(x1 ), g(x1 )) = (x2 , x2 ). On répète ce trajet jusqu’à la convergence (ou la
divergence) de l’algorithme.
On voit immédiatement la différence de comportement entre les cas conver-
gents 0 < g ′ (r) < 1 et −1 < g ′ (r) < 0. Bien que les itérations oscillent de part
et d’autre de la racine lorsque la pente est négative, la convergence n’en est
pas moins assurée. Par contre, lorsque la pente est supérieure à 1, les itérations
s’éloignent de la racine recherchée. On obtiendrait un résultat similaire dans
le cas où g ′ (r) < −1 ; les itérations s’éloigneraient de la racine en oscillant de
part et d’autre de la racine.
Nous terminons cette section par un dernier exemple qui illustre la conver-
gence généralement linéaire des méthodes des points fixes.

Exemple 2.25
On considère la résolution de e−x − x = 0, que l’on transforme en un problème
de points fixes x = e−x . En partant de x0 = 0 et en posant en = xn −r, l’erreur
à l’étape n, on obtient le tableau suivant.

Méthode des points fixes : g(x) = e−x

( (
( en+1 (
n xn |en | ( en (
1 1,000 0000 0,4328 × 10+0 0,4603
2 0,367 8794 0,1992 × 10 +0 0,6276
3 0,692 2006 0,1250 × 10 +0 0,5331
4 0,500 4735 0,6667 × 10−1 0,5864
5 0,606 2435 0,3910 × 10 −1 0,5562
6 0,545 3957 0,2174 × 10 −1 0,5733
7 0,579 6123 0,1246 × 10−1 —
.. .. .. ..
. . . .
14 0,566 9089 0,2344 × 10−3 0,5670
15 0,567 2762 0,1329 × 10−3 0,5672
.. .. .. ..
. . . .
35 0,567 1433 ≃0 0,5671
 Équations non linéaires 63

y = g(x) y=x

x0 x1 x2x3 r

y=x
y = g(x)

x0 x2 x4 r x 5 x3 x1

y = g(x) y=x

r x0x1 x2 x3

Figure 2.3 – Interprétation géométrique de la méthode des points fixes

64 Chapitre 2

Pour remplir ce tableau, on a d’abord calculé la racine r = 0,567 143 29, ce

qui a permis d’évaluer les erreurs par la suite. L’analyse de ce tableau illustre
plusieurs points déjà discutés. En premier lieu, on constate la convergence vers
la racine r = 0,567 143 29 puisque l’erreur en tend vers 0. Fait plus important
encore, la troisième colonne converge vers environ 0,5671. Ce nombre n’est pas
arbitraire. En effet, en vertu de la relation 2.10, ce rapport doit converger vers
|g ′ (r)|, qui vaut dans cet exemple 0,567 14. On constate bien la convergence de
ce rapport vers |g ′ (r)| pour cet exemple. #

Remarque 2.26
Le calcul de la suite en = xn − r permettant d’obtenir la dernière colonne
du tableau précédent requiert bien entendu de connaître la racine r et donc
d’avoir complété les itérations jusqu’à convergence. On peut cependant éviter
cela en procédant comme suit. Puisque :

en+1 ≃ g ′ (r)en

et :
en+2 ≃ g ′ (r)en+1
on a immédiatement en divisant que :
en+2 en+1
≃
en+1 en

c’est-à-dire :
xn+2 − r xn+1 − r
≃
xn+1 − r xn − r
En isolant r, on trouve facilement que :

xn+2 xn − x2n+1
r≃
xn+2 − 2xn+1 + xn

qui est une formule numériquement instable. On lui préférera l’expression équi-
valente :
(xn+1 − xn )2
r ≃ xn − (2.13)
xn+2 − 2xn+1 + xn
Partant de là, on a donc également :
en+1 xn+1 − r xn+1 − xn+2 En+1
= ≃ =
en xn − r xn − xn+1 En

où on a remplacé r à l’aide de l’expression 2.13. On a aussi introduit les écarts

successifs entre deux itérations :

En = xn − xn+1

On peut ainsi calculer(les écarts

( En sans connaître
( ( la valeur de r. On peut donc
( en+1 ( ( En+1 (
remplacer la colonne ( en ( par la colonne ( En (. De même, nous utiliserons
 Équations non linéaires 65
( (
( en+1 (
un peu plus loin des rapports de la forme ( (e n)
k ( que nous pourrons, au besoin,
( (
( En+1 (
remplacer par ( (E n)
k (. Reprenons l’exemple précédent en nous basant cette fois

sur les écarts pour faire l’analyse. On obtient :

Méthode des points fixes : g(x) = e−x

( (
( En+1 (
n xn |En | ( En (
1 1,000 0000 0,6321 × 10 +0 0,5131
2 0,367 8794 0,3243 × 10+0 0,5912
3 0,692 2006 0,1917 × 10 +0 0,5517
4 0,500 4735 0,1058 × 10 +0 0,5753
5 0,606 2435 0,6085 × 10−1 0,5623
6 0,545 3957 0,3422 × 10 −1 0,5698
7 0,579 6123 0,1950 × 10 −1 —
.. .. .. ..
. . . .
14 0,566 9089 0,3673 × 10−3 0,5672
15 0,567 2762 0,2083 × 10−3 0,5671
.. .. .. ..
. . . .
35 0,567 1433 0,2469 × 10−8 0,5671

On constate aisément que les conclusions restent les mêmes. En pratique, on

pourra se servir des en ou des En pour effectuer ce type d’analyse, avec une
légère préférence pour l’utilisation de en lorsque la racine r est connue. "

2.3.3 Extrapolation d’Aitken

À partir d’une méthode des points fixes convergeant à l’ordre 1, on peut
obtenir une méthode convergeant à l’ordre 2. Il suffit de remarquer que si on
pose n = 0 dans la relation 2.13, on trouve :

(x1 − x0 )2
r ≃= x0 − (2.14)
x2 − 2x1 + x0
La relation 2.14 est dite formule d’extrapolation d’Aitken et permet d’obtenir
à partir de x0 , x1 et x2 une meilleure approximation du point fixe r. Cela
peut résulter en un algorithme qui accélère grandement la convergence d’une
méthode des points fixes. C’est l’algorithme de Steffenson.

Algorithme 2.27 : Algorithme de Steffenson

1. Étant donné ϵa , un critère d’arrêt
2. Étant donné N , le nombre maximal d’itérations
3. Étant donné x0 , une valeur estimée initiale du point fixe
4. Effectuer :
– x1 = g(x0 )
66 Chapitre 2

– x2 = g(x1 )
(x1 − x0 )2
– x e = x0 −
x2 − 2x1 + x0
|xe − x0 |
5. Si < ϵa :
|xe |
– convergence atteinte
– écrire la solution xe
– arrêt
6. Si le nombre maximal d’itérations N est atteint :
– convergence non atteinte en N itérations
– arrêt
7. x0 = xe et retour à l’étape 4
!

Exemple 2.28
Reprenons l’exemple précédent de la méthode des points fixes :

xn+1 = g(xn ) = e−xn

en partant de x0 = 0. L’algorithme de Steffenson consiste à faire deux itérations

de points fixes, à extrapoler pour obtenir xe , à faire deux nouvelles itérations
de points fixes à partir de xe , à extrapoler à nouveau et ainsi de suite. On
obtient dans ce cas :
x 1 = e0 = 1,0
x2 = e−1 = 0,367 8794

La valeur extrapolée est alors :

(1 − 0)2
xe = 0 − = 0,612 6998
0,367 8794 − 2(1) + 0

À partir de cette nouvelle valeur, on fait deux itérations de points fixes :

x1 = e−0,612 6998 = 0,541 8859

x2 = e−0,541 8859 = 0,581 6503
La valeur extrapolée est alors :

(0,541 8859 − 0,612 6998)2

xe = 0,612 6998 − = 0,567 3509
0,581 6503 − 2(0,541 8859) + 0,612 6998
En continuant ainsi, on obtient :

Méthode de Steffenson : g(x) = e−x

x0 x1 x2 xe
0,567 3509 0,567 0256 0,567 2101 0,567 1433
0,567 1433 0,567 1433 0,567 1433 0,567 1433
 Équations non linéaires 67

On remarque que la convergence est plus rapide avec l’algorithme de Steffen-

son qu’avec la méthode des points fixes dont elle est issue. Quatre itérations
suffisent pour obtenir la même précision. On peut montrer en fait que la conver-
gence est quadratique. On note toutefois que chaque itération de l’algorithme
de Steffenson demande plus de calculs qu’une méthode des points fixes. Il y a
un prix à payer pour obtenir une convergence quadratique. #

2.4 Méthode de Newton

La méthode de Newton 3 est l’une des méthodes les plus utilisées pour la
résolution des équations non linéaires. Cette méthode possède également une
belle interprétation géométrique. Nous commençons cependant par donner une
première façon d’en obtenir l’algorithme, basée sur l’utilisation du dévelop-
pement de Taylor. Cette approche est également valable pour les systèmes
d’équations non linéaires que nous verrons au chapitre 3.
Soit une équation à résoudre de la forme :

f (x) = 0

À partir d’une valeur initiale x0 de la solution, on cherche une correction δx

telle que :
0 = f (x0 + δx)
En faisant un développement de Taylor autour de x = x0 , on trouve :

′ f ′′ (x0 )(δx)2 f ′′′ (x0 )(δx)3

0 = f (x0 ) + f (x0 )δx + + + ···
2! 3!
Il suffit maintenant de négliger les termes d’ordre supérieur ou égal à 2 en δx
pour obtenir :
0 ≃ f (x0 ) + f ′ (x0 )δx
On peut alors isoler la correction recherchée :

f (x0 )
δx = −
f ′ (x0 )

La correction δx est en principe la quantité que l’on doit ajouter à x0 pour

annuler la fonction f (x). Puisque nous avons négligé les termes d’ordre supé-
rieur ou égal à 2 dans le développement de Taylor, cette correction n’est pas
parfaite et l’on pose :
x1 = x0 + δx
On recommence le processus en cherchant à corriger x1 d’une nouvelle quantité
δx. On obtient alors l’algorithme suivant.

3. Sir Isaac Newton (1642-1727) fut l’un des plus brillants esprits de son époque. Ses
contributions en mathématiques, en optique et en mécanique céleste en ont fait l’un des plus
célèbres mathématiciens de tous les temps.
68 Chapitre 2

Algorithme 2.29 : Algorithme de la méthode de Newton

1. Étant donné ϵa , un critère d’arrêt
2. Étant donné N , le nombre maximal d’itérations
3. Étant donné x0 , une valeur initiale de la solution
f (xn )
4. Effectuer : xn+1 = xn − ′
f (xn )
|xn+1 − xn |
5. Si < ϵa :
|xn+1 |
– convergence atteinte
– écrire la solution xn+1
– arrêt
6. Si le nombre maximal d’itérations N est atteint :
– convergence non atteinte en N itérations
– arrêt
7. retour à l’étape 4
!

Exemple 2.30
On cherche à résoudre l’équation f (x) = e−x − x = 0. Pour utiliser la méthode
de Newton, calculons la dérivée de cette fonction, qui est f ′ (x) = −e−x − 1.
L’algorithme se résume à :
f (xn ) e−xn − xn
xn+1 = xn − = x n −
f ′ (xn ) −e−xn − 1
Les résultats sont compilés dans le tableau suivant à partir de x0 = 0.
Méthode de Newton : f (x) = e−x − x
( (
( en+1 (
n xn |en | ( en (
0 0,000 0000 0,5671 × 10 +0 0,1183 × 10+0
1 0,500 0000 0,6714 × 10−1 0,1239 × 10−1
2 0,566 3110 0,8323 × 10−3 0,1501 × 10−3
3 0,567 1432 0,1250 × 10−6 ≃0
4 0,567 1433 0,4097 × 10−9 —

On remarque la convergence très rapide de cette méthode. Il suffit en effet

pour s’en convaincre de comparer ces valeurs avec les résultats obtenus avec
la méthode des points fixes pour le même problème. On note également que
le nombre de chiffres significatifs double à chaque itération. Ce phénomène
est caractéristique de la méthode de Newton et nous en verrons la raison au
moment de l’analyse de convergence. La dernière colonne, qui converge vers 0,
donne une indication à ce sujet. Cette colonne est censée converger vers |g ′ (r)|,
qui est donc nul dans ce cas, ce qui semble indiquer que la convergence est
quadratique. #
 Équations non linéaires 69

2.4.1 Interprétation géométrique

La figure 2.4 permet de donner une interprétation géométrique assez simple
de la méthode de Newton. Sur cette figure, on a représenté la fonction f (x), la

(x0 , f (x0 ))

(x1 , f (x1 ))

(x2 , f (x2 ))
0

x0 x1 x2 r
Figure 2.4 – Interprétation géométrique de la méthode de Newton

valeur initiale x0 et le point (x0 , f (x0 )) qui est sur la courbe. La droite tangente
à la courbe en ce point est de pente f ′ (x0 ) et a pour équation :
y = f (x0 ) + f ′ (x0 )(x − x0 )
qui correspond au développement de Taylor de degré 1 autour de x0 . Cette
droite coupe l’axe des x en y = 0, c’est-à-dire en :
f (x0 )
x1 = x 0 −
f ′ (x0 )
qui devient la nouvelle valeur estimée de la solution. On reprend ensuite le
même raisonnement à partir du point (x1 , f (x1 )) et ainsi de suite.

2.4.2 Analyse de convergence

La méthode de Newton est un cas particulier de la méthode des points fixes
où :
f (x)
g(x) = x − ′
f (x)
Il n’est donc pas nécessaire de reprendre l’analyse de convergence à zéro. En
effet, on sait que la convergence dépend de g ′ (r) et l’on a dans ce cas précis :
(f ′ (x))2 − f (x)f ′′ (x) f (x)f ′′ (x)
g ′ (x) = 1 − = (2.15)
(f ′ (x))2 (f ′ (x))2
Puisque f (r) = 0, r étant une racine, on a immédiatement g ′ (r) = 0 et donc
une convergence au moins quadratique en vertu de la relation 2.9.
70 Chapitre 2

Remarque 2.31
Il faut noter que, dans le cas où f ′ (r) est également nul, le résultat précé-
dent n’est plus vrai dans la mesure où g ′ (r) pourra être différent de 0. Nous
étudierons cette question en détail un peu plus loin. "

Pour s’assurer que la convergence de la méthode de Newton est bel et bien

quadratique en général, il suffit de calculer g ′′ (r). On a, en vertu de l’équa-
tion 2.15 :
′′ [f ′ (x)f ′′ (x) + f (x)f ′′′ (x)](f ′ (x))2 − 2f (x)f ′ (x)(f ′′ (x))2
g (x) = (2.16)
(f ′ (x))4
On en conclut que puisque f (r) = 0 :
f ′′ (r)
g ′′ (r) =
f ′ (r)
et que g ′′ (r) n’a a priori aucune raison d’être nul. Il reste que l’on a supposé que
f ′ (r) ̸= 0, ce qui n’est pas toujours vrai. Enfin, de la relation 2.9, on déduit :
g ′′ (r) 2 f ′′ (r)
en+1 ≃ en = ′ e2n (2.17)
2 2f (r)
qui démontre bien la convergence quadratique (si f ′ (r) ̸= 0).
Exemple 2.32 √
Reprenons l’exemple où l’on doit calculer 2 en résolvant :
f (x) = x2 − 2 = 0
√ √
Dans ce cas, f ′ (x) = 2x et f ′ ( 2) = 2 2 ̸= 0. On doit donc s’attendre à une
convergence quadratique, ce que l’on peut constater dans le tableau suivant.

Méthode de Newton : f (x) = x2 − 2

( ( ( (
( en+1 ( ( en+1 (
n xn |en | ( en ( ( e2 (
n
0 2,000 0000 0,5858 × 10 +0 0,1464 × 10 +0 0,2499
1 1,500 0000 0,8578 × 10−1 0,2860 × 10−1 0,3333
2 1,416 6666 0,2453 × 10−2 0,8658 × 10−3 0,3529
3 1,414 2157 0,2124 × 10−5 0,7508 × 10−6 0,3535
4 1,414 2136 0,1594 × 10−11 — —

Le tableau précédent est encore ( une ( fois très instructif. On remarque que en
( en+1 (
tend vers 0 et que le rapport ( en ( tend aussi vers 0 (c’est-à-dire vers g ′ (r),
( (
( (
qui est 0 dans ce cas). De plus, le rapport ( en+1e2n (
tend vers à peu près 0,3535.
Encore une fois, ce nombre n’est pas arbitraire et correspond à :
√
f ′′ (r) f ′′ ( 2) 1
′
= √ = √ ≃ 0,353 553
2f (r) ′
2f ( 2) 2 2
en vertu de la relation 2.17. #
 Équations non linéaires 71

Remarque 2.33
Tout comme c’était le cas avec la méthode des points fixes, la convergence de la
méthode de Newton dépend de la valeur initiale x0 . Malgré ses belles propriétés
de convergence, une mauvaise valeur initiale peut provoquer la divergence de
cette méthode. "

Exemple 2.34
Au chapitre précédent, nous avons vu comment un ordinateur utilise une ap-
proximation rationnelle pour évaluer la fonction exponentielle. Nous allons
maintenant voir comment l’ordinateur évalue les racines carrées. C’est la mé-
thode de Newton qui est à la base de l’algorithme. Par souci d’efficacité, il est
toutefois nécessaire d’introduire quelques étapes intermédiaires. On pourrait
en effet se servir de la méthode de Newton pour résoudre :

x2 − q = 0
√
ce qui permettrait d’évaluer q pour q > 0. La √difficulté est de fournir une
valeur initiale x0 qui soit suffisamment près de q pour que la méthode de
Newton converge très rapidement. Cela est très difficile si l’on considère tout
l’intervalle [0 , ∞[. On va donc réduire la longueur de l’intervalle de travail.
Nous avons vu au chapitre 1, lors de la représentation des nombres réels en
binaire, que tout nombre q peut s’écrire sous la forme :

q = m × 2N

La normalisation de la mantisse m nous assure que 1

2 ≤ m < 1. On a alors à
distinguer 2 cas :
1. si N est pair, on a :
√ √ N
q= m×22
2. si N est impair, on a :
√
√ m (N +1)
q = √ ×2 2
2

Il reste seulement à définir un algorithme efficace pour évaluer la racine

carrée d’un nombre réel m dans l’intervalle [ 12 , 1]. On note cependant que le
√
nombre 2 doit être calculé une fois pour toutes et mis en mémoire.
C’est ici que l’on peut utiliser la méthode de Newton pour résoudre :

f (x) = x2 − m = 0
L’algorithme de base devient :
& '
f (xn ) (x2 − m) 1 m
xn+1 = xn − ′ = xn − n = xn +
f (xn ) 2xn 2 xn
72 Chapitre 2
×10−4
2

1,5

0,5

-0,5

-1

-1,5

-2
-2,5
0,5 0,55 0,6 0,65 0,7 0,75 0,8 0,85 0,9 0,95 1
x

√ # $
1,029 660 39
Figure 2.5 – Fonction x − 1,272 353 67 + 0,242 693 281x − 1+x

Cependant, le problème de la valeur x0 de départ se pose encore. Suivant

Cheney et Kincaid [8], la courbe :

1,029 660 39
y = 1,272 353 67 + 0,242 693 281x −
1+x
√
est une bonne approximation de la fonction x mais uniquement dans l’in-
tervalle [ 12 , 1]. C’est ce que l’on peut constater à la figure 2.5 où on a tracé
la différence entre ces 2 fonctions. Cela nous permet d’utiliser cette expression
pour déterminer l’approximation initiale x0 de la racine et de nous assurer ainsi
qu’elle est très près de la racine recherchée puisque l’erreur maximale commise
est de 2,0 × 10−4 . √
Ainsi, si l’on veut calculer par exemple 8,8528, on écrit d’abord que
8,8528 = 0,5533 × 24 . On doit dans un premier temps calculer la racine carrée
de 0,5533. Pour ce faire, on pose :
1,029 660 39
x0 = 1,272 353 67 + (0,242 693 281)(0,5533) − 1+0,5533
= 0,743 750 141 653 6794

Les itérations de la méthode de Newton donnent ensuite, à partir de ce x0

particulier :
x1 = 0,743 841 386 537 2300
x2 = 0,743 841 380 940 8563
et l’on constate que 2 itérations ont suffi. On a alors que :
)
8,8528 = 0,743 841 380 940 8563 × 22 = 2,975 365 523 763 425

qui est le résultat exact en double précision. #

 Équations non linéaires 73

L’exemple précédent nous amène à l’algorithme :

Algorithme 2.35 : Calcul d’une racine carrée

1. Exprimer q sous la forme q = m × 2N
1,029 660 39
2. x0 = 1,272 353 67 + 0,242 693 281m − 1+m
3. Pour n ≥ 1, et jusqu’à convergence :
& '
1 m
xn+1 = xn +
2 xn
√
4. On note r la racine obtenue (r = m)
5. On évalue la racine carrée :
⎧ N
⎪
⎨ r × 2 2 si N est pair
√
q=
⎩ √r × 2 2
⎪ (N +1)
si N est impair
2
!

2.4.3 Cas des racines multiples

Il arrive parfois que la méthode de Newton ne converge pas aussi vite que
l’on s’y attendait. Cela est souvent le signe d’une racine multiple, dont nous
rappelons la définition.

Définition 2.36 Une racine r de la fonction f (x) est dite de multiplicité m

si la fonction f (x) peut s’écrire sous la forme :

f (x) = (x − r)m h(x) (2.18)

et ce, pour une fonction h(x) vérifiant limx→r h(x) = h(r) ̸= 0.

Si l’on a une racine de multiplicité m en x = r, on peut mettre en facteur

un terme de la forme (x − r)m de telle sorte que le reste h(x) ne s’annule pas
en x = r. Il est facile de démontrer, en utilisant un développement de Taylor
autour de r, que le résultat suivant est vrai.

Théorème 2.37
Une racine r est de multiplicité m (où m est un entier) si et seulement si :

f (r) = f ′ (r) = f ′′ (r) = · · · = f (m−1) (r) = 0, f (m) (r) ̸= 0 (2.19)

c’est-à-dire si la fonction de même que ses (m−1) premières dérivées s’annulent

en r (la dérivée d’ordre m ne doit pas s’annuler en r). ⋆
74 Chapitre 2

Exemple 2.38
La fonction f (x) = x sin x possède une racine de multiplicité 2 en x = 0. En
effet :
f (x) = x sin x
f ′ (x) = sin x + x cos x
f ′′ (x) = 2 cos x − x sin x
et l’on conclut aisément que f (0) = 0 , f ′ (0) = 0 et f ′′ (0) ̸= 0. #

Qu’arrive-t-il si l’on applique la méthode de Newton à ce cas ? Rappelons

que :
f (x)f ′′ (x)
g ′ (x) =
(f ′ (x))2
et que, si l’on est en présence d’une racine de multiplicité m, on a :

f (x) = (x − r)m h(x)

f ′ (x) = m(x − r)m−1 h(x) + (x − r)m h′ (x)
f ′′ (x) = m(m − 1)(x − r)m−2 h(x)
+ 2m(x − r)m−1 h′ (x) + (x − r)m h′′ (x)

En remplaçant et en simplifiant le facteur (x − r)2m−2 , on trouve :

h(x)[m(m − 1)h(x) + 2m(x − r)h′ (x) + (x − r)2 h′′ (x)]

g ′ (x) =
[mh(x) + (x − r)h′ (x)]2

Cela entraîne que :

h(r)[m(m − 1)h(r) + 0]
g ′ (r) =
m2 (h(r))2

Puisque h(r) ̸= 0, on peut simplifier cette relation et obtenir :

1
g ′ (r) = 1 −
m
On constate maintenant que g ′ (r) = 0 seulement si m = 1, c’est-à-dire
si l’on a une racine simple (de multiplicité 1). La convergence ne sera donc
quadratique que pour les racines simples. Si m ̸= 1, la méthode de Newton
converge linéairement avec un taux de convergence de 1 − m 1
. On remarque
aussi que, plus m est grand, plus la convergence est lente, car g ′ (r) est de plus
en plus près de 1.

Exemple 2.39
On considère la résolution de :

f (x) = x3 − 5x2 + 7x − 3 = 0
 Équations non linéaires 75

En partant de x0 = 0, on obtient le tableau suivant.

Méthode de Newton : f (x) = x3 − 5x2 + 7x − 3
( ( ( (
( en+1 ( ( en+1 (
n xn |en | ( en ( ( e2 (
n
0 0,000 0000 1,0000 0,5714 0,5714
1 0,428 5714 0,5714 0,5499 0,9625
2 0,685 7143 0,3142 0,5318 1,6926
3 0,832 8654 0,1671 0,5185 3,1017
4 0,913 3299 0,0866 0,5102 5,8864
5 0,955 7833 0,0442 0,5045 11,429
6 0,977 6551 0,0223 — —
On voit tout de suite que la convergence vers la racine r = 1 est lente. On vérifie
aisément que f (1) = f ′ (1) = 0 et donc que 1 est une racine de multiplicité
2 (m = 2). Cela est confirmé par la quatrième colonne du tableau, qui doit
normalement converger vers 1 − m 1
, c’est-à-dire vers 0,5 dans ce cas précis.
On note enfin que les valeurs de la dernière colonne semblent augmenter sans
cesse et tendre vers l’infini. Cela indique une fois de plus que la convergence
est linéaire et non quadratique. #

Il existe des moyens de récupérer la convergence quadratique dans le cas de

racines multiples. Il suffit en effet de transformer le problème en un problème
équivalent ayant les mêmes racines, mais de multiplicité 1. Dans cette optique,
considérons la fonction :
f (x)
u(x) = ′
f (x)
On a immédiatement :
(x − r)m h(x) (x − r)h(x)
u(x) = ′
=
m(x − r) m−1 m
h(x) + (x − r) h (x) mh(x) + (x − r)h′ (x)
et :
[h(x) + (x − r)h′ (x)][mh(x) + (x − r)h′ (x)]
u′ (x) =
[mh(x) + (x − r)h′ (x)]2

[(x − r)h(x)][mh′ (x) + h′ (x) + (x − r)h′′ (x)]

−
[mh(x) + (x − r)h′ (x)]2
Puisque h(r) ̸= 0, on a u(r) = 0 mais aussi u′ (r) = m 1
̸= 0. r est donc
une racine simple de u(x), mais une racine multiple de f (x). On peut dès lors
appliquer l’algorithme de Newton à la fonction u(x) pour trouver cette racine.
L’algorithme devient :
f (xn )
u(xn ) f ′ (xn )
xn+1 = xn − ′ = xn − (f ′ (xn ))2 −f (xn )f ′′ (xn )
u (xn )
(f ′ (xn ))2

ou plus succinctement :
f (xn )f ′ (xn )
xn+1 = xn − (2.20)
(f ′ (xn ))2 − f (xn )f ′′ (xn )
76 Chapitre 2

On note que cet algorithme requiert la connaissance de f (x), de f ′ (x) et de

f ′′ (x), ce qui peut rendre laborieux le processus de résolution. Si l’on reprend
le problème de l’exemple précédent en utilisant cette fois l’algorithme 2.20,
on retrouve la convergence quadratique, comme en témoignent les résultats
suivants.

Méthode de Newton : u(x) = ff′(x)

( ( (x) ( (
( en+1 ( ( en+1 (
n xn |en | ( en ( ( e2 (
n
0 0,000 000 0,1000 × 10+1 0,1052 × 10+0 0,1053
1 1,105 263 0,1053 × 10+0 0,2927 × 10−1 0,2781
2 1,003 082 0,3081 × 10−2 0,7729 × 10−3 0,2508
3 1,000 002 0,2382 × 10−5 — —

Remarque 2.40
Il existe un autre algorithme qui permet de récupérer la convergence quadra-
tique de la méthode de Newton, mais il exige de connaître à l’avance la mul-
tiplicité m de la racine recherchée. Cela est évidemment très rare en pratique.
On retrouvera cet algorithme dans les exercices de fin de chapitre. "

r x 0 x2 x1 x3

Figure 2.6 – Cas pathologique pour la méthode de Newton

Exemple 2.41
Les racines multiples ne sont pas la seule source de difficultés que l’on peut
rencontrer avec la méthode de Newton. Quelques cas pathologiques, comme
celui qu’illustre la figure 2.6, aboutissent à la divergence de l’algorithme. Le
choix de la valeur initiale x0 est primordial, car la convergence de l’algorithme
en dépend fortement. Dans l’exemple de la figure 2.6, une valeur de x0 plus
près de la racine r permettrait de retrouver la convergence. #
 Équations non linéaires 77

2.5 Méthode de la sécante

La méthode de Newton possède de grands avantages, mais elle nécessite
le calcul de la dérivée de f (x). Si la fonction f (x) est complexe, cette dérivée
peut être difficile à évaluer et peut résulter en une expression complexe. 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 )) plutôt que la droite tangente passant par (xn , f (xn )). Ce choix
est représenté à la figure 2.7. Il en résulte l’algorithme suivant.

Algorithme 2.42 : Algorithme de la méthode de la sécante

1. Étant donné ϵa , un critère d’arrêt
2. Étant donné N , le nombre maximal d’itérations
3. Étant donné x0 et x1 , deux valeurs initiales de la solution
4. Effectuer :
f (xn )(xn − xn−1 )
xn+1 = xn − (2.21)
(f (xn ) − f (xn−1 ))
|xn+1 − xn |
5. Si < ϵa :
|xn+1 |
– convergence atteinte
– écrire la solution xn+1
– arrêt
6. Si le nombre maximal d’itérations N est atteint :
– convergence non atteinte en N itérations
– arrêt
7. retour à l’étape 4
!

Remarque 2.43
Plusieurs remarques s’imposent au sujet de cet algorithme.
1. La dérivée de f (x) n’apparaît plus dans l’algorithme.
2. Il faut fournir au départ 2 valeurs initiales. C’est ce qu’on appelle un
algorithme à deux pas.
3. On choisit les valeurs initiales le plus près possible de la racine recherchée.
Il n’est cependant pas nécessaire qu’il y ait un changement de signe dans
l’intervalle [x0 , x1 ], comme c’est le cas avec la méthode de la bissection.
"
78 Chapitre 2

(x0 , f (x0 ))

(x1 , f (x1 ))
(x2 , f (x2 )
(x3 , f (x3 ))
0

x0 x1 x2 x3 r
Figure 2.7 – Interprétation géométrique de la méthode de la sécante

Convergence de la méthode de la sécante

On ne peut pas se servir ici de l’analyse d’erreur élaborée pour les méthodes
des points fixes parce que la méthode de la sécante n’est pas une méthode
des points fixes au sens de l’équation 2.5. Il s’agit d’une méthode à deux pas
puisqu’on a besoin de xn−1 et xn pour calculer xn+1 . L’analyse d’erreur est
cependant similaire si l’on suit l’approche proposée par Gander et Gruntz [19].
En effet, en soustrayant r de chaque côté de la relation 2.21, on trouve :

f (xn )(xn − xn−1 )

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

f (r + (xn − r))((xn − r) − (xn−1 − r))

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

f (r + en )(en − en−1 )
= en −
f (r + en ) − f (r + en−1 )

On effectue ensuite les développements de Taylor appropriés :

en+1 = en −
. # $ /
f ′′ (r)
f (r) + f ′ (r)e
n+ 2 e2n
+ · · · (en − en−1 )
. # ′′ $ / . # ′′ $ /
f (r) + f ′ (r)en + f 2(r) e2n · · · − f (r) + f ′ (r)en−1 + f 2(r) e2n−1 · · ·
 Équations non linéaires 79

Puisque r est une racine, f (r) = 0 et nous supposerons par la suite que r est
une racine simple (f ′ (r) ̸= 0), mais aussi que f ′′ (r) ̸= 0. On a ainsi :
. # ′′ $ /
f ′ (r)en + f 2(r) e2n + · · · (en − en−1 )
en+1 = en − . # ′′ $ /
′ f (r) 2 2
f (r)(en − en−1 ) + 2 (en − en−1 ) + · · ·
. # $ /
f ′′ (r)
f ′ (r)e n + 2 e2n + ···
= en − . # $ /
f ′′ (r)
f ′ (r) + 2 (en + en−1 ) + · · ·
.# $ /
f ′′ (r)
2 en en−1 + · · ·
= . #′′
$ /
f ′ (r) + f 2(r) (en + en−1 ) + · · ·

On garde ensuite seulement les termes dominants au numérateur et au déno-

minateur pour obtenir :
[f ′′ (r)en en−1 ]
en+1 ≃ (2.22)
2f ′ (r)
Notons l’analogie avec la relation 2.17 caractérisant la méthode de Newton.
On cherche maintenant à déterminer l’exposant p de sorte que :
en ≃ Cepn−1
On aura alors :
2
en+1 ≃ Cepn ≃ C(Cepn−1 )p = C p+1 epn−1
de sorte qu’en remplaçant les expressions de en+1 et en en fonction de en−1
dans la relation 2.22, on a :
. /
0 ′′ 1 ′′ p+1
2
p
f (r)(Cen−1 en−1 ) f (r)(Cen−1 )
C p+1 epn−1 ≃ =
2f ′ (r) 2f ′ (r)
ou encore, en isolant à gauche tous les termes en p :
2
−p−1 f ′′ (r)
epn−1 ≃ C −p
2f ′ (r)
Cette relation doit être vérifiée quelle que soit la valeur de en−1 , c’est-à-dire
quelle que soit l’erreur de départ. Le terme de droite étant indépendant de
en−1 , cette relation n’est possible que si le terme de gauche est également
indépendant de en−1 , ce qui ne peut se produire que si :
p2 − p − 1 = 0
de sorte que : √ √
1+ 5 1− 5
p= ou
2 2
80 Chapitre 2

La dernière valeur étant négative, on retient que√ l’ordre de convergence de la

méthode de la sécante est le nombre d’or α = 1+2 5 . La convergence n’est donc
pas quadratique, mais elle est plus que linéaire. On parle alors de convergence
superlinéaire. Illustrons tout ceci à l’aide d’un exemple.

Exemple 2.44
On cherche à résoudre :
e−x − x = 0
que nous avons déjà abordé par d’autres méthodes. En prenant x0 = 0 et
x1 = 1, on trouve à la première itération :
(e−x1 − x1 )(x1 − x0 )
x 2 = x1 −
(e−x1 − x1 ) − (e−x0 − x0 )

(e−1 − 1)(1 − 0)
= 1− = 0,612 6998
(e−1 − 1) − (e0 − 0)
Les résultats sont compilés dans le tableau suivant.
Méthode de la sécante : f (x) = e−x − x
( ( ( ( ( (
( en+1 ( ( en+1 ( ( en+1 (
n xn |en | ( en ( ( eαn ( ( e2 (
n
0 0,000 0000 0,5671 × 10+0 0,7632 × 10+0 1,0835 1,342
1 1,000 0000 0,4328 × 10+0 0,1052 × 10+0 0,1766 0,243
2 0,612 6998 0,4555 × 10−1 0,7254 × 10−1 0,4894 1,592
3 0,563 8384 0,3305 × 10−2 0,8190 × 10−2 0,2796 2,478
4 0,567 1704 0,2707 × 10−4 0,6134 × 10−3 0,4078 22,66
5 0,567 1433 0,1660 × 10−7 ≃0 — —
6 0,567 1433 ≃0 — — —

( (
( en+1 (
La chose la plus importante à remarquer est que le rapport ( en ( tend vers
( (
( en+1 (
0, mais que le rapport ( e2 ( tend vers l’infini, ce qui confirme que l’ordre de
n
convergence
( ( se trouve
√ quelque part entre 1 et 2. On remarque que le quotient
( en+1 ( (1+ 5)
( eαn (, où α = 2 est le nombre d’or, semble se stabiliser autour de 0,4
bien que la précision soit insuffisante pour être plus affirmatif. Il semble bien
que cette suite ne tende √ni vers 0 ni vers l’infini, ce qui confirme que l’ordre de
convergence est bien 1+2 5 ≃ 1,618. #

2.6 Applications
Nous présentons dans cette section quelques exemples d’applications des
méthodes numériques vues dans ce chapitre à des problèmes d’ingénierie. Chaque
problème est brièvement décrit de manière à donner une idée assez précise du
contexte, sans toutefois s’attarder sur les détails.