Introduction Cas scalaire p = 1

EILCO : Analyse Numérique

Chapitre 3 : Résolution Numérique des
Equations
H. Sadok

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1

Plan

1 Introduction
Bibliographie
Introduction

2 Cas scalaire p = 1
Algorithmes de résolution
Méthode de dichotomie
Méthode de Newton
Méthode de la sécante
Etude de la convergence

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Bibliographie Introduction

Bibliographie

Quarteroni, Alfio, Saleri, Fausto

Calcul Scientifique Cours, exercices corrigés et illustrations
en Matlab et Octave
2006, XII, 319 p., Broché
ISBN: 978-88-470-0487-0
S. Guerre-Delabrière et M. Postel, «Méthodes
d’approximation, Equations différentielles, Applications
Scilab», Ellipses, Paris, 2004.

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Bibliographie Introduction

Position du problème

Le problème

Etant donné f : Rp → Rp ,
(1)
On cherche un vecteur x ∈ Rn solution de f (x) = 0.

Nous allons d’abord traiter le cas scalaire. La fin de ce chapitre

sera consacrée au cas vectoriel.

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Résolution numérique des équations

Résoudre numériquement l’équation f (x) = 0, revient à

chercher x ∗ tel que |f (x ∗ )| ≤ , avec  très petit.
On va supposer dans la suite que la racine x ∗ est séparable,
c’est à dire qu’il existe un intervalle [a, b] tel que x ∗ est la seule
racine dans cet intervalle.
On rappelle le théorème des valeures intermédiaires :
théorème des valeures intermédiaires
Soit f une fonction continue dans [a, b], et soit
y ∈ [min(f (a), f (b)), max(f (a), f (b))], alors il existe x ∈ [a, b] tel
que f (x) = y .

supposons qu’il existe un intervalle [a, b] tel que f (a)f (b) < 0,
donc d’aprs̀ le thérème des valeurs intermédiaires, il existe un
point x̄ tel que f (x̄) = 0.

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de dichotomie

Hypothèse : x ∗ est séparable dans [a, b]. Supposons de

plus que f (a)f (b) < 0.
On définit l’algorithme suivant :
algorithme de la bissection
Initialisation: a0 = a, b0 = b avec f (a)f (b) < 0
Iterations: Pour k = 0, 1, 2, . . .
ck = ak +b2 ,
k

Si f (ak )f (ck ) < 0

alors ak +1 = ak et bk +1 = ck

sinon ak +1 = ck et bk +1 = bk
fin du si
fin du pour

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de dichotomie : Exemple

f (x) = (5 − x)ex − 5 = 0, avec a = 1 et b = 6

50

40

30

20

10

−10
1 1.5 2 2.5 3 3.5 4 4.5 5

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de dichotomie : Critère de convergence

Il est évident que

b−a
bn − an = .
2n
Donc si |bn − an | ≤  alors 2n ≥ b−a  .
b−a


Et donc n ≥ log2  .
Si par exemple a = 1, b = 2 et  = 10−4 , alors n ≥ 14. Ce qui
montre que 14 itérations sont suffisante pour avoir une erreur
inférieure à 10−4 .
Comme approximation on propose an +b 2 . La convergence de la
n

méthode de dichotomie est linéaire.

Cette méthode nécessite une seule évaluation de fonctions par
itération. Nous allons voir dans ce qui suit une variante.

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de dichotomie : Première variante

Au lieu de prendre cn égal au milieu de [an , bn ], nous allons tout
d’abord tracer la droite passant par les deux points (an , f (an ))
et (bn , f (bn )). Le nouveau point cn sera donc l’intersection de
cette droite avec l’axe Ox.

f(a)

c
f(b)
a

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de dichotomie : Première variante

La droite passant par les points (an , f (an )) et (bn , f (bn )) a pour
équation
f (bn ) − f (an )
y = f (an ) + (x − an ) .
bn − an
On en déduit donc que cn est donné par

an f (bn ) − bn f (an )
cn = .
f (bn ) − f (an )

En modifiant l’algorithme précédent on obtient :

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de Regula-Falsi

Hypothèse : x ∗ est séparable dans [a, b]. Supposons de

plus que f (a)f (b) < 0.
On définit l’algorithme suivant :
algorithme de la fausse position (Regula-Falsi)
Initialisation: a0 = a, b0 = b avec f (a)f (b) < 0
Iterations: Pour k = 0, 1, 2, . . .
ck = ak ff (b k )−bk f (ak )
(bk )−f (ak ) ,
Si f (ak )f (ck ) < 0
alors ak +1 = ak et bk +1 = ck

sinon ak +1 = ck et bk +1 = bk
fin du si
fin du pour

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Interprétation de la Méthode de Regula-Falsi

Le principal inconvénient de cette méthode réside dans le fait
que l’on peut avoir une stagnation de l’un des des points,
comme le montre le graphe suivant :

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Interprétation de la Méthode de Regula-Falsi Modifiée

Nous allons remédier à ce petit problème, en changeant

l’ordonnée (on va le diviser par deux) du point qui cause la
stagnation. Si on reprend la figure précédente on obtient
maintenant :

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de dichotomie (Seconde variante) :

l’algorithme

Programme matlab
function [w,ier,N]=quest(f,a,b,xeps,feps,itermax)
fa=f(a); fb=f(b); w=a; fw=fa; a0=a; b0=b;
for N=1 : itermax
if(abs(a-b) < xeps)
ier=0; return
end
if ( abs(fw) <= feps)
ier = 1; return
end
w = (fa*b-fb*a)/(fa-fb);
fwp=fw; fw=f(w);

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de dichotomie (Seconde variante) :

l’algorithme (suite)
Programme matlab (suite)
if fa*fw > 0
a=w; fa=fw;
if( fw*fwp >0 )
fb = fb/2;
end
else
b=w; fb=fw;
if( fw*fwp > 0)
fa = fa/2;
end
end
end
ier = 2;
Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique
 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de dichotomie (Seconde variante) : Exemple

f (x) = (5 − x)ex − 5 = 0, avec a = 1 et b = 6

50

40

30

20

10

−10
1 1.5 2 2.5 3 3.5 4 4.5 5

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de Newton

La méthode de Newton est basée sur le développement de

Taylor. Soit x ∗ une solution de l’q́uation non linéaire f (x) = 0.
Nous savons d’après la formule des rectangles à gauche que :

x∗
(x ∗ − xk )2 00
Z
f (x ∗ ) − f (xk ) = f 0 (t)dt = (x ∗ − xk ) f 0 (xk ) + f (ηk ).
xk 2

En notant que f (x ∗ ) = 0 et en négligeant l’erreur de quadrature

numérique on obtient la méthode de Newton:

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

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Programmation de la méthode de Newton

Les paramètres d’entrée sont

x0 : approximation initiale,
ε : tolérance souhaitée,
itemax : nombre maximal d’itŕations

Algorithme
Etant donnés un point initial x0 et une tolérance ε,
Tant que |f (xk )| > ε et k ≤ itemax , faire

f (xk )
xk +1 = xk − ,
f 0 (xk )

Fait

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Interprétation géométrique de la méthode de Newton

Prenons
f (x) = arctan(x),
qui a pour solution exacte x ∗ = 0. L’itération de Newton pour
cette fonction s’écrit sous la forme suivante:
xk +1 = xk − (1 + xk2 ) arctan(xk ).
En prenant x0 = 1, on obtient :
1

0.8

0.6

0.4

0.2
atan(x)

x1
x*
0 x0
x3

−0.2

−0.4

−0.6

−0.8

−1
−1.5 −1 −0.5 0 0.5 1 1.5
x
Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique
 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de Newton : Remarques

la fonction f doit être dérivable.

xk +1 peut ne pas être calculable si f 0 (xk ) = 0 ou si xk n’est
pas dans le domaine de définition de f .
chaque itération nécessite une évaluation de f et une
évaluation de f 0 .
cette méthode est souvent appelée aussi méthode de
Newton-Raphson
la méthode de Newton est une méthode de point fixe
puisque xk +1 peut s’écrire sous la forme xk +1 = g(xk ) avec

f (x)
g(x) = x − .
f 0 (x)

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de Newton : Exemple1

Soit a un nombre positif, pour calculer a−1 , nous allons

appliquer la méthode de Newton à la fonction

1
f (x) = − a.
x
L’itération de Newton pour cette fonction s’écrit sous la forme
suivante:

xk +1 = 2xk − axk2 .

En prenant x0 ∈]0, a1 [, on a les propriétés suivantes :

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de Newton ( Exemple1 ) : propriétés

La suite {xk } est bien définie puisque xk ∈]0, a1 [

{xk } est une suite croissante majorée par a1 , elle est donc
convergente vers a1
{xk } est une suite de point fixe avec
xk +1 = 2xk − axk2 = g(xk ).
Notons ek l’erreur de la méthode i.e. ek = xk − a1 , il est
facile de voir que
Convergence Quadratique
ek +1
= −a.
ek2

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de Newton : Exemple2

√
Soit A un nombre positif, pour calculer A, nous allons
appliquer la méthode de Newton à la fonction

f (x) = x 2 − A.

L’itération de Newton pour cette fonction s’écrit sous la forme

suivante:
 
1 A
xk +1 = xk +
2 xk
√
En prenant x0 ∈] A, ∞[, on a les propriétés suivantes :

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de Newton ( Exemple2 ) : propriétés

√
La suite {xk } est bien définie puisque xk ∈] A, ∞[
√
{xk } est une suite décroissante minorée par A, elle est
donc convergente.
 
{xk } est une suite de point fixe avec xk +1 = 21 xk + xAk ,
√
qui converge vers A.
√
Notons ek l’erreur de la méthode i.e. ek = xk − A, il est
facile de voir que
Convergence Quadratique
ek +1 1 ek +1 1
2
= et lim 2
= √
ek 2xk k →∞ e
k 2 A

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de la sécante : introduction

Bien que la méthode de Newton est très utilisée dans la

pratique, son principal inconvénient vient du fait de l’utilisation à
chaque itération de la dérivée. Quand la fonction f n’est pas
définie explicitement, on n’ pas toujours accés à sa dérivée.
C’est pourquoi nous allons voir maintanant la méthode de la
sécante qui n’utilise pas la dérivée de f .
L’idée de cette méthode est d’approcher la dérivde f 0 (xk ) par
une différence dévisée
f (xk ) − f (xk −1 )
f 0 (xk ) ≈ [xk −1 , xk ] = .
xk − xk −1

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de la sécante
L’itération de la méthode de la sécante s’écrit donc
f (xk )(xk − xk −1 )
xk +1 = xk − .
f (xk ) − f (xk −1 )

Figure : Interprétation géométrique de la méthode de la sécante.

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de la sécante : Exemple

Appliquons la méthode de la sécante et la méthode de Newton
pour trouver la racine de f (x) = arctan(x). Nous partons des
itérés x0 = 1 et x1 = 3 pour la méthode de la sécante et x0 = 1
pour la méthode de Newton.

Plot of error with respect to iteration, f(x)=atan

0
Secant
Newton

−5
Relative residual

−10

−15

−20

−25
0 1 2 3 4 5
Nonlinear iterations

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de la sécante : Exemple1

1
f (x) = − a.
x
L’itération de la sécante pour cette fonction s’écrit sous la forme
suivante:

xk +1 = xk + xk −1 − axk xk −1 .

En prenant x0 et x1 dans ]0, a1 [, on a les propriétés suivantes :

La suite {xk } est bien définie puisque xk ∈]0, a1 [
Notons ek l’erreur de la méthode i.e. ek = xk − a1 , il est
facile de voir que
Convergence Super-linéaire
ek +1
= −a.
ek ek −1
Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique
 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Méthode de Newton : Exemple2

f (x) = x 2 − A.

L’itération de la sécante pour cette fonction s’écrit sous la forme

suivante:

xk xk −1 + A
xk +1 =
xk + xk −1
√
Notons ek l’erreur de la méthode i.e. ek = xk − A, il est facile
de voir que
Convergence Super-linéaire
ek +1 1 ek +1 1
= et lim = √
ek ek −1 2xk k →∞ ek ek −1 2 A

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Définition
Soit x∗ ∈ Rn , xk ∈ Rn , k = 1, 2, .... S’il existe une constante
c ∈ [0, 1) et un entier k0 ≥ 0 tels que pour tout k ≥ k0 ,
k ek +1 k≤ c k ek k
alors la suite {xk } converge linéairement vers x∗ . Si pour une
suite {ck } qui tend vers 0,
k ek +1 k≤ ck k ek k,
pour tout k , alors la suite {xk } converge super-linéairement
vers x∗ . S’il existe des constantes p > 1, c ≥ 0, et k0 ≥ 0 telles
que {xk } converge vers x∗ pour tout k ≥ k0 ,
k ek +1 k≤ c k ek kp ,
alors la suite {xk } converge vers x∗ avec au moins un ordre p.
Si p = 2 ou p = 3, alors la convergence est dite respectivement
quadratique ou cubique.
Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique
 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Etude de la convergence de la méthode de Newton

théoreme
Soit f : D → R, pour un ouvert D dans lequel
k f 0 (y ) − f 0 (z) k≤ K k y − z k .. Supposons qu’il existe ρ > 0 tel
que |f 0 (x)| > ρ pour tout x ∈ D. Si f (x) = 0 a une solution
x∗ ∈ D, alors il existe une constante η > 0 telle que: si
|x0 − x∗ | < η, alors la suite {xk } générée par

f (xk )
xk +1 = xk − , k = 0, 1, 2, ...
f 0 (xk )

existe et converge vers x∗ . En outre, pour k = 0, 1, ...,

K
|xk +1 − x∗ | ≤ |xk − x∗ |2 .
2ρ

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique

 Introduction Cas scalaire p = 1 Algorithmes de résolution Etude de la convergence

Etude de la convergence de la méthode de la sécante

théoreme
La méthode
√
de la sécante a une convergence d’ordre
(1+ 5)
r= 2 . En d’autres termes, nous avons

|xk +1 − x∗ | ≤ C|xk − x∗ |r .

Cours d’Analyse Numérique, Chapitre 3 : Résolution Numérique