Math 208 — Python pour le calcul scientifique Université Paris–Sud

L2 Informatique et Mathématiques 2017–2018

Notes de cours
Cours 7

1 Algorithmes de recherche de zéro

Soit f : I → R une fonction définie sur un intervalle I ⊂ R. Nous considérons le
problème de déterminer les valeurs x ∈ I telles que f (x) = 0, c’est-à-dire le problème
de déterminer les zéros de la fonction f . Si la fonction f est “simple”, par exemple
une fonction affine f (x) = ax + b, un polynôme de degré 2 f (x) = ax2 + bx + c, ou une
fonction du type f (x) = sin(ax) − b, f (x) = eax − b (avec a, b, c ∈ R des constantes), on
dispose de méthodes pour déterminer l’existence et la quantité de zéros et les calcu-
ler explicitement. Par contre, dès que la fonction f est un peu plus “compliquée”, par
exemple f (x) = cos(x)−x, f (x) = tan(x)−2x ou encore f (x) = ex −2x2 , il est plus compli-
qué de déterminer l’existence de zéros et un calcul explicite est en général impossible.
Nous nous intéressons donc à des méthodes numériques capables d’approcher un ou
des zéros d’une fonction f donnée.

1.1 Méthode de dichotomie

Commençons par rappeler l’énoncé du théorème des valeurs intermédiaires.

Théorème 1. Soit f : [a, b] → R une fonction continue et u un nombre réel entre f (a) et
f (b). Alors il existe c ∈ [a, b] tel que f (c) = u.

La base de la méthode de dichotomie est la conséquence suivante du théorème des

valeurs intermédiaires : si f : [a, b] → R est continue et f (a) et f (b) ont signes opposés,
alors il existe x ∈ [a, b] tel que f (x) = 0. Ce résultat permet donc de garantir l’existence
d’un zéro de f dans l’intervalle [a, b] (mais ne donne pas d’informations sur la quantité
de zéros en [a, b], on pourrait en avoir plusieurs).
Méthode de dichotomie
Données : f , x0 , x1 , ε avec f : [x0 , x1 ] → R continue, f (x0 )f (x1 ) ≤ 0, et ε > 0.
1. Calculer x2 = (x0 + x1 )/2.
2. Si f (x2 )f (x0 ) ≤ 0, alors x1 ← x2 , sinon x0 ← x2 .
3. Reprendre à partir de 1 tant que |f (x2 )| ≥ ε.

L’idée de la méthode est de tester le signe de f au point x2 = x0 +x 1

2 , le centre de
l’intervalle [x0 , x1 ]. Si f (x2 ) et f (x0 ) ont signes opposés, alors f admet un zéro dans
l’intervalle [x0 , x2 ], et on recommence en remplaçant x1 par x2 ; sinon, alors f (x2 ) et
f (x1 ) ont forcément signes opposés, f admet un zéro dans l’intervalle [x2 , x1 ], et on
recommence en remplaçant x0 par x2 . On repète jusqu’à ce que |f (x2 )| < ε, ε > 0 étant
une tolérance donnée.

1
Proposition 2. Soient a, b ∈ R avec a < b et f : [a, b] → R une fonction continue telle que
f (a)f (b) ≤ 0. Définissons deux suites (an )n∈N et (bn )n∈N de façon récurrente comme suit :
a0 = a, b0 = b, et, pour n ∈ N∗ ,
  
1 1
 a
 n
 = an−1 b n = (a
2 n−1 + b n−1 ) si f (a
2 n−1 + b n−1 f (an−1 ) ≤ 0,
)
 a = 1 (a

+b ) b =b sinon.

n 2 n−1 n−1 n n−1

Alors (an )n∈N et (bn )n∈N convergent toutes les deux vers une même valeur x ∈ [a, b] telle que
f (x) = 0.
Démonstration. Remarquons que, pour tout n ∈ N∗ , on a
bn−1 − an−1
bn − an = ,
2
et ainsi
b−a
0 < bn − an < . (1)
2n
On observe que (an )n∈N est une suite croissante, bornée supérieurement par b, et que
(bn )n∈N est décroissante, bornée inférieurement par a, donc les deux suites convergent.
D’après (1), bn − an → 0 lorsque n → ∞, et donc (an )n∈N et (bn )n∈N convergent toutes les
deux vers une même valeur x ∈ [a, b].
On remarque que, pour tout n ∈ N, on a f (an )f (bn ) ≤ 0, et donc, par le théorème
des valeurs intermédiaires, il existe cn ∈ [an , bn ] tel que f (cn ) = 0. Comme limn→∞ an =
limn→∞ bn = x, on a limn→∞ cn = x par le théorème des gendarmes. Comme f est conti-
nue, on obtient donc que f (x) = 0. 

Corolaire 3. Sous les notations de la Proposition 2, soit (xn )n∈N la suite définie par xn =
1 ∗
2 (an + bn ) pour tout n ∈ N et x la limite de (an )n∈N et (bn )n∈N . Alors, pour tout n ∈ N ,
l’erreur εn = |xn − x| satisfait
b−a
εn < n+1 . (2)
2
Le code suivant donne une implémentation de la méthode de dichotomie en Py-
thon.
def dichotomie(a, b, eps , f):
x0 = a
x1 = b
y0 = f(x0)
y1 = f(x1)

if y0 * y1 > 0:
raise Exception("f(a) et f(b) ont même signe.")

x2 = (x0 + x1)/2
y2 = f(x2)

while abs(y2) > eps:

if y0 * y2 <= 0:
x1 = x2
y1 = y2

2
 else:
x0 = x2
y0 = y2
x2 = (x1 + x0)/2
y2 = f(x2)

return x2

1.2 Méthode de Newton

L’idée de la méthode de Newton est la suivante. Supposons que l’on dispose d’une
approximation xn d’une solution x∗ de f (x∗ ) = 0. Alors on approche la fonction f au
voisinage du point xn par sa droite tangente y = f (xn ) + f 0 (xn )(x − xn ). On utilise cette
équation de la droite tangente pour trouver une nouvelle approximation xn+1 de x∗ :
on résout
f (xn ) + f 0 (xn )(xn+1 − xn ) = 0, (3)
ce qui donne
f (xn )
xn+1 = xn − . (4)
f 0 (xn )
Une illustration de la méthode de Newton est donnée dans la Figure 1.

xn+1
xn xn+2

Figure 1 – Illustration de la méthode de Newton pour le calcul de xn+1 et xn+2 .

On arrive à montrer assez facilement que, si la méthode de Newton converge, alors

la limite est bien un zéro de f .
Proposition 4. Soit f : R → R une fonction de classe C1 , x0 ∈ R, et considérons la suite
(xn )n∈N construite par (4). Si cette suite est bien définie et converge vers une valeur x ∈ R,
alors f (x) = 0.
Démonstration. En passant à la limite en (3), on obtient

f (x) + f 0 (x)(x − x) = 0,

et donc f (x) = 0. 

3
 Le résultat suivant (admis dans ce cours) donne des conditions pour garantir la
convergence de la méthode de Newton.
Théorème 5. Soit f : R → R une fonction de classe C1 et x∗ un zéro de f tel que f 0 (x∗ ) , 0.
Alors il existe un intervalle I ⊂ R contenant x∗ dans son intérieur tel que, pour tout x0 ∈ I,
la suite (xn )n∈N définie par (4) converge vers x∗ .
Si en plus f est de classe C2 , alors on peut choisir l’intervalle I de sorte qu’il existe M > 0
tel que l’erreur εn = |xn − x∗ | satisfait, pour tout n ∈ N

εn+1 ≤ Mεn2 . (5)

À cause de l’estimée (5), la méthode de Newton est dite quadratique. C’est son prin-
cipal avantage par rapport à la méthode de dichotomie : l’erreur décroissant de façon
quadratique, on a une convergence beaucoup plus rapide. Par exemple, pour le calcul
numérique du zéro positif de la fonction f (x) = x2 − 2 avec une précision de 10−15 , il
faut 51 itérations à la méthode de dichotomie avec comme condition initiale l’inter-
valle [1, 2], et seulement 5 itérations à la méthode de Newton avec condition initiale
x0 = 2.
Un autre avantage de la méthode de Newton est qu’elle se généralise bien pour
résoudre des systèmes d’équations à plusieurs variables (ce qui sort du cadre de ce
cours), la dérivée de f étant remplacée par sa matrice Jacobienne, alors que la méthode
de dichotomie se limite à des fonctions à une variable.
Par contre, la méthode de Newton possède plusieurs inconvénients. Le Théorème 5
garantit la convergence si x0 est choisi dans un intervalle I autour de x∗ , mas ne donne
pas d’indication sur quel est cet intervalle I. La méthode peut diverger si l’on prend x0
assez loin de x∗ : par exemple, pour

f (x) = x3 − 2x + 2,

la méthode de Newton s’écrit

xn3 − 2xn + 2 2xn3 − 2
xn+1 = xn − = 2 .
3xn2 − 2 3xn − 2
Si x0 = 0, alors x1 = 1, x2 = 0, x3 = 1, x4 = 0, et la suite oscille entre 0 et
r1qsans ja-
3 19
mais converger vers un zéro de f (l’unique zéro de f dans ce cas étant 27 − 1 −
rq
3 19
27 + 1 ≈ −1,76929235).
La méthode de Newton exige également que f soit de classe C1 , alors que la mé-
thode de dichotomie ne demande que la continuité de f . La méthode de Newton peut
diverger si f n’est pas dérivable en son zéro. Par exemple, pour
√
f (x) = 3 x,

la méthode de Newton s’écrit

√
3 xn
xn+1 = xn − 2
= −2xn
1 −3
x
3 n

et donc xn = (−2)n x0 , qui diverge pour tout x0 , 0.

4
 La méthode de Newton est très utilisée en pratique à cause de sa convergence qua-
dratique, mais il faut garder en tête ses limitations pour savoir dans quelles situations
on peut l’appliquer.
Le code suivant donne une implémentation de la méthode de Newton en Python.
import warnings

def newton(x0 , f, fprime , Nmax , eps):

i = 0
x = x0
y = f(x)

while (i < Nmax) and (abs(y) >= eps):

x = x - y/( fprime(x))
y = f(x)
i += 1

if i== Nmax:
[Link]("Nombre maximal d’itérations atteint.")

return x

1.3 Méthode de la sécante

La méthode de Newton utilise une approximation de la fonction par sa droite tan-
gente en un point, ce qui implique le calcul de la dérivée f 0 . Or, dans plusieurs si-
tuations pratiques, la fonction f peut être compliquée et on peut ne pas avoir une
formule explicite pour sa dérivée. La méthode de la sécante propose de remplacer la
droite tangente par une droite sécante en deux points.
Plus précisément, on suppose que l’on dispose de deux approximations xn−1 et xn
d’une solution x∗ de f (x∗ ) = 0. On approche f au voisinage des points xn−1 et xn par la
droite sécante à f en xn−1 et xn , c’est-à-dire la droite d’équation
f (xn ) − f (xn−1 )
y = f (xn ) + (x − xn ).
xn − xn−1
On utilise cette équation de la droite sécante pour trouver une nouvelle approximation
xn+1 de x∗ : on résout
f (xn ) − f (xn−1 )
f (xn ) + (xn+1 − xn ) = 0,
xn − xn−1
ce qui donne
xn − xn−1
xn+1 = xn − f (xn ) .
f (xn ) − f (xn−1 )
Une illustration de la méthode de la sécante est donnée dans la Figure 2.
Les résultats théoriques pour la méthode de la sécante sont très similaires à ceux
de la méthode de Newton, la différence principale étant l’ordre de convergence : pour
des conditions initiales x0 , x1 proches de x∗ , l’erreur εn = |xn − x∗ | satisfait
√
5+1
εn+1 ≤ Mεn 2 (6)

5
 xn+1
xn−1 xn xn+2

Figure 2 – Illustration de la méthode de la secante pour le calcul de xn+1 et xn+2 .

pour une constante M > 0.

La méthode de la sécante partage plusieurs inconvénients avec la méthode de New-
ton, notamment le fait qu’il faut choisir des conditions initiales “proches” du zéro x∗
et que la fonction f doit être de classe C1 (C2 pour l’estimée de l’erreur (6)). Sa conver-
gence
√
n’est pas aussi rapide que celle de Newton (on a remplacé le facteur 2 de (5) par
5+1
2 ≈ 1,618), mais elle est encore beaucoup plus rapide que la méthode de dichoto-
mie. Elle est utile pour des cas où la méthode de Newton s’appliquerait mais le calcul
de la dérivée f 0 devient trop couteux.
Le code suivant donne une implémentation de la méthode de la sécante en Python.
import warnings

def secante(x0 , x1 , f, Nmax , eps ):

i = 0
y0 = f(x0)
y1 = f(x1)

while(i < Nmax) and (abs(y1) >= eps):

x = x1 - y1 * (x1 - x0)/(y1 - y0)
y = f(x)

x0 = x1
x1 = x

y0 = y1
y1 = y

i += 1

if i== Nmax:
[Link]("Nombre maximal d’itérations atteint.")

return x