Résolution numérique des équations non

linéaires

Ibrahim Trabelsi
février 2021

Cours - Analyse Numérique - 2 IM - février 2021 1 / 15

Introduction Dichotomie Point fixe Newton

Plan

1 Introduction

2 La méthode de dichotomie ou méthode de la bissection

3 La méthode du point fixe

4 La méthode de Newton

Cours - Analyse Numérique - 2 IM - février 2021 2 / 15

Introduction Dichotomie Point fixe Newton

Introduction

- Soit f (x ) = x 2 − 3x + 2.
- Résoudre f (x ) = 0 ⇒ x = 1 ou √
x =2 f (x )
x 3
- Soit g (x ) = 2 − sin(x ) + 6 − 2
π

- Résoudre g (x ) = 0 ⇒ x =?
- Pas de solution analytique! Quoi faire?
- Utiliser des méthodes numériques,
x
généralement itératives, qui consistent à
1 2α
construire une suite (xn ) qui converge
vers la solution α telle que g (α) = 0

Cours - Analyse Numérique - 2 IM - février 2021 3 / 15

Introduction Dichotomie Point fixe Newton

Définition
Une méthode itérative est d’ordre p, pour la recherche d’un
zéro α de f si la suite (xn ) converge vers α et si

| xn + 1 − α |
lim =M
n→+∞ |xn − α |p

Cours - Analyse Numérique - 2 IM - février 2021 4 / 15

Introduction Dichotomie Point fixe Newton

La méthode de dichotomie

Théorème des valeurs intermédiaires

Soit f une fonction définie et continue sur un segment [a, b ] de
R. Si f (a).f (b ) < 0, alors il existe α ∈ [a, b ] tel que f (α) = 0.
- Choisir in intervalle [a0 , b0 ] tel que f (x )
f (a0 )f (b0 ) < 0.
- Calculer xk = bk +2 ak f ( b0 )
- Si f (ak )f (xk ) < 0 alors ak +1 = ak et
bk +1 = xk x1 x0
- Si f (xk )f (bk ) < 0 alors ak +1 = xk et f ( x0 ) x
bk +1 = bk a0 α b0
f ( a0 ) a1 b1
- Jusqu’à |bk − ak | < ε

Cours - Analyse Numérique - 2 IM - février 2021 5 / 15

Introduction Dichotomie Point fixe Newton

La méthode de dichotomie

Théorème des valeurs intermédiaires

Soit f une fonction définie et continue sur un segment [a, b ] de
R. Si f (a).f (b ) < 0, alors il existe α ∈ [a, b ] tel que f (α) = 0.
- Choisir in intervalle [a0 , b0 ] tel que f (x )
f (a0 )f (b0 ) < 0.
- Calculer xk = bk +2 ak f ( b0 )
- Si f (ak )f (xk ) < 0 alors ak +1 = ak et
bk +1 = xk x1 x0
- Si f (xk )f (bk ) < 0 alors ak +1 = xk et f ( x0 ) x
bk +1 = bk a0 α b0
f ( a0 ) a1 b1
- Jusqu’à |bk − ak | < ε

Cours - Analyse Numérique - 2 IM - février 2021 5 / 15

Introduction Dichotomie Point fixe Newton

La méthode de dichotomie

Théorème des valeurs intermédiaires

Soit f une fonction définie et continue sur un segment [a, b ] de
R. Si f (a).f (b ) < 0, alors il existe α ∈ [a, b ] tel que f (α) = 0.
- Choisir in intervalle [a0 , b0 ] tel que f (x )
f (a0 )f (b0 ) < 0.
- Calculer xk = bk +2 ak f ( b0 )
- Si f (ak )f (xk ) < 0 alors ak +1 = ak et
bk +1 = xk x1 x0
- Si f (xk )f (bk ) < 0 alors ak +1 = xk et f ( x0 ) x
bk +1 = bk a0 α b0
f ( a0 ) a1 b1
- Jusqu’à |bk − ak | < ε

Cours - Analyse Numérique - 2 IM - février 2021 5 / 15

Introduction Dichotomie Point fixe Newton

La méthode de dichotomie

Théorème des valeurs intermédiaires

Soit f une fonction définie et continue sur un segment [a, b ] de
R. Si f (a).f (b ) < 0, alors il existe α ∈ [a, b ] tel que f (α) = 0.
- Choisir in intervalle [a0 , b0 ] tel que f (x )
f (a0 )f (b0 ) < 0.
- Calculer xk = bk +2 ak f ( b0 )
- Si f (ak )f (xk ) < 0 alors ak +1 = ak et
bk +1 = xk x1 x0
- Si f (xk )f (bk ) < 0 alors ak +1 = xk et f ( x0 ) x
bk +1 = bk a0 α b0
f ( a0 ) a1 b1
- Jusqu’à |bk − ak | < ε

Cours - Analyse Numérique - 2 IM - février 2021 5 / 15

Introduction Dichotomie Point fixe Newton

La méthode de dichotomie

Théorème des valeurs intermédiaires

Soit f une fonction définie et continue sur un segment [a, b ] de
R. Si f (a).f (b ) < 0, alors il existe α ∈ [a, b ] tel que f (α) = 0.
- Choisir in intervalle [a0 , b0 ] tel que f (x )
f (a0 )f (b0 ) < 0.
- Calculer xk = bk +2 ak f ( b0 )
- Si f (ak )f (xk ) < 0 alors ak +1 = ak et
bk +1 = xk x1 x0
- Si f (xk )f (bk ) < 0 alors ak +1 = xk et f ( x0 ) x
bk +1 = bk a0 α b0
f ( a0 ) a1 b1
- Jusqu’à |bk − ak | < ε

Cours - Analyse Numérique - 2 IM - février 2021 5 / 15

Introduction Dichotomie Point fixe Newton

Soit f une fonction numérique donnée, définie et continue sur le

segment [a0 , b0 ]. ε désigne l’erreur absolue tolérée sur la
valeur approchée de la solution xn de l’équation f (x ) = 0.

Algorithm 1: Algorithme dichotomie

Result: α = xn
a0 , b0 , ε et Nmax ;
repeat
xn = an +2 bn ;
if f (an )f (xn ) < 0 then
an+1 = an , bn+1 = xn ;
else
an+1 = xn , bn+1 = bn ;
end
until f (xn ) = 0 ou |xn − an | 6 ε ou n = Nmax ;

Cours - Analyse Numérique - 2 IM - février 2021 6 / 15

Introduction Dichotomie Point fixe Newton

Convergence
La méthode de dichotomie est toujours convergente. Mais cette
convergence est en général assez lente.
Le nombre d’itérations nécessaires n pour la convergence de
l’Algorithme vérifie :

b0 − a0
(n + 1)log2 > log
ε
bn − an 1
⇒ | xn − α | 6 = n (b0 − a0 )
2 2
Application : si b0 − a0 = 1 et ε = 10−5 on a n = 16.

Cours - Analyse Numérique - 2 IM - février 2021 7 / 15

Introduction Dichotomie Point fixe Newton

La méthode du point fixe

Cette méthode consiste à transformer l’équation générale

f (x ) = 0 sous la forme x = g (x ) où g est une fonction à
déterminer.
Par exemple, si f (x ) = x 2 + 2x
√ − 1, on peut choisir :
1 2
g (x ) = 2 (1 − x ) ou g (x ) = 1 − 2x
g (x )

- Choisir in intervalle x0 .
- Calculer xk +1 = g (xk ) g ( x0 )
- Jusqu’à |xk +1 − xk | < ε g ( x1 )
g ( x2 )
α = g (α)
x
α x3 x2 x1x0
Cours - Analyse Numérique - 2 IM - février 2021 8 / 15
Introduction Dichotomie Point fixe Newton

La méthode du point fixe

Cette méthode consiste à transformer l’équation générale

f (x ) = 0 sous la forme x = g (x ) où g est une fonction à
déterminer.
Par exemple, si f (x ) = x 2 + 2x
√ − 1, on peut choisir :
1 2
g (x ) = 2 (1 − x ) ou g (x ) = 1 − 2x
g (x )

- Choisir in intervalle x0 .
- Calculer xk +1 = g (xk ) g ( x0 )
- Jusqu’à |xk +1 − xk | < ε g ( x1 )
g ( x2 )
α = g (α)
x
α x3 x2 x1x0
Cours - Analyse Numérique - 2 IM - février 2021 8 / 15
Introduction Dichotomie Point fixe Newton

La méthode du point fixe

Cette méthode consiste à transformer l’équation générale

f (x ) = 0 sous la forme x = g (x ) où g est une fonction à
déterminer.
Par exemple, si f (x ) = x 2 + 2x
√ − 1, on peut choisir :
1 2
g (x ) = 2 (1 − x ) ou g (x ) = 1 − 2x
g (x )

- Choisir in intervalle x0 .
- Calculer xk +1 = g (xk ) g ( x0 )
- Jusqu’à |xk +1 − xk | < ε g ( x1 )
g ( x2 )
α = g (α)
x
α x3 x2 x1x0
Cours - Analyse Numérique - 2 IM - février 2021 8 / 15
Introduction Dichotomie Point fixe Newton

La méthode du point fixe

Cette méthode consiste à transformer l’équation générale

f (x ) = 0 sous la forme x = g (x ) où g est une fonction à
déterminer.
Par exemple, si f (x ) = x 2 + 2x
√ − 1, on peut choisir :
1 2
g (x ) = 2 (1 − x ) ou g (x ) = 1 − 2x
g (x )

- Choisir in intervalle x0 .
- Calculer xk +1 = g (xk ) g ( x0 )
- Jusqu’à |xk +1 − xk | < ε g ( x1 )
g ( x2 )
α = g (α)
x
α x3 x2 x1x0
Cours - Analyse Numérique - 2 IM - février 2021 8 / 15
Introduction Dichotomie Point fixe Newton

La méthode du point fixe

Cette méthode consiste à transformer l’équation générale

f (x ) = 0 sous la forme x = g (x ) où g est une fonction à
déterminer.
Par exemple, si f (x ) = x 2 + 2x
√ − 1, on peut choisir :
1 2
g (x ) = 2 (1 − x ) ou g (x ) = 1 − 2x
g (x )

- Choisir in intervalle x0 .
- Calculer xk +1 = g (xk ) g ( x0 )
- Jusqu’à |xk +1 − xk | < ε g ( x1 )
g ( x2 )
α = g (α)
x
α x3 x2 x1x0
Cours - Analyse Numérique - 2 IM - février 2021 8 / 15
Introduction Dichotomie Point fixe Newton

Partant d’une estimation initiale x0 de la solution α, on construit

la suite (xn ), avec
xn+1 = g (xn )

Algorithm 2: Algorithme point fixe

Result: α = xn
x0 , ε et Nmax ;
repeat
xn+1 = g (xn );
n = n + 1;
until |xn − xn−1 | 6 ε ou n − 1 = Nmax ;

Cours - Analyse Numérique - 2 IM - février 2021 9 / 15

Introduction Dichotomie Point fixe Newton

Convergence

Théorème
Soit g : [a, b ] → [a, b ] telle que g ([a, b ]) ⊂ [a, b ] et g est une
fonction contractante. (i. e. il existe λ ∈ [0, 1[ tel que :
|g (x ) − g (y )| 6 λ|x − y |, ∀x, y ∈ [a, b ]).
Alors, pour tout choix de x0 ∈ [a, b ], la suite définie par :
xn+1 = g (xn ) converge vers l’unique point fixe α de g.

Corollaire
Le résultat du théorème précédent reste valable si l’on
remplace l’hypothèse “g contractante” par :
- g de classe C 1 sur [a, b ] et
- |g 0 (x )| < 1, ∀x ∈ [a, b ].

Cours - Analyse Numérique - 2 IM - février 2021 10 / 15

Introduction Dichotomie Point fixe Newton

Corollaire
Soit g une fonction numérique admettant un point fixe α.
Supposons que g est continuement dérivable au point α.
Alors :
Si |g 0 (α)| < 1, la méthode du point fixe est localement
convergente, (i.e. il existe un voisinage V de α tel que,
pour tout choix x0 ∈ V , la suite (xn ) définie par
xn+1 = g (xn ) converge vers α.
Si |g 0 (α)| > 1, la méthode du point fixe est divergente pour
tout x0 .
Si |g 0 (x )| = 1 on peut avoir convergence ou divergence.

Cours - Analyse Numérique - 2 IM - février 2021 11 / 15

Introduction Dichotomie Point fixe Newton

Ordre de convergence

Théorème
Soit g une fonction numérique admettant un point fixe α.
Supposons qu’il existe p ∈ N∗ tel que g soit de classe C p au
voisinage de α et que g (p) (α) 6= 0, g (k ) (α) = 0, k 6 p − 1.
Alors : si la méthode du point fixe converge, elle est d’ordre p.
En particulier,
- si g 0 (α) 6= 0, la convergence est d’ordre 1.
- si g 0 (α) = 0 et g 00 (α) 6= 0, la convergence est d’ordre 2.

Cours - Analyse Numérique - 2 IM - février 2021 12 / 15

Introduction Dichotomie Point fixe Newton

La méthode de Newton
Soit f une fonction de classe C 2 dans un voisinage d’une racine
simple α de l’équation f (x ) = 0.
La méthode de Newton consiste à construire, à partir de x0 ,
une suite (xn ) tel que xn+1 est l’intersection de la tangente à la
courbe au point (xn , f (xn )) et l’axe des x. D’où
(x0 , f (x0 ))
f (x )
f (xn )
xn+1 = xn − 0
f ( xn )
- Choisir in intervalle x0 au voisi-
nage de α. (x1 , f (x1 ))
f (x )
- Calculer xk +1 = xk − f 0 (xk )
k x
- Jusqu’à |xk +1 − xk | < ε x2x1 x0
α

Cours - Analyse Numérique - 2 IM - février 2021 13 / 15

Introduction Dichotomie Point fixe Newton

La méthode de Newton
Soit f une fonction de classe C 2 dans un voisinage d’une racine
simple α de l’équation f (x ) = 0.
La méthode de Newton consiste à construire, à partir de x0 ,
une suite (xn ) tel que xn+1 est l’intersection de la tangente à la
courbe au point (xn , f (xn )) et l’axe des x. D’où
(x0 , f (x0 ))
f (x )
f (xn )
xn+1 = xn − 0
f ( xn )
- Choisir in intervalle x0 au voisi-
nage de α. (x1 , f (x1 ))
f (x )
- Calculer xk +1 = xk − f 0 (xk )
k x
- Jusqu’à |xk +1 − xk | < ε x2x1 x0
α

Cours - Analyse Numérique - 2 IM - février 2021 13 / 15

Introduction Dichotomie Point fixe Newton

La méthode de Newton
Soit f une fonction de classe C 2 dans un voisinage d’une racine
simple α de l’équation f (x ) = 0.
La méthode de Newton consiste à construire, à partir de x0 ,
une suite (xn ) tel que xn+1 est l’intersection de la tangente à la
courbe au point (xn , f (xn )) et l’axe des x. D’où
(x0 , f (x0 ))
f (x )
f (xn )
xn+1 = xn − 0
f ( xn )
- Choisir in intervalle x0 au voisi-
nage de α. (x1 , f (x1 ))
f (x )
- Calculer xk +1 = xk − f 0 (xk )
k x
- Jusqu’à |xk +1 − xk | < ε x2x1 x0
α

Cours - Analyse Numérique - 2 IM - février 2021 13 / 15

Introduction Dichotomie Point fixe Newton

La méthode de Newton
Soit f une fonction de classe C 2 dans un voisinage d’une racine
simple α de l’équation f (x ) = 0.
La méthode de Newton consiste à construire, à partir de x0 ,
une suite (xn ) tel que xn+1 est l’intersection de la tangente à la
courbe au point (xn , f (xn )) et l’axe des x. D’où
(x0 , f (x0 ))
f (x )
f (xn )
xn+1 = xn − 0
f ( xn )
- Choisir in intervalle x0 au voisi-
nage de α. (x1 , f (x1 ))
f (x )
- Calculer xk +1 = xk − f 0 (xk )
k x
- Jusqu’à |xk +1 − xk | < ε x2x1 x0
α

Cours - Analyse Numérique - 2 IM - février 2021 13 / 15

Introduction Dichotomie Point fixe Newton

La méthode de Newton
Soit f une fonction de classe C 2 dans un voisinage d’une racine
simple α de l’équation f (x ) = 0.
La méthode de Newton consiste à construire, à partir de x0 ,
une suite (xn ) tel que xn+1 est l’intersection de la tangente à la
courbe au point (xn , f (xn )) et l’axe des x. D’où
(x0 , f (x0 ))
f (x )
f (xn )
xn+1 = xn − 0
f ( xn )
- Choisir in intervalle x0 au voisi-
nage de α. (x1 , f (x1 ))
f (x )
- Calculer xk +1 = xk − f 0 (xk )
k x
- Jusqu’à |xk +1 − xk | < ε x2x1 x0
α

Cours - Analyse Numérique - 2 IM - février 2021 13 / 15

Introduction Dichotomie Point fixe Newton

Partant d’une estimation initiale x0 de la solution α, on construit

la suite (xn ), avec

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

Algorithm 3: Algorithme de Newton

Result: α = xn
x0 , ε et Nmax ;
repeat
if f 0 (xn ) 6= 0 then
f (x )
xn+1 = xn − f 0 (xnn ) ;
end
n = n + 1;
until |xn − xn−1 | 6 ε ou n − 1 = Nmax ;
Cours - Analyse Numérique - 2 IM - février 2021 14 / 15
Introduction Dichotomie Point fixe Newton

Convergence

Théorème
Soit f une fonction de classe C 2 dans un voisinage V d’une
racine simple α de l’équation f (x ) = 0. La méthode de Newton
est localement convergente et est à convergence au moins
quadratique (d’ordre 2).

Cours - Analyse Numérique - 2 IM - février 2021 15 / 15