C h a pi

tr e 2
Résolution d’équations non linéaires

Sommaire
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.1.1 Localisation d’une racine . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.2 Méthode de dichotomie (ou de bissection) . . . . . . . . . . . . . . 71

5.3 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.3.1 Interprétation géométrique . . . . . . . . . . . . . . . . . . . . . . . . 75

5.3.2 Analyse de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . 76

67
 5.1. Introduction

5.1 Introduction

Dans ce chapitre, nous présenterons les méthodes d’approximation des solutions d’équations
algébriques non linéaires. Nous nous limiterons au cas de la recherche des racines d’une seule
équation d’une variable.
Soit f : [a, b] ⊂ R → R une fonction continue sur [a, b]. Nous serons intéressés à trouver des
points x pour lesquels
f (x) = 0.

Introduisons dès maintenant la terminologie qui nous sera utile pour traiter ce problème.
Définition 24
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 −b + b2 − 4ac
r1 = et r2 = .
2a 2a

Il s’agit d’un cas simple dans lequel les racines peuvent être calculées à l’aide d’une formule
analytique. Il existe des formules pour trouver les racines des polynômes de degré 3 et 4, mais
elles sont assez complexes. Dans le cas plus général, lorsque f est un polynôme de degré qui est
≥ 5, les formules analytiques (par radicaux) pour les racines ne plus exister. Non pas que les
mathématiciens ne l’aient pas encore trouvées, mais Abel et par la suite Galois ont démontré
que ces formules n’existe pas.
Dans la plupart des cas, lorsque f est une fonction arbitraire, il n’y a pas de méthode analytique
pour calculer les racines. Au lieu de cela, nous devons utiliser des méthodes d’approximation.
En fait, même dans les cas où des formules exactes sont disponibles, comme avec des polynômes
de degré 3 ou 4, une formule exacte peut être trop complexe pour être utilisée en pratique, et
les méthodes d’approximation peuvent rapidement fournir une solution précise.

68
 5.1. Introduction

5.1.1 Localisation d’une racine

Il n’y a vraiment pas beaucoup d’outils généraux pour savoir à l’avance si le problème de
recherche de racines peut être résolu. Pour nos besoins, le problème le plus important sera
d’obtenir des informations sur l’existence ou non d’une racine, et si une racine existe, il sera
alors important de tenter d’estimer un intervalle auquel appartient cette racine. Pour localiser
une telle racine, en général, deux méthodes se présentent.

Méthode graphique

L’une de nos premières tentatives pour résoudre les problèmes de recherche de racines peut être
d’essayer de tracer le graphe de la fonction. Après tout, si le but est de résoudre f (x) = 0, et
que la fonction f peut être tracée de manière à ce que l’intersection de f (x) avec l’axe des x
soit visible, alors nous devrions avoir une bonne idée de l’endroit où chercher la racine. Il n’y
a absolument rien de mal avec une telle méthode, mais il n’est pas toujours facile de tracer le
graphe de la fonction.
Parfois, il arrive que f se décompose en deux fonctions f1 et f2 simples à étudier, telles que
f = f1 − f2 , et on cherche les points d’intersection des graphes de f1 et f2 , dont les abscisses
sont exactement les racines de f .
Exemple 30
1
La fonction f définie par f (x) = Log x − , x ∈ ]0, +∞[ a une racine unique dans l’intervalle
x
3  1
2
, 2 . En effet, posons f1 (x) = Log x et f2 (x) = . Alors f (x) = 0 équivalent à f1 (x) = f2 (x)
3  x
et d’après le graphe ci-contre il existe α ∈ 2 , 2 telle que f1 (α) = f2 (α).
y

1
f2 (x) =
x

f1 (x) = Log x
1

1 1.5 α 2 3 4 5 x

−1

69
 5.1. Introduction

Méthode du théorème des valeurs intermédiaires

Ce qui est parfois plus facile, c’est de vérifier que la fonction f est continue, auquel cas il
suffit de trouver un point a dans lequel f (a) > 0, et un point b, dans lequel f (b) < 0. La
continuité garantira alors, grâce au théorème des valeurs intermédiaires, qu’il existe un point c
entre a et b pour lequel f (c) = 0, et la recherche de ce point peut alors commencer. Comment
trouver de tels points a et b? Encore une fois, il n’y a vraiment pas de méthode générale. Une
combinaison d’intuition, de bon sens, de graphiques, de réflexion et d’essais à plusieurs reprises
est généralement utile.

Exemple 31
Considérons le polynôme p défini par

p(x) = x4 − x3 − x2 + 7x − 10.

Selon le théorème des valeurs intermédiaires pour les fonctions continues et d’apres le tableau
suivant

x −4 −3 −2 −1 0 1 2 3 4

p (x) 266 68 −4 −16 −10 −4 8 56 194

le polynôme p a au moins deux racines réelles α1 ∈ ]−3, −2[ et α2 ∈ ]1, 2[ .

Dans ce qui suit, nous présentons plusieurs méthodes de résolution, chacune ayant ses avantages
et ses inconvénients.
Les méthodes que nous allons décrire sont toutes des méthodes itératives. De telles méthodes
commenceront généralement par une estimation initiale de la racine (ou du voisinage de la
racine) et tenteront progressivement de s’approcher de la racine. Dans certains cas, la suite
d’itérations convergera vers une limite, auquel cas nous nous demanderons alors si le point
limite est réellement une solution de l’équation. Si tel est effectivement le cas, une autre
question intéressante est à quelle vitesse la méthode converge-t-elle vers la solution?

70
 5.2. Méthode de dichotomie (ou de bissection)

5.2 Méthode de dichotomie (ou de bissection)

Soit f une fonction continue sur l’intervalle [a, b] telle que f a des signes opposés aux extrémités
a et b, c’est-à-dire f (a) f (b) < 0.
y y

ou

b a
a c x c b x

Il existe au moins une racine r dans l’intervalle [a, b] telle que f (r) = 0. Si de plus f est
strictement monotone dans l’intervalle [a, b], alors r est unique.
La méthode de dichotomie, aussi appelée méthode de bisection, consiste à diviser l’intervalle
a+b
[a, b] en deux sous-intervalles, c = 2
.
Cela génère deux sous-intervalles, [a, c] et [c, b], de mêmes longueurs. Nous voulons conserver le
sous-intervalle qui est garanti pour contenir une racine. Bien sûr, dans le cas rare où f (c) = 0,
nous avons terminé. Sinon, on vérifie si f (a) f (c) < 0. Si oui, on garde le sous-intervalle gauche
[a, c]. Si f (a) f (c) > 0, on garde le sous-intervalle droit [c, b]. Cette procédure se répète jusqu’à
ce que le critère d’arrêt soit satisfait : on fixe un petit paramètre ε > 0 et on s’arrête quand
|f (c)| < ε. Pour simplifier la notation, nous désignons les intervalles successifs par [a0 , b0 ],
[a1 , b1 ],· · · . Les deux premières itérations de la méthode de dichotomie sont représentées sur la
figure ci-dessous.
y y

c0 b0 c1 b1= c0
a0 x a1 x
=

a0

Noter que dans le cas illustré sur la figure ci-dessus, la fonction f a plusieurs racines mais la
méthode converge vers une seule d’entre elles.

71
 5.2. Méthode de dichotomie (ou de bissection)

Nous aimerions maintenant comprendre si la méthode de la bissection converge toujours vers

une racine. Nous aimerions également savoir à quel point nous sommes proches d’une racine
après avoir répété plusieurs fois l’algorithme. Nous notons d’abord que

a0 ≤ a1 ≤ a2 ≤ · · · ≤ b 0 et b 0 ≥ b 1 ≥ b 2 ≥ · · · ≥ a0 .

Nous remarquons également que chaque itération réduit la longueur de l’intervalle de moitié,
c’est-à-dire,
1
bn+1 − an+1 = (bn − an ) , n ≥ 0,
2
ce qui signifie que
bn − an = 2−n (b0 − a0 ) .

Les suites (an )n∈N et (bn )n∈N sont monotones et bornées, et donc convergent. Également,

lim bn − lim an = lim 2−n (b0 − a0 ) = 0,

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

de sorte que les deux suites convergent vers la même valeur. Nous notons cette valeur par r,
c’est-à-dire,
r = lim an = lim bn .
n→+∞ n→+∞
2
Puisque f (an ) f (bn ) ≤ 0, donc (f (r)) ≤ 0, ce qui signifie que f (r) = 0, c’est-à-dire que r est
une racine de f .
Nous supposons maintenant que nous nous arrêtons dans l’intervalle [an , bn ]. Cela signifie que
r ∈ [an , bn ]. Étant donné un tel intervalle, si nous devons deviner où est la racine (dont
nous savons qu’elle est dans l’intervalle), il est facile de voir que la meilleure estimation de
l’emplacement de la racine est le centre de l’intervalle, c’est-à-dire
an + b n
r ' cn = .
2
Dans ce cas, nous avons |r − cn | ≤ 21 (bn − an ) = 2−(n+1) (b0 − a0 ).
Nous résumons ce résultat avec le théorème suivant.
Théorème 25
Si [an , bn ] est l’intervalle obtenu dans la n-ième itération de la méthode de dichotomie, alors
les limites lim an et lim bn existent, et
n→+∞ n→+∞

r = lim an = lim bn , où f (r) = 0.

n→+∞ n→+∞

an +bn
De plus, si cn = 2
alors
|r − cn | ≤ 2−(n+1) (b0 − a0 ) .

72
 5.2. Méthode de dichotomie (ou de bissection)

Remarque 26
Pour garantir que l’erreur |r − cn | < ε, pour une tolérance ε donnée, il suffit d’effectuer kmin
itérations, où kmin est le plus petit entier tel que

Log b−a


ε
kmin > − 1.
Log 2

Exemple 32
Soit à résoudre par la méthode de dichotomie f (x) = x3 + x2 − 3x − 3 dans l’intervale [a0 , b0 ] =
[1, 2]. On a
f (1) f (2) = −4 × 3 = −12 < 0.
1+2
On a alors c0 = 2
= 1.5 et f (1.5) = −1.875. L’intervalle [1.5, 2] possède encore un change-
ment 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 milieu est

1.5 + 2
c1 = = 1.75.
2

Puisque f (1.75) = 0.171875, on prendra l’intervalle [1.5, 1.75] et ainsi de suite.

Dans cette exemple, si on veut une erreur absolue plus petite que 0.5 × 10−2 , il faut effectuer
au moins
2−1


Log b−a


ε
Log 0.5×10 −2
kmin > −1= − 1 ' 6.643856.
Log 2 Log 2
On fera donc 7 itérations pour s’assurer de cette précision.
Le tableau suivant résume les résultats :

n an cn bn f (an ) f (cn ) f (bn ) |cn − cn−1 |

0 1 1.5 2 -4 -1.875 3
1 1.5 1.75 2 -1.875 0.171875 3 0.25
2 1.5 1.625 1.75 -1.875 -0.943359 0.171875 0.125
3 1.625 1.6875 1.75 -0.943359 -0.409423 0.171875 0.0625
4 1.6875 1.71875 1.75 -0.409423 -0.124786 0.171875 0.03125
5 1.71875 1.734375 1.75 -0.124786 0.022029 0.171875 0.015625
6 1.71875 1.726563 1.734375 -0.124786 -0.051755 0.022029 0.007812
7 1.726563 1.730469 1.734375 -0.051755 -0.049572 0.022029 0.003906

73
 5.3. Méthode de Newton

5.3 Méthode de Newton

La méthode de Newton est une méthode de recherche de racine relativement simple, pratique
et largement utilisée. Il est facile de voir que si dans certains cas la méthode converge rapi-
dement vers une racine de la fonction, dans d’autres cas, elle peut ne pas converger du tout.
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éveloppement de Taylor.
Comme toujours, nous supposons que f (x) a au moins une racine réelle et la désignons par
r. Nous commençons par une estimation initiale de l’emplacement de la racine, disons x0 . À
partir de cette valeur initiale x0 de la solution de f (x) = 0, on cherche une correction δx telle
que
f (x0 + δx) = 0.

En faisant un développement de Taylor autour de x = x0 , on trouve

1 00 1
0 = f (x0 ) + f 0 (x0 ) δx + f (x0 ) (δx)2 + f 000 (x0 ) (δx)3 + · · · .
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 0 (x0 ) δx.

On peut alors isoler la correction recherchée

f (x0 )
δx = − .
f 0 (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,

ce qui donne
f (x0 )
x 1 = x0 − . (5.1)
f 0 (x0 )
En général, la méthode de Newton (également connue sous le nom de méthode de Newton-
Raphson) pour trouver une racine est donnée en itérant (5.1) à plusieurs reprises, c’est-à-dire

f (xn )
xn+1 = xn − .
f 0 (xn )

74
 5.3. Méthode de Newton

Exemple 33
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 0 (x) = −e−x − 1. L’algorithme se résume à
f (xn ) e−xn − xn
xn+1 = xn − = x n − .
f 0 (xn ) −e−xn − 1
Les résultats sont compilés dans le tableau suivant à partir de x0 = 0.

n xn |xn − xn−1 |

0 0.0000000
1 0.5000000 0.5000 × 100
2 0.5663110 0.6631 × 10−1
3 0.5671432 0.8322 × 10−3
4 0.5671433 0.1 × 10−6

On remarque la convergence très rapide de cette méthode. 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.

5.3.1 Interprétation géométrique

Soit x0 l’estimation initiale de la solution de f (x) = 0 et soit l (x) la droite tangente à f (x) en
x0 qui a pour équation
y = f (x0 ) + f 0 (x0 ) (x − x0 ) ,

qui correspond au développement de Taylor de degré 1 autour de x0 .

L’intersection de l (x) avec l’axe des x sert comme l’estimation suivante de la racine. Nous
notons ce point par x1 et écrivons

0 = f (x0 ) + f 0 (x0 ) (x1 − x0 ) ,

ce qui donne
f (x0 )
x 1 = x0 − .
f 0 (x0 )
On reprend ensuite le même raisonnement à partir de x1 et ainsi de suite. Deux exemples
d’itérations de la méthode sont illustrés dans la figure ci-dessous.

75
 5.3. Méthode de Newton

fig

5.3.2 Analyse de convergence

Il est facile de voir que la méthode de Newton ne converge pas toujours. Nous démontrons un
tel cas dans la figure ci-dessous. Nous considérons ici la fonction f (x) = Arctg x et montrons
ce qui se passe si nous partons d’un point qui est un point fixe de la méthode de Newton, itéré
deux fois. Dans ce cas, x0 = 1.3917 est un tel point.

fig

Afin d’analyser l’erreur dans la méthode de Newton, nous notons l’erreur dans la n-ième
itération par
en = xn − r.

On suppose que f 00 (x) est continue et que f 0 (r) 6= 0, c’est-à-dire que r est une simple racine
de f (x). Si la méthode de Newton converge, alors elle a un taux de convergence quadratique,
c’est-à-dire,
en+1 ≈ ce2n .

En effet, nous réécrivons en+1 comme

f (xn ) f (xn ) en f 0 (xn ) − f (xn )

en+1 = xn+1 − r = xn − − r = en − = .
f 0 (xn ) f 0 (xn ) f 0 (xn )

En écrivant un développement de Taylor de f (r) autour de x = xn , nous avons

1
0 = f (r) = f (xn − en ) = f (xn ) − en f 0 (xn ) + e2n f 00 (ξn ) ,
2

ce qui signifie que

1
en f 0 (xn ) − f (xn ) = e2n f 00 (ξn ) .
2
D’où
1 f 00 (ξn ) 2
en+1 = e .
2 f 0 (xn ) n
1 f 00 (ξn )
Par conséquent, la relation en+1 ≈ ce2n , est vraie avec c = 2 f 0 (xn )
. Puisque nous supposons que
1 f 00 (ξn )
la méthode converge, dans la limite lorsque n → +∞ nous pouvons remplacer c = 2 f 0 (xn )
par
1 f 00 (r)
c= 2 f 0 (r)
.

76
 5.3. Méthode de Newton

Revenons maintenant à la question de la convergence et montrons que pour certaines fonctions,

la méthode de Newton converge quel que soit le point de départ.
Théorème 27
Soit f ∈ C 2 ([a, b]). Supposons que f vérifiant
1) f (a) f (b) < 0.
2) f 0 (x) 6= 0 pour tout x ∈ [a, b]. (strictement monotone)
3) f 00 (x) 6= 0 pour tout x ∈ [a, b]. (convexe ou bien concave)
Alors
a) f admet une racine unique r ∈ [a, b].
b) la suite (xn )n converge vers r pour chaque x0 ∈ [a, b] vérifiant f (x0 ) f 00 (x0 ) > 0. De plus,
cette convergence est quadratique telle que

en+1 1 f 00 (r)
lim = .
n→+∞ e2
n 2 f 0 (r)

Démonstration. Exercice.

77