Résolution numérique de l'équation f ( x ) = 0

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Ce document, destiné à des étudiants de L3, explique quelques méthodes permettant de trouver numériquement les zéros de fonctions d'une variable réelle.

I Introduction

II Méthode de dichotomie

III Méthode de point fixe

IV Méthode de Newton

V Méthode de Lagrange

VI Bibliographie

VII Exercices

Vous trouverez ici le fichier pdf doczero.pdf

I Introduction

Résolution numérique de l'équation f ( x ) = 0 → I Introduction

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

I-1 Préambule

I-2 Exemple motivant: équation d'état d'un gaz

I-3 Rappels d'analyse

I-4 Critère d'arrêt pour la résolution numérique de f(x) = 0

I-1 Préambule

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-1 Préambule

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

L'étude générale des fonctions à variables réelles nécessite de temps à autre la résolution d'équations de type

f (x) = 0

. Autrement dit, nous sommes amenés à trouver les zéros de fonctions non linéaires, c'est-à-dire les valeurs réelles alpha

telles que

f (α) = 0,

ou, ce qui est équivalent, à résoudre une équation de type

g (x) = x .

I-2 Exemple motivant: équation d'état d'un gaz

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-2 Exemple motivant: équation d'état d'un gaz

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

On veut déterminer le volume

V

occupé par un gaz de température

T

et de pression

p

. L'équation d'état (c'est-à-dire l'équation qui lie

p, V

T

) est :

[p + a {(\frac{N}{V})}^{2}] (V - N b) = k N T

où

a

b

sont deux coefficients dépendants de la nature du gaz,

N

le nombre de molécules contenues dans le volume

V

k

la constante de Boltzmann. Il faut donc résoudre une équation non linéaire d'inconnue

V

. Ceci revient à trouver les zéros de la fonction :

f (V) = [p + a {(\frac{N}{V})}^{2}] (V - N b) - k N T .

Dans le cas le plus général, il s'agit de résoudre une équation non linéaire dont on n'est pas capable de trouver une solution exacte. Dans ce cas, on dispose de quelques méthodes numériques exécutables sur des logiciels comme Matlab, Maple, Octave, Scilab pour approximer la solution exacte. Ces méthodes numériques sont toutes basées sur la construction d'une suite

{(x_{n})}_{n \in ℕ}

convergeant vers un réel alpha

vérifiant

f (α) = 0

.
Dans ce document, nous allons traiter quatre méthodes: la méthode de dichotomie, de point fixe, de Newton et de Lagrange. Pour le faire, nous avons besoin de quelques rappels d'analyse.

I-3 Rappels d'analyse

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Une équation de type

f (x) = 0

peut être écrite d'une manière équivalente sous la forme de

g (x) = x

. La fonction

g

est une fonction dépendante de

f

non unique comme le montre l'exemple suivant :
Exemple

f (x) = \sin (2 x) - 1 + x = 0,

la fonction

g

peut être

g (x) = 1 - \sin (2 x), x \in ℝ

g (x) = \frac{1}{2} \arcsin (1 - x), 0 \leq x \leq 1 .

Les instructions Matlab suivantes permettent de tracer les représentations graphiques de ces fonctions, y compris celle de la droite

y = x

:
Code Matlab

x = 0:0.001:1;
f = inline('sin(2*x)-1 + x');
g1 = inline('1-sin(2*x)');
g2 = inline('1/2*(asin(1-x))');
h = inline('x');
plot(x, f(x), '--.b',  x, g1(x), '-.b', x, g2(x), '--b', x, h(x),'b');
legend('f', 'y=1-sin(2x)', 'y=1/2*(Arcsin(1-x))', 'y=x');
grid on;
ylabel('y(x)');
xlabel('x');

On voit bien que

f

admet un unique zéro

α \in [0, 1]

et que les graphes des fonctions

y = x, y = 1 - \sin (2 x), et y = 1 / 2 (\arcsin (1 - x))

se coupent en

(α, α)

I-3-1 Point fixe

I-3-2 Multiplicité d'une racine, fonction contractante

I-3-3 Théorème de point fixe

I-3-4 Fonctions convexes

I-3-5 Vitesse de convergence d'une suite

I-3-1 Point fixe

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-1 Point fixe

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Définition

Un réel

l \in [a, b]

est dit point fixe d'une fonction

g : [a, b] ⟶ ℝ

g (l) = l

I-3-2 Multiplicité d'une racine, fonction contractante

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-2 Multiplicité d'une racine, fonction contractante

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Définition

Soit

p

un entier et

f

une fonction

p

fois dérivable.

On dit que est un zéro de $f$ de multiplicité $p$ si
$f (α) = f^{(1)} (α) = . . . = f^{(p - 1)} (α) = 0 et f^{(p)} (α) \neq 0 .$
Un zéro de multiplicité $1$ (respectivement $2$ ) est appelé un zéro simple (respectivement double ).

Définition

Soit

k \in] 0, 1 [

. Une fonction

g : [a, b] ⟶ ℝ

est dite fonction contractante de rapport

k

\forall x, y \in [a, b], ∣ g (x) - g (y) ∣ \leq k ∣ x - y ∣

Remarque

Soit $g \in 𝒞^{1} ([a, b])$ . Si
$∣ g' (x) ∣ < 1, \forall x \in [a, b],$
alors $g$ est contractante sur $[a, b]$ .
Une fonction contractante est continue.

I-3-3 Théorème de point fixe

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-3 Théorème de point fixe

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Théorème

Soit

g : [a, b] ⟶ [a, b]

une fonction contractante de rapport

k

. Alors

g

admet un unique point fixe

l \in [a, b]

. De plus, pour tout choix de

x_{0} \in [a, b],

la suite définie par

x_{n + 1} = g (x_{n}), \forall n \geq 0

converge vers

l

quand

n ⟶ + ∞

Démonstration

Etape 1: Existence de l et convergence de la suite Remarquons d'abord que

g ([a, b]) \subset [a, b]

ce qui implique que la suite

(x_{n})

est bien définie. Soit

x_{0}

dans

[a, b]

x_{n + 1} = g (x_{n}), \forall n \geq 0

. Nous allons montrer:

$(x_{n})$ est de Cauchy (donc convergente, car $[a, b]$ est complet)
$x_{n} ⟶ l$ quand $n ⟶ + ∞,$ où $l$ est un point fixe de $g$ .

Par hypothèse, on sait que

\forall n \geq 1, ∣ x_{n} - x_{n + 1} ∣ = ∣ g (x_{n - 1}) - g (x_{n}) ∣ \leq k ∣ x_{n - 1} - x_{n} ∣ .

Par récurrence sur

n,

on obtient:

∣ x_{n} - x_{n + 1} ∣ \leq k^{n} ∣ x_{0} - x_{1} ∣, \forall n \geq 0 .

Soit

n \geq 0

p \geq 1,

on a donc:

\begin{matrix} ∣ x_{n + p} - x_{n} ∣ & \leq & ∣ x_{n + p} - x_{n + p - 1} ∣ + \dots + ∣ x_{n + 1} - x_{n} ∣ \\ \leq & \sum_{q = 1}^{p} ∣ x_{n + q} - x_{n + q - 1} ∣ \\ (*) & \leq & \sum_{q = 1}^{p} k^{n + q - 1} ∣ x_{1} - x_{0} ∣ \\ \leq & ∣ x_{1} - x_{0} ∣ k^{n} (1 + k + \dots + k^{p - 1}) \\ \leq & ∣ x_{1} - x_{0} ∣ \frac{k^{n}}{1 - k} ⟶ 0 quand n ⟶ + ∞ car k < 1 \end{matrix}

La suite

(x_{n})

est donc de Cauchy dans

[a, b]

qui est complet et par conséquent

(x_{n})

converge vers une limite

l

quand

n ⟶ + ∞

. Comme la fonction

g

est contractante, elle est continue, et donc

g (x_{n}) ⟶ g (l)

quand

n ⟶ + ∞

. En passant à la limite dans l'égalité:

x_{n + 1} = g (x_{n}),

on en déduit que

l = g (l),

c'est à dire que

l

est un point fixe de

g

.
Etape 2: Unicité
Soient

l_{1}

l_{2}

deux points fixes de

g,

donc

l_{1} = g (l_{1}) et l_{2} = g (l_{2}),

alors

∣ g (l_{1}) - g (l_{2}) ∣ = ∣ l_{1} - l_{2} ∣ \leq k ∣ l_{1} - l_{2} ∣

; comme

k < 1,

ceci est impossible sauf si

l_{1} = l_{2}

Remarque

g

est une application vérifiant

{\begin{matrix} g ([a, b]) \subset [a, b] \\ ∣ g' (x) ∣ < 1, \forall x \in [a, b] \end{matrix}

alors la suite définie par

x_{n + 1} = g (x_{n}), \forall n \geq 0

converge vers l'unique point fixe

l

g

sur

[a, b]

pour tout choix de

x_{0} \in [a, b]

. De plus en faisant tendre

p

vers l'infini dans

(*)

et en gardant

n,

on obtient:

∣ x_{n} - l ∣ \leq ∣ x_{1} - x_{0} ∣ \frac{k^{n}}{1 - k}, \forall n \in ℕ avec k = \max_{x \in [a, b]} ∣ g' (x) ∣

I-3-4 Fonctions convexes

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-4 Fonctions convexes

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Définition [fonction convexe]

Soit

I

un intervalle de

ℝ

. Une fonction

f : I ⟶ ℝ

est dite convexe sur I si

\forall λ \in [0, 1], \forall x, y \in I, f (λ x + (1 - λ) y) \leq λ f (x) + (1 - λ) f (y)

Si l'inégalité est stricte,

f

est dite strictement convexe .

Proposition

I = [a, b], α \in] a, b [et f : I ⟶ ℝ

convexe, alors la fonction

Φ_{α} : x ⟶ Φ_{α} (x) = \frac{f (x) - f (α)}{x - α}

est croissante sur

I ∖ {α}

Proposition

f : I \subset ℝ ⟶ ℝ

est deux fois dérivable, alors:

f^{(2)} \geq 0 ⟹ f convexe

f^{(2)} > 0 ⟹ f strictement convexe

Définition

On dit que

f : I \subset ℝ ⟶ ℝ

est concave sur I si

(- f)

est convexe sur

I

I-3-5 Vitesse de convergence d'une suite

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-3 Rappels d'analyse → I-3-5 Vitesse de convergence d'une suite

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Définition

Soit

(x_{n})_{n \in ℕ}

une suite convergente vers alpha

. On appelle ordre de convergence de la suite

(x_{n})

le réel fini ou infini

r > 0

défini par:

r = \sup {s \in ℝ_{+} tel que \lim_{n ⟶ + ∞} \frac{∣ x_{n + 1} - α ∣}{∣ x_{n} - α ∣^{s}} < ∞}

Si $r = 2$ , on dit que la convergence de $(x_{n})$ est quadratique .
Si $r = 3$ , on dit que la convergence de $(x_{n})$ est cubique .
Supposons que l'ordre de convergence de la suite $(x_{n})$ est $r = 1$ et que:
$\lim_{n ⟶ + ∞} \frac{∣ x_{n + 1} - α ∣}{∣ x_{n} - α ∣} = k \leq 1$
1. Si $0 < k < 1$ on dit que la suite $(x_{n})$ est à convergence linéaire .
2. Si $k = 0$ on dit que la suite $(x_{n})$ est à convergence super-linéaire .
3. Si $k = 1$ on dit que la suite $(x_{n})$ est à convergence logarithmique .

Exemple

Soit

a \in ℝ_{+}^{*}

. Soit la suite récurrente

(x_{n})_{n \in ℕ}

définie par

{\begin{matrix} x_{0} & = & 3 \\ x_{n + 1} & = & g (x_{n}) \end{matrix}

avec

g (x) = \frac{1}{2} (x + \frac{a}{x}) .

La suite

(x_{n})

converge vers

\sqrt{a}

et son ordre de convergence est égal à

2

. En effet:

\frac{x_{n + 1} - \sqrt{a}}{(x_{n} - \sqrt{a})^{2}} = \frac{x_{n}^{2} + a - 2 {\sqrt{ax}}_{n}}{2 (x_{n} - \sqrt{a})^{2} x_{n}} ⟶ \frac{1}{2 \sqrt{a}} quand n ⟶ + ∞

\frac{x_{n + 1} - \sqrt{a}}{(x_{n} - \sqrt{a})^{3}} ⟶ + ∞ quand n ⟶ + ∞

I-4 Critère d'arrêt pour la résolution numérique de f(x) = 0

Résolution numérique de l'équation f ( x ) = 0 → I Introduction → I-4 Critère d'arrêt pour la résolution numérique de f(x) = 0

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Une fois construite la suite

(x_{n})

convergeant vers

l

vérifiant

g (l) = l,

quand peut-on arrêter les itérations de l'algorithme numérique si l'on désire déterminer une valeur approchée de

l

avec une tolérance varepsilon

fixée à l'avance. Un bon critère d'arrêt est le contrôle de l'incrément :

On constate la convergence : les résultats numériques se stabilisent.
On s'arrête à l'itération $n_{0}$ si on peut montrer théoriquement que:
$\forall n \geq n_{0}, ∣ x_{n + 1} - x_{n} ∣ < ε$

Exemple

Soit

f (x) = x^{3} - 4 x + 1

. On vérifie que

f

admet

3

racines réelles

l_{1} \in [- 2.5, - 2]

l_{2} \in [0, 0.5]

l_{3} \in [1.5, 2]

en posant

g (x) = x - \frac{x^{3} - 4 x + 1}{3 x^{2} - 4} = \frac{2 x^{3} - 1}{3 x^{2} - 4}

Un simple calcul donne les valeurs suivantes:

$x_{0}$	-2	0	2
$x_{1}$	-2.125	0.25	1.875
$x_{2}$	-2.114975450	0.254098301	1.860978520
$x_{3}$	-2.114907545	0.254101688	1.860805877
$x_{4}$	-2.114907541	0.254101688	1.860805853
$x_{5}$	-2.114907541	0.254101688	1.860805853
$x_{6}$
$x_{7}$
$x_{8}$

On constate que les valeurs numériques se stabilisent et on a alors les valeurs approchées de

l_{1},

l_{2}

l_{3}

à environ

10^{- 9}

près.

II Méthode de dichotomie

Résolution numérique de l'équation f ( x ) = 0 → II Méthode de dichotomie

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

II-1 Principe

II-2 Etude de la convergence

II-3 Test d'arrêt

II-1 Principe

Résolution numérique de l'équation f ( x ) = 0 → II Méthode de dichotomie → II-1 Principe

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Considérons une fonction

f

continue sur un intervalle

[a, b]

. On suppose que

f

admet une et une seule racine alpha

dans

] a, b [

et que

f (a) f (b) < 0

. On note

c = \frac{a + b}{2}

le milieu de l'intervalle.

Si $f (c) = 0,$ c'est la racine de $f$ et le problème est résolu.
Si $f (c) \neq 0,$ nous regardons le signe de $f (a) f (c)$ .
1. Si $f (a) f (c) < 0,$ alors $α \in] a, c [$
2. Si $f (c) f (b) < 0,$ alors $α \in] c, b [$

On recommence le processus en prenant l'intervalle

[a, c]

au lieu de

[a, b]

dans le premier cas, et l'intervalle

[c, b]

au lieu de

[a, b]

dans le second cas. De cette manière, on construit par récurrence sur

n

trois suites

(a_{n})

(b_{n})

(c_{n})

telles que

a_{0} = a, b_{0} = b

et telles que pour tout

n \geq 0

$c_{n} = \frac{a_{n} + b_{n}}{2}$
Si $f (c_{n}) f (b_{n}) < 0$ alors $a_{n + 1} = c_{n}$ et $b_{n + 1} = b_{n}$ .
Si $f (c_{n}) f (a_{n}) < 0$ alors $a_{n + 1} = a_{n}$ et $b_{n + 1} = c_{n}$ .

L'algorithme ci-dessus s'appelle l'algorithme de dichotomie .

II-2 Etude de la convergence

Résolution numérique de l'équation f ( x ) = 0 → II Méthode de dichotomie → II-2 Etude de la convergence

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Théorème

Soit

f

une fonction continue sur

[a, b],

vérifiant

f (a) f (b) < 0

et soit

α \in [a, b]

l'unique solution de l'équation

f (x) = 0

. Si l'algorithme de dichotomie arrive jusqu'à l'étape

n

alors on a l'estimation:

∣ α - c_{n} ∣ \leq \frac{b - a}{2^{n + 1}} .

Par conséquent, la suite

(c_{n})

converge vers alpha

. C'est aussi vrai si

(c_{n}) = α

Démonstration

Il suffit de remarquer qu'à chaque itération, on divise l'intervalle par deux.

II-3 Test d'arrêt

Résolution numérique de l'équation f ( x ) = 0 → II Méthode de dichotomie → II-3 Test d'arrêt

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Pour que la valeur de

c_{n}

de la suite à la

n

-ième itération soit une valeur approchée de alpha

ε > 0

près, il suffit que

n

vérifie:

\frac{b - a}{2^{n + 1}} \leq ε

On a alors:

∣ α - c_{n} ∣ \leq \frac{b - a}{2^{n + 1}} \leq ε

ce qui permet de calculer à l'avance le nombre maximal

n_{0} \in ℕ

d'itérations assurant la précision varepsilon

\frac{b - a}{2^{n + 1}} \leq ε ⟺ \frac{b - a}{ε} \leq 2^{n + 1} ⟺ n \geq \frac{\log \frac{b - a}{ε}}{\log (2)} - 1

Exemple

On considère la fonction

f (x) = \exp (x) + 3 \sqrt{x} - 2

sur l'intervalle

[0, 1]

. Le code Matlab suivant trace le graphe de

f

.
Code Matlab

x = 0:0.001:1;
f = inline('exp(x)+3*sqrt(x)-2');
plot(x, f(x))
grid on;
ylabel('f(x)');
xlabel('x');
title('graphe de f');

La figure montre que

f

admet un unique zéro

α \in [0, 1]

. Si on veut utiliser la méthode de dichotomie pour estimer alpha

à une tolérance

ε = 10^{- 10}

près, il nous faut au plus 33 itérations. En effet, la suite

(x_{n})

qui approche alpha

vérifie

∣ x_{n} - α ∣ \leq \frac{1}{2^{n + 1}}

\frac{1}{2^{n + 1}} \leq 10^{- 10} ⟹ n \geq 10 \frac{\log (10)}{\log (2)} - 1 \approx 33 .

Vérification numérique. Le code Matlab suivant permet de calculer la valeur de

n

nécessaire pour atteindre la précision

ε = 10^{- 10}

en choisissant

a = 0

b = 1

.
Code Matlab

g = inline('exp(t) + 3*sqrt(t)-2');
Nit = 0;
epsilon = 1e-10;
borneinf = 0;
bornesup = 1;
pmilieu = (borneinf + bornesup)/2;


while and(g(pmilieu) ~= 0, (bornesup-borneinf) >= epsilon )
    Nit = Nit+1;
    if g(pmilieu)*g(borneinf) < 0
        bornesup = pmilieu;
    else
       borneinf = pmilieu;
    end
    pmilieu = (borneinf + bornesup)/2;
end
pmilieu
g(pmilieu)
Nit - 1
n_theorique = 10*log(10)/log(2) - 1

Résultats

α = 0.0910

f (α) = - 8.9593 e - 12

n_{numerique} = 33

n_{theorique} = 10 \log (10) / \log (2) - 1 = 32.2193

Exemple

Si nous reprenons l'exemple précédent avec la fonction

f (x) = 10 x - 5

, nous obtenons les résultats suivants:

α = 0.5000

f (α) = 0

n_{numerique} = 0

n_{theorique} = 10 \log (10) / \log (2) - 1 = 32.2193

On voit alors qu'on atteint la racine alpha

sans aucune itération, ce qui montre contrairement à l'exemple précédent que la majoration du théorème ci-dessus est parfois assez large.

Exercice

Méthode de dichotomie

III Méthode de point fixe

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

III-1 Principe

III-2 Point attractif

III-3 Point répulsif

III-4 Point douteux

III-5 Ordre de convergence

III-6 Test d'arrêt

III-1 Principe

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-1 Principe

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Le principe de cette méthode consiste à transformer l'équation

f (x) = 0

en une équation équivalente

g (x) = x

où

g

est une fonction auxiliaire "bien" choisie. Le point alpha

est alors un point fixe de

g

. Approcher les zéros de

f

revient à approcher les points fixes de

g

. Le choix de la fonction

g

est motivé par les exigences du théorème de point fixe. En effet, elle doit être contractante dans un voisinage

I

, ce qui revient à vérifier que

∣ g' (x) ∣ < 1

sur ce voisinage. Dans ce cas, on construit une suite

{(x_{n})}_{n \in ℕ}

définie par:

{\begin{matrix} x_{0} dans un voisinage I de α \\ \forall n \geq 0, x_{n + 1} = g (x_{n}) \end{matrix}

Il ne reste plus qu'à appliquer localement le théorème de point fixe pour démontrer que

α = \lim_{n ⟶ + ∞} x_{n} .

C'est l'objet du paragraphe suivant:
Exercice

Méthode de point fixe

III-2 Point attractif

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-2 Point attractif

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

III-2-1 Théorème de convergence

III-2-2 Illustration graphique

III-2-3 Intervalle de convergence

III-2-1 Théorème de convergence

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-2 Point attractif → III-2-1 Théorème de convergence

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Théorème

Soit

g : I = [a, b] ⟶ [a, b]

de classe

𝒞^{1}

. On suppose que

g

admet un point fixe

α \in [a, b]

vérifiant

∣ g' (α) ∣ < 1

. Alors il existe un voisinage

V_{α}

dans

I

tel que la suite

(x_{n})

définie par :

{\begin{matrix} x_{0} \in V_{α} \\ x_{n + 1} = & g (x_{n}), \forall n \geq 0 \end{matrix}

converge vers alpha

Démonstration

Comme

∣ g' (α) ∣ < 1,

il existe

k \neq 0

tel que

∣ g' (α) ∣ \leq k < 1

. De plus,

g'

est continue sur

I

donc il existe un voisinage

V_{α} = [α - h, α + h] \subset I (h > 0)

tel que

\forall x \in V_{α}, ∣ g' (x) ∣ \leq k < 1 .

Donc

g

est

k

-contractante sur

V_{α}

. En particulier,

g (x) \in V_{α}

. Le théorème de point fixe appliqué localement à

g

dans le voisinage

V_{α}

implique que

\forall x_{0} \in V_{α}, \lim_{n ⟶ + ∞} x_{n} = α

Définition

Le réel

vérifiant les hypothèses du théorème précédent est appelé point fixe attractif de

g

et le voisinage

V_{α}

correspondant est dit intervalle de convergence de la méthode d'approximation.

III-2-2 Illustration graphique

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-2 Point attractif → III-2-2 Illustration graphique

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Code Matlab

x = 1.3:0.001:2.3;
plot(x, log(x)+1.1, '-', x, x, '--')
grid on;
ylabel('y');
xlabel('x');
title('Cas d''un point fixe attractif');

Exercice

Nature d'un point fixe

III-2-3 Intervalle de convergence

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-2 Point attractif → III-2-3 Intervalle de convergence

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Proposition

En pratique, un intervalle de convergence

V_{α}

peut être calculé comme suit:

Si $0 \leq g' (α) < 1$ , prendre comme intervalle de convergence
$V_{α} = [β, γ]$
contenant tel que
$0 \leq g' (x) < 1, \forall x \in [β, γ] .$
Si $- 1 < g' (α) < 0$ , prendre comme intervalle de convergence
$V_{α} = [β, g (β)]$
tel que
$- 1 < g' (x) < 0, \forall x \in [β, g (β)] .$

Démonstration

Cas où $0 \leq g' (α) < 1$ . D'après la continuité de $g',$ il existe $[β, γ]$ contenant tel que
$0 \leq g' (x) < 1, \forall x \in [β, γ] .$
On a alors
$g ([β, γ]) \subset [β, γ] .$
En effet, comme $g$ est croissante sur $[β, γ]$ , on a:
$g ([β, γ]) = [g (β), g (γ)] .$
D'autre part, on a
$α - g (β) = g (α) - g (β) = (α - β) g' (ξ), ξ \in] β, γ [.$
Comme $g' (ξ) \in [0, 1 [$ ,
$0 \leq α - g (β) \leq (α - β)$
ce qui donne $g (β) \geq β$ . Donc $α - β \geq 0$ . De plus,
$g (γ) - α = g (γ) - g (α) = (γ - α) g' (ν), ν \in] α, γ [.$
Comme $g' (ν) \in [0, 1 [$ ,
$0 \leq g (γ) - α \leq (γ - α),$
ce qui donne $g (γ) \leq γ$ .
D'où $g ([β, γ]) \subset [β, γ]$ . De plus:
- si $x_{0} < α$ , alors $(x_{n})$ est croissante convergeant vers ;
- si $x_{0} > α$ , alors $(x_{n})$ est décroissante convergeant vers
Cas où $- 1 < g' (α) < 0$ . D'après la continuité de $g',$ il existe un voisinage $[β, γ]$ de tel que
$- 1 < g' (x) < 0, \forall x \in [β, γ],$
et $γ = g (β) .$ Les réels et sont nécessairement de part et d'autre de : $β < α < γ$ ou $γ < α < β$ . En effet, on a
$γ - α = g (β) - g (α) = (β - α) g' (ξ), ξ \in] β, α [.$
Comme $g' (ξ) \in] - 1, 0 [$ , $γ - α$ et $β - α$ sont de signes contraires, ce qui prouve le résultat.
Montrons que si $x_{0} \in [β, γ]$ , alors
$x_{n} \in [β, γ], \forall n \in ℕ .$
On suppose que $β < γ$ ; on a $x_{0} \in [β, γ]$ , ce qui implique que $β \leq x_{0}$ , puis que
$γ = g (β) \geq g (x_{0}) = x_{1} .$
D'où $x_{1} \in [β, γ]$ . Soit $n \in ℕ,$ en supposant que $x_{n}$ et $x_{n - 1}$ appartiennent à $[β, γ]$ , on montre de la même façon que
$x_{n + 1} \in [β, γ] .$

On conclut donc que
$\forall n \in ℕ, x_{n} \in [β, γ] .$

Remarquons finalement que est toujours entre deux termes successifs de la suite $(x_{n})$ . On dit que $(x_{n})$ encadre . Par conséquent si $∣ x_{n} - x_{n - 1} ∣ \leq ε,$ $∣ x_{n} - α ∣ \leq ε$ .

III-3 Point répulsif

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-3 Point répulsif

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

III-3-1 Théorème de non-convergence

III-3-2 Illustration graphique

III-3-3 Remarque sur la convergence

III-3-1 Théorème de non-convergence

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-3 Point répulsif → III-3-1 Théorème de non-convergence

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Théorème

Soit

g : I = [a, b] ⟶ [a, b]

de classe

𝒞^{1}

. On suppose que

g

admet un point fixe

α \in [a, b]

vérifiant

∣ g' (α) ∣ > 1

. Alors il existe un voisinage

V_{α}

dans

I

tel que la suite

(x_{n})

définie par:

{\begin{matrix} x_{0} \in V_{α} ∖ {α} \\ x_{n + 1} = g (x_{n}); & \forall n \geq 0 \end{matrix}

ne converge pas vers alpha

Démonstration

Comme

\lim_{x ⟶ α} ∣ \frac{g (x) - g (α)}{x - α} ∣ = ∣ g' (α) ∣ > 1,

il existe un voisinage

V_{α} = [α - h, α + h] \subset I,

avec

h > 0

tel que

\forall x \in V_{α} ∖ {α}, ∣ g (x) - α ∣ > ∣ x - α ∣

. Donc

(x_{n})

ne converge pas vers alpha

Définition

Le réel

vérifiant les hypothèses du théorème précédent est appelé point fixe répulsif de

g

III-3-2 Illustration graphique

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-3 Point répulsif → III-3-2 Illustration graphique

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Code Matlab

x = 1:0.0001:2;
plot(x, exp(x)-2, '-', x, x, '--')
grid on;
ylabel('y');
xlabel('x');
title('Cas d''un point fixe repulsif')

III-3-3 Remarque sur la convergence

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-3 Point répulsif → III-3-3 Remarque sur la convergence

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Remarque

Lorsque

est un point répulsif de

g,

celle-ci devient bijective au voisinage de alpha

∣ (g^{- 1})' (α) ∣ = \frac{1}{∣ g' (α) ∣} < 1

. Par conséquent, le point alpha

devient un point attractif pour

g^{- 1}

. En effet, si

∣ g' (α) ∣ > 1

alors

g

est strictement monotone au voisinage de alpha

Exercice

Différents types de points fixes

III-4 Point douteux

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-4 Point douteux

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

III-4-1 Définition

III-4-2 Exemple1

III-4-3 Exemple2

III-4-1 Définition

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-4 Point douteux → III-4-1 Définition

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Définition

Soit

g : I = [a, b] ⟶ [a, b]

de classe

𝒞^{1}

pour laquelle alpha

est un unique point fixe vérifiant

∣ g' (α) ∣ = 1

. Alors

est appelé point douteux de

g,

car il peut être attractif ou répulsif comme le montre les deux exemples suivants:

III-4-2 Exemple1

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-4 Point douteux → III-4-2 Exemple1

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Exemple

Soit la fonction

g

définie par

g (x) = \sin x, x \in [0, \frac{π}{2}]

. On a

\forall x \in] 0, \frac{π}{2}], \sin x < x

et pour tout

x_{0} \in] 0, \frac{π}{2}],

la suite itérée

(x_{n})

définie par

x_{n + 1} = g (x_{n})

est strictement décroissante minorée par

0

donc convergeant vers une limite alpha

. Comme

g

est continue et que

α = g (α), α = 0

est l'unique point fixe de

g

sur

[0, \frac{π}{2}]

Illustration graphique
Code Matlab

x = -pi/2:0.0001:pi/2;
g = inline('sin(x)');
plot(x, g(x), '--', x, x, '-')
grid on;
ylabel('g(x)');
xlabel('x');
axis on;
title('graphe de g');

III-4-3 Exemple2

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-4 Point douteux → III-4-3 Exemple2

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Exemple

Soit la fonction

g (x) = \sinh x, x \in [0, + ∞]

. On a

\sinh x > x

et pour tout

x_{0} \in] 0, + ∞ [,

la suite itérée

(x_{n})

définie par

x_{n + 1} = g (x_{n})

est strictement croissante et non majorée donc divergente. Par conséquent, le point fixe

α = 0

g

est répulsif.

Illustration graphique
Code Matlab

x = -1:0.0001:2;
g = inline('sinh(x)');
plot(x, g(x), '--', x, x, '-')
grid on;
ylabel('g(x)');
xlabel('x');
axis on;
title('graphe de g');

Exercice

Point douteux

III-5 Ordre de convergence

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-5 Ordre de convergence

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Soit

un point fixe de

g

Remarque

g' (α) = 0,

on sait que alpha

est un point attractif. Si de plus

g

est de classe

𝒞^{2}

sur

I

et s'il existe

M > 0

tel que

∣ g^{(2)} (x) ∣ \leq M

, pour tout

x

dans un voisinage

V_{α}

alors d'après la formule de Taylor :

\begin{matrix} g (x) & = & g (α) + (x - α) g' (α) + \frac{(x - α)^{2}}{2} g^{(2)} (c) & avec c \in] α, x [ \\ = & α + \frac{1}{2} g^{(2)} (c) (x - α)^{2} \end{matrix}

d'où

∣ g (x) - α ∣ \leq \frac{1}{2} M ∣ x - α ∣^{2}

avec

M = \sup_{x \in I} ∣ g^{(2)} (x) ∣

. La suite

(x_{n})

est alors convergente à convergence au moins quadratique (voir introduction).
Nous allons maintenant présenter un résultat simplifié concernant l'ordre de la méthode de point fixe.

Théorème

Soit

g : I = [a, b] ⟶ [a, b]

de classe

𝒞^{m},

avec

m \in ℕ

. On suppose que

g

admet un unique point fixe

α \in [a, b]

vérifiant

∣ g' (α) ∣ < 1

. Il existe alors un voisinage

V_{α}

dans

I

tel que la suite itérée

(x_{n})

définie par:

{\begin{matrix} x_{0} \in V_{α} \\ x_{n + 1} = g (x_{n}) & \forall n \geq 0 \end{matrix}

converge vers alpha

. De plus, si

g' (α) = \dots = g^{(m - 1)} (α) = 0 et g^{(m)} (α) \neq 0

alors l'ordre de convergence de

(x_{n})

est égal à

m

Démonstration

L'existence de

V_{α}

est assurée par le théorème de convergence pour un point attractif. La formule de Taylor appliquée à la fonction

g

au point

à l'ordre

m

donne: il existe un réel

c_{n}

dans l'intervalle

(x_{n}, α)

tel que :

x_{n + 1} = g (α) + g' (α) (x_{n} - α) + \dots + \frac{g^{(m - 1)} (α)}{(m - 1)!} {(x_{n} - α)}^{m - 1} + \frac{g^{(m)} (c_{n})}{m!} {(x_{n} - α)}^{m}

Si on suppose de plus que

g' (α) = \dots = g^{(m - 1)} (α) = 0 et g^{(m)} (α) \neq 0

, alors

x_{n + 1} = α + \frac{g^{(m)} (c_{n})}{m!} {(x_{n} - α)}^{m} .

Donc,

le rapport $\frac{∣ x_{n + 1} - α ∣}{{∣ x_{n} - α ∣}^{m}} = \frac{∣ g^{(m)} (c_{n}) ∣}{m!}$ tend vers $\frac{∣ g^{(m)} (α) ∣}{m!}$ qui est fini et non nul,
pour tout $ε > 0$ , le rapport $\frac{∣ x_{n + 1} - α ∣}{{∣ x_{n} - α ∣}^{m + ε}} = \frac{∣ g^{(m)} (c_{n}) ∣}{m! {∣ x_{n} - α ∣}^{ε}}$ tend vers $+ ∞$ .

III-6 Test d'arrêt

Résolution numérique de l'équation f ( x ) = 0 → III Méthode de point fixe → III-6 Test d'arrêt

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Comme nous l'avons expliqué dans l'introduction, la suite

(x_{n})

converge vers un réel alpha

vérifiant

g (α) = α

. En fixant la tolérance varepsilon

on estime qu'on atteint la précision varepsilon

dès qu'il existe

n_{0} \in ℕ

tel que:

∣ x_{n_{0} + 1} - x_{n_{0}} ∣ < ε

Néanmoins, la situation devient plus concrète lorsque

g'

est négative au voisinage de alpha

. En effet:

Proposition

Soit

g : [a, b] ⟶ [a, b]

de classe

𝒞^{1}

. On suppose que

g

admet un unique point fixe

α \in [a, b]

vérifiant

- 1 < g' (x) < 0

pour tout

x

dans un intervalle de convergence

V_{α}

. Soit la suite

(x_{n})

définie par:

{\begin{matrix} x_{0} \in V_{α} \\ x_{n + 1} = g (x_{n}); & \forall n \geq 0 \end{matrix}

Alors:

\forall n \in ℕ, ∣ x_{n + 1} - α ∣ \leq ∣ x_{n + 1} - x_{n} ∣

Par conséquent, soit

n_{0}

tel que

∣ x_{n_{0}} - α ∣ < ε,

alors

x_{n_{0}}

approche

près.

Démonstration

On applique le théorème des accroissements finis à

g

entre

x_{n}

. Il existe alors

c_{n}

entre

x_{n}

telle que:

g (x_{n}) - g (α) = g' (c_{n}) (x_{n} - α)

ce qui donne:

x_{n + 1} - α = g' (c_{n}) (x_{n} - α)

Comme

g' (c_{n}) < 0, (x_{n + 1} - α) et (x_{n} - α)

sont de signes contraires.

Finalement,

∣ x_{n + 1} - α ∣ \leq ∣ x_{n + 1} - x_{n} ∣

IV Méthode de Newton

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

IV-1 Principe et convergence

IV-2 Illustration graphique

IV-3 Méthode de Newton modifiée

IV-4 Théorème de convergence globale

IV-5 Test d'arrêt

IV-1 Principe et convergence

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-1 Principe et convergence

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

La méthode de Newton est une méthode particulière de point fixe. Elle est basée sur l'idée de construction d'une suite

(x_{n})

qui converge vers alpha

d'une manière quadratique. Rappelons que d'après le théorème , si

g

est une application de

[a, b]

dans

[a, b]

, on a les résultats suivants:

Si $g \in 𝒞^{1} ([a, b]), g' (α) \neq 0, ∣ g' (α) ∣ < 1$ , et si $\forall n \in ℕ, x_{n} \neq α$ alors
$\lim_{n ⟶ + ∞} \frac{∣ x_{n + 1} - α ∣}{∣ x_{n} - α ∣} = ∣ g' (α) ∣ \in] 0, 1 [$
et la convergence est linéaire.
Si $g \in 𝒞^{2} ([a, b]), g' (α) = 0$ et $\forall n \in ℕ, x_{n} \neq α$ , alors
$\lim_{n ⟶ + ∞} \frac{∣ x_{n + 1} - α ∣}{{∣ x_{n} - α ∣}^{2}} = \frac{1}{2} ∣ g^{(2)} (α) ∣$
et la convergence est au moins quadratique.

Poursuivons maintenant notre construction de la méthode de Newton. Considérons

f \in 𝒞^{3} ([a, b])

α \in [a, b]

tel que

f (α) = 0

. Posons

g (x) = x + h (x) f (x),

avec

h \in 𝒞^{2} ([a, b])

tel que

h (x) \neq 0, \forall x \in [a, b] .

Nous avons donc

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

Si on choisit

h

pour que

g' (α) = 0

, la méthode de point fixe appliquée

g

donne pour

x_{0} \in V_{α}

une suite

(x_{n})

convergeant vers alpha

d'une manière au moins quadratique (d'ordre supérieur ou égal à

2

). Or

g' (x) = 1 + h^{'} (x) f (x) + f' (x) h (x)

et donc

g' (α) = 1 + h (α) f' (α) .

Il suffit donc de choisir

h

telle que

h (α) = - \frac{1}{f' (α)} .

Ceci n'est possible que si

f' (α) \neq 0 .

En résumé, si

f \in 𝒞^{3} ([a, b])

est telle que

f' (α) \neq 0

f (α) = 0

, on prend

h = - \frac{1}{f'}

pour

x

assez proche de

α,

et la fonction

g \in 𝒞^{2} ([a, b])

définie par :

g (x) = x - \frac{f (x)}{f' (x)}

vérifie

g' (α) = 0

. Grâce au théorème , il existe un voisinage

V_{α}

dans

[a, b]

tel que la suite

(x_{n})

définie par

{\begin{matrix} x_{0} \in V_{α} \\ x_{n + 1} = g (x_{n}) = x_{n} - \frac{f (x_{n})}{f' (x_{n})}, & \forall n \geq 0 \end{matrix}

est convergente vers alpha

de manière au moins quadratique.

Remarque

La suite de Newton vérifie

f' (x_{n}) (x_{n + 1} - x_{n}) = - f (x_{n})

ou encore

f (x_{n}) + f' (x_{n}) (x_{n + 1} - x_{n}) = 0 .

Soit

x_{0}

un point donné (proche de alpha

). On considère la droite

D

qui passe par le point

(x_{n}, f (x_{n}))

et qui a comme pente

f' (x_{n})

. Elle a comme équation :

y = f' (x_{n}) (x - x_{n}) + f (x_{n}) .

D'après l'équation ,

x_{n + 1}

est le point où la droite

D

intersecte l'axe

Ox

IV-2 Illustration graphique

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-2 Illustration graphique

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Code Matlab

x = 0.1:.001:3;
x0 = 2;
x1 = 2*(1 - log(2));
plot(x, x.^-1 - 1 , '-b', x, -(1/x0)^2*(x - x0) + (1/x0 -1), '--b')
grid on;
ylabel('y');
xlabel('x');
title('Illustration de la methode de Newton');

Exercice [ Convergence locale de la méthode de Newton ]

Soit

f : [a, b] ⟶ ℝ

une fonction de classe

𝒞^{2}

admettant un unique zéro

α \in] a, b [

de multiplicité 1.

Montrer qu'il existe $η > 0$ tel que $V_{α} = [α - η, α + η] \subset] a, b [$ vérifie $\forall x \in V_{α}, f' (x) \neq 0$ et que la suite $(x_{n})$ définie par : ${\begin{matrix} x_{0} \in V_{α} \\ x_{n + 1} = x_{n} - \frac{f (x_{n})}{f' (x_{n})} & \forall n \in ℕ \end{matrix}$ converge vers .
On pose $e_{n} = x_{n} - α$ . Montrer que $\lim_{n ⟶ + ∞} \frac{e_{n + 1}}{e_{n}^{2}} = \frac{1}{2} \frac{f^{(2)} (α)}{f' (α)}$ . En déduire que $\forall n \in ℕ, \frac{∣ e_{n + 1} ∣}{e_{n}^{2}} \leq \frac{M_{2}}{2 m_{1}},$ avec ${\begin{matrix} m_{1} & = & \inf_{x \in V_{α}} ∣ f' (x) ∣ \\ M_{2} & = & \sup_{x \in V_{α}} ∣ f^{(2)} (x) ∣ \end{matrix}$

Exercice

Méthode de Newton

Dans ce qui précède, nous avons supposé que la fonction

f

dont nous cherchons le zéro alpha

vérifie

f (α) = 0 et f' (α) \neq 0 .

Autrement dit, nous avons supposé que alpha

est une racine simple de

f

. La question qu'on doit se poser maintenant est : que se passe-t-il quand alpha

est une racine de

f

de multiplicité

m \geq 2

? Si on garde la même fonction

g

que précédemment, la méthode de Newton perd son caractère de convergence quadratique. En effet, on peut écrire

f (x) = (x - α)^{m} h (x) avec h (α) \neq 0 .

Donc

g (x) = x - \frac{(x - α)^{mh} (x)}{m (x - α)^{m - 1} h (x) + (x - α)^{mh}' (x)} = x - \frac{(x - α) h (x)}{mh (x) + (x - α) h' (x)}

et \lim_{x ⟶ α} \frac{g (x) - g (α)}{x - α} = 1 - \frac{1}{m} \neq 0

, ce qui implique en terme de suite que

\frac{∣ x_{n + 1} - α ∣}{∣ x_{n} - α ∣}

tend vers

1 - \frac{1}{m} \in] 0, + ∞ [

. Ceci se traduit par une convergence linéaire et pas du tout quadratique. Pour récupérer cette dernière, on fait appel à la méthode de Newton modifiée.

IV-3 Méthode de Newton modifiée

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-3 Méthode de Newton modifiée

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

On suppose ici que alpha

est une racine de

f

de multiplicité

m \geq 2,

c'est-à-dire :

f (x) = (x - α)^{m} h (x) avec h (α) \neq 0 .

On suppose que

f \in 𝒞^{2} ([a, b])

et par conséquent

h

aussi. On définit alors la fonction

g

par :

g (x) = x - m \frac{f (x)}{f' (x)} .

Dans ce cas,

\lim_{x ⟶ α} \frac{g (x) - g (α)}{x - α} = 0,

ce qui implique :

\lim_{n ⟶ + ∞} \frac{∣ x_{n + 1} - α ∣}{∣ x_{n} - α ∣} = 0 et \lim_{n ⟶ + ∞} \frac{∣ x_{n + 1} - α ∣}{{∣ x_{n} - α ∣}^{2}} < + ∞ .

Exercice

Montrer que

\lim_{n ⟶ + ∞} \frac{∣ x_{n + 1} - α ∣}{{∣ x_{n} - α ∣}^{2}} = \frac{h^{'} (α)}{m h (α)}

IV-4 Théorème de convergence globale

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-4 Théorème de convergence globale

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Nous allons énoncer un résultat de convergence globale (

x_{0}

est choisi n'importe où dans le domaine de

f

) concernant la méthode de Newton pour des fonctions ayant une concavité déterminée (convexe ou concave).

Théorème

Soit

f : [a, b] ⟶ ℝ

de classe

𝒞^{2}

vérifiant :

$f (a) f (b) < 0$
$f' (x) \neq 0, \forall x \in [a, b]$
$f^{(2)} (x) \neq 0, \forall x \in [a, b]$

La suite

(x_{n})

définie par :

{\begin{matrix} x_{0} \in [a, b] & tel que f (x_{0}) f^{(2)} (x_{0}) > 0 \\ x_{n + 1} = x_{n} - \frac{f (x_{n})}{f' (x_{n})} \end{matrix}

est convergente vers alpha

Démonstration

Les hypothèses

{\begin{matrix} f (a) f (b) < 0 \\ f' (x) \neq 0, & \forall x \in [a, b] \end{matrix}

implique qu'il existe un unique

α \in [a, b]

tel que

f (α) = 0

. Comme

f^{(2)}

est de signe constant, on distingue deux cas :

Premier cas : $f^{(2)} (x) > 0, \forall x \in [a, b]$ (donc $f (x_{0}) > 0$ ).
1. Si $f' (x) > 0, \forall x \in [a, b]$ on a :
  $f (x) > 0 \forall x \in] α, b] et f (x) < 0 \forall x \in [a, α [.$
  Comme $f (x_{0}) > 0$ , alors $x_{0} \in] α, b]$ . Rappelons que $g$ est la fonction définie par $g (x) = x - \frac{f (x)}{f' (x)}$ $\forall x \in [a, b]$ . Comme
  $g' (x) = \frac{f (x) f^{(2)} (x)}{(f' (x))^{2}} \geq 0 \forall x \in] α, b],$
  $g$ est croissante sur $] α, b]$ . D'où, $α = g (α) \leq g (x_{0}) = x_{1}$ puisque $α < x_{0}$ . On en déduit que $x_{1} \in] α, b]$ . De plus,
  $g (x_{0}) = x_{1} = x_{0} - \frac{f (x_{0})}{f' (x_{0})} < x_{0} .$
  Donc, $α \leq x_{1} < x_{0} .$ Par récurrence, on obtient :
  $α \leq x_{n + 1} < x_{n} \leq \dots < x_{2} < x_{1} < x_{0} \forall n \in ℕ .$
  Donc la suite $(x_{n})$ est décroissante et minorée par , ce qui montre qu'elle est convergente. Comme $x_{n + 1} = g (x_{n})$ et comme $g$ est continue, $(x_{n})$ converge vers l'unique point fixe de $g$ . On remarque de plus que
  $∣ x_{n + 1} - α ∣ < ∣ x_{n} - α ∣ \forall n \in ℕ .$
2. Si $f' (x) < 0, \forall x \in [a, b]$ un raisonnement semblable au précédent implique que $(x_{n})$ est croissante majorée par . Donc $(x_{n})$ est convergente. Comme $x_{n + 1} = g (x_{n})$ et que $g$ est continue, on obtient que $(x_{n})$ converge vers l'unique point fixe de $g$ .
Second cas : $f^{(2)} (x) < 0, \forall x \in [a, b]$ (donc $f (x_{0}) < 0$ ). Alors le raisonnement précédent, avec $f$ remplacée par $- f,$ implique que la suite $(x_{n})$ converge vers .

IV-5 Test d'arrêt

Résolution numérique de l'équation f ( x ) = 0 → IV Méthode de Newton → IV-5 Test d'arrêt

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Une fois construite la suite

(x_{n})

convergeant vers le réel alpha

vérifiant

g (α) = α,

et une fois fixée la tolérance

ε,

nous cherchons le premier entier

n_{0}

vérifiant :

∣ x_{n_{0} + 1} - x_{n_{0}} ∣ < ε .

Si on note

e_{n} = x_{n} - α

l'erreur à l'itération

n,

on a :

e_{n + 1} = x_{n + 1} - α = g (x_{n}) - g (α) = g' (c_{n}) e_{n}

avec

c_{n}

un réel entre

x_{n}

donné par le théorème des accroissements finis. Par conséquent,

\begin{matrix} x_{n + 1} - x_{n} & = & (x_{n + 1} - α) - (x_{n} - α) \\ = & e_{n + 1} - e_{n} \\ = & (g' (c_{n}) - 1) e_{n} . \end{matrix}

Or si

n

est suffisament grand,

g' (c_{n}) \approx g' (α) = 0

et donc

e_{n} \approx x_{n + 1} - x_{n} .

L'erreur qu'on commet lorsque l'on adopte ce critère est donc plus petite que la tolérance varepsilon

fixée.

∣ x_{n + 1} - x_{n} ∣ = ∣ g' (c_{n}) - 1 ∣ ∣ x_{n} - α ∣

V Méthode de Lagrange

Résolution numérique de l'équation f ( x ) = 0 → V Méthode de Lagrange

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

V-1 Principe

V-2 Interprétation géométrique

V-3 Convergence

V-1 Principe

Résolution numérique de l'équation f ( x ) = 0 → V Méthode de Lagrange → V-1 Principe

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

La méthode de Lagrange est une variante de la méthode de Newton.
Soit

f \in 𝒞^{1} ([a, b], ℝ)

ayant une convexité déterminée. Rappelons que pour calculer un zéro alpha

f

par la méthode de Newton, on considère la suite

(x_{n})

définie par :

{\begin{matrix} x_{0} proche de α \\ f' (x_{n}) (x_{n + 1} - x_{n}) = - f (x_{n}), \forall n \geq 0 \end{matrix}

Dans certaines situations, la dérivée de

f

est très compliquée voir même impossible à calculer. Dans ce cas, nous approchons la dérivée par un taux d'accroissement. Ce que nous obtenons est appelée la méthode de Lagrange ou méthode de la sécante :

{\begin{matrix} x_{0}, x_{1} proche de α \\ \frac{f (x_{n}) - f (x_{n - 1})}{x_{n} - x_{n - 1}} (x_{n + 1} - x_{n}) = - f (x_{n}), & \forall n \geq 1 \end{matrix}

Ici,

x_{n + 1}

dépend de

x_{n}

et de

x_{n - 1}

: on dit que c'est une méthode à deux pas ; nous avons d'ailleurs besoin de deux itérés initiaux

x_{0}

x_{1}

.
L'avantage de cette méthode est qu'elle ne nécessite pas le calcul de la dérivée

f'

. L'inconvénient est que la convergence n'est plus quadratique.
La fonction

g

correspondante vérifie :

x_{n + 1} = g (x_{n}) = x_{n} - f (x_{n}) \frac{x_{n} - x_{n - 1}}{f (x_{n}) - f (x_{n - 1})} .

V-2 Interprétation géométrique

Résolution numérique de l'équation f ( x ) = 0 → V Méthode de Lagrange → V-2 Interprétation géométrique

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Code Matlab

x = 0:.001:2;
plot(x, x.^2 - 1 , '-b')
grid on;
ylabel('y');
xlabel('x');
title('Illustration de la methode de Lagrange');

V-3 Convergence

Résolution numérique de l'équation f ( x ) = 0 → V Méthode de Lagrange → V-3 Convergence

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Nous allons nous inspirer de l'exemple précédent pour présenter un théorème de convergence.

Théorème

Soit

f : [a, b] ⟶ ℝ

de classe

𝒞^{2}

telle que

f'

f^{(2)}

soient strictement positives sur

[a, b]

. On suppose que

f (a) < 0, f (b) > 0

et on appelle alpha

l'unique solution de l'équation

f (x) = 0

. Alors

La suite $(x_{n})$ telle que :
${\begin{matrix} x_{0} = a \\ x_{n + 1} = \frac{x_{n} f (b) - b f (x_{n})}{f (b) - f (x_{n})}, & \forall n \geq 0 \end{matrix}$
est bien définie.
La suite $(x_{n})$ est croissante et converge vers .
La méthode de Lagrange est d'ordre au moins 1 :
$\lim_{n ⟶ + ∞} \frac{∣ x_{n + 1} - α ∣}{∣ x_{n} - α ∣} = ∣ 1 + (α - a) \frac{f' (α)}{f (a)} ∣$

Démonstration

On pose

x_{n + 1} = g (x_{n})

où

g (x) = \frac{x f (b) - b f (x)}{f (b) - f (x)} .

La fonction

f

est strictement convexe : sa courbe est en dessous de tout segment reliant deux points de cette courbe. Donc

f

admet son unique zéro alpha

dans l'intervalle

[a, b]

. Comme

f (a) < 0

f (b) > 0

, le réel

x_{1}

est l'abscisse de l'intersection de la droite passant par

(a, f (a))

(b, f (b))

et vérifie

f (x_{1}) < 0

; de même,

f (x_{2}) < 0

et par récurrence on a

f (x_{n}) < 0, \forall n \in ℕ .

On vérifie que la suite

(x_{n})

est croissante majorée par

b,

donc convergente. Comme

x_{n + 1} = g (x_{n})

et que

g

est continue, la limite est l'unique point fixe de

g

. De plus,

∣ \frac{x_{n + 1} - α}{x_{n} - α} ∣ = ∣ \frac{g (x_{n}) - g (α)}{x_{n} - α} ∣ ⟶ ∣ g' (α) ∣ = ∣ 1 + (α - b) \frac{f' (α)}{f (a)} ∣

(la dernière égalité est obtenue en dérivant

g

au point

Exercice

Méthode de Lagrange

VI Bibliographie

Résolution numérique de l'équation f ( x ) = 0 → VI Bibliographie

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Philipe G. Ciarlet. Introduction à l'analyse numérique et à l'optimisation . Dunod 1990.
Jean-Pierre Demailly. Analyse numérique et équations différentielles . Presses Universitaires de Grenoble, 1996.
Ernst Hairer. Introduction à l'analyse numérique . Université de Genève, section mathématiques, case postale 240. Octobre 2001.

VII Exercices

Résolution numérique de l'équation f ( x ) = 0 → VII Exercices

I Introduction
II Méthode de dichotomie
III Méthode de point fixe
IV Méthode de Newton
V Méthode de Lagrange
VI Bibliographie
VII Exercices
Index

Exercice

On veut calculer les zéros de l'équation

f (x) = \frac{x}{2} - \sin (x) + \frac{π}{6} - \frac{\sqrt{3}}{2} = 0

dans l'intervalle

[- \frac{π}{2}, π]

. Le graphe de la fonction

f

est montré dans la figure suivante :

Peut-on appliquer la méthode de la bissection pour calculer les deux racines ? Pourquoi ? Dans le cas où c'est possible, estimer le nombre minimal d'itérations nécessaires pour calculer le(s) zéro(s) avec une tolérance $ε = 10^{- 10},$ après avoir choisi un intervalle convenable.
Ecrire la méthode de Newton pour la fonction $f$ . A l'aide du graphe de la fonction $f,$ déduire l'ordre de convergence de la méthode pour les deux zéros.
On considère maintenant la méthode de point fixe $x_{k + 1} = ϕ (x_{k}),$ avec
$ϕ (x_{k}) = \sin (x_{k}) + \frac{x_{k}}{2} (\frac{π}{6} - \frac{\sqrt{3}}{2})$
pour calculer le zéro $α > 0$ . En observant que $α \in [\frac{2 π}{3}, π],$ établir si cette méthode de point fixe est convergente.
En considérant encore le zéro $α \in [\frac{2 π}{3}, π]$ et la méthode de point fixe introduite à la question précédente, montrer qu'il existe une constante positive $C > 0$ telle que
$∣ x_{k + 1} - α ∣ \leq C ∣ x_{k} - α ∣$
et estimer cette constante.

Exercice

On veut calculer le zéro alpha

de la fonction

f (x) = x^{3} - 2

en utilisant la méthode de point fixe

x_{k + 1} = ϕ (x_{k})

x_{k + 1} = x_{k} (1 - \frac{w}{3}) + (x_{k})^{3} (1 - w) + \frac{2 w}{3 (x_{k})^{2}} + 2 (w - 1), k \geq 0,

w \in ℝ

étant un paramètre réel.

Pour quelles valeurs du paramètre $w$ , le zéro de la fonction $f$ est-il un point fixe de la méthode proposée ?
Pour quelles valeurs de $w$ , la méthode proposée est-elle d'ordre $2$ ?
Existe-t-il une valeur de $w$ telle que l'ordre de la méthode de point fixe est supérieur à $2$ ?

Exercice

On considère l'équation non linéaire

f (x) = e^{x} - \frac{x^{2}}{2} - x - 1 = 0

sur l'intervalle

[- 1, 1]

Montrer que la fonction $f$ admet un zéro dans $[- 1, 1]$ et qu'il est unique.
Ecrire la méthode de Newton pour résoudre l'équation $f (x) = 0$ . Quel est l'ordre de convergence de cette méthode ? Justifier la réponse.
Proposer une méthode d'ordre $2$ pour la résolution de l'équation donnée.

Exercice

Soit

une racine double de la fonction

f

f (α) = f' (α) = 0 et f^{(2)} (α) \neq 0 .

En tenant compte du fait qu'on peut écrire la fonction $f$ comme
$f (x) = (x - α)^{2} h (x) où h (α) \neq 0,$
vérifier que la méthode de Newton pour l'approximation de la racine est seulement d'ordre~ $1$ .
On considère la méthode de Newton modifiée suivante :
$x_{k + 1} = x_{k} - 2 \frac{f (x_{k})}{f' (x_{k})} .$
Vérifier que cette méthode est d'ordre deux si l'on veut approcher .

Exercice

On considère la fonction

f (x) = e^{x} + 3 \sqrt{x} - 2

sur l'intervalle

[0, 1]

Montrer qu'il existe un zéro pour la fonction $f$ dans $[0, 1]$ et qu'il est unique.
On veut calculer le zéro de la fonction $f$ par une méthode de point fixe convenable. En particulier on se donne deux méthodes de point fixe $x = ϕ_{i} (x), i = 1, 2,$ où les fonctions $ϕ_{1}$ et $ϕ_{2}$ sont définies comme :
$ϕ_{1} (x) = \ln (2 - 3 \sqrt{x}) et ϕ_{2} (x) = \frac{(2 - e^{x})^{2}}{9}$
Laquelle de ces deux méthodes utiliseriez-vous pour calculer numériquement le zéro de la fonction $f$ ? Justifiez votre réponse.
En utilisant la méthode de la bissection sur l'intervalle $[0, 1],$ estimer le nombre d'itérations nécessaires pour calculer le zéro de la fonction $f$ avec une tolérance $ε = 10^{- 10}$ .

document sur les méthodes de résolution d'équations numériques f(x) = 0.
: equations, roots, méthode de dichotomie, méthode de Lagrange, méthode de Newton, point fixe, interactive mathematics, interactive math, server side interactivity

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.