Polytech Lyon, département MAM Année universitaire 2017-2018

Analyse numérique Philomène BOBICHON

Correction feuille d’exercices n°3

Exercice 1.
Algorithme du double gradient conjugué (BiCG).
1. Soit A = A∗ > 0, b1 = b2 , et x01 = x02 , montrer que le BiCG est identique à
l’algorithme du CG dans le cas complexe.
On reprend l’algorithme du BiCG :
Données : x01 , x02
r10 = b1 − A∗ x02 ;
r20 = b2 − Ax01 ;
d01 = r10 ;
d02 = r20 ;
pour k = 0, . . . faire
(rk , rk )
αk = k2 1 k ;
(d2 , Ad1 )
x1 = xk1 + αk dk2 ;
k+1

xk+1
2 = xk2 + αk dk1 ;
r1k+1 = r1k − αk Adk2 ;
r2k+1 = r2k − αk A∗ dk1 ;
(rk+1 , rk+1 )
βk+1 = 2 k 1k ;
(r2 , r1 )
dk+1
1 = r1
k+1
+ βk+1 dk1 ;
dk+1
2 = r2k+1 + βk+1 dk2 ;
fin

Et on le modifie avec les hypothèses de départ. Si A = A∗ et x02 = x01 , alors r10 = r20 ,
donc d01 = d02 .
On a également
r1k ,r1k
• αk = (dk1 ,Ad1 )

• xk+1
1 = xk+1
2
• r1k+1 = r2k+1
(r1k+1 ,r1k+1 )
• βk = (r1k ,rk )

• dk+1
1 = dk+1
2

1
2. Soit A est une matrice symétrique complexe avec A = At (non hermitienne)
inversible, b1 = b2 et x01 = x02 . Montrer que le BiCG est identique à un algorithme
du CG appliqué directement au cas complexe.
Données : x01 , x02
t
r10 = b2 − A x01 ;
r20 = b2 − Ax01 ;
d01 = r10 ;
0
d02 = r20 = d1 ;
r10 = r02 ;
x02 = x01 ;
pour k = 0, . . . faire
(rk , rk )
αk = k1 1 k ;
(d1 , Ad1 )
x1 = xk1 + αk dk2 ;
k+1
k
xk+1
2 1 ;
= xk1 + αk d2 = xk+1
Abandon;
fin
Non équivalent. Il faut prendre le produit scalaire et non le produit hermitien.
3. Soit A une matrice inversible, supposons qu’il existe b 6= 0 tel que (b, Ab) = 0.
Montrer que l’initialisation x01 = x02 = 0 et b1 = b2 = b du BiCG conduit à un
Breakdown.
Données : x01 , x02
r10 = b − A∗ x01 ;
r20 = b − Ax02 ;
d01 = r10 = b;
d02 = r20 = b;
pour k = 0 faire
(r0 , r0 ) (b, b)
α0 = 02 1 0 = ;
(d2 , Ad1 ) b, Ab
fin
Impossible.
Exercice 2.
Soit la matrice A = Id +αB avec Id la matrice identité, α ∈ R et B anti-symétrique
(B T = −B).
(Ax, x)
1. Monter que = 1 pour x 6= 0.
(x, x)
On a B = −B T . ∀x ∈ Rn ,
(Bx, x) = (x, B T x)
= −(x, Bx)
= −(Bx, x)

2
donc

(Bx, x) = −(Bx, x)
⇔(Bx, x) = 0
⇔α(Bx, x) = 0

pour tout α ∈ R.
Donc :

(Ax, x) = (Id x, x) + α(Bx, x)

= (Id x, x)
= (x, x)

donc, pour tout x 6= 0

(Ax, x)
=1
(x, x)

2. A l’aide du procédé d’Arnoldi sur A, montrer que la matrice de Hessenberg est

une matrice tridiagonale de la forme :
 
1 −ν2
 ν2 1
 −ν3 


 ν3 1 −ν4 


 . . . . . . . . . 

 νn−1 1 −νn 
νn 1

Données : r0 6= 0
0
v 1 = krr0 k ;
pour j = 0, . . . faire
hi,j = (Avj , vi ) avec 1 ≤ i ≤ j;
ṽj+1 = Avj − ji=1 hi,j vi ;
P
hj+1,j = kṽj+1 k;
ṽj+1
vj+1 = ;
kṽj+1 k
fin
Pour i = j = 1 :

h11 = (Av1 , v1 ) = (v1 , v1 ) = 1

Pour i = 2, j = 1, on a

ṽ2 = Av1 − h11 v1 = (Id +αB)v1 − v1 = αBv1

h21 = |α|kBv1 k = ν2

3
 αBv1
v2 =
ν2

Pour i = 1, j = 2

h12 = (Av2 , v1 )
= (v2 , v1 ) + α(Bv2 , v1 )
(BBv1 , v1 )
= 0 + α2
ν2
(Bv 1 , −Bv 1)
= α2
ν2
α2
= − kBv1 k2 = −ν2
ν2

Pour i = 2 = j :

h22 = (Av2 , v2 ) = (v2 , v2 ) = 1

Pour i = 2, j = 3 :
2
X
v˜3 = Av2 − hi,2 vi
i=1
= Av2 − ν2 v1 − v2
= (Id +αB)v2 − ν2 v1 − v2
= αBv2 − ν2 v1

h3,2 = kαBv2 − ν2 v1 k = ν3

Supposons

νj = kαBvj−1 − νj−1 vj−2 k

(αBvj−1 − νj−1 vj−2 )
vj =
νj

On a

hi,j+1 = (Avj+1 , vi )
= ((Id +αB)vj+1 , vi )
= (vj+1 , vi ) + α(Bvj+1 , vi )
α
=0+ (B(αvj + νj vj−1 ), vi )
νj+1
α
= ((αBvj , vi ) + (Bνj vj−1 , vi ))
νj

4
Anwar réessaye :

r
v1 =
krk
h1,1 = (Av1 , v1 ) = 1
ṽ2 = Av1 − h12 v1 = (Id +αB)v1 − v1 = αBv1
p
h2,1 = kṽ2 k = |α| (Bv1 , Bv1 ) = ν2
v2 = ṽ2 (?)

h1,2 = (Av2 , v1 )
1
= α(ABv2 , v2 ) ×
ν2
α
= (Bv1 , At v2 )
ν2
α
= (Bv1 , v1 − αBv1 )
ν2
α α2
= (Bv1 , v1 ) − kBv1 k2
ν2 ν2
α
= − kBv1 k2 = −ν2
ν2

h2,2 = (Av2 , v2 ) = 1
v˜3 = Av2 − v2 + ν2 v1 = αBv2 + ν2 v1
h3,2 = kṽ3 k = kαBv2 + ν2 v1 k = ν3

Soit j ∈ J1, nK, on suppose que

pour i < j − 1


 hi,j = 0
hj,j = 1


 hj−1,j = −νj
hj+1,j = kαBvj + νj vj−1 k = νj+1


1
vj+1 = (αBvj + νj vj1 ) ×
νj+1

hi,j+1 = (Avj+1 , vi )
= (vj+1 , At vi )
1
= (αBvj + νj vj+1 , vi − αBvi ) ×
νj+1

5
 1
α(Bvj , vi ) + (νi vj+1 , vi ) − α2 (Bvj , Bvi ) − α(νj vj−1 , Bvi )


=
νj+1
α
=− (vj + αBvj + νj vj−1 , Bvi )
νj+1
α
=− (Avj + νj vj−1 , Bvi )
νj+1

1
vi+1 = (αBvi + νi vi−1 )
νi+1

αBvi = vi+1 νi+1 − νi vi1

1
=− (Avj + νj−1 vj−2 , vi+1 νi+1 − νi vi−1 )
νj+1

Cas i < j :
1
hi,j+1 = − (νi+1 (Avj , vi+1 ) −νi (Avj , vi−1 ) + νj−1 , vi+1 (vj−1 , vi+1 ) − νj−1 νi (vj−1 , vi−1 ))
νj+1 | {z } | {z }
=0 =0

Cas i < j − 1 < j :

hi,j+1 = 0

Cas i = j − 1 < j : (à vérifier)

hi,j+1 = constante(νj (Avj , vj ) + νj νj (vj−1 , vj ))
| {z }
=0

Cas i = j : on a visiblement fait une erreur

Exercice 3.
(GMRES) Soit la matrice A de taille n × n et b le second membre :
   
0 0 ... 1 1
1 0 . . . 0 0
A =  .. . . . . ..  b =  .. 
   
. . . . .
0 ... 1 0 0

1. Calculer les valeurs propres de A.

Soit λ ∈ C.

 
−λ 0 . . . 1
 1 −λ . . . 0 
det(A − λ In ) = det  .. . . .. 
 
 . . . . . . 
0 . . . 1 −λ

6
 −λ 1 −λ . . . 0
   
0 ... 0
..   . . . . . . .. 
1 −λ .  0 . 

n
= −λ det  .. . . . . . . ..  − (−1) det  .

 .. . . . −λ

 . . 
0 . . . 1 −λ 0 ... ... 1
n−1
Y
= −λ (−λ) − (−1)n
i=1
= (−λ) − (−1)n = 0
n

⇒ (−λ)n = (−1)n
⇒ λn = 1

avec λ ∈ exp i2πk et k ∈ J0, n − 1K.



n

2. En combien d’itérations l’algorithme du GMRES converge-t-il avec x0 = 0 ?

On rappelle l’algorithme d’Arnoldi :
Données : r0 6= 0
v1 = krr00 k ;
pour j = 0, . . . faire
hi,j = (Avj , vi );
ṽj+1 = Avj − ji=1 hi,j vi ;
P
hj+1,j = ṽj+1 ;
si hj+1,j 6= 0 alors
ṽj+1
vj+1 = ;
hj+1,j
sinon
Fin de l’algorithme;
fin
fin
Algorithme 1 : Algorithme d’Arnoldi

r0 b − Ax0 b
v1 = = = = b = e1
kr0 k kb − Ax0 k kbk

Pour j = 1 :

h1,1 = (e2 , e1 ) = 0
ṽ2 = Av1 − h1,1 v1 = Av1 = e2
h2,1 = ke2 k = 1
v2 = ṽ2 = e2

Pour j = 2 :

Av2 = e3

7
 h1,2 = (Av2 , v1 ) = 0
h2,2 = (Av2 , v2 ) = (e3 , e2 ) = 0
ṽ3 = Av2 − 0 = e3
v3 = ṽ3 = e3

Supposons vj = ej . C’est vrai pour k = 1, montrons que c’est vrai pour k + 1.

Pour j = k + 1 :

hi,j = (Avj , vi ) = (ej+1 , vi ) = 0 1≤i≤j

ṽj+1 = Avj − 0 = ej+1
hj+1,j = 1
vj+1 = ṽj+1 = ej+1

Si on résoud Ax = b avec b = e1 , alors x = en . On voit que dans l’algo les vi sont

la i-ème base (ei ). La solution est alors vn , on a donc pas d’échec de l’algorithme
d’Arnoldi : pas de convergence, donc GMRES converge en n itérations parce qu’on
construit un espace qui n’est pas suffisamment riche.
3. Démontrer que l’algorithme CGN converge en une itération dans ce cas particulier.
Exercice 4.
(GMRES) Soit la matrice A définie par blocs :
 
Id B
A=
0 Id

En combien d’itérations au maximum (quel que soit le choix de b) l’algorithme du

GMRES va-t-il converger ?