Recherche de zéro

Alessandro Torcini et Andreas Honecker

LPTM
Université de Cergy-Pontoise

Recherche de zéro – p. 1
Recherche de zéro
Dans beaucoup des contextes il faut résoudre des équations non-linéaires et s’ils n’ont
pas de solution analytique, on a encore une fois besoin de méthodes numeriques.
Supposons d’abord que nous avons une fonction f : R → R et nous cherchons un ou
plusieurs zéros x0 :
f (x0 ) = 0 (1)

En premier lieu, il faut qu’on connait quelques propriétés de la fonction f .

1. L’équation (1) peut avoir pas du solution, une solution ou

plusieurs solutions.
2. Si l’équation a plusieurs solutions, le(s)quelle(s) cherchons-
nous ? Peut-être on peut répondre qu’on prend toutes, mais
l’équation sin x = 0 a des solutions xn = π n avec n ∈ Z et
il est impossible de les trouver tous de manière numérique.
3. Même si l’équation (1) a seulement une solution, les
conditions initiales peuvent jouer une rôle importante pour
la recherche de zéro. Bref, si vous ne connaissez pas la
fonction f très bien, il faudra mieux commencer avec une
trace de f .

Recherche de zéro – p. 2
Recherche de zéro par dichotomie

Supposons que nous avons a0 < b0 ∈ R avec f (a0 ) < 0 et f (b0 ) > 0. Si la fonction f
est continue sur l’intervalle [a0 , b0 ] nous savons que la function f (x) au moins un zéro
dans cet intervalle
f

m1 = b2

0
[ [ ] ] x
a0 m0 = a1 = a2 b0 = b1

La condition de continuité est nécessaire pour assurer cette conclusion. Prenons par
exemple la fonction f (x) = 1/x. f (−1) = −1 < 0 et f (1) = 1 > 0, mais f (x) n’a pas de
zéro dans l’intervalle [−1, 1], seulement une singularité à x = 0

Recherche de zéro – p. 3
Recherche de zéro par dichotomie
f

Nous voulons trouver le zéro de la fonction

m1 = b2
avec une certaine précision requise, par
[ [ ] ]
0 a0 m0 = a1 = a2 b0 = b1 x
exemple :
ε = 10−9

Maintenant on peut répéter les règles suivantes :

1. Calculer la moyenne
an + b n
mn = .
2

2. Quand f (mn ) > 0, on prend an+1 = an , bn+1 = mn , soit on remplace b.

3. Quand f (mn ) < 0, on prend an+1 = mn , bn+1 = bn , soit on remplace a.
4. Si |f (mn )| ≤ ε on peut terminer, autrement le processus peut redémarrer à
partir du point 1

Recherche de zéro – p. 4
Recherche de zéro par dichotomie

Ces règles définissent la méthode de dichotomie.

Pendant chaque pas, on prend la moitié d’intervalle, même si c’est pas très vite, on
gagne d’information sur la position d’un zéro de f : après n pas, la longueur d’intervalle
[an , bn ] est
b 0 − a0
b n − an = .
2n

Donc la précision requise ε = 10−K est atteinte en m étapes,

K K
m≃ = = 3.32K
log10 (2) 0.301

si |b0 − a0 | ∼ O(1).
Démonstration
Si
b 0 − a0 −K
b m − am = = ε = 10
2m
alors
−K = log10 (b0 − a0 ) − m log10 (2) ≃ −m log10 (2)

Recherche de zéro – p. 5
Recherche de zéro par dichotomie

Exercice :
Prenez la fonction
f (x) := x2 − 2 .

Créez d’abord une trace de la fonction f (x). Vérifiez que f a un zéro dans l’intervalle
[a0 , b0 ] = [0, 2]. Évaluez le nombre d’itérations m nécessaires pour atteindre la précision
requise ε = 10−K avec K = 3, 6, 9, 12, enfin comparez votre résultat avec le résultat
√
exact 2.

Recherche de zéro – p. 6
Recherche de zéro par dichotomie
import numpy as np # importer le module NumPy comme "np"
def f(x):
return x*x-2 # la fonction

prec=1.e-4 # précision 10ˆ(-K)

a = 0 # intervalle initiale
b = 2
if f(a) < 0 and f(b) > 0: #f(0)=-2 et f(2)=2, nous avons un zero dans [0,2]
print "l’intervalle est bon", "precision =", prec

for n in range(0,200): # 200 iterations

m = 0.5*(a+b)
if f(m) < 0: # dichotomie :
a = m # remplacer a si f(m) < 0
else:
b = m # autrement remplacer b
dd=abs(b-a)
if dd < prec:
print "Nombre d’itérations pour atteindre la précision = ",n
break
Recherche de zéro – p. 7
Méthode de la sécante
La méthode de dichotomie est lente. En plus, on peut seulement utiliser cette méthode
quand on connait des points a0 et b0 où les signes de f (a0 ) et f (b0 ) sont différents.

La méthode de la sécante est très anciennne (env. 2000 av. J.C). . Cela vien du papyrus
Rhind, qui est un célèbre papyrus de la deuxième période intermédiaire qui a été écrit
par le scribe Ahmès. Depuis 1865 il est conservé au British Museum (à Londres). Il est
une des sources les plus importantes concernant les mathématiques dans l’Égypte
antique.

Papakonstantinou, J. M., & Tapia, R. A. (2013). Origin and

evolution of the secant method in one dimension. American
Mathematical Monthly, 120(6), 500-517.
Recherche de zéro – p. 8
Méthode de la sécante

La méthode de la sécante,suppose que f (x) est presque linéaire dans l’intervalle

[xn−1 , xn ]. Étant donnés xn−1 et xn ] on construit la droite passant par
(xn−1 , f (xn−1 )) et (xn , f (xn )) (la sécante de la courbe) pour trouver l’intersection
avec l’axe zéro de la sécante : xn+1 .
xn+1 représente l’approximation du zéro de la fonction f (x)

(x0 , x1 ) → x2 (x1 , x2 ) → x3 (x2 , x3 ) → x4

Recherche de zéro – p. 9
Méthode de la sécante
Pour être plus précis, la sécante est donnée par

f (xn ) − f (xn−1 )
sf (x) = f (xn ) + (x − xn )
xn − xn−1

et la solution de sf (xn+1 ) = 0 la relation de récurrence :

f (xn ) xn−1 − f (xn−1 ) xn

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

L’initialisation nécessite deux points x0 et x1 , proches, si possible, de la solution

recherchée. Il n’est pas nécessaire, contrairement à la méthode de dichotomie, que x0
et x1 encadrent une racine de f .

Exercice : Cherchez encore une fois la racine da la fonction

f (x) := x2 − 2 .

Essayez l’intervalle [x0 , x1 ] = [0, 2] et faites au plus 10 itérations de la méthode de la

√
sécante et affichez xn . Comparez x10 avec le résultat numérique de 2.

Recherche de zéro – p. 10
Méthode de la sécante
import numpy as np # importer le module NumPy comme "np"
def f(x):
return float(x*x-2) # la fonction (assurer flottantes !)

xvieux, xactuel = 0, 2

n = 0
while n<10 and xactuel != xvieux: # 10 iterations maximum
# ... et terminer quand xactuel=xvieux
print "x(", n, ") =", xactuel
fvieux = f(xvieux) # f(x(n-1)) - x(n-1) est dans xvieux
factuel = f(xactuel) # f(x(n)) - x(n) est dans xactuel
# formule pour x(n+1):
xnouveau = (factuel*xvieux-fvieux*xactuel)/(factuel-fvieux)
xvieux = xactuel # stocker x(n) dans xvieux
xactuel = xnouveau # et x(n+1) dans xactuel
n += 1 # prochaine iteration

print "x(", n, ") =", xactuel

r2 = [Link](2)
Recherche de zéro – p. 11
Méthode de la sécante

Évidemment, la méthode de la sécante est très vite quand elle converge, mais elle ne
converge pas toujours, même s’il y’a un zéro dans l’intervalle [x0 , x1 ].
Exercice : Cherchez la racine de la fonction

f (x) := x exp(−x2 ) .

Essayez les intervalles [x0 , x1 ] = [0, 2], [−1, 1] et [−1, 3]. Faites toujours au plus 10
itérations de la la méthode de la sécante et affichez xn .

Recherche de zéro – p. 12
Méthode de Newton-Raphson

La méthode de résolution des équations

numériques a été initiée par Isaac Newton vers
1669 sur des exemples numériques mais la
formulation était assez compliqué.

1. En 1680, Joseph Raphson met en évidence une formule de récurrence.

2. Un siècle plus tard, Mouraille et Lagrange étudient la convergence des
approximations successives en fonction des conditions initiales par une
approche géométrique.
3. Cinquante ans plus tard, Fourier et Cauchy s’occupe de la rapidité de la
convergence.

Recherche de zéro – p. 13
Méthode de Newton-Raphson

Si on prend la limite xn−1 → xn de

la méthode de la sécante, on arrive à la
méthode de Newton-Raphson.

La sécante passant pour les deux points (xn−1 , f (xn−1 ) et (xn , f (xn )) est donnée par

f (xn ) − f (xn−1 )
sf (x) = f (xn ) + (x − xn )
xn − xn−1

si on prend la limite xn−1 → xn de le coefficient directeur de sf (x) on obtient le dérivé

in xn
f (xn ) − f (xn−1 ) df
lim = (xn ) = f ′ (xn )
xn−1 →xn xn − xn−1 dx
et donc
lim sf (x) −→ tf (x) = f (xn ) + (x − xn ) f ′ (xn )
xn−1 →xn

au lieu de la sécante, on utilise la tangente au point xn

Recherche de zéro – p. 14
Méthode de Newton-Raphson

1. L’équation de la tangente en xn est

tf (x) = f (xn ) + (x − xn ) f ′ (xn )
2. xn+1 est l’abscisse du point
d’intersection de la tangente tf en
xn avec l’axe des abscisses.
3. Cette tangente coupe l’axe des abscisse
quand tf (xn+1 ) = 0
4. f (xn ) + (xn+1 − xn ) f ′ (xn ) = 0 =⇒
(xn+1 − xn ) f ′ (xn ) = −f (xn )
f (x )
5. (xn+1 − xn ) = − f ′ (xn )
n

On a donc la relation de récurrence suivante :

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

Recherche de zéro – p. 15
Méthode de Newton-Raphson

La méthode consiste à introduire une suite

{xn } d’approximation successives de l’équation
f (x) = 0

1. On part d’un x0 proche de la solution.

2. À partir de x0 , on calcule un nouveau
terme x1 de la manière suivante : on
trace la tangente à f en x0 . Cette
tangente coupe l’axe des abscisses en
x1 comme indiqué sur le figure.
3. On réitère ce procédé en calculant x2 en
remplaçant x0 par x1
4. puis x3 en remplaçant x1 par x2 et ainsi
de suite . . .

Recherche de zéro – p. 16
Conditions d’application

Pour que la suite {xn } existe :

1. La fonction f doit être dérivable en chacun des points considérés. En pratique la

fonction doit être dérivable dans un intervalle centré en α (la solution) et
contenant x0
2. La dérivée ne doit pas s’annuler sur cet intervalle.
3. En pratique, il faut prendre un x0 assez proche de la valeur α qui annule la
fonction.

Avantages et inconvénients de la méthode

1. Un avantage de cette méthode est qu’un seul point xn suffit.

2. En revanche il nous faut maintenant une expression analytique de la dérivée de
f ′ (x) (en principe, on peut utiliser une dérivation numérique, mais si on fait ça,
on revient à une version de la méthode de la sécante).

Recherche de zéro – p. 17
Algorithme

1. Lorsque la suite converge, elle converge de façon quadratique c’est à dire que le
nombre de chiffres significatifs double à chaque itération
2. Si l’on s’en tient à une précision inférieure à 10−15 (double pécision -
représentation des flottantes en Python) , la suite doit alors converger en moins
de 10 itérations
3. On pourra mettre une condition d’arrêt de l’algorithme lorsque le nombre de
boucle dépassera 10 car alors la suite ne converge pas. Il faudra alors prendre
un x0 plus proche de α
4. On prendra comme critère d’arrêt pour une précision de p :

f (xn ) −p
|xn − xn+1 | = < 10
f ′ (xn )

5. Pour utiliser cet algorithme, il faudra calculer la fonction dérivée f ′

2
Exercice : Cherchez encore une fois la racine de la fonction f (x) = xe−x mais
maintenant avec la méthode de Newton-Raphson. Essayez x0 = 0.4, 0.5 et 0.6. Faites
toujours 10 itérations.

Recherche de zéro – p. 18
La méthode Newton-Raphson

import numpy as np # importer le module NumPy comme "np"

def f(x): # la fonction

return x*[Link](-x*x)

def df(x): # et sa derivee

return (1-2*x*x)*[Link](-x*x)

x = 0.4 # le debut de la recherche

precision = 1.e-4 # Précision requise
n, diff=0 , 33.

while n<10 and diff > precision: # 10 iterations maximum

pas = f(x)/df(x) # L’incrément
x -= pas # iteration
diff=abs(pas)
print "x(", n, ") =", x, " L’incrément ", diff # afficher x(n)
n += 1

print "resultat final : ", x

Recherche de zéro – p. 19
Un exemple

Prenons l’exemple historique qu’avait pris Newton pour expliquer sa méthode :

Déterminer une approximation de la solution de :

x3 − 2x − 5 = 0

1. On pose la fonction f (x) = x3 − 2x − 5

2. La fonction f est dérivable (car polynôme) et : f ′ (x) = 3x2 − 2
2
3. La dérivée est nulle in f ′ (x) = 3x2 − 2 = 0 =⇒ x2 = 3
q
=⇒ x = ± 23 ≃ ±0.816
4. On obtient le tableau de variation suivant :

Recherche de zéro – p. 20
Un exemple

q
1. Si x ∈] − ∞; + 32 [ , alors f (x) < 0. La fonction ne peut s’annuler.
q
2. Si x ∈ [+ 23 ; +∞[ la fonction f est continue (car dérivable), monotone et
f (x) ∈ [−6.089; +∞[ et donc il existe un unique solution ou f (α) = 0
3. On peut affiner l’intervalle de α : f (2) = −1 et f (3) = 16 donc α ∈ [2; 3]

La fonction f ne s’annule qu’une seule fois et la solution α ∈ [2; 3]

Recherche de zéro – p. 21
Un exemple

1. On peut utiliser pour x0 soit 2 soit 3, mais f (2) est plus proche de 0, sa
convergence est plus rapide.
2. Si l’on effectue l’algorithme à la main, on a le tableau suivant pour une précision
de 10−3
3. On s’aperçoit de la redoutable efficacité de cet algorithme car en deux termes il
arrive à une précision de 10−3

On peut comparer cet algorithme avec l’algorithme de dichotomie à l’aide du nombre de

boucles que le programme effectue pour une précision donné.

Recherche de zéro – p. 22
Méthode de Newton-Raphson pour systèmes

Supposons que nous cherchons la solution simultanée de N équations non-linéaires

dans N variables, donc la solution du système suivante



 F1 (x1 , x2 , x3 , . . . , xN ) = 0


 F (x , x , x , . . . , x ) = 0
2 1 2 3 N


 ...


 F (x , x , x , . . . , x ) = 0
N 1 2 3 N

La méthode de Newton-Raphson se généralise facilement aN variables. Si on regroupe

~ et ~
les équations Fi et les variables xj , i, j = 1, 2, . . . N dans des vecteurs F x, nous
pouvons réécrire le système comme :

~ (~
F x) = 0

On peux d’abord étendre la fonction F~ (~

x) au premier ordre avec la série de Taylor
T~F (~
x) = F~ (~
xn ) + JF (~
xn ) (~
x−~xn )

où la tangente a été remplacé par le vecteur T~F (~

x) et le dérivé par la matrice
jacobienne JF
Recherche de zéro – p. 23
Méthode de Newton-Raphson pour systèmes

~ est
La matrice jacobienne de F

∂ F1 ∂ F1
 
∂x1
··· ∂xN
. .. .
 
JF =
 . . . .

 . . 
∂ FN ∂ FN
∂x1
··· ∂xN

Après on peut résoudre l’équation T~F (~

xn+1 ) = 0 et on arrive à la récurrence suivante

~ xn − JF−1 (~
xn+1 = ~ ~ (~
xn ) F xn ) .

Cette équation est très semblable à celui pour la fonction scalaire, mais maintenant il
s’agit de vecteurs et de matrices
Nous avons besoin de trouver l’inverse d’une matrice, nous avons besoin de l’algèbre
linéaire en Python

Recherche de zéro – p. 24
Algèbre linéaire en Python

x = ~b :
Je le fais avec un exemple d’un système linéaire de type A ~
      
x1 1 2 x 5
A =   1 =   .
x2 3 4 x2 6

Nous cherchons les solutions du système

   
x 5
 1  = A−1   .
x2 6

Nous utilisons encore une fois le module NumPy et traitons la matrice A et le vecteur ~b
comme des array, C’est très facile avec Python

Recherche de zéro – p. 25
Algèbre linéaire en Python

import numpy as np
A = [Link]([[1,2],[3,4]]) # une matrice
b = [Link]([5,6]) # un vecteur
print "A*b =", [Link](b) # A*b
Ainv = [Link](A) # calculer l’inverse d’A
print "Aˆ{-1} =", Ainv
x = [Link](b)

print "solution de A*x=b :", x # la solution de A*x=b

Les éléments du code ci-dessus sont :

1. A1 .dot(A2 ) calcule le produit des deux array Ai ; ici c’est le produit d’une
matrice et un vecteur.
2. La fonction [Link](A) calcule l’inverse A−1 d’une matrice A.
D’abord, la notation des array est très similaire à des listes (ou des listes de listes). En
particulier b[0] vous rend le premier élément b1 de ~b et A[1][0] vous rend l’élément
A2,1 (rappel : en Python on commence à compter avec 0).

Recherche de zéro – p. 26
Un exemple bidimensionnel

Exercice : Cherchez les trois racines de deux équations suivantes :


 x3 − 3 x y 2 − 1 = 0
 3 x2 y − y 3 = 0

Utilisez la méthode de Newton-Raphson et faites toujours 10 itérations. Essayez

plusieurs points (x0 , y0 ) pour commencer la recherche.

Recherche de zéro – p. 27
La méthode Newton-Raphson en 2 dimensions

import numpy as np # importer le module NumPy comme "np"

def F(xv): # la fonction

x, y = xv[0], xv[1] # les deux coordonnees
return [Link]([x**3-3*x*y**2-1,3*x**2*y-y**3])

def JF(xv): # et sa derivee, soit la matrice jacobienne

x, y = xv[0], xv[1] # les deux coordonnees
return [Link]([[3*x*x-3*y*y,-6*x*y],[6*x*y,3*x*x-3*y*y]])

precision=1.e-3
x = [Link]([8.0,0]) # le point pour demarrer la recherche

Recherche de zéro – p. 28
La méthode Newton-Raphson en 2 dimensions

n, pas2 = 0, 4e4
# 10 iterations maximum et on peut s’arreter quand on ne fait plus des pas
while n<10 and pas2 > precision:
print "x(", n, ") =", x, "pas2",pas2 # afficher x(n)
# le pas (notez le produit de l’inverse de la matrice avec la "fonction")
pas = [Link](JF(x)).dot(F(x))
x -= pas # iteration
pas2 = [Link]([Link](pas))
# pas2 est la racine carrée de||pas||ˆ2,
# soit le module du produit scalaire de pas avec soi-meme
n += 1

print "resultat final : ", x

Recherche de zéro – p. 29