COURS UM6P

ANNEE 2020-2021

Laurent Dumas
2
CHAPITRE 1
INTERPOLATION POLYNOMIALE

3
4 CHAPITRE 1. INTERPOLATION POLYNOMIALE
CHAPITRE 2
RESOLUTION DE SYSTEMES NON LINEAIRES

L’objectif de ce chapitre est de présenter différentes méthodes de résolution appro-

chée d’une équation f (x) = 0 où f est une fonction définie sur un sous-ensemble
A de Rn et à valeurs dans Rn . Dans le premier paragraphe, le problème est retraduit
en termes de recherche de points fixes pour une fonction auxiliaire g à préciser
afin de définir la famille des méthodes itératives. La méthode de Newton peut alors
être construite puis étudiée en détail dans le paragraphe suivant. Le paragraphe 3
présente ensuite trois autres méthodes de recherche de zéros d’une fonction réelle.
Enfin, le paragraphe 4 propose un procédé général d’accélération de convergence
d’une suite pouvant être appliqué aux suites itératives précédentes.

2.1 Méthodes itératives

2.1.1 Théorème du point fixe
Commençons par rappeler le théorème classique suivant dû à Picard :

Théorème 1. soit A un fermé de Rn et g une application de A dans Rn telle que :

(i) g(A) ⊂ A.
(ii) g est contractante pour une certaine norme de Rn , à savoir :

∃K ∈ [0, 1[, ∀(x, y) ∈ A2 , ||g(x) − g( y)|| ≤ K||x − y||.

Alors, g admet un unique point fixe x̄ ∈ A. De plus, la suite (x n )n∈N construite par
récurrence :
x 0 ∈ A et x n+1 = g(x n ) (n ∈ N) (1)

5
6 CHAPITRE 2. RESOLUTION DE SYSTEMES NON LINEAIRES

converge vers x̄ et

K k−l
∀k ∈ N, ∀l ∈ {0, ..., k}, ||x k − x̄|| ≤ ||x l+1 − x l || (2)
1−K
Démonstration. L’unicité du point fixe est immédiate avec l’hypothèse (ii). Pour démontrer
son existence, on considère la suite (x n )n∈N définie correctement par la relation (1).
Grâce à l’hypothèse (ii), on remarque que :

∀n ∈ N∗ , ||x n+1 − x n || = ||g(x n ) − g(x n−1 )|| ≤ K||x n − x n−1 ||... ≤ K n ||x 1 − x 0 ||

puis en utilisant l’inégalité triangulaire

n−k−1
X Kk
∀n ∈ N, ∀k ∈ N, k ≤ n ⇒ ||x n − x k || ≤ K k+i ||x 1 − x 0 || ≤ ||x 1 − x 0 || (3)
i=0
1−K

La suite (x n )n∈N est donc de Cauchy dans le sous-espace complet A (fermé dans
un espace complet) et converge ainsi vers x̄ ∈ A. Par passage à la limite dans (1), la
fonction g étant continue (car K-Lipschitzienne), on a bien g(x̄) = x̄.
En passant ensuite à la limite dans l’inégalité (3) lorsque n → +∞, on obtient
la relation (2) pour l = 0. Le cas général l > 0 est obtenu par un simple décalage
d’indice.

Le corollaire suivant est souvent utilisé dans la pratique :

Corollaire 1. En conservant les notations du Théorème 1, on suppose que la fonction

g vérifie (i) et la nouvelle proposition (ii)’ :
(ii)’ il existe un entier n0 > 0 tel que g n0 (g itérée n0 fois) soit contractante. Alors, g
admet un unique point fixe.

Démonstration. L’unicité d’un point fixe de g provient aisément de l’hypothèse (ii)’.

Pour démontrer son existence, on applique le Théorème 1 à la fonction g n0 : soit
x̄ ∈ A tel que
g n0 (x̄) = x̄.
Comme g(x̄) est aussi un point fixe de g n0 , on a par unicité de ce dernier :

g(x̄) = x̄

Remarque : L’hypothèse (ii)’ est strictement plus faible que l’hypothèse (ii) : Il
2.1. MÉTHODES ITÉRATIVES 7
 2
R → R2

suffit pour cela de considérer la fonction g : . On observe que
(x 1 , x 2 ) 7→ (2x 2 , 0)
g 2 = 0 est contractante tandis que g ne l’est pas. Par contre, (0,0) est bien l’unique
point fixe de g et de g 2 .

2.1.2 Notion d’ordre

Le théorème précédent permet de construire par récurrence une suite d’appro-

ximations (x n )n∈N convergeant vers le point fixe x̄ d’une fonction g, stable et contractante
sur un ensemble fermé A de Rn . Afin de préciser la vitesse de convergence de cette
suite, on note en = x n − x̄, l’erreur commise au rang n, et on définit la notion d’ordre
de convergence :

Définition 1. La convergence de la suite (x n )n∈N vers x̄ est (au moins) d’ordre p ∈ N∗

si
∃C ∈ R∗+ , ∃n0 ∈ N∗ , ∀n ∈ N, n ≥ n0 ⇒ ||en+1 || ≤ C||en || p
(avec C < 1 si p = 1).

On observe que la convergence d’ordre p > 1 d’une suite permet de multiplier

approximativement par p à chaque étape le nombre de décimales exactes de x̄
calculées avec la suite en question (lorsque p = 1 on rajoute simplement une décimale
exacte après chaque itération).
Dans le cadre général du Théorème 1, la convergence est d’ordre 1 (on dit aussi
géométrique). Cet ordre peut être amélioré dans certains cas lorsque g est deux fois
différentiable :

Théorème 2. : les notations et hypothèses (i) et (ii) du Théorème 1 sont conservées. On

suppose en outre que g ∈ C 2 (A, Rn ) et x̄ appartient à l’intérieur de A. On peut préciser
la vitesse de convergence de la suite (x n )n∈N dans deux cas :
(i) si D g(x̄) (différentielle de g en x̄) est un isomorphisme de Rn , la convergence est
exactement d’ordre 1, à savoir :

∃(C1 , C2 ) ∈ ]0, 1[2 , ∃n0 ≥ 1, ∀n ∈ N, n ≥ n0 ⇒ C1 ||en || ≤ ||en+1 || ≤ C2 ||en ||

(ii) si D g(x̄) est l’endomorphisme nul, la convergence est au moins d’ordre 2 (on dit
aussi quadratique).
8 CHAPITRE 2. RESOLUTION DE SYSTEMES NON LINEAIRES

Démonstration. On écrit la formule de Taylor-Young à l’ordre 2 entre x n et x̄ pour la

fonction g :
1 2
en+1 = g(x n ) − g(x̄) = Dg(x̄) · en + D g(x̄)(en , en ) + ||en ||2 "(en )
2
où " est une fonction continue définie au voisinage de 0 ∈ Rn et nulle en ce point.
Sachant déjà que en tend vers 0, on peut écrire :

∃C > 0, ∃n0 ∈ N∗ , ∀n ∈ N, n ≥ n0 ⇒ ||en+1 − Dg(x̄) · en || ≤ C||en ||2 .

Le cas (ii) où Dg(x̄) ≡ 0 est ainsi démontré. Dans le cas (i) où Dg(x̄) est un
isomorphisme, soit correctement n1 ∈ N tel que
1
∀n ∈ N, n ≥ n1 ⇒ C||en || ≤ inf ||Dg(x̄) · v||
2 v∈S(0,1)
où S(0, 1) représente la sphère unité de Rn . Alors, pour n ≥ max(n0 , n1 ),

||en+1 || ||Dg(x̄) · en + (en+1 − Dg(x̄) · en )||

= ≥ inf ||Dg(x̄) · v|| − C||en ||
||en || ||en || v∈S(0,1)
1
≥ inf ||Dg(x̄) · v|| > 0.
2 v∈S(0,1)
1
Il suffit alors de prendre C1 = inf ||Dg(x̄) · v|| (et C2 = K) pour achever la
2 v∈S(0,1)
démonstration de ce cas

2.1.3 Cas particulier des fonctions réelles

L’ordre de convergence peut être précisé lorsque g est une fonction réelle suffisamment
régulière :

Théorème 3. : soit g ∈ C 1 (R, R) et x̄ un point fixe de g tel que |g 0 (x̄)| < 1 (point
fixe attractif). Alors, il existe un voisinage V de x̄ tel que la suite (x n )n∈N des itérées
construite à partir de g suivant (1) avec x 0 ∈ V , converge vers x̄.
(i) Si g 0 (x̄) 6= 0, la convergence est exactement géométrique.
(ii) S’il existe un entier p ≥ 2 et un voisinage V de x̄ tel que g ∈ C p (V, R) et

g 0 (x̄) = g 00 (x̄) = ... = g (p−1) (x̄) = 0, g (p) (x̄) 6= 0,

alors la convergence est exactement d’ordre p.

2.2. MÉTHODE DE NEWTON 9

Démonstration. On remarque tout d’abord que l’hypothèse |g 0 (x̄)| < 1 permet de

déduire l’existence d’un voisinage fermé V de x̄ sur lequel g/V soit stable et contractante
(en utilisant la continuité de g 0 et l’inégalité des accroissements finis). Ceci permet
d’assurer grâce au Théorème 1 la convergence de la suite (x n )n∈N vers x̄ lorsque
x 0 ∈ V . Si de plus g 0 (x̄) 6= 0 (cas (i)), on peut en outre supposer que
∃(C1 , C2 ) ∈]0, 1[2 , ∀x ∈ V, C1 ≤ |g 0 (x)| ≤ C2
et à nouveau grâce à l’inégalité des accroissements finis,
∀n ∈ N, C1 |x n − x̄| ≤ |x n+1 − x̄| ≤ C2 |x n − x̄|
et la convergence est exactement géométrique. Dans le cas (ii), on écrit l’égalité de
Taylor-Lagrange à l’ordre p entre x n et x̄ :
g (p) ( yn )
x n+1 − x̄ = (x n − x̄) p ( yn ∈]x n , x̄[)
p!
et la conclusion suit aisément en utilisant la continuité de g (p)

2.2 Méthode de Newton

2.2.1 Définition générale

Théorème 4. : on considère une fonction f ∈ C 3 (A, Rn ) (avec A ouvert de Rn ) et x̄ ∈ A

tel que f (x̄) = 0. Si D f (x̄) est un isomorphisme, alors il existe un voisinage V ⊂ A
de x̄ telle que la suite (x n )n∈N 
construite à partir de la formule (1) pour la fonction
V → Rn
g: et avec x 0 ∈ V soit bien définie et converge vers x̄ de
x 7→ x − D f (x)−1 · f (x)
manière quadratique.
Démonstration. Comme f ∈ C 3 (A, Rn ) et D f (x̄) est un isomorphisme, on sait qu’il
existe un voisinage fermé V de x̄ tel que la fonction g de l’énoncé soit correctement
définie sur V . Par construction, on a g(x̄) = x̄. De plus, Dg(x̄) = 0 : en effet,
D g(x̄) = I − D(D f (x̄)−1 )(x̄) · f (x̄) − D f (x̄)−1 · D f (x̄) = I − 0 − I = 0.
On peut donc supposer en outre que V est stable par g. Il suffit alors d’invoquer
le Théorème 3 pour en déduire que la suite (x n )n∈N est bien définie et converge
quadratiquement vers x̄
10 CHAPITRE 2. RESOLUTION DE SYSTEMES NON LINEAIRES

2.2.2 Cas particulier des fonctions réelles

Si on se place dans le cas où n = 1, on peut préciser le Théorème 5 :

Théorème 5. : soit f ∈ C 2 (A, R) (A ouvert de R) et x̄ ∈ A tel que f (x̄) = 0.

(i) On suppose que f 0 (x̄) 6= 0. Alors, il existe un voisinage V de x̄ telle que la suite
(x n )n∈N construite par la formule

f (x n )
x0 ∈ V et x n+1 = x n − (n ∈ N) (4)
f 0 (x n )

existe et converge vers x̄ de manière quadratique.

(ii) Si f 0 (x̄) = 0 et f 00 (x̄) 6= 0, la suite (x n )n∈N est encore bien définie par la formule
(4) dans un voisinage V de x̄ (en supposant de plus x n+1 = x̄ si x n = x̄) et converge
géométriquement vers x̄.

Démonstration. La partie (i) du théorème concernant l’existence et la convergence

de la suite (x n )n∈N n’est qu’une récriture du Théorème 4. On peut également remarquer
directement que

f 00 ( yn )
∀n ∈ N, ∃ yn ∈]x n , x̄[, en+1 = x n+1 − x̄ = en2 (5)
2 f 0 (x n )

en écrivant la relation de Taylor-Lagrange à l’ordre 2 entre x̄ et x n :

1
0 = f (x̄) = f (x n ) + (x̄ − x n ) f 0 (x n ) + (x̄ − x n )2 f 00 ( yn ) ( yn ∈]x n , x̄[)
2
et en utilisant la relation de récurrence (4). Dans le cas (ii) où f 0 (x̄) = 0 et f 00 (x̄) 6= 0,
on peut considérer un voisinage fermé V de x̄ tel que

∀x ∈ V, x 6= x̄ ⇒ f 0 (x) 6= 0

et constuire la fonction g sur V telle que

 x̄ si x = x̄


g(x) = f (x)
x − 0 si x 6= x̄
f (x)
1
Ainsi définie, on montre que g est C 1 et g 0 (x̄) = : en effet, pour x 6= x̄, on a
2
f 02 (x) − f (x) f 00 (x) f (x) f 00 (x)
g 0 (x) = 1 − =
f 02 (x) f 02 (x)
2.2. MÉTHODE DE NEWTON 11

et en écrivant les formules de Taylor-Young autour de x̄ pour f , f 0 et f 00 ,

(x − x̄)2 00

f (x) = f (x̄) + o((x − x̄)2 )


2

 f 0 (x) = (x − x̄) f 00 (x̄) + o(x − x̄)

f (x) = f 00 (x̄) + o(1)
 00

on obtient bien
1 g(x) − g(x̄)
= lim
lim g 0 (x) = .
x→x̄ 2 x→x̄ x − x̄
Le Théorème 3 permet alors de conclure dans ce cas

2.2.3 Interprétation géométrique

La méthode de Newton peut s’interpréter géométriquement en dimension un : la

valeur de x n+1 est égale à l’abscisse de l’intersection de l’axe Ox avec la tangente à la
courbe représentative de f au point x n . Autrement dit, f est localement remplacée
par sa tangente afin d’obtenir une meilleure approximation de x̄.
Il est également aisé de comprendre graphiquement pourquoi la méthode n’est
pas forcément convergente si le point initial x 0 n’est pas suffisamment proche de x̄.
On devra donc procéder au cas par cas pour trouver un voisinage V de x̄ convenable.
À noter cependant qu’il existe de nombreux résultats donnant des conditions suffisantes
sur f pour assurer la convergence de la méthode sur un certain voisinage (voir TD).

2.2.4 Extensions de la méthode

Même lorsque x̄ est une racine de f de multiplicité m supérieure ou égale à 2,

il est possible dans le cas réel de construire une suite d’approximations convergeant
quadratiquement vers x̄ en modifiant légèrement la méthode de Newton (voir TD).
En particulier, la méthode de Newton améliorée basée sur la relation de récurrence

∀n ∈ N, x n+1 = h(x n )

avec
f
(f0) f (x) f 0 (x)
h(x) = x − f (x) = x − 0 2
( 0 )0 f (x) − f (x) f 00 (x)
f
12 CHAPITRE 2. RESOLUTION DE SYSTEMES NON LINEAIRES

permet de retrouver (avec un supplément de calcul) une convergence quadratique

si m = 1 ou 2.
Une autre extension possible en dimension quelconque correspond à la possibilité
de pouvoir remplacer l’isomorphisme D f (x)−1 par une approximation de celui-ci (en
contrepartie, la convergence est seulement géométrique). Le théorème correspondant
peut s’énoncer ainsi :

Théorème 6. : soit f ∈ C 1 (A, Rn ) (avec A ouvert de Rn ) et x̄ ∈ A tel que f (x̄) = 0 et

D f (x̄) est un isomorphisme. On considère une famille (An )n∈N d’isomorphismes de Rn
telle que
1 λ
∃λ ∈ [0, [, sup |||An − D f (x̄)||| ≤ .
2 n∈N |||D f (x̄)|||
Il existe un voisinage fermé V de x̄ tel que la suite (x n )n∈N définie par la formule :

xo ∈ V et x n+1 = x n − A−1
n
· f (x n ) (n ∈ N)

est bien définie et converge géométriquement vers x̄. De plus, la convergence est géométrique :

∃β ∈ [0, 1[, ∀n ∈ N, ||x n − x̄|| ≤ β n ||x o − x̄||.

On parle dans ce cas de la méthode de Newton généralisée.

Remarque : On peut dresser un lien entre la méthode de Newton généralisée et les

méthodes de gradient (à pas simple, variable ou optimal) destinées à la recherche
du minimum d’une fonctionnelle J : Rn → R. En effet, ces dernières reviennent à
rechercher des zéros de l’application ∇J avec la méthode de Newton généralisée.

2.2.5 Exemples

(i) Calcul approché d’une racine réelle

p
Soit a ∈ R∗+ . On peut calculer une valeur approchée de a en appliquant la
méthode de Newton à la fonction f (x) = x 2 −a. La suite des approximations est alors
construite à partir de la relation de récurrence (appelée aussi algorithme phénicien)

1 a
x n+1 = (x n + ) (n ∈ N)
2 xn
p
On montre qu’il suffit de prendre x 0 > 0 pour que la suite converge vers a (en
décroissant à partir du rang 1).
2.3. AUTRES MÉTHODES 13

(ii) Calcul approché des racines d’un polynôme réel scindé

Soit r
Y
P(x) = (x − ξi )mi
i=1

un polynôme réel scindé. On commence par diviser P par le PGCD de P et de

P 0 afin de se ramener à un polynôme à racines simples (on peut donc à présent
supposer que mi = 1). On applique alors la méthode de Newton avec f (x) = P(x)
partant de x 0 ≥ max1≤i≤r (ξi ). On peut montrer que la suite des itérées converge
quadratiquement vers la plus grande racine de P, par exemple ξ r . Deux choix sont
ensuite possibles pour déterminer les autres racines : le premier consiste à effectuer
d’abord la division euclidienne de P par X − ξ (où ξ est la valeur approchée de
ξ r obtenue) puis à recommencer l’opération précédente. Cette méthode (dite de
déflation) est cependant dangereuse numériquement (car instable). Une autre méthode
(dite de suppression de zéros et dûe à Maehly) consiste à construire la suite itérative
suivante :
P(x n )
x n+1 = x n − P(x n )
P 0 (x n ) − x n −ξ
P
(issue du calcul approché de la dérivée logarithmique du polynôme X −ξ r
). On montre
que cette suite, correctement initialisée, peut converger vers toutes les autres racines
du polynôme P.

2.2.6 Implémentation numérique

L’implémentation de la méthode de Newton peut s’avérer coûteuse en dimension

n > 1 car elle requiert à chaque étape l’inversion du Jacobien de f en x n . On
utilise plutôt la méthode de Newton généralisée pour des suites particulières An :
on peut par exemple prendre (en s’assurant que les conditions du théorème sont
bien vérifiées) An = D f −1 (x 0 ) (et effectuer une factorisation LU de cette matrice)
ou choisir de ne réactualiser D f −1 (x n ) que toutes les N itérations. Le gain réalisé en
temps de calcul compense en général largement la perte de rapidité de la convergence.

2.3 Autres méthodes

Trois autres méthodes d’approximation des zéros d’une fonction réelle f sont
présentées dans ce paragraphe.
14 CHAPITRE 2. RESOLUTION DE SYSTEMES NON LINEAIRES

2.3.1 Méthode de la sécante

Dans cette variante de la méthode de Newton, la dérivée f 0 (x n ) est remplacé par le

f (x n ) − f (x n−1 )
taux d’accroissement :
x n − x n−1

Théorème 7. : soit f ∈ C 2 (R, R) et x̄ un zéro de f tel que f 0 (x̄) 6= 0. Alors, il existe

un voisinage V de x̄ tel que la suite (x n )n∈N construite suivant la formule

f (x n )(x n − x n−1 )
(x 0 , x 1 ) ∈ V 2 , x 1 6= x 0 et ∀n ∈ N∗ , x n+1 = x n −
f (x n ) − f (x n−1 )

est correctement définie (ou prend la valeur x̄ et dans ce cas on suppose qu’elle stationne)
et converge vers x̄. De plus, si f 00 (x̄) 6= 0

∃C > 0, ∃q ∈]0, 1[, ∃n0 ∈ N, ∀n ∈ N, n ≥ n0 ⇒ |en | ≤ Cqα

n

p
1+ 5
avec α = .
2
Démonstration. Soit tout d’abord I un voisinage de x̄ tel que

∃m ∈ R∗+ , ∀x ∈ I, | f 0 (x)| ≥ m.

On note M = max | f 00 (x)| et on considère J =]x̄ − β, x̄ + β[⊂ I avec β tel que

x∈I
2M β
0< < 1.
m
On montre que la suite (x n )n∈N de l’énoncé avec (x 0 , x 1 ) ∈ J 2 et x 1 6= x 0 est bien
définie. Pour cela, on démontre par récurrence la propriété suivante :
(x n ∈ J) et (x n 6= x n−1 ou x n = x n−1 = x̄)
Supposons la propriété vraie jusqu’au rang n (elle est vraie pour n = 1) : il est
alors possible de définir x n+1 (dans un cas f (x n ) 6= f (x n−1 ) car f est strictement
monotone sur J et x n+1 = x̄ dans l’autre cas). En utilisant deux fois le théorème des
accroissements finis :

f (x n ) = (x n − x̄) f 0 ( y1,n ), ( y1,n ∈]x n , x̄[)



f (x n ) − f (x n−1 ) = (x n − x n−1 ) f 0 ( y2,n ) ( y2,n ∈]x n−1 , x n [)

il vient

(x n − x̄) f 0 ( y1,n )(x n − x n−1 ) f 0 ( y1,n )

x n+1 = x n − = x n − (x n − x̄)
(x n − x n−1 ) f 0 ( y2,n ) f 0 ( y2,n )
2.3. AUTRES MÉTHODES 15

ou
” f 0 ( y2,n ) − f 0 ( y1,n ) —
x n+1 − x̄ = (x n − x̄)
f 0 ( y2,n )
f 00 ( y3,n )
= (x n − x̄) 0 ( y2,n − y1,n ) ( y3,n ∈] y1,n , y2,n [)
f ( y2,n )
Grâce à la propriété de récurrence, on a alors

M
|en+1 | = |x n+1 − x̄| ≤ |x n − x̄| 2β (6)
m
ce qui permet d’affirmer que x n+1 ∈ J. Pour démontrer la deuxième partie de la
propriété, on observe que si x n = x̄, alors x n+1 = x n = x̄ tandis que si x n 6=
x̄, on a x n+1 6= x n (car dans ce cas x n 6= x n−1 , f (x n ) 6= f (x n−1 ) et f (x n ) 6= 0).
L’inégalité (6) permet en outre d’assurer que la suite (x n )n∈N converge vers x̄ de
manière géométrique. Pour améliorer cette estimation, on écrit (en adoptant les
notations relatives aux différences divisées, voir chapitre sur l’interpolation polynomiale) :

f (x n ) 1
en+1 = en − = en − (x n − x̄) f [x n , x̄]
f [x n , x n−1 ] f [x n , x n−1 ]
€ f [x n , x̄] Š
= en 1 −
f [x n , x n−1 ]
f [x n , x n−1 , x̄]
= en en−1 .
f [x n , x n−1 ]

En utilisant alors les propriétés classiques suivantes :

lim f [x n , x n−1 ] = f 0 (x̄)

n→+∞

et
f 00 (x̄)
lim f [x n , x n−1 , x̄] = ,
n→+∞ 2
M
on peut affirmer qu’il existe M 0 > tel que pour n assez grand,
2m

|en+1 | ≤ M 0 |en en−1 |

ou de manière équivalente "n+1 ≤ "n + "n−1 en posant "n = ln (M 0 |en |).

On obtient ensuite par récurrence

€ 1 + p5 Šn € 1 − p5 Šn
"n ≤ A +B
2 2
16 CHAPITRE 2. RESOLUTION DE SYSTEMES NON LINEAIRES

avec  p
 "1 − 1−2 5 "0
A = p


5
p
1+ 5
2 "0 − "1

B =

 p
5
Il est toujours possible de choisir un voisinage V de x̄ inclus dans J tel que "0 et "1
1 m
soient toujours négatifs (prendre V =]x̄ − γ, x̄ + γ[ avec γ < min( 0 , )). Dans
M 2M
ce cas, A < 0 et pour n assez grand,
p
A € 1 + 5 Šn A n
"n ≤ = α
2 2 2

soit
A n
1 α
en ≤ 0 e 2
M
ce qui permet de clôre ensuite aisément la démonstration du théorème

Remarque : Cette méthode possède l’avantage par rapport à la méthode de Newton

de ne pas nécessiter le calcul de f 0 mais s’avère moins performante qu’elle (car
α < 2). Comme la méthode de Newton, elle est en outre aisément programmable.
À noter qu’il peut survenir cependant un problème de compensation d’erreur dans
l’estimation du taux d’accroissement

f (x n ) − f (x n−1 )
τn = .
x n − x n−1

En effet, si l’on dispose d’une précision machine de ", il est inutile et vain de calculer
p
τn dès que |x n − x n−1 | ≤ ". Pour atteindre une précision " sur x̄, on doit alors
continuer le calcul avec la dernière valeur (constante) de ce taux.

2.3.2 Méthode de dichotomie (ou de bissection)

Soit f ∈ C 0 (R). On suppose connu un intervalle [a, b] de R sur lequel f ne

s’annule qu’une fois (en x̄) en changeant de plus de signe (on peut par exemple
supposer f continue et strictement monotone sur [a, b] avec f (a) f (b) < 0). La
2.3. AUTRES MÉTHODES 17

méthode de dichotomie se construit ainsi : les trois premiers termes de la suite

d’approximations sont pris égaux à
x0 = a


x1 = b


 x = x0 + x1

2
2
Ensuite, parmi les deux réels f (x 0 ) f (x 2 ) et f (x 1 ) f (x 2 ), il en existe forcément un
(par exemple le premier) qui soit strictement négatif (sinon x 2 = x̄ et la construction
s’arrête). Dans ce cas, on construit alors
x0 + x2
x3 =
2
et le processus se répète indéfiniment (ou s’arrête si pour un certain n ∈ N, x n = x̄)
permettant de construire les termes de la suite (x n )n∈N . On montre aisément que
lim x n = x̄ et que la convergence est géométrique :
n→+∞

1
∀n ∈ N, |en | ≤ |x 1 − x 0 |.
2n−1

2.3.3 Méthode de la fausse position (ou regula falsi)

Cette méthode reprend les hypothèses de la méthode de dichotomie (par exemple

f continue et strictement monotone sur [a, b] avec f (a) f (b) < 0) et construit la
suite d’approximations suivante :
x0 = a



x1 = b


x f (x 1 ) − x 1 f (x 0 )
 x2 = 0


f (x 1 ) − f (x 0 )
(x 2 correspond au point d’intersection de la corde de f entre x 0 et x 1 avec l’axe des
abscisses). La construction de la suite (x n )n∈N suit alors en tout point celle associée à
la méthode de dichotomie (seule change la façon de découper l’intervalle de départ).
La convergence est encore en général géométrique mais peut dans certains cas devenir
quadratique.

Remarque : L’avantage essentiel des deux dernières méthodes présentées par rapport
aux deux premières (dont la convergence est plus rapide) tient au fait que leur
convergence est plus facilement assurée.
18 CHAPITRE 2. RESOLUTION DE SYSTEMES NON LINEAIRES

2.4 Accélération de convergence

2.4.1 Procédé ∆2 d’Aitken

Le théorème suivant donne un procédé d’accélération de convergence pour certaines

suites itératives. Auparavant, on introduit l’opérateur classique aux différences finies
progressives ∆ :  N
R → RN

∆: .
(x n )n∈N 7→ ( yn = x n+1 − x n )n∈N

Théorème 8. : soit x̄ ∈ R et (x n )n∈N une suite réelle ne prenant jamais la valeur x̄. On
suppose qu’il existe un coefficient k ∈ [0, 1[ et une suite auxiliaire (zn )n∈N convergeant
vers 0 vérifiant
∀n ∈ N, x n+1 − x̄ = (k + zn )(x n − x̄) (7)
Alors, la suite (x n0 ) telle que

(∆x n )2
2
x n+1 − 2x n+1 x n + x n2
x n0 = xn − = xn −
∆2 x n x n+2 − 2x n+1 + x n
est bien définie pour n assez grand et vérifie
x n0 − x̄
lim = 0.
n→+∞ x n − x̄
Démonstration. On note en = x n − x̄. La relation (7) se récrit en+1 = (k + zn )en . Par
conséquent
∆x n = ∆en = (k − 1 + zn )en
et
∆2 x n = ∆2 en = (k − 1 + zn+1 )en+1 − (k − 1 + zn )en
 
= (k − 1 + zn+1 )(k + zn ) − (k − 1 + zn ) en
 
= (k − 1)2 + k(zn + zn+1 ) + zn zn+1 − 2zn en .
En particulier, on observe qu’avec les hypothèses faites ∆2 x n 6= 0 pour n assez
grand, ce qui permet de définir la suite (x n0 ) à partir d’un certain rang. De plus, on a
alors
(k − 1 + zn )2 en2
x n − x̄ = x n − x̄ − 
0

(k − 1)2 + k(zn + zn+1 ) + zn zn+1 − 2zn en
” k(zn + zn+1 ) + zn zn+1 − 2zn − 2zn (k − 1) + z 2 —
n
= en
(k − 1)2 + k(zn + zn+1 ) + zn zn+1 − 2zn
ce qui assure ensuite facilement le résultat annoncé
2.4. ACCÉLÉRATION DE CONVERGENCE 19

2.4.2 Méthode de Steffensen

Il s’agit du procédé d’Aitken appliqué aux suite itératives du paragraphe 1 du

type x n+1 = g(x n ). Formellement, on a

(g(x n ) − x n )2 x n (g ◦ g)(x n ) − g(x n )2

x n0 = xn − = .
(g ◦ g)(x n ) − 2g(x n ) + x n (g ◦ g)(x n ) − 2g(x n ) + x n
Le théorème suivant précise l’existence et le comportement de la suite (x n0 ) :

Théorème 9. : soit p ∈ N∗ , g ∈ C p+1 (R, R) et x̄ ∈ R tel que


 g(x̄) = x̄

g 0 (x̄) = ... = g (p−1) (x̄) = 0
 g (p) (x̄) 6= 0


(on suppose en outre que g 0 (x̄) 6= 1 si p = 1).

Alors, il existe un voisinage V de x̄ sur lequel la fonction
V →R

2

  x(g ◦ g)(x) − g(x)
h: x 7→ (g ◦ g)(x) − 2g(x) + x si x 6= x̄
x̄ si x = x̄


est correctement définie et où la suite (x n0 )n∈N construite par la formule

x 00 ∈ V et 0
x n+1 = h(x n0 ) (n ∈ N)

est également bien définie et converge vers x̄ avec un ordre 2p − 1 si p > 1 et 2 si

p = 1.

Démonstration. : On se ramène tout d’abord facilement au cas x̄ = 0 en posant

g1 ( y) = g( y + x̄) − x̄. Ensuite, on écrit la formule de Taylor-Young à l’ordre p + 1
pour g en 0 :
g (p) (0) p
g(x) = x + O(x p+1 ) ≡ Ax p + O(x p+1 ).
p!
En itérant cette relation, il vient
(g ◦ g)(x) = A(Ax p + O(x p+1 )) p + O(x p(p+1) )
2
¨
O(x p ) si p > 1
=
A2 x + O(x 2 ) si p = 1
20 CHAPITRE 2. RESOLUTION DE SYSTEMES NON LINEAIRES

On reporte ces estimations dans l’expression de h (en observant au préalable que

A 6= 1 si p = 1) :
2
O(x p +1 ) − A2 x 2p + O(x 2p+1 )

∼ A2 x 2p−1 si p > 1


O(x p2 ) − 2Ax p + O(x p+1 ) + x

h(x) =
A2 x 2 + O(x 3 ) − A2 x 2 + O(x 3 ) O(x 3 )
= = O(x 2 ) sinon


A2 x + O(x 2 ) − 2Ax + O(x 2 ) + x (A − 1)2 x + O(x 2 )


La démonstration s’achève alors aisément en s’inspirant du Théorème 4

Remarque : Cette méthode est intéressante car elle permet de construire une suite
d’approximations avec convergence quadratique d’un point fixe x̄ d’une fonction g
même si |g 0 (x̄)| > 1 (point fixe répulsif). Par contre, elle n’a pas d’utilité pratique
lorsque p > 1 car dans ce cas, la fonction h(x) = (g ◦ g)(x) donne une convergence
plus rapide (d’ordre p2 > 2p − 1).