YIHS FATIMA ZAHRA MPSI
Chapitre 14 : Résolution numérique des équations
f(x) = 0
Nous nous intéresserons dans ce cours à la recherche des zéros d’une fonction réelle d’une variable réelle.
Autrement dit, étant donné un intervalle I de R et une application ∶ I → R, on cherche à trouver un réel
∈ tel que ( ) = (s’il en existe).
Le but de ce cours est de trouver une solution approchée à ce problème dans le cadre où la théorie nous assure
qu’une telle solution existe, ceci tout en minimisant le temps d’exécution, mais en obtenant quand même une
bonne approximation.
I. Principe général :
Toutes les méthodes que nous allons voir dans ce cours sont des méthodes itératives. Elles consistent en la
construction d’une suite de valeurs ( )( ∈ ) qui converge vers l’un des zéros de la fonction f.
Pour l’utilisation pratique de telles méthodes itératives, il faut introduire un critère d’arrêt pour interrompre le
processus itératif lorsque l’approximation du zéro de la fonction par la valeur est jugée satisfaisante.
Pour cela, plusieurs choix sont possibles :
imposer un nombre maximal d’itérations > 0 à ne pas dépasser : on s’arrête lorsque le nombre
des itérations devient > .
imposer une tolérance > 0 sur la largeur de l’intervalle de recherche a, b : on s’arrête lorsque
| − | ≤ ".
imposer une tolérance > 0 sur l’écart entre deux solutions successives : on s’arrête lorsque
| $%&' − $% | ≤ ".
imposer une tolérance > 0 sur le résidu : on s’arrête lorsque | ($% ) | ≤ ".
II. Dichotomie :
1) Principe :
Nous considérons une fonction f continue sur un intervalle
, telle que f(a) et f(b) soient de signes opposés, ce qui se
traduit par la relation : ( ) ( ) ≤
Le théorème des valeurs intermédiaires nous assure qu’il
existe au moins un réel ( ∈ , ) tel que (() = 0
Le principe de la recherche dichotomique consiste à découper en deux l’intervalle de recherche. On calcule
+&,
donc * -
., et suivant le signe de cette quantité l’une des deux relations est nécessairement vérifiée :
CPGE Agadir Page 1
YIHS FATIMA ZAHRA MPSI
& &
• ( ) * .≤ ce qui assure l’existence d’une racine dans 0 , 1
/ /
& &
• ( ) * .≤ ce qui assure l’existence d’une racine dans 0 , 1
/ /
Ceci ramenant, dans les deux cas, la recherche à un intervalle d’amplitude
divisé sur deux.
On procède alors ainsi par itération en encadrant de plus en plus finement
une racine.
2) Implémentation :
En utilisant comme critère d’arrêt la largeur de l’intervalle de recherche , , et on renvoie une valeur
dans le dernier intervalle obtenu (ici on renvoie la valeur au milieu) :
def dicho(f, a, b, e) : def dicho(f, a, b, e) :
if f(a)*f(b) > 0 : if f(a)*f(b) > 0 :
return "condition non vérifiée" return "condition non vérifiée"
while abs(b – a) > e : if abs(b – a) <= e :
m = (a + b) / 2 return (a + b) / 2
if f(a) * f(m) <= 0 : m = (a + b) / 2
b=m if f(a) * f(m) <= 0 :
else : return dicho(f, a, m, e)
a=m else :
return (a + b) / 2 return dicho(f, m, b, e)
En ajoutant au critère d’arrêt précédant un nombre maximal d’itérations imax à ne pas dépasser :
def dicho(f, a, b, e, imax) :
def dicho(f, a, b, e, i = 0) :
if f(a)*f(b) > 0 :
if f(a)*f(b) > 0 :
return "condition non vérifiée"
return "condition non vérifiée"
i=0
if abs(b – a) <= e or i >= imax :
while abs(b – a) > e and i < imax :
return (a + b) / 2
m, i = (a + b) / 2, i + 1
m = (a + b) / 2
if f(a) * f(m) <= 0 :
if f(a) * f(m) <= 0 :
b=m
else : return dicho(f, a, m, e, i + 1)
a=m else :
return dicho(f, m, b, e, i + 1)
return (a + b) / 2
3) Conclusion :
Points forts : c’est une méthode simple qui offre une garantie de convergence vers une solution approchée qui
est à une distance précise de la solution réelle.
Points faibles : elle nécessite un encadrement préalable du zéro (l’intervalle , avec ( ) ( ) < 0), et
sa vitesse de convergence est lente par rapport à d’autres méthodes.
CPGE Agadir Page 2
YIHS FATIMA ZAHRA MPSI
III. Newton :
1) Principe :
La méthode de Newton consiste à approcher la courbe d’une fonction continue : , ) → 4 par sa tangente
en un point initial $ ∈ , choisi arbitrairement.
La tangente de la fonction au point 5 est donnée par l’équation :
8 ($
6 = ($ ) + )( $ – $ )
On détermine l’abscisse $' du point d’intersection de cette
tangente avec l’axe des abscisses (le point ( : , 0)).
Soit donc :
8(
($ )
0 = ( 5) + 5 )( : − 5) ⇔ $' = $ − 8 ($)
On procède alors ainsi par itération, chaque fois :
On trace la tangente au dernier point trouvé < = , ( = )>
On détermine l’abscisse =&: du point d’intersection de
cette tangente avec l’axe des abscisses :
($? )
$?&' = $? − 8 ($ )
?
Et donc, en plus de la fonction f, on a besoin de sa dérivée (df).
2) Implémentation :
On utilise par exemple comme critère d’arrêt l’écart entre deux solutions successives :
def newton(f, df, x0, e) :
if df(x0) == 0 : def newton(f, df, x0, e) :
return " Dérivée nulle ! " if df(x0) == 0 :
x1 = x0 – f(x0) / df(x0) return " Dérivée nulle ! "
while abs(x0 – x1) > e : x1 = x0 – f(x0) / df(x0)
if df(x0) == 0 : if abs(x0 – x1) <= e :
return "Dérivée nulle ! " return x1
x0 = x1 else:
x1 = x0 – f(x0) / df(x0) return newton(f, df, x1, e)
return x1
3) Dérivation numérique :
La méthode de Newton nécessite la connaissance de la dérivée de la fonction f en jeu.
Dans certains contextes, la fonction dérivée est connue a priori, dans d’autres, on doit calculer une
approximation de cette dérivée en fonction de f en utilisant les formules de Taylor-Young.
CPGE Agadir Page 3
YIHS FATIMA ZAHRA MPSI
Par exemple, pour un réel h > 0 très petit (très proche de 0) :
8(
( = + ℎ) = ( = ) + ℎ =) + A(ℎ- )
Ainsi, la dérivée peut être approximée par la valeur :
8(
( = + ℎ) − ( = )
=) =
ℎ
Ainsi, la fonction newton() devient :
def newton(f, x0, e, h) :
g = (f(x0 + h) – f(x0)) / h
x1 = x0 – f(x0) / g
while abs(x1 – x0) > e :
x0 = x1
g = (f(x0 + h) – f(x0)) / h
x1 = x0 – f(x0) / g
return x1
4) Conclusion :
Points forts : Si elle converge, elle converge rapidement
Points faibles :
On peut rencontrer des divisions par zéro (dérivée nulle en un point $? )
La terminaison n’est pas assurée (le critère d’arrêt jamais vérifié) dans ce cas on peut imposer un
nombre maximal d’itérations pour arrêter l’exécution.
La convergence est non garantie : même si un résultat est renvoyé, il peut être éloigné d’un zéro de f !
IV. Sécante :
1) Principe :
On partant de deux points différents <$ , ($ )> et <$' , ($' )>
la méthode de la sécante consiste à tracer la droite reliant ces
deux points, et à remplacer l’ancien point calculé < 5 , ( 5 )>
par le point < - , ( - )>, dont l’abscisse - est l’abscisse du
point d’intersection de cette droite avec l’axe des abscisses.
La corde en question a pour équation :
( :) − ( 5)
D = ( − :) + ( :)
:− 5
Le point ( - , 0), intersection de l’axe des abscisses avec la corde reliant < 5 , ( 5 )> et < : , ( : )> vérifie :
( :) − ( 5) $' − $
0 = ( - − :) + ( :) ⇔ $ / = $' − ($' )
:− 5 ($' ) − ($ )
CPGE Agadir Page 4
YIHS FATIMA ZAHRA MPSI
On procède alors ainsi par itération : chaque fois on détermine
l’abscisse =&: du point d’intersection de la corde reliant les deux
derniers points calculés < =E: , ( =E: )> et < = , ( = )> et de l’axe
des abscisses :
$? − $?E'
$?&' = $? − ($? )
($? ) − ($?E' )
La méthode de la sécante est donc équivalente à la méthode de newton, en approximant la dérivée en = par :
8 ($
($? ) − ($?E' )
?) ≈
$? − $?E'
2) Implémentation :
On utilise comme critère d’arrêt l’écart entre deux solutions successives (selon une tolérance e) :
3) Conclusion :
Points forts :
Si elle converge, elle converge rapidement
Facilité d’expression (ne nécessite pas la dérivée contrairement à la méthode de Newton)
Points faibles :
La terminaison n’est pas assurée (le critère d’arrêt jamais vérifié) dans ce cas on peut imposer un
nombre maximal d’itérations pour arrêter l’exécution.
La convergence est non garantie : la corde peut être parallèle à l’axe des abscisses, dans ce cas il n’y a
pas de point d’intersection.
V. Fausse position (Regula Falsi)
1) Principe :
Soit une fonction continue ∶ , ) → 4 telle que ( ) ()) ≤ 0, Le principe de cette méthode est le même
que celui de la méthode dichotomie sauf qu’au lieu de calculer le point milieu, on calcule l’abscisse « m » du
point d’intersection de la corde reliant les points de coordonnées ( , ( )) et ( , ( )) avec l’axe des
abscisses.
CPGE Agadir Page 5
YIHS FATIMA ZAHRA MPSI
La corde (droite) en question a pour équation :
()) − ( )
D = ( − ) + ( )
)−
Donc l’abscisse m du point d’intersection vérifie :
()) − ( )
0 = ( − )+ ( )
)−
− ( )− ( )
⇔ G= − ( ) =
( )− ( ) ( )− ( )
Certainement on aura l’une des deux conditions vérifiée :
• ( ) (G) ≤ ce qui assure l’existence d’une racine dans l’intervalle ,G
• ( ) (G) ≤ ce qui assure l’existence d’une racine dans l’intervalle G ,
On recommence alors la même procédure avec le nouvel intervalle de taille moins grande, tant qu’un critère
d’arrêt n’est pas vérifié.
2) Implémentation :
En utilisant par exemple comme critère d’arrêt une tolérance > 0 sur le résidu : on s’arrête
lorsque | ( = ) | ≤ et on retourne ce =
3) Conclusion :
Points forts :
Elle offre une garantie de convergence comme la méthode de dichotomie
Converge généralement plus rapidement que la méthode de la dichotomie
Points faibles :
Nécessite un encadrement préalable du zéro (l’intervalle , avec ( ) ( ) < 0)
CPGE Agadir Page 6
