Enoncs et corrections : Ana Matos.

Mthodes itratives

Z  ZZ  Z    Z Z  Z Z

Exo7

Exercice 1 1 a a Soit a R et A = a 1 a a a 1 1. Pour quelles valeurs de a A estelle dnie positive ? 2. Pour quelles valeurs de a la mthode de GaussSeidel estelle convergente ? 3. Ecrire la matrice J de litration de Jacobi. 4. Pour quelles valeurs de a la mthode de Jacobi convergetelle ? 5. Ecrire la matrice L1 de litration de GaussSeidel. Calculer (L1 ). 6. Pour quelles valeurs de a la mthode de GaussSeidel convergetelle plus vite que celle de Jacobi ?
[002235]

Exercice 2 Soit A une matrice hermitienne inversible dcompose en A = M N o M est inversible. Soit B = I M 1 A la matrice de litration : xn+1 = Bxn + c. Supposons que M + M A soit dnie positive. 1. Soit x un vecteur quelconque et on pose y = Bx. Montrer lidentit : (x, Ax) (y, Ay) = ((x y), (M + M A)(x y)). 2. Supposons que A est dnie positive. Soit x = 0 un vecteur propre de B associ la valeur propre , y = Bx = x. Utiliser lidentit prcdente pour montrer que | | < 1. Que peuton conclure sur la convergence de la mthode ? 3. Supposons maintenant que (B) < 1. montrer que A est dnie positive. 4. Supposons A dcompose par points ou par blocs sous la forme A = D E F avec D dnie positive. Montrer que la mthode de relaxation par points ou par blocs pour 0 < w < 2 converge si et seulement si A est dnie positive.
Correction
[002236]

Exercice 3 Soit A = I E E une matrice carre dordre N o E est une matrice strictement triangulaire infrieure (ei j = 0 pour i j). Pour rsoudre le systme Ax = b, on propose la mthode itrative dnie par (I E)x2k+1 = E x2k + b (I E )x2k+2 = Ex2k+1 + b 1. Dterminer B et c pour que lon ait : x2k+2 = Bx2k + c. Vrier que B = M 1 N et A = M N avec M = (I E)(I E ) , N = EE .

2. Montrer que M + N est une matrice dnie positive. En dduire une condition ncessaire et sufsante pour la convergence de la mthode.
Correction
[002237]

Exercice 4 Soient A et B deux matrices relles dordre N et a, b deux vecteurs de Rn . On considre les deux itrations suivantes : xk+1 = Byk + a k = 0, 1, (1) yk+1 = Axk + b avec x0 , y0 Rn donns. 1. Dterminer une condition ncessaire et sufsante de convergence des deux suites de vecteurs. 2. Soit zk = (xk , yk )T R2n . Montrer que (1) peut scrire zk+1 = Czk + c o C est une matrice dordre 2n. Expliciter C et c. 3. Montrer que 2 (C) = (AB). 4. On considre maintenant les deux itrations suivantes : xk+1 = Byk + a yk+1 = Axk+1 + b k = 0, 1, (2)

Donner une condition ncessaire et sufsante de convergence. Montrer que (2) est quivalent zk+1 = Dzk + d o D est une matrice dordre 2N. Montrer que (D) = (AB). 5. Taux de convergence On appelle taux de convergence asymptotique de la matrice itrative M le nombre R(M) = ln((M))). On pose ek = xk x lerreur de litr dordre k. (a) Montrer que le nombre ditrations k pour rduire lerreur dun facteur , i.e., k ln . R(M)
ek e0

vrie

(b) Comparer le taux de convergence des algorithmes (1) et (2).

Exercice 5 On considre le systme Ax = b avec A= 3 1 0 0 0 1 2 2 0 0 0 1 3 1 0 0 0 1 4 1 0 0 0 3 1 (3)

1. Dcomposer A sous la forme LU et en dduire que (3) admet une solution unique x . 2. Ecrire litration de GaussSeidel pour ce systme, cestdire, le systme linaire donnant Xn+1 = (xn+1 , yn+1 , zn+1 ,tn+1 , un+1 ) en fonction de Xn = (xn , yn , zn ,tn , un ). 2

3. Pour tout n N on pose en = Xn x . Montrer quil existe a [0, 1[ tel que : n N En dduire la convergence de la suite. 4. Dterminer la matrice de GaussSeidel L1 associe A. Calculer L1 (Xn ) vers x . 5. Soit A Rnn vriant la proprit suivante : |ai j | j=i |ai j | i = 2, , n |a11 | > j=1 |a1 j | et sur chaque ligne de A il existe il existe un terme non nul ai j pour i 2 et j < i. Montrer qualors la mthode de GaussSeidel converge.
Correction
[002239]
.

en+1

a en

En dduire la convergence de

Retrouver cette che et dautres exercices de maths sur exo7.emath.fr 3

Correction de lexercice 2 1. Pour le membre de gauche on obtient (x, Ax) (y, Ay) = (x, AM 1 Mx) + (M 1 Ax, Ax) (M 1 Ax, AM 1 Ax) Pour le membre de droite on obtient y = Bx = x M 1 Ax x y = M 1 Ax et donc (x y, (M + M A)(x y)) = (M 1 Ax, (M + M A)M 1 Ax) = (M 1 Ax, Ax) + (M 1 Ax, M M 1 Ax) (M 1 Ax, AM 1 Ax) Mais (M 1 Ax, M M 1 Ax) = (x, (M 1 A) M M 1 Ax) = (x, AM 1 Ax) ce qui ni la dmonstration. 2. y = Bx = x x y = (1 )x. En utilisant lgalit prcdente (x, Ax) (y, Ay) = (x, Ax) ( x, A( x)) = (1 | |2 )(x, Ax) (x y, (M + M A)(x y)) = ((1 )x, (M + M A)((1 )x)) = |1 |2 (x, (M + M A)x) et donc (1 | |2 )(x, Ax) = |1 |2 (x, (M + M A)x) ne peut pas tre = 1 car sinon y = Bx = x x M 1 Ax = x M 1 Ax = 0 x = 0. Donc = 1, M + M A dnie positive, |1 |2 > 0, A dnie positive impliquent que 1 | |2 > 0 | | < 1. Donc (B) < 1 et la mthode itrative converge. 3. Dmonstration par absurde. Supposons que ce nest pas vrai : x0 = 0 0 = (x0 , Ax0 ) 0. Alors la suite xn = Bxn1 = Bn x0 tend vers 0 et lim n = lim(xn , Axn ) = 0 On utilise maintenant la relation de la question 1 avec x = xn1 et y = Bxn1 = xn et on obtient n1 n = (xn1 xn , (M + M A)(xn1 xn ) > 0 si xn1 xn = 0 (ce qui est vrai car sinon xn1 = xn = Bxn1 et B a une valeur propre = 1) Donc (n1 n ) est une suite strictement dcroissante convergeant vers 0 avec 0 < 0. Ceci est impossible et donc A est dnie positive 4. Soit A = D E F la dcomposition usuelle de A. Comme A est hermitienne, D = D et F = E . Pour la mthode de relaxation on a M = D/w E et donc M + M A = D/w F + D/w E D + E + F = 2w D w

qui est hermitienne. Pour 0 < w < 2, M +M A est dnie positive, alors des deux questions prcdentes on conclut que la mthode converge ssi A est dnie positive.

Correction de lexercice 3 1. On a x2k+1 = (I E)1 E x2k + (I E)1 b et donc x2k+2 = (I E )1 E(I E)1 E x2k + (I E )1 E(I E)1 b + (I E )1 b Mais E(I E)1 = (I E)1 E et alors x2k+2 = (I E )1 (I E)1 EE x2k + (I E )1 (I E)1 (E + I E)b = M 1 Nx2k + M 1 b avec M = (I E)(I E ), N = EE , M N = I E E = A

2. M + N = I E E + 2EE et donc v (M + N)v = v 2 v Ev v E v + 2v EE v = E v 2 + ( v 2 + E v 2 2 2 galit 2 v E v 2|(v, E v)| 2|Re(v, E v)| et donc ( v v (M + N)v E v
2 +( 2 2

2 2Re(v, E v)) 2

On a lin-

E v 2 )2 v

2 2+

E v

2 2 2Re(v, E v)

v E v 2 )2 implique que
2

v (M + N)b = 0 E v

= 0 et v

= E v

=0

Donc M + N est dnie positive et en appliquant un rsultat dun exercice prcdent on conclut que la mthode converge ssi A est dnie positive.

Correction de lexercice 4 1. Cest facile voir que si (xk ) converge vers x et (yk ) converge vers y , alors x et y sont solution des systmes (I BA)x = Bb + a et (I AB)y = Aa + b. On a : xk+1 = B(Axk1 + b) + a = BAxk1 + Bb + a yk+1 = A(Byk1 + a) + b = AByk1 + Aa + b et donc (xk ) converge ssi (BA) < 1 et (yk ) converge ssi (AB) < 1. 2. zk+1 = Czk + c avec C = 0 B A 0 ,c = a b

3. Soit valeur propre non nulle de C et z = (x, y)T vecteur propre associ Cz = z By = x ABy = Ax = 2 y Ax = y

2 est valeur propre de AB. Soit maintenant valeur propre de AB u = 0 : C et donc 2 (C) = (AB) 4. D = 0 B , 0 AB tion prcdente. (a) ek = M k e0 d=
ek e0

ABu = u. On pose 2 = et x = Bu, y = u = Bu 2u = x y

x y

Bu ABu

a Aa + b

. La dmonstration de (D) = (AB) se fait comme dans la ques1/k

5.

M k . Il suft donc davoir M k

1/k log( M k

1/k )

1 log k

cest- dire k

log log( M k

Mais comme (M) M k

1/k

on obtient nalement

k log /R(M) (b) nous avons 2 (C) = (AB) (C) = (AB) et (D) = (AB) . Donc (D) < (C) R(D) > R(C). Donc on atteint la mme rduction derreur avec un plus petit nombre ditrations de la mthode 2)

Correction de lexercice 5 1.

2. Itration de Gauss-Seidel : (D E)Xn+1 = FXn + b avec 0 1 3 1 2 0 1 , F = 0 1 DE = 0 2 3 0 0 1 4 0 3 0 0 0 0 1 1

3. en = Xn X , , Xn+1 = (D E)1 FXn + (D E)1 b, X = (D E)1 FX + (D E)1 b en+1 = (D E)1 Fen On obtient alors (D E)en+1 = (D E)1 Fen et si on crit composante composante on obtient 3e1 = e2 |e1 | 1 en n n+1 n+1 3 1 1 e1 + 2e2 = e3 |e2 | 6 en + 2 en = 2 en n n+1 n+1 n+1 3 22 7 2e2 + 3e3 = e4 |e3 | 3 3 en + 1 en = 9 en n n+1 n+1 n+1 3 en+1 32 + 4e4 = 3e5 |e4 | n n+1 n+1 e4 + e5 n+1 n+1 et donc en 4. (D E)
1 17 49

en

3 + 4

en

34 16

en

=0

|e5 | n+1

17 18

en

17 en 18 0 1 3 1 12 1 12
1 2

1 6 = 1 9 1 36
1 36

1 3

0 0
1 12 1 12 1 3

0 0 0 1 4 0 0
1 12 1 12 1 3 1 4

0 0 0 0 1

, 0 0 0 3 4
3 4

L1 = (D E) F =
1

1 0 3 1 0 6 1 0 9 1 0 36 1 0 36

0
1 2 1 12 1 12 1 2

4 et donc L1 = max( 1 , 6 , 17 , 32 , 32 ) = 17 . 3 18 36 36 18 On en dduit donc la convergence de (Xn ) vers X .