Corrigé de l’EXAMEN 1

MAT-18996: Analyse numérique pour l’ingénieur Hiver 2009

Question 1. (20 points)

L’équation x3 − 3x2 + x + 2 = 0 peut être ramenée de plusieurs façons à un problème
de point fixe x = g(x). Considérons les 3 algorithmes suivants du point fixe:

(i)
xn+1 = −x3n + 3x2n − 2 = g1 (xn )

(ii)
2
x2n + 1 +
xn
xn+1 = = g2 (xn )
3
(iii)
xn+1 = x3n − 3x2n + 2xn + 2 = g3 (xn )

a) [3 pts] Montrer que x̄ = 2 est un point fixe pour chacune des méthodes ci-dessus.
Réponse:

Le x̄ = 2 est un point fixe de g1 (x) car

g1 (2) = −23 + 3 ∗ 22 − 2 = −8 + 3 ∗ 4 − 2 = −10 + 12 = 2.

Le x̄ = 2 est un point fixe de g2 (x) car

2
22 + 1 +
g2 (2) = 2 = 6 = 2.
3 3
Le x̄ = 2 est un point fixe de g3 (x) car

g3 (2) = 23 − 3 ∗ 22 + 2 ∗ 2 + 2 = 8 − 12 + 4 + 2 = 2.

1
b) [9 pts] Sans calculer d’itération, faites l’étude de la convergence pour chacune
des trois méthodes ci-dessus: déterminer si la méthode est convergente ou non,
identifier le type de convergence (linéaire ou quadratique) lorsque la convergence
a lieu, et le taux de convergence le cas échéant.
Réponse:

Traitement de g1 (x):

g10 (x) = −3x2 + 6x alors g10 (2) = −3 ∗ 22 + 6 ∗ 2 = −12 + 12 = 0

Donc, la méthode est convergente car |g10 (x̄)| = |g10 (2)| < 1

De plus, g100 (x) = −6x + 6 alors g100 (2) = −6 ∗ 2 + 6 = −6 ; |g100 (2)| = 6

Donc, la convergence est quadratique.

Traitement de g2 (x):

2x 2 2∗2 2 4 2 7
g20 (x) = − 2 alors g20 (2) = − 2
= − =
3 3x 3 3∗2 3 12 6

Donc, la méthode est divergente car g20 (x̄) = g20 (2) > 1

Traitement de g3 (x):

g30 (x) = 3x2 − 6x + 2 alors g30 (2) = 3 ∗ 22 − 6 ∗ 2 + 2 = 12 − 12 + 2 = 2

Donc, la méthode est divergente car g30 (x̄) = g30 (2) > 1

2
c) [3 pts] Donnez un 4ème algorithme de point fixe (sans en faire l’étude).
Réponse:
Il y a plusieurs réponses possibles. Une parmi elles serait:
s
x3n + xn + 2
xn+1 =
3
On remarque que x̄ = 2 n’est pas le point fixe de cet algorithme.

d) [2 pts] Pour le premier algorithme, c’est-à-dire xn+1 = −x3n + 3x2n − 2, calculer

la première itération de l’algorithme de Steffenson à partir de x0 = 1.
Réponse:

Étape 1: 

 x1 = g(x0 )


x2 = g(x1 )
Algo de Steffenson est donné par
 (x1 − x0 )2
xStef f = x0 −


x2 − 2x1 + x0


Étape 2: 



x1 = g1 (1) = −1 + 3 − 2 = 0

x2 = g(0) = −0 + 0 − 2 = −2
Donc, pour x0 = 1,  (0 − 1)2 1
xStef f = 1 − =1− =2



−2 − 2 ∗ 0 + 1 −1

3
e) [3 pts] Expliciter la méthode de Newton appliquée à l’équation x3 −3x2 +x+2 =
0 et calculer la première itération à partir de x0 = 1.
Identifier f (x): f (x) = x3 − 3x2 + x + 2


 x0
Écrire l’algo de Newton: f (xn )
 xn+1 = xn −
f 0 (xn )


Calcul de f 0 (x): f 0 (x) = 3x2 

− 6x + 1
 x0

Donc, l’algo de Newton est: x3n − 3x2n + xn + 2
 xn+1 = xn −

3x2n − 6xn + 1

Calcul à partir de x0 = 1
 x0 = 1

x30 − 3x20 + x0 + 2 13 − 3 ∗ 12 + 1 + 2 1 3
 x1 = x 0 − 2
= 1 − 2
=1− =
3x0 − 6x0 + 1 3∗1 −6∗1+1 −2 2


4
Question 2. (16 points)
On désire approcher la racine x̄ située entre 2.5 et 2.8 de l’équation

f (x) = 0.

L’application de la méthode de Newton a produit les itérés suivants:

n xn
4 2.61421
5 2.62453
6 2.63151
7 2.63621
8 2.63937
9 2.64149

a) [12 pts] Déterminer l’ordre de convergence de l’algorithme pour la racine x̄. On

utilisera la définition suivante de l’erreur : en = |xn − xn+1 |

Réponse:

Construction des en :
e4 = |x4 − x5 | = |2.61421 − 2.62453| = 0.01032
e5 = |x5 − x6 | = |2.62453 − 2.63151| = 0.00698
e6 = |x6 − x7 | = |2.63151 − 2.63621| = 0.0047
e7 = |x7 − x8 | = |2.63621 − 2.63937| = 0.00316
e8 = |x8 − x9 | = |2.63937 − 2.64149| = 0.00212

en+1
Construction des :
en
e5 0.00698
= = 0.67635658914728
e4 0.01032
e6 0.0047
= = 0.67335243553011
e5 0.00698
e7 0.00316
= = 0.67234042553186
e6 0.0047
e8 0.00212
= = 0.67088607594944
e7 0.00316

5
 Discussion sur l’ordre de convergence:

en+1
Le quotient semble converger vers 0.67.
en
en+1
Comme |g 0 (x̄)| ≈ ≈ 0.67 alors la convergence est linéaire.
en
De plus, le taux de convergence est donné par |g 0 (x̄)| et, par conséquent, il
est de 0.67.

b) [4 pts] Que peut-on dire de la multiplicité de la racine? Justifier.

Réponse:

Pour la méthode de Newton, on a que

en+1 1
≈ |g 0 (x̄)| = g 0 (x̄) = 1 −
en m
où m est la multiplicité de la racine x̄.
1
Comme g 0 (x̄) ≈ 0.67 ≈ 1 −
m
2 1
on a que ≈1− d’où m = 3.
3 m
Donc, la racine x̄ est de multiplicité 3.

6
Question 3. (16 points)
On considère le système linéaire
    
2 −4 0 x1 0

 3 −7 −2  2  =  1 

x   

0 1 4 x3 −3

que l’on veut résoudre par la méthode de factorisation LU donnée par Crout. On
notera les éléments des matrices L et U respectivement par lij et uij avec i, j = 1, 2, 3.

a) [10 pts] Sachant que l22 = −1 et u12 = −2, compléter le calcul de la factorisation
de la matrice du système tout en tenant compte de la structure particulière de
la matrice.

b) [6 pts] Utiliser cette factorisation pour résoudre le système linéaire.

Réponse:

a) En mettant à profit la structure bande de A, on obtient :

   
2 0 0 1 −2 0
L =  3 −1 0 

, U = 0 1 2 


0 1 2 0 0 1
 
0
b) On résout d’abord Ly =  1 . On trouve
 

−3
 
0
 1 
y= 

−2

On résout ensuite U x = y. On trouve

 
2
x= 1 
 

−1

7
Question 4. (16 points)
On considère le système linéaire
! ! !
1 1.01 x1 1.005
Ax= = = b.
1.01 1 x2 1.005

a) [3 pts] Déterminer la solution exacte x = (x1 , x2 ) du système linéaire.

b) [2 pts] Calculer le résidu correspondant à l’approximation x̂ = (−4.5, 5.5).

c) [8 pts] Trouver une borne inférieure du conditionnement de A en utilisant la

norme infinie.

d) [3 pts] La valeur du conditionnement est-elle affectée si l’on change le second

membre du système linéaire par b = (−1, 1)? Justifier.

8
Question 5. (16 points)
a) [6 pts] Écrire la méthode de Newton pour résoudre le système

3 x2 + x y − 1 = 0
x y 2 + 4 y + 4 = 0.

Réponse:

X = (x, y)t , F (X) = (3 x2 + x y − 1, x y 2 + 4 y + 4)t

Xn+1 = Xn + ∆X où ∆X est la solution de J(Xn )∆X = −F (Xn ) et J(X) est
le jacobien de F en X.

!
6x + y x
J(X) =
y2 2xy + 4

b) [6 pts] Effectuer une itération en partant de (0, 1).

Réponse:

X0 = (0, 1)t , F (X0 ) = (−1, 8)

!
1 0
J(X0 ) =
1 4

∆X = (1, −9/4)t
X1 = (1, −5/4)t

c) [4 pts] Peut-on prendre comme point initial (0, 0)? Expliquer.

Réponse:

X0 = (0, 0)t
!
0 0
J(X0 ) =
0 4

J(X0 ) n’est pas inversible (car le déterminant est nul, par exemple), ∆X n’est
donc pas uniquement défini.

9
Question 6. (16 points)
Soit f (x) = ln(1 + x).
a) [6 pts] Trouver le développement de Taylor P2 (x) de degré 2 de la fonction f (x)
au voisinage de x0 = 0.
Réponse:

2
f (x0 + h) = f (x0 ) + hf 0 (x0 ) + h2! f 00 (x0 ) + ...
2
Ou f (x) = f (x0 ) + (x − x0 )f 0 (x0 ) + (x−x 2!
0)
f 00 (x0 ) + ...
2
Donc P2 (x) = f (x0 ) + (x − x0 )f 0 (x0 ) + (x−x 2!
0)
f 00 (x0 )

f 0 (x) = 1
1+x
, f 00 (x) = − (1+x)
1
2

x0 = 0, f (x0 ) = 0,f 0 (x0 ) = 1, f 00 (x0 ) = −1

P2 (x) = x − x2 /2

b) [4 pts] En utilisant P2 (x), calculer une approximation de ln(1.1).

Réponse:

ln(1.1) ≈ P2 (0.1) = 0.1 − 0.005 = 0.095

c) [6 pts] À l’aide de la formule d’erreur de Taylor, estimer l’erreur commise et la
comparer avec la valeur exacte de l’erreur fournie par votre calculatrice.
Réponse:

(x−x0 )3 000
f (x) = P2 (x) + R2 (x) où R2 (x) = 3!
f (ξ) et ξ compris entre x0 et x.

Ici, x0 = 0, x = 0.1, et f 000 (x) = 2

(1+x)3
donc

0.13 2
R2 (x) =
3! (1 + ξ)3

Comme 0 ≤ ξ ≤ 0.1, 1 ≤ 1 + ξ ≤ 1.1, donc 1 ≤ (1 + ξ)3 ≤ 1.13 et

1
≤1
(1 + ξ)3

10
D’où
10−3
|R2 (0.1)| ≤
3
La calculatrice donne ln(1.1) ≈ 0.0953101798, donc l’erreur est environ 3.101798×
−3
10−4 ce qui est bien inférieur à 103 ≈ 3.333333 × 10−4 .

11