Résolution d’équation non linéaire

15 mars 2024

15 mars 2024 1 / 45
Plan

1 Introduction

2 Localisation des zéros

3 Construction d’une suite convergente

Méthodes de dichotomie (ou bissection), de Lagrange (ou
Regula falsi )
Méthode de la sécante
Méthode de point fixe
Méthodes de point fixe particulièrement connues

15 mars 2024 1 / 45
Recherche des solutions de l’équation non linéaire
f (x) = 0 où f est une fonction donnée

Un des problèmes classiques en mathématiques appliquées est

celui de la recherche des valeurs pour lesquelles une fonction
donnée s’annule. Dans certains cas bien particuliers, comme pour
les fonctions x 7→ x + 1, x 7→ cos(2x) ou encore x 7→ x 2 + 2x + 1, le
problème est simple car il existe pour ces fonctions des formules
qui donnent les zéros explicitement. Toutefois, pour la plupart des
fonctions f : R → R il n’est pas possible de résoudre l’équation
f (x) = 0 explicitement et il faut recourir à des méthodes
numériques. Ainsi par exemple une brève étude de la fonction
f (x) = cos(x) − x montre qu’elle possède un zéro à proximité de 0.7
mais ce zéro ne s’exprime pas au moyen de fonctions usuelles et
pour en obtenir une valeur approchée il faut recourir à des
méthodes numériques.

Introduction 15 mars 2024 2 / 45

Recherche des solutions de l’équation non linéaire
f (x) = 0 où f est une fonction donnée

Soit f : R → R une fonction continue donnée dont on veut évaluer

numériquement un ou plusieurs zéros x̂, c’est-à-dire qu’on cherche
tous les x̂ tels que f (x̂) = 0. Les méthodes numériques pour
approcher x̂ consistent à :
1 localiser grossièrement le (ou les) zéro(s) de f en procédant à
l’étude du graphe de f et/ou à des évaluations qui sont souvent
de type graphique ; on note x0 cette solution grossière ;
2 construire, à partir de x0 , une suite x1 , x2 , x3 , · · · telle que
limk →+∞ xk = x̂ où f (x̂) = 0. On dit alors que la méthode est
convergente.

Introduction 15 mars 2024 3 / 45

Méthode itérative à deux niveaux

Definition
On appelle méthode itérative à deux niveaux un procédé de calcul
de la forme
xk +1 = G(xk ), k = 0, 1, 2, · · ·
dans lequel on part d’une valeur donnée x0 pour calculer x1 , puis à
l’aide de x1 on calcul x2 etc. La formule même est dite formule de
récurrence. Le procédé est appelé convergent si xk tend vers un
nombre fini lorsque k tend vers +∞. Il est bien évident qu’une
méthode itérative n’est utile que s’il y a convergence vers les
valeurs cherchées.

Introduction 15 mars 2024 4 / 45

Ordre de convergence

Definition
Soit p un entier positif. On dit qu’une méthode (à deux niveaux)
convergente est d’ordre p s’il existe une constante C telle que

|x̂ − xk +1 | ≤ C |x̂ − xk |p

ou encore
xk +1 − x̂
lim = C.
p→+∞ (xk − x̂)p
Si p = 1 (et C < 1 ) on parle de convergence linéaire, si p = 2 on
parle de convergence quadratique.

Introduction 15 mars 2024 5 / 45

Etape 1

Definition
Soit f : R → R une fonction. On dit que x̂ est un zéro de f si
f (x̂) = 0. Il est dit simple si f ′ (x̂) ̸= 0, multiple sinon.
Si f est de classe C p avec p ∈ N, on dit que x̂ est un zéro de
multiplicité p si

f (i) (x̂) = 0 ∀i = 0, · · · , p − 1 et f (p) (x̂) ̸= 0.

Pour localiser grossièrement le (ou les) zéro(s) de f on va d’abord

étudier de la fonction f , puis on va essayer d’utiliser un corollaire du
théorème des valeurs intermédiaires et le théorème de la bijection
afin de trouver un intervalle qui contient un et un seul zéro.

Localisation des zéros 15 mars 2024 6 / 45

Etape 1

Theorem
Soit f une fonction continue sur un intervalle I = [a; b] de R. Alors f
atteint toutes les valeurs intermédiaires entre f (a) et f (b). Autrement
dit :
• si f (a) ≤ f (b) alors pour tout d ∈ [f (a), f (b)] il existe c ∈ [a; b] tel
que f (c) = d ;
• si f (b) ≤ f (a) alors pour tout d ∈ [f (b), f (a)] il existe c ∈ [a; b] tel
que f (c) = d ;

Ce théorème donne alors le corollaire immédiat suivant.

Localisation des zéros 15 mars 2024 7 / 45

Etape 1

Corollary
Soit une fonction continue f : [a, b] → R. Si f (a).f (b) < 0, alors il existe
(au moins un) x̂ ∈]a, b[ tel que f (x̂) = 0.

Ce théorème garantit juste l’existence d’un zéro. Pour l’unicité on

essayera d’appliquer le théorème de la bijection dont l’énoncé est
rappelé ci-dessous.

Theorem
Soit f une fonction continue et strictement monotone sur un intervalle I
de R, alors f induit une bijection de Idans f (I). De plus, sa bijection
réciproque est continue sur I, monotone sur I et de même sens de
variation que f .

Localisation des zéros 15 mars 2024 8 / 45

Etape 2

Ayant encadré les zéros de f , la construction de suites qui

convergent vers ces zéros peut se faire à l’aide de plusieurs
méthodes numériques. Ci-dessous on décrit les méthodes les plus
connues et on étudie leurs propriétés (convergence locale vs
globale, vitesse de convergence, etc.)

Construction d’une suite convergente 15 mars 2024 9 / 45

Dichiomie/Lagrange

Dans les méthodes de dichotomie et de LAGRANGE, à chaque pas

d’itération on divise en deux un intervalle donné et on choisit le
sous-intervalle où f change de signe.
Concrètement, soit f : [a, b] → R une fonction strictement
monotone sur un intervalle [a, b]. On suppose que l’équation
f (x) = 0 n’a qu’une et une seule solution dans cet intervalle. On se
propose de déterminer cette valeur avec une précision donnée.
Soit [a0 , b0 ] un intervalle dans lequel f (a0 ).f (b0 ) < 0 et soit
c0 ∈]a0 , b0 [. Si f (a0 ).f (c0 ) < 0, alors la racine appartient à l’intervalle
[a0 , c0 ] et on reprend le procédé avec a1 = a0 et b1 = c0 . Sinon,
c’est-à-dire si f (a0 ).f (c0 ) < 0 on pose a1 = c0 et b1 = b0 . On
construit ainsi une suite d’intervalles emboîtés [ak , bk ]. Les suites ak
et bk sont adjacentes 1 et convergent vers x̂.

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 10 / 45
Dichiomie/Lagrange

Definition
Soit deux points a0 et b0 (avec a0 < b0 ) d’images par f de signe
contraire (i.e. f (a0 ).f (c0 ) < 0). En partant de I0 = [a0 , b0 ], les
méthodes de dichotomie et de LAGRANGE produisent une suite de
sous-intervalles Ik = [ak , bk ], k ≥ 0, avec Ik ⊂ Ik +1 pour k ≥ 1 et tels
que f (ak )f (bk ) < 0.
• Dans la méthode de dichotomie, on découpe l’intervalle [ak ; bk ]
en deux intervalles de même longueur, i.e. on divise [ak , bk ] en
[ak , ck ] et [ck , bk ] où ck est
ak +bk
ck = 2 .

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 11 / 45
Dichiomie/Lagrange

Definition
• Dans la méthode de LAGRANGE, plutôt que de diviser
l’intervalle [ak , bk ] en deux intervalles de même longueur, on
découpe [ak ; bk ] en [ak ; ck ] et [ck , bk ] où ck est l’abscisse du
point d’intersection de la droite passant par (ak , f (ak )) et
(bk , f (bk )) et l’axe des abscisses, autrement dit ck est solution
de l’équation
f (bk )−f (ak )
bk −ak (ck − bk ) + f (bk ) = 0
qui est
bk −ak ak f (bk )−bk f (ak )
ck = bk − f (bk )−f (ak ) f (bk ) = f (bk )−f (ak )

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 12 / 45
Dichiomie/Lagrange

Dans les deux cas, pour l’itération suivante, on pose soit

[ak +1 ; bk +1 ] = [ak ; ck ] soit [ak +1 ; bk +1 ] = [ck ; bk ] de sorte à ce que
f (ak +1 ).f (bk +1 ) < 0. La suite (ck )k ∈N converge vers x̂ puisque la
longueur de ces intervalles tend vers 0 quand k tend vers +∞.
Soit ε l’erreur maximale qu’on peut commettre, les algorithmes
s’écrivent alors comme suit :

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 13 / 45
Dichiomie/Lagrange

On n’est pas obligé de stoker tous les intervalles et les itérées, on

peut gagner de la mémoire en les écrasant à chaque étape :

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 14 / 45
Dichiomie/Lagrange

Avec la méthode de la dichotomie, les itérations s’achèvent à la

m−ème étape quand |xm − x̂| ≤ |Im | < ε, où ε est une tolérance
fixée et |Im | désigne la longueur de l’intervalle Im . Clairement
Ik = b−a
2k
, donc pour avoir une erreur |xm − x̂| < ε, on doit prendre le
plus petit m qui vérifie

ln(b−a)−ln(a)
m ≥ log2 b−a
ε = ln(2)

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 15 / 45
Dichiomie/Lagrange : Exemple

Soit f (x) = −39 − 43x + 39x 2 − 5x 3 . On cherche a estimer x ∈ [1; 5]

tel que f (x) = 0.

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 16 / 45
Dichiomie/Lagrange : Exemple

La méthode de dichotomie est simple mais elle ne garantit pas une

réduction monotone de l’erreur d’une itération à l’autre : tout ce
dont on est assuré, c’est que la longueur de l’intervalle de
recherche est divisée par deux à chaque étape.

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 17 / 45
Dichiomie/Lagrange : Exemple

Par conséquent, si le seul critère d’arrêt est le contrôle de la

longueur de Ik , on risque de rejeter de bonnes approximations de
x̂. En fait, cette méthode ne prend pas suffisamment en compte le
comportement réel de f . Il est par exemple frappant que la
méthode ne converge pas en une seule itération quand f est
linéaire (à moins que le zéro x̂ ne soit le milieu de l’intervalle de
recherche initial).

Méthodes de dichotomie (ou bissection),

Construction d’une suite convergente de Lagrange (ou Regula falsi ) 15 mars 2024 18 / 45
Méthode de la sécante

Soit f : R → R une fonction continue et soit x̂ ∈ [a, b] un zéro de f .

La méthode de la sécante est une variante de la méthode de
LAGRANGE dans laquelle on ne demande plus à ce que le zéro soit
entre ak et bk . Pour calculer xk +1 on prend l’intersection de l’axe
des abscisses avec la droite passant par les points (xk , f (xk )) et
(xk −1 , f (xk −1 )), i.e. on cherche x solution du système linéaire
(
f (xk )−f (xk −1 )
y = xk −xk −1 (x − xk ) + f (xk )
y = 0,

ce qui donne
xk − xk −1
x = xk − f (xk ).
f (xk ) − f (xk −1 )

Construction d’une suite convergente Méthode de la sécante 15 mars 2024 19 / 45

Méthode de la sécante

Definition
Il s’agit d’une méthode à trois niveaux : approcher les zéros de f se
ramène à calculer la limite de la la suite récurrente

 x0
 donné,
x1 donné,
 xk +1 = xk − xk −xk −1 f (xk )

f (xk )−f (xk −1 )
√
1+ 5
Cette méthode a ordre de convergence 2 .

Construction d’une suite convergente Méthode de la sécante 15 mars 2024 20 / 45

Méthode de point fixe

Definition
Soit φ : R → R une fonction. Si x̂ ∈ R est tel que φ(x̂) = x̂, on dit que
x̂ est un point fixe de φ (l’image de x̂ par φ est lui-même).

Précisons ce principe : soit f : [a, b] → R la fonction dont on cherche

le zéro. Il est toujours possible de transformer le problème
• (Pb − 1) : "‘chercher x tel que f (x) = 0"’ en un problème
équivalent (i.e. admettant les mêmes solutions)
• (Pb − 2) :"‘chercher x tel que x − φ(x) = 0."’

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 21 / 45

Méthode de point fixe

Pour que les deux problèmes soient équivalent, la fonction

auxiliaire φ : [a, b] → R doit être choisie de manière à ce que
φ(x̂) = ˆ(x) si et seulement si f (x̂) = 0 dans [a, b] (on dit alors que le
problème (Pb − 2) est consistant avec le problème (Pb − 1)).
Clairement, il existe une infinité de manières pour opérer cette
transformation. Par exemple, on peut poser φ(x) = x + f (x) ou plus
généralement φ(x) = x + γf (x) avec γ ∈ R∗ quelconque. On peut
même remplacer γ par une fonction de x pour autant qu’elle ne
s’annule pas.

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 22 / 45

Méthode de point fixe

Definition
Supposons que x̂ ∈ R soit un point fixe de φ. La méthode de point
fixe consiste en la construction d’une suite (xk )k ∈N définie par
récurrence comme suit :

x0 donné,
xk +1 = φ(xk ) ∀k ∈ N.

Naturellement une telle suite n’est pas forcement convergente. Par

contre, si elle converge, c’est-à-dire si la suite xk a une limite que
nous notons l et si φ est continue, alors cette limite est
nécessairement un point fixe de φ puisque
 
l = lim xk +1 = lim φ(xk ) = φ lim xk = φ(l).
k →+∞ k →+∞ k →+∞

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 23 / 45

Méthode de point fixe

On utilise alors l’algorithme itératif suivant pour construire la suite

(comme l’ordinateur ne peux pas construire une infinité de termes,
on calcul les premiers termes de la suite et on s’arrête dès que la
différence entre deux éléments de la suite est inférieure à une
tolérance ε > 0 donnée) :

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 24 / 45

Méthode de point fixe

On va maintenant s’intéresser à la convergence de la suite

construite par une méthode de point fixe.

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 25 / 45

Convergence (globale) des itérations de point fixe

Theorem
onsidérons une fonction φ : [a; b] → R. On se donne x0 ∈ [a; b] et on
considère la suite xk +1 = φ(xk ) pour k ∈ N Si les deux conditions
suivantes sont satisfaites :
Condition de stabilité : φ(x) ∈ [a, b] pour tout x ∈ [a, b]
condition de contraction stricte : il existe K ∈ [0, 1[ tel que
|φ(x) − φ(y )| ≤ |x − y | pour tout x, y ∈ [a, b] alors
• φ est continue,
• φ a un seul point fixe x̂ dans [a, b],
• la suite xk +1 = φ(xk ) converge vers x̂. pour tout choix de x0 dans
[a, b].

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 26 / 45

Démonstration

Continuité La condition de contraction stricte implique que ’ est

continue puisque, si on prend une suite (yk )k ∈N ⊂ [a, b] qui
converge vers un élément x de [a, b], alors nous avons
|φ(x) − φ(yn )| ≤ |x − yn | et par suite limk →∞ φ(yk ) = φ(x).
Existence Commençons par prouver l’existence d’un point fixe de
φ. La fonction g(x) = φ(x) − x est continue dans [a, b] et, grâce à la
condition de stabilité, on a g(a) = φ(a) − a ≥ 0 et
g(b) = φ(b) − b ≤ 0. En appliquant le théorème des valeurs
intermédiaires, on en déduit que g a au moins un zéro dans [a, b],
i.e. φ a au moins un point fixe dans [a, b].

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 27 / 45

Démonstration
Unicité L’unicité du point fixe découle de la condition de
contraction stricte. En effet, si on avait deux points fixes distincts x̂1
et x̂2 , alors
|x̂1 − x̂2 | = |φ(x̂1 ) − φ(x̂2 )| ≤ K |x̂1 − x̂2 |
ce qui est impossible car K ∈ [0, 1[.
Convergence Prouvons à présent que la suite (xk ) converge vers
l’unique point fixe x̂ quand k tend vers +∞ pour toute donnée
initiale x0 ∈ [a, b]. On a
0 ≤ |xk +1 − x̂| = |φ(xk ) − φ(x̂)| ≤ K |xk − x̂|
où K < 1 est la constante de contraction. En itérant k Å1 fois cette
relation on obtient
|xk +1 − x̂|
≤ K k +1 .
|x0 − x̂|
En passant à la limite quand k tend vers +∞ on obtient |xk +1 − x̂|
tend vers zéro□
Construction d’une suite convergente Méthode de point fixe 15 mars 2024 28 / 45
Théorème d’OSTROWSKI ou de convergence (locale)
des itérations de point fixe

Le théorème de convergence globale assure la convergence, avec

un ordre 1, de la suite (xk )k ∈N vers le point fixe x̂ pour tout choix
d’une valeur initiale x0 ∈ [a; b]. Mais en pratique, il est souvent
difficile de déterminer à priori l’intervalle [a; b] ; dans ce cas, le
résultat de convergence locale suivant peut être utile.

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 29 / 45

Théorème d’OSTROWSKI ou de convergence (locale)
des itérations de point fixe

Theorem
Soit φ : [a; b] → [a; b] une application de classe C 1 ([a; b]). Soit x̂ ∈ [a; b]
un point fixe de φ. On peut distinguer trois cas :
1 Soit |φ′ (x)| < 1. Par continuité de φ′ il existe un intervalle
[x̂ − ε, x̂ + ε] ⊂ [a; b] sur lequel |φ′ (x)| < K < 1, donc (xk )k ∈N est
contractante stricte sur cet intervalle. On a nécessairement
φ ([x̂ − ε, x̂ + ε]) ⊂ [x̂ − ε, x̂ + ε] et par conséquent la suite (xk )k ∈N
converge vers x̂ pour tout x0 ∈ [x̂ − ε, x̂ + ε] . On dit que x̂ est un
point fixe attractif. De plus,
• si 0 < φ(x) < 1 la suite converge de façon monotone, c’est-à-dire
l’erreur xk − x̂ garde un signe constant quand k varie ;
• si −1 < φ(x) < 0 la suite converge de façon oscillante, c’est-à-dire
l’erreur xk − x̂ change de signe selon la parité de k .

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 30 / 45

Suite du théorème

Theorem
2 Si |φ′ (x)| > 1, alors il n’existe aucun intervalle
[x̂ − ε, x̂ + ε] ⊂ [a; b] tel que la suite (xk )k ∈N converge vers x̂ pour
tout x0 ∈ [x̂ − ε, x̂ + ε] à l’exception du cas x0 . On dit que x̂ est un
point fixe répulsif. De plus,
• si φ′ (x) > 1 la suite diverge de façon monotone,
• si φ′ (x) < −1 la suite diverge en oscillant.
3 φ′ (x) = 1 on ne peut en général tirer aucune conclusion : selon le
problème considéré, il peut y avoir convergence ou divergence.

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 31 / 45

Exemple

1 La fonction φ(x) = cos(x) vérifie toutes les hypothèses du

théorème d’OSTROWSKI : elle est de classe C ∞ (R) et
|φ′ (x)| = |sin x| ∼
= 0.67 < 1 donc il existe par continuité un
intervalle [c,d] qui contient x̂ tel que |φ′ (x)| < 1 pour x ∈ [c, d].
La fonction 3
2
√ ϕ(x) = x − x possède
√ deux points fixes
x̂1 = (1 + 5/2) et x̂2 = (1 − 5/2) mais ne vérifie l’hypothèse
du théorème d’OSTROWSKI pour aucun d’eux puisque
ϕ′ x̂1,2 > 1. Les itérations de point fixe ne convergent pas.

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 32 / 45

Remarque

Le théorème d’OSTROWSKI dit que, demanière générale, la

méthode de point fixe ne converge pas pour des valeurs arbitraires
de x0 , mais seulement pour des valeurs suffisamment proches de
x̂, c’est-à-dire appartenant à un certain voisinage de x̂. Au premier
abord, cette condition semble inutilisable : elle signifie en effet que
pour calculer x̂ (qui est inconnu), on devrait partir d’une valeur
assez proche de bx. En pratique, on peut obtenir une valeur initiale
x0 en effectuant quelques itérations de la méthode de dichotomie
ou en examinant le graphe de f . Si x0 est convenablement choisi
alors la méthode de point fixe converge.

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 33 / 45

Calcul de l’ordre de convergence d’une méthode de
point fixe

Theorem
Soit x̂ un point fixe d’une fonction φ ∈ C p+1 pour un entier p ≥ 1 dans
un intervalle [a, b] contenant x̂. Si φ(i) (x̂) = 0 pour 1 ≤ i ≤ p et
φ(p+1) (x) ̸= 0, alors la méthode de point fixe associée à la fonction
d’itération φ est d’ordre p + 1
xk +1 −x̂ φp+1 (x̂)
limk →+∞ (xk −x̂)p+1
= (p+1)! .

Construction d’une suite convergente Méthode de point fixe 15 mars 2024 34 / 45

Démonstration
Ecrivons le développement de TAYLOR avec le reste de LAGRANGE
de φ en x = x̂ :
p
φ(i) (x̂) φ(p+1) (ξ)
(x − x̂)i + (x − x̂)p+1
X
φ(x) = φ (x̂) +
i! (p + 1)!
i=1
où ξ est entre x et x̂. Comme φ(x̂) = x̂ et φ(x̂) = 0 pour 1 ≤ i ≤ p,
cela se simplifie et on a
φ(p+1)(ξ)
φ(x) = x̂ + (xk − x̂)p+1
(p + 1)!
En évaluant l’expression ainsi trouvée en xk et sachant que
φ(xk ) = xk , on a alors
φ(p+1)(ξ)
xk +1 − x̂ = (xk − x̂)p+1
(p + 1)!
Lorsque k → ∞, xk tend vers x̂ et donc ξ, qui se trouve entre xk et
x̂, tend vers x̂ aussi. Alors
x
Construction d’une suite convergente − x̂ φ (p+1)(ξ)
Méthode de point fixe x̂)mars 2024
φ(p+1)(15 35 / 45
Quelques méthodes de points connues

Soit f : [a, b] → R une fonction continue (continûment dérivable

pour la méthode de la corde 2 et la méthode de NEWTON) et soit
bx un zéro de f . Supposons que l’on connaisse une valeur x0
proche de x̂. Approcher les zéros de f se ramène au problème de la
détermination des points fixes de la fonction φ, ce qui se fait en
construisant la suite récurrente

x0 donné, (1)
xk +1 = φ(xk ). (2)

Pour choisir la fonction φ il est nécessaire de prendre en compte

les informations données par les valeurs de f et, éventuellement,
par sa dérivée f ′ ou par une approximation convenable de celle-ci
(si f est différentiable).

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 36 / 45
Quelques méthodes de points connues

Ecrivons pour cela le développement de TAYLOR de f en x̂ au

premier ordre : f (x̂) = f (x) + (x̂ − x)f ′ (ξ) où ξ est entre x̂ et x. Le
problème

chercher x̂ tel que f (x̂) = 0

devient alors

chercher x̂ tel que f (x) + (x̂ − x)f ′ (ξ) = 0.

Cette équation conduit à la méthode itérative suivante :

pour tout k ≥ 0, étant donné xk , déterminer xk +1 en résolvant

l’équation f (xk ) + (xk +1 − xk )qk = 0, où qk est égal à f ′ (ξk ) (ou en est
une approximation) avec ξk un point entre xk et xk +1 .

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 37 / 45
Quelques méthodes de points connues

La méthode qu’on vient de décrire revient à chercher l’intersection

entre l’axe des x et la droite de pente qk passant par le point
(xk , f (xk )), ce qui s’écrit sous la forme d’une méthode de point fixe
avec
f (xk )
xk +1 = φ (xk ) ≡ xk − , k ≥ 0.
qk
Considérons maintenant quatre choix particuliers de qk et donc de
φ qui définissent des méthodes célèbres :
b−a
• Méthode de la Corde 1 : qk = f (b)−f b−a
(a) ; φ(x) = x − f (b)−f (a) f (x)
f (x)
• Méthode de la Corde 2 : qk = f ′ (x0 ) ; φ(x) = x − f ′ (x0 )
f (x)
• Méthode de Newton qk = f ′ (xk ) , φ(x) = x − f ′ (x)

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 38 / 45
Quelques méthodes de points connues

Theorem
Si la méthode de la corde converge, elle converge à l’ordre 1 ; si la
méthode de Newton converge, elle converge à l’ordre 2 si la racine est
simple, à l’ordre 1 sinon.

Attention À noter que même si la méthode de Newton permet en

général d’obtenir une convergence quadratique, un mauvais choix
de la valeur initiale peut provoquer la divergence de cette méthode
(notamment si la courbe représentative de f présente au point
d’abscisse x0 un tangente à peu près horizontale). D’où
l’importance d’une étude préalable soignée de la fonction f (cette
étude est d’ailleurs nécessaire pour toute méthode de point fixe).

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 39 / 45
Quelques méthodes de points connues

Soit f : R → R une fonction continûment dérivable et soit x̂ un zéro

simple de f , c’est-à-dire f (x̂) = 0 et f ′ (x̂) ̸= 0. Supposons que l’on
connaisse une valeur xk proche de x̂. Pour calculer xk +1 on prend
l’intersection de l’axe des abscisses avec la droite tangente au
graphe de f passant par le point (xk , f (xk )), i.e. on cherche x
solution du système linéaire

y = f ′ (xk )(x − xk ) + f (xk ),

y = 0.

On obtient
f (x)
x = xk −
f ′ (x)
ce qui correspond à laméthode de NEWTON.

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 40 / 45
Quelques méthodes de points connues

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 41 / 45
Critéres d’arrêt

Supposons que (xn )n∈N soit une suite qui converge vers x̂ zéro de la
fonction f . Nous avons le choix entre deux types de critères d’arrêt
pour interrompre le processus itératif d’approximation de x̂ : ceux
basés sur le résidu et ceux basés sur l’incrément. Nous
désignerons par ε une tolérance fixée pour le calcul approché de x̂
et par en en = x − xn l’erreur absolue.
Nous supposerons de plus f continûment différentiable dans un
voisinage de la racine.

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 42 / 45
Critéres d’arrêt

Contrôle du résidu : les itérations s’achèvent dès que |f (xn )| < ε.

Il y a des situations pour lesquelles ce test s’avère trop restrictif ou,
au contraire, trop optimiste.
• si |f (xn )| ≈ 1 alors |en | ≈ 1 : le test donne donc une indication
satisfaisante de l’erreur ;
• si |f (xn )| ≺≺ 1 si le test n’est pas bien adapté car |en | peut être
assez grand par rapport à ε (voir la figure 1.2 à droite) ;
• si enfin |f (xn )| ≻≻ 1 alors |en | ≺≺ 1 et le test est trop restrictif
(voir la figure 1.2 à gauche).

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 43 / 45
Critéres d’arrêt

Contrôle de l’incrément : les itérations s’achèvent dès que

|xn+1 − xn | < ε. Soit (xn )n∈N la suite produite par la méthode de
point fixe xn+1 = φ(xn ). Comme x̂ = φ(x̂) et xn+1 = φ(xn ), si on
développe au premier ordre on sait qu’il existe ξn ∈ Ix̂,xn (l’intervalle
d’extrémités x̂ et xk ) tel que

en+1 = x̂ − xn+1 = φ(x̂) − φ(xn ) = φ′ (ξn )(x̂ − xn ) = φ′ (ξn )en

En utilisant l’identité

en = (x̂ −xn+1 )+(xn+1 −xn ) = en+1 +(xn+1 −xn ) = φ′ (ξn )en +(xn+1 −xn )

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 44 / 45
Critéres d’arrêt

on en déduit que
xn+1 − xn
en = .
1 − φ′ (ξn )
Par conséquent, ce critère fournit un estimateur d’erreur
satisfaisant si φ′ (x) ∼
= 0 dans un voisinage de x̂. C’est le cas
notamment des méthodes d’ordre 2, dont la méthode de NEWTON.
Cette estimation devient d’autant moins bonne que φ′ s’approche
de 1. Notons d’ailleurs que si la méthode de point fixe converge
avec K < 1 et si on considère le critère d’arrêt |xn+1 − xn | < ε alors
ε
|en | = |xn − x̂| ≤ ≤ 2ε.
1−K

Méthodes de point fixe particulièrement

Construction d’une suite convergente connues 15 mars 2024 45 / 45