Chapitre 3

Racines d’équations

Contenu
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Dichotomie . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Méthode de Ridder . . . . . . . . . . . . . . . . . . . 23
3.3.1 Méthode de la position fausse . . . . . . . . . . . . . . 23
3.3.2 Méthode de Ridder . . . . . . . . . . . . . . . . . . . . 24
3.4 Méthode de Brent . . . . . . . . . . . . . . . . . . . . 25
3.5 Newton-Raphson . . . . . . . . . . . . . . . . . . . . . 25
3.6 Racines de Polynômes . . . . . . . . . . . . . . . . . 26
3.6.1 Réduction polynomiale . . . . . . . . . . . . . . . . . . 26
3.6.2 Méthode de Laguerre . . . . . . . . . . . . . . . . . . 27

3.1 Introduction
L’une des tâches rencontrées fréquemment lors d’un calcul est la recherche
de la racine d’une équation. Sans perte de généralité, on peut toujours écrire
une équation où le membre de droite est égal à zéro,

f (x) = 0 (3.1)

Si x est une variable scalaire, le problème est unidimensionnel. Si x est une

variable vectorielle (à N dimensions) et que l’on a N équations à satisfaire, on
peut formellement écrire sous une notation vectorielle

f (x) = 0 (3.2)

Malgré la similarité des équations (3.1) et (3.2), un système d’équations à N

variables est considérablement plus compliqué à résoudre qu’un système unidi-
mensionnel. La raison vient du fait que la méthode générale pour la recherche de
racines est liée à la capacité d’encadrer numériquement la région où le système
d’équations possède une racine particulière.
On exclut de ce chapitre le cas des systèmes linéaires qui sera traité dans
le chapitre de l’algèbre linéaire. Le principe dominant la recherche de racines

21
Racines d’équations

d’équations est celui de méthodes itératives, où en partant d’une valeur d’essai
(ou un couple de valeurs d’essai), on s’approche de plus en plus près de la
solution exacte. Il est évident qu’une estimation de départ raisonnable associée
à une fonction f qui varie suffisamment lentement est nécessaire pour obtenir
une convergence vers la solution recherchée.
Nous allons considérer le problème unidimensionnel pour lequel plusieurs
méthodes sont disponibles afin de choisir la méthode la mieux adaptée compte
tenu des informations que l’on dispose sur la fonction f . Une dernière partie de
ce chapitre sera consacrée aux méthodes plus spécifiques pour la recherche de
racines de polynômes

3.2 Dichotomie
Comme nous l’avons mentionné ci-dessus, la clé de la recherche de racines
d’équations repose sur l’existence d’un encadrement préalable de cette racine.
S’il existe un couple (a, b) tel que le produit f (a)f (b) < 0 et si la fonction est
continue, le théorème de la valeur intermédiaire nous dit que fonction s’annule
au moins une fois à l’intérieur de cet intervalle.
La méthode de dichotomie est une méthode qui ne peut pas échouer, mais
sa rapidité de convergence n’est pas la meilleure en comparaison avec les autres
méthodes. L’idée de cette méthode est la suivante : soit une fonction f monotone
sur un intervalle [a0 , b0 ] telle que f (a0 )f (b0 ) < 0 , on sait alors qu’il existe une
et une seule racine comprise dans cet intervalle.
L´algorithme de la méthode de dichotomie est le suivante : tout d’abord,
on calcule f ( a0 +b2 ).
0

– Si f ( a0 +b
2 )f (a0 ) < 0, on définit un nouvel encadrement de la racine par
0

le couple (a1 , b1 ) tel que

a1 = a 0 (3.3)
a0 + b0
b1 = . (3.4)
2
– Si f ( a0 +b
2 )f (a0 ) > 0, alors on définit un nouvel encadrement de la racine
0

par le couple (a1 , b1 ) tel que

a0 + b0
a1 = (3.5)
2
b1 = b0 . (3.6)
En itérant cette méthode, on obtient une suite de couple (an , bn ) telle que
²n = bn − an vérifie la relation
²n
²n+1 = (3.7)
2
où ²0 = (b0 − a0 )/2 Cela signifie que si l’on se fixe la tolérance ² qui représente
la précision à laquelle on souhaite obtenir la racine, on a un nombre d’itérations
à effectuer égal à µ ¶
|b0 − a0 |
n = ln2 (3.8)
²

22
 3.3 Méthode de Ridder

où la notation ln2 signifie le logarithme en base 2.

Le choix de la valeur de la tolérance nécessite quelques précautions. Si la
racine recherchée est de l’ordre de l’unité, on peut très raisonnablement choisir ² 0
de l’ordre de 10−6 à 10−13 selon que l’on travaille en simple ou double précision.
Par contre pour une racine dont la valeur est de l’ordre de 1010 , une précision
de 10−4 sera la valeur maximale que l’on peut atteindre en double précision.
Inversement, pour une racine proche de zéro, la précision peut être meilleure
que 10−14 .

3.3 Méthode de Ridder

3.3.1 Méthode de la position fausse
La méthode de dichotomie sous-exploite le fait que l’on peut mieux utiliser la
fonction à l’intérieur de l’encadrement effectué à chaque itération. La méthode
de la position fausse approche la fonction de manière linéaire dans l’intervalle
considéré.
Soit la droite y = cx+d passant par f (a0 ) et f (b0 ) en a0 et b0 respectivement,
on obtient facilement que
f (b0 ) − f (a0 )
c= (3.9)
b0 − a0
b0 f (a0 ) − a0 f (b0 )
d= (3.10)
b0 − a0
La nouvelle abscisse estimée pour la racine de l’équation est donnée par y =
cx + d = 0, ce qui donne
d
x=− (3.11)
c
b0 f (a0 ) − a0 f (b0 )
= (3.12)
f (b0 ) − f (a0 )
soit encore
f (a0 )
x = a0 − (b0 − a0 ) (3.13)
f (b0 ) − f (a0 )
f (b0 )
= b0 + (b0 − a0 ) (3.14)
f (b0 ) − f (a0 )
On reprend à ce stade le principe de l’algorithme précédent si f (x)f (a0 ) > 0
alors
a1 = x (3.15)
b1 = b0 (3.16)
sinon
a1 = a 0 (3.17)
b1 = x (3.18)
La figure

23
Racines d’équations

2
4

4
0

1
-2

0 0.5 1 1.5 2 2.5 3

Fig. 3.1 – Schéma illustrant le principe de la position fausse. Les lignes en

pointillé correspondent aux interpolations linéaires. A partir de l’encadrement
repéré par les points 1 et 2, le processus itératif conduit aux points 3, puis 4...

3.3.2 Méthode de Ridder

Une variante de la méthode précédente qui est très efficace est basée sur
l’algorithme suivant. On évalue la fonction au point x = a0 +b 2
0
et on résout
l’équation en z
f (a0 ) − 2f (x)z + f (b0 )z 2 = 0 (3.19)
La solution positive est donnée par
p
f (x) + sgn(f (x)) f (x)2 − f (a0 )f (b0 )
z= (3.20)
f (b0 )
En appliquant la méthode de la position fausse non pas à f (a0 ), f (x) et f (b0 ),
mais à f (a0 ), f (x)z et f (b0 )z 2 , on obtient une approximation de la racine, notée
x4 et donnée par
sgn(f (a0 ) − f (b0 ))f (x)
x4 = x + (x − a0 ) p (3.21)
f (x)2 − f (a0 )f (b0 )
Parmi les propriétés remarquables, notons que x4 est toujours située à l’in-
térieur de l’intervalle [a0 , b0 ]. Si le produit f (x3 )f (x4 ) est négatif, on prend
l´intervalle [x3 , x4 ] comme nouvelle encadrement, sinon si on considère le pro-
duit f (x1 )f (x4 ) ; si celui est négatif, le nouvel encadrement est [x1 , x4 ], sinon
on prend [x4 , x2 ]. On itère ensuite le procédé.

24
 3.4 Méthode de Brent

3.4 Méthode de Brent

Le principe de cette méthode est de combiner les avantages des méthodes
précédemment exposées en utilisant, le principe de l’encadrement de la racine, la
dichotomie, et l’interpolation quadratique inverse. Cela nécessite de connaı̂tre
trois valeurs de la fonction f dont la racine est à déterminer. Soit (a, f (a)),
(b, f (b)), et (c, f (c)) la formule d’interpolation est donnée par

(y − f (a))(y − f (b))c
x=
(f (c) − f (a))(f (c) − f (b))
(y − f (b))(y − f (c))a (y − f (c))(y − f (a))b
+ + (3.22)
(f (a) − f (b))(f (a) − f (c)) (f (b) − f (c))(f (b) − f (a))

En choisissant y = 0, on peut écrire l’équation (3.22) comme

P
x=b+ (3.23)
Q
où P et Q sont donnés par

P = S[T (R − T )(c − b) − (1 − R)(b − a)] (3.24)

Q = (T − 1)(R − 1)(S − 1) (3.25)

où R, S et T s’expriment comme

f (b)
R= (3.26)
f (c)
f (b)
S= (3.27)
f (a)
f (a)
T = (3.28)
f (c)
P
En pratique, b est une première estimation de la racine et Q une petite correc-
P
tion. Quand Q → 0 la valeur de Q peut devenir très grande et l’itération par la
méthode de Brent est remplacée par une itération de dichotomie.

3.5 Newton-Raphson
Toutes les méthodes précédentes ne nécessitaient que la connaissance de la
fonction en différents points de l’intervalle encadrant la racine. Sous réserve
que la variation de la fonction ne soit pas trop rapide, seule une hypothèse de
continuité est nécessaire.
La méthode de Newton-Raphson nécessite de plus que la fonction f dont
on cherche à déterminer une racine, soit dérivable au voisinage de celle-ci.
Les itérations successives de la méthode de Newton-Raphson sont basées sur
le développement limité de la fonction autour d’un point

f 00 (x) 2
f (x + δ) = f (x) + f 0 (x)δ + δ + ... (3.29)
2

25
Racines d’équations

Si δ est suffisamment petit, on peut négliger les termes non linéaires et une
estimation de la racine est donnée par f (x + δ) = 0.

f (x)
δ=− (3.30)
f 0 (x)
On voit immédiatement qu’il est nécessaire que la dérivée de la fonction ne
s’annule pas dans le voisinage de x, sous peine que l’estimation de δ devienne
très grande et ne permette pas à la méthode de converger.
Si les conditions précédemment énoncées sont vérifiées, on a une méthode
qui converge de manière quadratique.
En effet, la relation de récurrence entre estimations successives est donnée
par
f (xi )
xi+1 = xi − 0 (3.31)
f (xi )
En posant ²i+1 = xi+1 − x, où x est la racine exacte, on a
f (xi )
²i+1 = ²i − (3.32)
f 0 (xi )
Si on utilise un développement limité de f au deuxième ordre au point xi (ce
qui suppose que la fonction est deux fois dérivable au voisinage de la racine),
on obtient
f 00 (xi )
²i+1 = −²2i 0 (3.33)
2f (xi )
La méthode converge donc très rapidement par comparaison avec les méthodes
précédentes.
A noter que si la dérivée de la fonction n’est pas connue analytiquement,
l’évaluation numérique de sa dérivée est possible par une formule d’accroisse-
ment
f (x + ∆x) − f (x)
f 0 (x) ' (3.34)
∆x
Dans ce cas, la méthode de Newton-Raphson se réduit à une méthode d’in-
tersection et la convergence de celle-ci est moins rapide que la convergence
quadratique.

3.6 Racines de Polynômes

3.6.1 Réduction polynomiale
La recherche de racines d’un polynôme se construit de la manière suivante :
soit Pn (x) un polynôme de degré n. Si on obtient une première racine, on peut
écrire
Pn (x) = (x − x1 )Pn−1 (x) (3.35)
où Pn−1 (x) est un polynôme de degré n−1. Ainsi, théoriquement, une fois obte-
nue une première racine, on peut recommencer la recherche d’une autre racine
pour une polynôme de degré strictement inférieur. Successivement, on poursuit
cette procédure jusqu’à l’obtention de l’ensemble des n racines du polynôme

26
 3.6 Racines de Polynômes

Pn (x). Rappelons que les polynômes à coefficients complexes se factorisent en

un produit de monômes de degré 1. Cette propriété exprime le fait que les po-
lynômes à coefficients complexes ont l’ensemble de leurs racines dans le plan
complexe,
Yn
Pn (x) = (x − xi ) (3.36)
i=1
(C est un corps algébriquement clos).

3.6.2 Méthode de Laguerre

Les méthodes de recherche de zéros de polynômes sont nombreuses et une
présentation détaillée dépasse largement le cadre de ce cours. Nous avons choisi
de présenter une méthode dont le principe est assez simple. La méthode de
Laguerre utilise le fait que les dérivées logarithmiques successives d’un polynôme
divergent au voisinage d’une racine. En prenant le logarithme de l’équation
(3.36), on obtient
Xn
ln(|Pn (x)|) = ln(|x − xi |) (3.37)
i=1
En dérivant l’équation (3.37), on obtient
n
d ln(|Pn (x)|) X 1
=
dx x − xi
i=1
Pn0 (x)
= (3.38)
Pn (x)
=G (3.39)
En dérivant l’équation (3.38), il vient
n
d2 ln(|Pn (x)|) X 1
− 2
=
dx (x − xi )2
i=1
· 0 ¸
Pn (x) 2 Pn00 (x)
= −
Pn (x) Pn (x)
=H (3.40)
Soit la racine x1 à déterminer, on suppose que la valeur de départ x est située
à une distance a de x1 et que l’ensemble des autres racines sont situées à une
distance supposée identique et qui vaut b
x − x1 = a (3.41)
x − xi = b i ∈ [2, n] (3.42)
En insérant les équations (3.41) et (3.42) dans les équations (3.38), (3.40), on
en déduit respectivement les relations suivantes
1 n−1
+ =G (3.43)
a b
1 n−1
2
+ 2 =H (3.44)
a b

27
Racines d’équations

Après élimination de b, la valeur de a est

n
a= p (3.45)
G ± (n − 1)(nH − G2 )

Le signe placé devant la racine du dénominateur est choisi tel que le dénomina-
teur soit le plus grand possible. x−a devient alors la nouvelle valeur de départ et
on itère le processus. En combinant cette méthode avec celle de la réduction po-
lynomiale, on peut calculer l’ensemble des racines. En pratique, comme chaque
racine n’est déterminée qu’avec une précision finie, il est nécessaire d’ajouter
une procédure dite de lissage pour éviter les problèmes d’instabilité numérique.

28