Livre_silo 30 août 2013 16:32 Page 214
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
214
Informatique pour tous
Exercice 8.12 Méthode de la sécante.
Soit f : I → R continue, s’annulant en a ∈ I, concave ou convexe au voisinage de a. On fixe u 0 , u 1 ∈ I
au voisinage de a et on construit (un) n⩾2 de la façon suivante : pour tout n ⩾ 2, on définit un comme
l’abscisse de l’intersection de l’axe des abscisses avec la sécante au graphe de f passant par les points
d’abscisse u n−2 et u n−1 .
1 Faire un dessin ; constater qu’il peut y avoir divergence, ou même que un peut ne pas être défini à partir
d’un certain rang, mais que si u 0 et u 1 sont assez proches de a, on peut raisonnablement espérer qu’il
y ait convergence de (un) n∈N vers a.
2 Donner une relation liant u n−2 , u n−1 et un.
3 Proposer un test d’arrêt pour la méthode de la sécante, qui consiste à approcher a en calculant des un
jusqu’à ce qu’une certaine condition soit vérifiée.
4 Programmer et tester la méthode de la sécante.
5 On admet que sous des conditions favorables (mais réalistes si u 0 et u 1 sont suffisamment proches de a),
alors la distance δn = |un − a| vérifie une relation de la forme δ n+1 ⩽ Kδ
φ
n , avec φ =
1 +
√
5
2
·
Donner alors le nombre d’étapes nécessaires pour approcher a avec une erreur majorée par 2 −52 ,
puis 2 −1000 . Comparer avec la méthode de Newton.
6 On fait l’hypothèse suivante, très optimiste pour la méthode de Newton : le coût de chaque évaluation
de f ′ est de l’ordre de celui de deux évaluations de f . Comparer alors les coûts des méthodes de
Newton et de la sécante, pour obtenir une précision donnée.
Tout comme la méthode de Newton, pour laquelle on peut remplacer f ′ (un) par la jacobienne, la méthode de la sécante a un analogue dans R n : il s’agit de la très belle méthode de Broyden.
Exercice 8.13 * Inversion par la (pseudo-)méthode de Newton.
Si on applique la méthode de Newton à la fonction x → ax−1 (avec a ∈ R ∗
+ ), on peut espérer approcher
l’inverse de a.
1 Expliciter la relation de récurrence mise en place dans la méthode de Newton... et constater qu’elle est
inutilisable !
On va plutôt s’intéresser à une autre suite convergeant vers
1
a
: on fixe x 0 (on verra comment plus tard)
et on définit par récurrence la suite (xn) n∈N par la relation x n+1 = xn(2 − axn).
2 Expliquer qualitativement le lien avec la méthode de Newton. Démontrer qu’en cas de convergence, la
limite vaut 0 ou
1
a
·
3 Programmer cette méthode et déterminer les cinq premiers termes de la suite, lorsque a = 2 et
x 0 ∈ {0, 0.4, 0.9, 1, 2}.
4 On suppose maintenant que A est une matrice et on considère une suite de matrice (Xn) n∈N vérifiant
la relation X n+1 = Xn(2In − AXn).
a) Quel est le coût (en termes d’opérations sur les flottants) de chaque itération ?
b) D’après [Pan et Schreiber], un bon choix de valeur de départ est X 0 = α 0
t A, avec
α 0 =
1
∥A∥ 1 ∥A∥ ∞
, où ∥A∥ 1 = max j
∑
i
|a i,j | et ∥A∥ ∞ = max i
∑
j
|a i,j |.
Programmer cette méthode d’inversion matricielle, en décidant d’un test d’arrêt raisonnable.
c) Évaluer la complexité de cette méthode (en cas de convergence, et en fonction du nombre d’itérations
finalement effectuées).
d) Tester, comparer avec les méthodes du chapitre précédent.
On représente figure 8.8 l’évolution de
A −1 − Xn
1
en fonction de n, avec A =
1 2
3
4 5
6
7 8 10
.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
214
Informatique pour tous
Exercice 8.12 Méthode de la sécante.
Soit f : I → R continue, s’annulant en a ∈ I, concave ou convexe au voisinage de a. On fixe u 0 , u 1 ∈ I
au voisinage de a et on construit (un) n⩾2 de la façon suivante : pour tout n ⩾ 2, on définit un comme
l’abscisse de l’intersection de l’axe des abscisses avec la sécante au graphe de f passant par les points
d’abscisse u n−2 et u n−1 .
1 Faire un dessin ; constater qu’il peut y avoir divergence, ou même que un peut ne pas être défini à partir
d’un certain rang, mais que si u 0 et u 1 sont assez proches de a, on peut raisonnablement espérer qu’il
y ait convergence de (un) n∈N vers a.
2 Donner une relation liant u n−2 , u n−1 et un.
3 Proposer un test d’arrêt pour la méthode de la sécante, qui consiste à approcher a en calculant des un
jusqu’à ce qu’une certaine condition soit vérifiée.
4 Programmer et tester la méthode de la sécante.
5 On admet que sous des conditions favorables (mais réalistes si u 0 et u 1 sont suffisamment proches de a),
alors la distance δn = |un − a| vérifie une relation de la forme δ n+1 ⩽ Kδ
φ
n , avec φ =
1 +
√
5
2
·
Donner alors le nombre d’étapes nécessaires pour approcher a avec une erreur majorée par 2 −52 ,
puis 2 −1000 . Comparer avec la méthode de Newton.
6 On fait l’hypothèse suivante, très optimiste pour la méthode de Newton : le coût de chaque évaluation
de f ′ est de l’ordre de celui de deux évaluations de f . Comparer alors les coûts des méthodes de
Newton et de la sécante, pour obtenir une précision donnée.
Tout comme la méthode de Newton, pour laquelle on peut remplacer f ′ (un) par la jacobienne, la méthode de la sécante a un analogue dans R n : il s’agit de la très belle méthode de Broyden.
Exercice 8.13 * Inversion par la (pseudo-)méthode de Newton.
Si on applique la méthode de Newton à la fonction x → ax−1 (avec a ∈ R ∗
+ ), on peut espérer approcher
l’inverse de a.
1 Expliciter la relation de récurrence mise en place dans la méthode de Newton... et constater qu’elle est
inutilisable !
On va plutôt s’intéresser à une autre suite convergeant vers
1
a
: on fixe x 0 (on verra comment plus tard)
et on définit par récurrence la suite (xn) n∈N par la relation x n+1 = xn(2 − axn).
2 Expliquer qualitativement le lien avec la méthode de Newton. Démontrer qu’en cas de convergence, la
limite vaut 0 ou
1
a
·
3 Programmer cette méthode et déterminer les cinq premiers termes de la suite, lorsque a = 2 et
x 0 ∈ {0, 0.4, 0.9, 1, 2}.
4 On suppose maintenant que A est une matrice et on considère une suite de matrice (Xn) n∈N vérifiant
la relation X n+1 = Xn(2In − AXn).
a) Quel est le coût (en termes d’opérations sur les flottants) de chaque itération ?
b) D’après [Pan et Schreiber], un bon choix de valeur de départ est X 0 = α 0
t A, avec
α 0 =
1
∥A∥ 1 ∥A∥ ∞
, où ∥A∥ 1 = max j
∑
i
|a i,j | et ∥A∥ ∞ = max i
∑
j
|a i,j |.
Programmer cette méthode d’inversion matricielle, en décidant d’un test d’arrêt raisonnable.
c) Évaluer la complexité de cette méthode (en cas de convergence, et en fonction du nombre d’itérations
finalement effectuées).
d) Tester, comparer avec les méthodes du chapitre précédent.
On représente figure 8.8 l’évolution de
A −1 − Xn
1
en fonction de n, avec A =
1 2
3
4 5
6
7 8 10
.