Sup’Galilée Année 2020/2021

MACS1

Analyse numérique - TD4 & TD5

Résolution numérique des équations non linéaires
TM : Travail à la Maison

1 Méthode de dichotomie pour la résolution de l’équation f pxq “ 0.

Exercice 1 - (TM)
Soient a et b deux réels tels que a ă b et f : ra, bs Ă R Ñ R une fonction continue vérifiant f paq f pbq ă 0. On définit par
récurrence les trois suites pak qkPN , pbk qkPN et pxk qkPN suivantes :

a`b
- a0 “ a, b0 “ b et x0 “ .
2
- @ k P N˚ ,
# #
ak , si f pak q f pxk q ă 0, xk , si f pak q f pxk q ă 0, ak`1 ` bk`1
ak`1 “ bk`1 “ et xk`1 “ . (1)
xk sinon, bk sinon, 2

1. Montrer qu’il existe γ P ra, bs tel que f pγq “ 0. γ est-il unique ? que se passe-t-il si f n’est pas continue ?

2. Montrer que l’algorithme (1) est bien défini, que γ P rak , bk s, @k P N, et que
pb ´ aq
bk ´ ak “ , @k P N.
2k

3. Montrer que les deux suites pak qkPN et pbk qkPN sont adjacentes (Indication : on montrera que pak qkPN est croissante,
pbk qkPN est décroissante, et on déduira de la question 2 que lim pbk ´ ak q “ 0).
kÑ`8

4. En déduire que les trois suites pak qkPN , pbk qkPN et pxk qkPN ont même limite α.

5. Démontrer que pour tout k P N, f pak qf pbk q ď 0. En déduire que f pαq “ 0. Comparer α et γ.

6. Montrer que, pour tout k P N,

b´a
|xk ´ α| ď .
2k`1
7. Soit ε ą 0 donné.

(a) Déterminer k pour avoir |xk ´ α| ď ε.

ε
(b) Combien faut-il d’itérations supplémentaires pour avoir une majoration en ?
10

2 Méthode du point fixe pour la résolution de l’équation f pxq “ x.

Exercice 2 (dimension 1)
Soit ra, bs un intervalle non vide de R et φ une fonction continue de ra, bs dans lui même (φpra, bsq Ă ra, bs). Soit x0 P ra, bs.
On considère la suite pxk qkPN définie par
xk`1 “ φpxk q @k P N. (2)
1. Montrer que la suite (2) est bien définie (xk existe pour tout k P N).
2. Montrer que si la suite (2) converge, alors elle converge vers un point fixe de φ.
3. Existence du point fixe (Théorème du point fixe de Brouwer) : montrer qu’il existe α P ra, bs tel que φpαq “ α.
4. On suppose de plus que φ est contractante, c’est à dire que
D L P r0, 1r, tel que, @px, yq P ra, bs2 , |φpxq ´ φpyq| ď L|x ´ y|.
a- Montrer que φ admet un unique point fixe α P ra, bs.
b- Montrer que la suite pxk qkPN converge vers α, pour toute donnée initiale x0 dans ra, bs.

5. (algo) Écrire l’algorithme du point fixe (fonction PointFixe) permettant de résoudre l’équation φpxq “ x.

1
Exercice 3 (Extension au cas d’un espace de Banach) - (TM)
Soit pE, } ¨ }q un espace de Banach (espace vectoriel normé complet, de norme notée } ¨ }). On considère une application
φ : E ÞÑ E contractante :
D L P r0, 1r, tel que, @px, yq P E 2 , }φpxq ´ φpyq} ď L}x ´ y}.
A partir de x0 P E donné, on construit la suite récurrente pxk qkPN définie par

xk`1 “ φpxk q @k P N. (3)

1. Montrer que la suite pxk qkPN est bien définie.

2. Montrer que la fonction φ est continue. En déduire que si la suite xk converge, alors elle converge vers un point fixe de φ.
3. Montrer que si φ admet un point fixe alors ce point fixe est unique.
4. Montrer que la suite pxk qkPN est une suite de Cauchy. En déduire que φ admet une unique point fixe qui est donné par la
limite de la suite pxk qkPN quand k tend vers `8.

Exercice 4 (Point fixe attractif)

Soit α P R, sα´ , α` r un voisinage de α et φ P C 1 psα´ , α` rq. On suppose que α est un point fixe de φ tel que

|φ1 pαq| ă 1.

1. Montrer qu’il existe δ ą 0 tel que pour tout x P V “ rα ´ δ, α ` δs, |φ1 pxq| ă 1. Montrer que φ est contractante sur V et
que φpVq Ă V.En déduire que pour tout x0 P V, la suite pxk qkPN obtenue à l’aide de l’algorithme du point fixe

@k P N, xk`1 “ φpxk q, (4)

est bien définie et converge.

2. Soit x0 P V et la suite pxk qkPN définie par l’algorithme du point fixe. Montrer que
xk`1 ´ α
lim “ φ1 pαq.
kÑ`8 xk ´ α

En déduire que la méthode du point fixe est au moins d’ordre 1.

3. Supposons maintenant que φ P C pp`1q pVq, que φpiq pαq “ 0 pour tout entier i tel que 1 ď i ď p, et φpp`1q pαq ‰ 0. Soit
x0 P V et la suite pxk qkPN définie par l’algorithme du point fixe. Montrer que

xk`1 ´ α φpp`1q pαq

lim p`1
“ .
kÑ`8 pxk ´ αq pp ` 1q!
En déduire que la méthode du point fixe est d’ordre p ` 1 dans ce cas.

Exercice 5 (Application)
Soit f la fonction définie sur R par f pxq “ x2 ´ 10. On cherche à calculer de façon approchée la racine positive, notée α, de
l’équation f pxq “ 0 par une méthode de type point fixe.

1. On pose φ1 pxq “ x ´ f pxq. Montrer que α est un point fixe de φ1 . On choisit xp0q “ 3 et on pose xpk`1q “ φ1 pxpkq q
pour k P N. Calculer les trois premiers itérés de cette suite et utiliser le graphe de la Figure 1 (à gauche) pour appliquer
les 3 premières itérations de la méthode du point fixe avec φ1 , en partant de xp0q “ 3. En déduire que cette suite ne
converge pas.
Pour palier à ce problème, une idée est de “sous-relaxer” la méthode itérative en posant φω pxq “ x ´ ωf pxq, avec 0 ă ω ă 1.

2. Prouver qu’un point fixe de φω est aussi racine de f pour tout ω ‰ 0.

` ˘
On choisit dans la suite ω “ 18 . On choisit de nouveau xp0q “ 3 et on pose xpk`1q “ φ 18 xpkq , pour k ě 0.

3. Utiliser le graphe de la Figure 1 (à droite) pour appliquer les 3 premières itérations de la méthode du point fixe avec
φ 18 , en partant de xp0q “ 3.
4. Montrer que
´ ¯ ´ ¯„ 1 ´ pkq ¯
xpk`1q ´ α “ xpkq ´ α 1 ´ x `α .
8

2
11
3.4
10
9
8
7
6
3.2
5
4
3
2
1
0 3
-1
-2
-3
-4
-5 2.8
-5 -4 -3 -2 -1 0 1 2 3 4 5 2.6 2.8 3 3.2 3.4

F IGURE 1 – Gauche : la fonction φ1 (en trait plein). Droite : la fonction φ 18 (en trait plein). Pour chaque figure la courbe rouge en
pointillés est la droite y “ x

5. Montrer que la fonction φ 81 est croissante sur r3, 4s. En déduire que φ 18 pr3, 4sq Ă r3, 4s.
6. Déduire des questions 3 et 4 que pour k ě 0 :
ˇ ˇ ˆ5 ´ α˙ ˇ ˇ
ˇ pk`1q ˇ pkq
´ αˇ ď ˇx ´ αˇ .
ˇ ˇ
ˇx
8
7. En déduire que pour k ě 0 :
ˇ ˇ ˆ 5 ´ α ˙k ˇ ˇ
ˇ pkq ˇ p0q
ˇx ´ αˇ ď ˇx ´ αˇ ,
ˇ ˇ
8
(
puis en déduire la convergence de la suite xpkq ně0 vers α. Retrouver par le théorème du cours que φ 81 a un unique
point fixe dans r3, 4s et que l’algorithme du point fixe converge vers α, pour tout xp0q dans r3, 4s.
ˇ ˇ ` ˘k`1
Quel est l’ordre de cette méthode ? Montrer que pour k ě 0 : ˇxpkq ´ αˇ ď 41 , puis estimer le nombre d’itérations
nécessaire pour obtenir une valeur de α précise à 10´3 près.

Exercice 6 (Application) - (TM)

Soit f la fonction définie sur r0, 1s par f pxq “ cospxq. On cherche à calculer une approximation de la solution de l’équation
f pxq “ x.
1. Montrer que cette équation possède une solution unique dans r0, 1s, que l’on notera x˚ .
` ˘ ` ˘
2. Pour approcher x˚ , on définit une suite xpnq , pour n ě 0 par xp0q “ 1 et xpn`1q “ f xpnq .
(a) Utiliser le graphe de la Figure 2 pour appliquer les 4 premières itérations de cette méthode, en partant de xp0q “ 0.5.

(b) Montrer que

ˆ pnq ˙ ˆ pnq ˙
´ ¯ x ` x˚ x ´ x˚
xpn`1q ´ x˚ “ ´2 sin sin
2 2
(c) En déduire la convergence de la suite vers x˚ , asymptotiquement comme une suite géométrique de raison ´ sin px˚ q.
(d) Est-ce que cela correspond au résultat vu en cours ?

3 Méthodes de Newton pour la résolution de l’équation f pxq “ 0.

Exercice 7
Soit f une fonction appartenant à C 1 pRq (f continue et dérivable sur R, de dérivée continue sur R) qui admet une racine
x̄ P R. La méthode de Newton est une méthode iterative d’approximation de x̄. Soit x0 P R. Pour k ě 0, on définit xk`1 par
f pxk q
xk`1 “ xk ´ . (5)
f 1 pxk q

3
 F IGURE 2 – la fonction f (en trait plein), et la droite y “ x (en rouge pointillés)

L’objectif de cet exercice est de montrer que sous certaines conditions, la suite pxk qkPN converge vers x̄.
1. Sous quelle condition la suite pxk qkPN est-elle bien définie ?
2. Interpréter graphiquement l’algorithme (5).
3. Montrer que l’algorithme de Newton est un algorithme du point fixe appliqué à une fonction g que l’on déterminera.
4. On suppose que f P C 2 pRq et que f 1 pxq ‰ 0. En déduire une condition suffisante de convergence de l’algorithme de Newton.
5. On suppose que f P C 3 pRq avec f 1 pxq ‰ 0, et f 2 pxq ‰ 0. Montrer que la méthode de Newton, lorsqu’elle converge est
d’ordre 2 (on dit alors que l’erreur de convergence est quadratique).

Exercice 8 (Application) - (TM)

Soit la fonction f définie sur R par f pxq “ x3 ´ 3x ´ 2.
1. Quelles sont les racines de l’équation f pxq “ 0 ?

Nous allons illustrer les résultats vus en cours sur la convergence de la méthode de Newton appliquée à la résolution de cette
équation.

2. Calculer f 1 pxq
` et˘écrire la relation de récurrence liant deux itérés successifs de la méthode de Newton sous la forme
xpk`1q “ F xpkq avec une fonction F que l’on précisera.
3. Utiliser le graphe de la Figure 3 pour appliquer les 3 premières itérations de la méthode de Newton avec f , en partant
de xp0q “ ´2.
4. Selon les résultats vus dans l’exercice 5, qu’attend on comme convergence de la suite de Newton autour des racines
calculées à la question 1) ?
?
Exercice 9 (Application : calcul approché de a)
1. Ecrire l’algorithme de Newton pour la résolution de x2 ´ a “ 0, où a est un réel strictement positif.
2. Lorsque a “ 2 et que l’itéré initial est xp0q “ 2, calculer
? les trois premiers itérés de cette suite sous forme fractionnaire
et sous forme décimale approchée ; comparez avec 2 dont une valeur approchée à 10´10 près est 1, 4142135624.
Comparez avec la précision donnée par l’algorithme de dichotomie (voir Exercice 1).
? ? ?
3. Montrer que pxpn`1q ´ aq “ 2x1pnq pxpnq ´ aq2 . En déduire que si xp0q ě 0, alors xpnq ě a pour tout n ě 1 puis
montrer que la suite est décroissante à partir de n “ 2.
?
4. En déduire que la suite converge quadratiquement vers a. Est ce le résultat attendu en appliquant le théorème vu en
cours ?

4
 1

0.5

-0.5

-1

-1.5

-2

-2.5

-3

-3.5

-4
-3 -2.5 -2 -1.5 -1 -0.5 0

F IGURE 3 – La fonction f (en trait plein)

Exercice 10 (Vrai ou faux ?) - (TM)

1. Pour obtenir un encadrement à 10´3 près de la solution de x2 ´ 2 “ 0 par la méthode de dichotomie en partant de
l’intervalle r1, 2s, il suffit de 10 itérations.
2. La méthode de dichotomie fournit une approximation de plus en plus précise de la solution d’une équation non-linéaire.
3. La méthode de dichotomie permet de trouver les zéros de n’importe quelle fonction.
4. Les itérés de la méthode de Newton appliquée à la fonction x ÞÑ x2 convergent quadratiquement vers 0.
? ` ˘
3
5. A condition que l’itéré initial soit suffisamment proche de 3, la suite définie par xpn`1q “ 21 xpnq ` xpnq converge
?
quadratiquement vers 3.
pnq
6. La suite définie par xp0q “ 0 et xpn`1q “ exppx 3
q
converge vers la solution de l’équation exppxq “ 3x située dans
r0, 1s. En revanche, cette méthode itérative ne permet pas de s’approcher de la solution de cette équation située dans
r 32 , 2s.