Introduction

Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Méthodes itératives pour la résolution de

systèmes linéaires de grande taille

Université Cadi Ayyad, Faculté des Sciences et Techniques -

Master MODASIM S3

Abdeslem Had Bentbib

22-10-2024

1/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Contenu
1 Introduction
2 Méthodes de projection
3 Méthode de type sous-espaces de Krylov
Motivation
4 Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
5 Méthode de GMRES : Generalized Minimal Residual Method
6 Méthode de Lanczos
Algorithme de LANCZOS symétrique
7 Lanczos Bi-orthogonalisation
8 Lanczos et le Gradient Conjugué
9 Le Gradient Biconjugué variante de Lanczos Biorthogonal
Gradient biconjugué
2/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Introduction

La résolution de nombreux problèmes de calcul scientique se

ramène à la résolution de systèmes linéaires :
Ax = b (1)
où A∈ Rn×n est une matrice inversible, généralement creuse
de grande taille.
Les méthodes classiques, directes (Gauss, LU, ...) ou itératives
(Jacobi, Gauss-Siedel, SOR, ...) ne sont pas applicables
directement.
.
3/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Méthodes de projection

Dénition
Soit K et L deux s.e.v de Rn de même dimension m. Une méthode
de projection sur K orthogonalement à L est un procédé qui donne
une approximation x̃ de x ∗ = A−1 b vériant :
x̃ ∈ K et r˜ = b − Ax̃ ⊥ L.

Si x 0 est une donnée initiale dans Rn , alors on cherche x̃ = x 0 + δ

tel que r˜ = r 0 − Aδ ⊥ L avec δ ∈ K (Petrov-Galerkin).

4/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

C'est-à-dire :
x̃ = x 0 + δ

δ∈K
< − Aδ, w >= 0
r0 ∀w ∈ L

Les méthodes de projection dièrent par le choix des sous espaces

L et K.

5/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Représentation matricielle
Soient V = [v1 , · · · , vm ] ∈ Rn×m une base de K et
W = [w1 , · · · , wm ] ∈ Rn×m une base de L. La solution
approximative est écrite sous la forme :
x̃ = x 0 + Vy y ∈ Rm


W ⊤ r˜ = W (r − AVy ) = 0 ⇒ W AVy = W ⊤ r 0 (⋆)

⊤ 0 ⊤

6/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Le problème revient a résoudre le système (⋆) de petite taille, la

matrice B = W ⊤ AV est la matrice obtenu par projection de taille
m × m.

La solution est donnée par :

x̃ = x 0 + Vy = x 0 + V (W ⊤ AV )−1 W ⊤ r 0

7/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Deux classes de méthodes polynomiales de type Krylov appelées

aussi méthodes de Projection :
1 Méthodes de Projection Orthogonal, L ≡ K ( Arnoldi, FOM)
2 Méthodes de Projection Oblique, L ≡ AK (GMRES)
x k = arg min∥Ax − b∥
x∈Kk

8/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Proposition
si A, L et K remplissent une des deux conditions suivantes :
1 A dénie positive et L = K

2 A régulière et L = AK

Alors, B = W ⊤ AV est une matrice régulière pour n'importe quelle

base V de K et W de L.

9/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme générale

tant que ||r k || > tolerance

i) choisir deux sous espaces Kk et Lk de même dimension
m << n.
ii) choisir deux bases Vk de Kk et Wk deLk .
iii) résolution de (WkT AVk )y k = WkT r k .
vi) x k+1 = x k + Vk y k et r k+1 = r k − AVK yk

10/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Remarque
La méthode de Gauss-Seidel n'est qu'une méthode de
projection où à chaque étape k on prend
Kk = Lk = vect{ei }i = 1, · · · , n et on recommence.
La plus profonde descente est une méthode de projection
orthogonale où à chaque étape (k) on a :
Lk = Kk = vect{r (k) } .
Gradient conjuguée est une méthode de projection orthogonale
où à chaque étape (k) on a :
Lk = Kk = vect{r (0) , Ar (0) , · · · , Ak−1 r (0) } ( sous-espace de
Krylov d'ordre k associé à A et r (0) ).

11/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Proposition
Si A est symétrique dénie positive et L = K, alors x̃ ∈ K est
le résultat d'une projection orthogonale sur K avec comme
vecteur initiale x (0) ssi
x̃ = arg min E (x) avec E (x) = ∥x − x ∗ ∥A C'est une méthode
x∈x (0) +K
de minimisation de l'erreur.
Si A est régulière et si L = A(K), alors x̃ ∈ K est le résultat
d'une projection oblique sur K orthogonalement à L = A(K)
avec comme vecteur initiale x (0) ssi
x̃ = arg min ∥b − Ax∥2 C'est une méthode de minimisation du
x∈x (0) +K
résidu.
12/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Motivation
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Méthode de type sous-espaces de Krylov

Motivation des méthodes de type sous-espaces de Krylov

(méthodes polynomiales) pour approximer la solution x ∗ = A−1 b.
Cayley-Hamilton
Il existe un polynôme p de degré au plus n − 1 tel que
A−1 b = p(A)b

L'objectif des méthodes polynomiales est d'approcher ce polynôme

p(X).

13/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Motivation
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Motivation

Soient x (0) une donnée initiale, r (0) le résidu correspondant

r (0) = b − Ax (0) et s = gradA r (0) . Donc P(A)r (0) = 0Rn où P(A)
s'écrit sous la forme suivante :
P(A) = As + αs−1 As−1 + · · · + α1 A + α0 In

avec α0 ̸= 0 et P(A) le polynôme minimale associé à r (0) .

14/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Motivation
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

P(A)r (0) = 0Rn

⇒ As r (0) + αs−1 As−1 r (0) + · · · + α1 Ar (0) + α0 r (0) = 0Rn
−1 s (0) αs−1 s−1 (0)
⇒ α0 A r − · · · − αα01 Ar (0) + Ax (0) = b
− α0 A r
 
−1 s−1 (0) αs−1 s−2 (0)
 
α1 (0)
⇒ A A r − A r − ··· − r +x (0)  = b
α0 α0 α0
| {z }
Ps−1 (A)r (0) ∈ Ks = Vect{r (0) , Ar (0) , · · · , As−1 r (0) }
(0)
La solution x ∗ = A−1 b est dans le sous-espaces ane x (0) + KmA,r .
A,r (0)
Km = Vect{r (0) , Ar (0) , · · · , Am−1 r (0) }, est appelé sous-espaces
de Krylov d'ordre m associé à la matrice A et le vecteur r (0) . En
particulier, x ∗ = A−1 b ∈ KmA,b = Vect{b, Ab, · · · , Am−1 b}.
15/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Motivation
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Dénition
Une méthode itérative est polynomiale si et seulement si elle génère
une suite vectorielle
xk = x0 + pk (A)v
où pk est un polynôme, v un vecteur et x0 une donnée initiale.
L'objectif des méthodes de type sous-espaces de Krylov est
d'approximer la solution sans calcul explicite des polynômes pk .

16/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Motivation
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Remarque
Une méthode de projection de type sous-espace de Krylov est une
méthode itérative basée sur le principe de projection orthogonale ou
oblique sur K = Km (A, r (0) ) un sous-espace de Krylov. Elle est
aussi directe puisqu'on atteint la solution en m = gradr (0) (A) + 1
(théoriquement parlant). Le choix des bases de K et L inuence sur
l'ecacité numérique de la méthode.

17/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Full Orthogonalization Method (FOM)

FOM est une méthode de projection orthogonale sur le sous-espace
de Krylov Km . La première des choses à faire est de déterminer une
base V de sous-espace de Krylov. Le Procédé d'Arnoldi permet de
calculer une base orthonormé V de Km .

18/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithm 1 Arnoldi Simple

r (0)
1: v1 ← où β = ∥r (0) ∥
β
2: for j = 1, 2, · · · , m do
j
où hi,j =< A · vj , vi >
X
3: w ← A · vj − hi,j · vi
i=1
4: hj+1,j ← ∥w ∥
5: if hj+1,j = 0 then
6: Stop ▷ solution atteinte
7: else w
8: vj+1 =
hj+1,j
9: end if
19/97 10: end for Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

D'après l'algorithme on a :
A · v1 = h1,1 v1 +h2,1 v2
A · v2 = h1,2 v1 +h2,2 v2 + h3,2 v3
.. .. ..
. . .
A · vm = h1,m v1 +h2,m v2 + · · · + hm,m vm + hm+1,m vm+1

20/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Matriciellement, on pose Vm = [v1 , v2 , · · · , vm ]

 
h1,1 h1,2 h1,3 ··· h1,m
 h2,1 h2,2 h2,3 ··· h2,m 
... ... .. .. 
 
 0 . .  ⊤

A·Vm = Vm · +hm+1,m (vm+1 ·em )
 .. ... ... ... .. 
 . . 
0 0 0 hm−1,m hm,m
(2)

21/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

d'où
⊤
A · Vm = Vm · Hm + hm+1,m (vm+1 · em ) ⇒ Vm⊤ · A · Vm = Hm

Remarque
D'après l'algorithme on a :
x (m) = x (0) + Vm y (m)


r (m) = r (0) − AVm y (m)
 ⊤)
A · Vm = Vm · Hm + hm+1,m (vm+1 · em

22/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

En utilisant la condition de Galerkin c'est-à-dire r (m) ⊥ Vm on a :

Vm⊤ · r (m) = Vm⊤ · r (0) − Vm⊤ AVm y (m) = 0

or Vm⊤ · A · Vm = Hm donc y (m) est solution d'un système de petite

taille :
Hm y (m) = Vm⊤ · r (0) = ∥r (0) ∥e1 = βe1
d'où
x (m) = x (0) + Vm Hm
−1 ⊤ (0)
Vm r

23/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

A chaque étape on résout le système de Hessenberg Hm y (m) = βe1

de taille m ≪ n.
On a aussi : A · Vm = Vm+1 · H̃m où H̃m est de taille (m + 1) × m
 
Hm
H̃m =
0 ··· 0 hm+1,m

De plus on sait que :

r (m) = r (0) − Vm Hm y (m) − hm+1,m (em
⊤
· y (m) )vm+1

24/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

D'où :
∥r (m) ∥ = ∥Vm βe1 − Hm y (m) − hm+1,m (em
⊤ · y (m) )v


m+1 ∥
(m)
= ∥hm+1,m · ym vm+1 ∥
(m)
= | ym | · | hm+1,m |

Proposition
Si pour j < m, on obtient hj+1,j = 0 dans l'algorithme d'Arnoldi,
cela veut dire que j = gradr (0) et que la solution x ∗ ∈ x (0) + Kj
(solution atteinte). De plus le sous espace Kj est invariant par A.

25/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithm 2 Arnoldi Modié

r (0)
1: v1 ← où β = ∥r (0) ∥
β
2: for j = 1, 2, · · · , m do
3: w ← A · vj
4: for i = 1, · · · , j do
5: hi,j ←< w , vi > et w ← w − hi,j · vi
6: end for
7: hj+1,j ← ∥w ∥
8: if hj+1,j = 0 then Stop ▷ solution atteinte
9: else w
10: vj+1 =
hj+1,j
11: end if
26/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Remarque
L'algorithme d'Arnoldi modié est mathématiquement équivalent à
celui d'Arnoldi, par contre il présente une stabilité numérique.
Malheureusement si l'instabilité est trop grande d'autres techniques
sont nécessaires.

27/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Orthonormalisation
une famille de vecteurs de Rn . Cherchons une base
{u1 , u2 , u3 }
orthonormé du sous-espace vect{u1 , u2 , u3 }.
Gram-Schmidt
u1
q1 = , r11 = ∥u1 ∥
∥u1 ∥
u2 − < u2 , q1 > q1
q2 = , r12 =< u2 , q1 >
∥u2 − < u2 , q1 > q1 ∥
| {z }
r22
u3 − < u3 , q2 > q2 − < u3 , q1 > q1
q3 = , ri 3 =< u3 , qi >, i = 1, 2
∥u3 − < u3 , q2 > q2 − < u3 , q1 > q1 ∥
| {z }
r33
28/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Gram-Schmidt

Gram-Schmidt
donc  
r11 r12 r13
[u1 , u2 , u3 ] = [q1 , q2 , q3 ] ·  0 r22 r23 
0 0 r33
d'où {q1 , q2 , q3 } forme une base orthonormée de vect{u1 , u2 , u3 } si
rang {u1 , u2 , u3 } = 3.

29/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Householder

Householder
Étape 1 : Calcul du vecteur v1 de norme 1 tel que
I − 2v1 · v1⊤ ·u1 = α1 e1 = r11 e1 = ±∥u1 ∥e1
 

| {z }
H1

On sait que ce vecteur est donné par :

u1 + sign e1⊤ · u1 ∥u1 ∥e1


v1 =
∥u1 + sign e1⊤ · u1 ∥u1 ∥e1 ∥

30/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Householder

Householder
à la n de l'étape 1 on obtient :
 
r11
0 
H1 · [u1 , u2 , u3 ] =  . , H1 u2 , H1 u3 
 ..
 

0
Étape 2 : Posons w = H1 u2 et annulons w (1). Et calculons v2
I − 2v2 · v2⊤ ·w = α2 e2
 

| {z }
H2
31/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Householder

Householder
à la n de l'étape 2 on obtient :
 
r11 r12
 0 r22 
0 0 , H2 · H1 u3 
 
H2 · H1 · [u1 , u2 , u3 ] = 
 .. ..

 . .


0 0
Étape 3 : nalement on pose w = H 2 H1 u 3 et on annule w (1) et
w (2) on obtient

32/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Householder

Householder
 
r11 r12 r13
 0 r22 r23 
0 0
 
r33

[u1 , u2 , u3 ] = H1 H2 H3 ·  0 0 0
 
. .. .. 
 ..
| {z }  
Q∈Rn×n 
. .
0 0 0
la méthode de Householder présente les propriétés suivantes :
Le rang de {u1 , u2 , u3 } est déterminé par le nombre des rii non
nuls. Une base orthonormée de vect{u1 , u2 , u3 } est donnée par
{Qe1 , Qe2 , Qe3 } si rang {u1 , u2 , u3 } = 3.
33/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Householder

Householder
Les r premières colonnes de Q forme une base orthonormée de
vect{u1 , u2 , u3 } = vect{A} et le reste forme une base de
vect{A}⊥ .
Toute matrice orthogonale d'ordre n est le produit de n
matrices de Householder. Soit A une matrice orthogonal
d'ordre n, en appliquant QR-Householder sur
A = [a1 , a2 , · · · , an ] on obtient :

±1 ∗ · · ·
 
∗
 0 ∗ ··· ∗
[u1 , u2 , u3 ] = H1 ·  .
 .. ∗ · · ·
 

∗
34/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Householder

Algorithm 3 Arnoldi Householder

1: z1 = r (0) ,
2: for j = 1, 2, · · · , m, m + 1 do
3: on calcul le vecteur de Householder w de norme 1 tel que
w (i) = 0, i = 1, 2, · · · , j − 1
4: on calcul la matrice de Householder Pj = I − 2w · w ⊤ .
5: hj−1 ← Pj · zj ▷ hj−1 = H(:, j − 1) est la colonne j − 1 de la
matrice de Hessenberg
6: v j = P1 · · · Pj e j
7: if j < m then
8: zj+1 = Pj Pj−1 · · · P1 Avj
9: end if
35/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Restarted FOM
la méthode FOM est dénie par l'itération x (m) = x (0) + Vm y (m)
où y (m) = Hm−1 (βe1 ) et on sait que le résidu en chaque itération
est donnée par : r (m) = b − Ax (m) = −hm+1,m ym(m) vm+1 . Au lieu de
travailler avec la méthode d'Arnoldi en augmentant a chaque foi m,
ce qui conduit à augmenter considérablement la taille de Hm , on
peut faire mieux en redémarrant notre méthode par x (0) = x (m) ,
C'est la méthode Restarted FOM.

36/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme Général :
tant que ||r m−1 || > tolerance
i) Lm = Km = Km (A, r 0 )
ii) Construction d'une base Vm orthonormale de Km (A, r 0 ) en
appliquant l'algorithme d'Arnoldi avec :
Gram-Schmidt modié oubien les transformations de
Householder dans l'étape d'orthonormalisation.
iii) Résolution du système (Hm )y m = ||r 0 ||e1
avec une décomposition LU par exemple.
vi) x m = x 0 + Vm y m et r m = r 0 − AVm ym

37/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Méthode de GMRES

Méthode de GMRES
La méthode de GMRES est une méthode de projection oblique sur
le sous espace de Krylov Km = {r0 , Ar0 , · · · , Am−1 r0 }. D'après une
proposition précédente, c'est une méthode de minimisation du
résidu de x = x0 + Vm y avec Vm est la base obtenu par Arnoldi :
∥b − Ax̃∥ = min ∥b − Ax∥
x∈x0 +Km

38/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Méthode de GMRES

On a : ∥b − Ax∥ = ∥b − Ax0 − AVm y ∥

= ∥r0 − Vm+1 H̃m y ∥
= ∥βVm+1 e1 − Vm+1 H̃m y ∥ (β = ∥r0 ∥)
= ∥Vm+1 (βe1 − H̃m y )∥ (Vm+1 orthogonale)
= ∥(βe1 − H̃m y )∥
= J (y )

Le problème revient à calculer ỹ ∈ Rn t.q : ỹ = arg minm J (y ).

y ∈R
Donc c'est un problème de moindres-carrés de Hessenberg de taille
(m + 1) × m avec m << n.
39/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

QR de la matrice de Hessenberg H̃m par rotations de Givens

Le but de cette partie est de résoudre le problème
min ∥(βe1 − H̃m y )∥ par résolution d'un système linéaire
y ∈Rm

triangulaire R̃y = βQ ⊤ e1 où R̃ = 0 ·R· · 0 00

 

Remarquons d'abord que : ∃θ tel que :

a2 + b 2
    √ 
cos θ sin θ a
=
− sin θ cos θ b 0
pour c = cos θ et s = sin θ on a :
√
ca + sb = a2 + b 2

(∗)
−sa + cb = 0
40/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Rotations de Givens
Posons c = √a2a+b2 et s = √a2b+b2 ( c et s vérie (∗) ). Une
rotation de Givens dans Rm+1 d'axes ei , ej permettant d'annuler la
j -ème composante utilisant la i -ème :

Gi,j = In + (c − 1) ei ei⊤ + ej ej⊤ + s ei ej⊤ − ej ei⊤

   

À l'aide des rotations de Givens on obtient la décomposition :

H̃m = G1⊤,2 G2⊤,3 · · · Gm,m+
⊤
1 R̃

41/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

il soutient sa thèse (qu'il envoya à Albert Einstein)sur la

théorie de la relativité en 1921 à l'université de Szeged, puis sa
thèse d'habilitation à Francfort(1927)
Ses articles couvrent un vaste éventail de disciplines, y compris
la relativité générale, la mécanique quantique, le calcul
scientique, les mathématiques appliquées et l'analyse
numérique.
1)L'algorithme de Lanczos, pour trouver les valeurs propres des
matrices symétriques ;
2) L'approximation de Lanczos, pour la fonction gamma ;
3) La méthode du gradient conjugué pour la résolution itérative des
systèmes d'équations linéaires de grande taille...
42/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme de Lanczos symétrique

La méthode de Lanczos se base sur le théorème suivant :

Théorème :
A partir de tout vecteur unitaire u = q1 et toute matrice
symétrique A, il existe une famille orthonormée q1 , q2 , ... tel que
Aqj = bj−1 qj−1 + aj qj + bj qj+1 : Les qj sont les colonnes d'une
matrice orthogonale Q T Q = I et la matrice T = Q T AQ
symétrique tridiagonale.

43/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

L'algorithme de Lanczos s'écrit :

Algorithme de Lanczos symétrique
1 : u vecteur initial donné, β = ||u||
u
2 : q1 =
β
3 : On pose β1 = 0 , q0 = 0
4 : for k = 1 : n
5 : αk = ⟨qk , Aqk ⟩
6 : w = Aqk − βk qk−1 − αk qk
7 : βk+1 = ||w ||. Si βk+1 = 0 stop sinon
w
8 : qk+1 =
βk+1
9 : end
10 : T = tridiag (βi , αi , βi ) et Q = [q1 , q2 , ..., qn ]
44/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Si la matrice A est symétrique, alors la matrice Hm de Hessenberg

calculée par Arnoldi l'est aussi. Hm est donc symétrique
tridiagonale.
En eet, d'après l'algorithme d'Arnoldi
hij =< Avj , vi >=< vj , Avi > pour i = 1, · · · , j et on sait que
i+1
. Pour i = 1, · · · , j − 2 on a k varie de
X
Avi = hki vk
k=1
1, · · · , j − 1 et donc hij =< vj , Avi >= 0. et on a de plus
hj,j−1 =< Avj−1 , vj >=< vj−1 , Avj >=< Avj , vj−1 >= hj−1,j

45/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Donc
 
α1 β2
 β2 α2 β3 
... ...
 
⊤
 
A·V =V · β3  + βm+1 vm+1 · em
...
 
 
 αm−1 βm 
βm αm

46/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Montrons eectivement que Vm est orthogonale c'est-à-dire :

montrons l'assertion (Pk ) vk+1 ⊥ vi i = 1, · · · , k . On suppose
que (Pj ) est vraie pour j = 1, 2, · · · , k − 1.
(P1 ) est vraie car
< v1 , v2 >= 0 ⇒< v1 , A v1 − α1 v 1 >= 0 ⇒ α1 =< A v1 , v1 >.

47/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

1
< vk+1 , vk > = < wk , vk >
βk+1
1
= < A vk − βk vk−1 − αk vk , vk >
βk+1
 
1 < A vk , vk > −αk 
=
βk+1 | {z }
=0

48/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

1
< vk+1 , vk−1 > = < A vk − βk vk−1 − αk vk , vk−1 >
βk+1
1
= (< A vk , vk−1 > −βk )
βk+1

or on a < A vk , vk−1 > −βk = 0 car

2

< A vk , vk−1 > =< vk , A vk−1 >

=< vk , βk vk + αk−1 vk−1 + βk−1 vk−2 >
= βk

49/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

1 pour i ≤ k − 2
1
< vk+1 , vi > = < A vk − βk vk−1 − αk vk , vi >
βk+1
1
= < A vk , vi >
βk+1 | {z }
=0
en eet < A vk , vi > =< vk , A vi >
=< vk , βi+1 vi+1 + αi vi + βi vi−1 >
= 0 (car i + 1 ≤ k − 1)

d'où (Pk ) est juste

50/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

L'algorithme de Lanczos pour les matrices symétriques construit

bien une base orthonormale du sous-espaces de Krylov Km
vériant :
⊤
A · Vm = Vm · Hm + βm+1 (vm+1 · em )
avec Hm symétrique tridiagonale.

51/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Algorithme de LANCZOS symétrique
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithm 4 Lanczos symétrique

1: function Lanczos(A, r (0) , m)
2: v1 = r (0) , β1 = 0 et v0 = 0Rn
3: for k = 1, 2, · · · , m do
4: αk =< A vk , vk >
5: wk = A vk − βk vk−1 − αk vk
6: βk+1 = ∥wk ∥ et vk+1 = βwk+k 1
7: end for
8: T = tridiag (βi , αi , βi ) et Vm = [v1 , v2 , ..., vm ]
9:
10: Résoudre Tm ym = (βe1 ) et xm = x0 + Vm ym
11: end function
52/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Lanczos Bi-orthogonalisation

Lanczos Bi-orthogonalisation est une généralisation au cas non

symétrique de l'orthonormalisation dans le cas symétrique. Il
consiste à construire une paire de famille biorthogonale pour :
Km (A, q1 ) = vect{q1 , Aq1 , . . . , Am−1 q1 }

et
Km (AT , p1 ) = vect{p1 , AT p1 , . . . , Am−1 p1 }
où {q1 , . . . , qm } et {p1 , . . . , pm } sont biothogonaux.
1 si j = i

qiT pj = δij =
0 si j ̸= i
53/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

On considère la décomposition de la section précédente pour une

matrice symétrique A ∈ Rn×n
VmT AVm = Tm ∈ Rm×m Tridiagonale symétrique
La modication constructive d'une telle décompossition est de la
forme :
WmT AVm = Tm ∈ Rm×m Tridiagonale non symétrique

Avec Vm , Wm ∈ Rn×m satisfaisant WmT Vm = Im , et c'est

exactement le but qui vise à réaliser la procédure de Lanczos
biorthogonale.
54/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

L'idée de Lanczos est d'utiliser simultanément deux procédures de

Lanczos pour la matrice A et AT .
AVm = Vm+1 T̄m (1)

AT Wm = Wm+1 S̄m (2)

55/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

 
α1 β2
 δ2 α2 β3 0 
... ... ...
 
 ∈ R(m+1)×m
 
T̄m = 
 
 δm−1 αm−1 βm 
0
 
 δm αm 
αm+1
 
α1 δ2
 β2 α2 δ3 0 
... ... ...
 
 ∈ R(m+1)×m
 
S̄m = 
 
 βm−1 αm−1 δm 
0
 
 βm αm 
βm+1
56/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Les relations désirées de (1) et (2) sont équivalentes à :

Avj = βj vj−1 + αj vj + δj+1 vj+1

AT wj = δj wj−1 + αj wj + βj+1 wj+1

Pour j = 1, . . . m, avec β1 = δ1 = 0, on peut calculer v2 . . . vm et

w2 . . . wm à partir de chaqu'une de ces deux relations.

Si la biorthogonalité des vecteurs vi et wj est assurée, alors on a la

décomposition suivante :
WmT AVm = WmT Vm+1 T̄m = Tm
57/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Explication
On se donne v1 , w1 vériant < v1 , w1 >= 1 ( si < v1 , w1 >= γ ̸= 0
v w1
alors v1 ←− p 1 et w1 ←− p ). On a
|γ| sign(γ) |γ|

A · v1 = α1 v1 + δ1 v2
⊤
A · w1 = α1 w1 + β1 v2

On en déduit que α1 =< w1 , A · v1 > pour avoir < v2 , w1 >= 0 et

< v1 , w2 >= 0 (bi-orthogonalité). puis on pose :

z = A · v1 − α1 v1
t = A⊤ · w1 − α1 w1
58/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

On en déduitpque < z, t >= γ , on prend δ1 = |γ| et

p

β1 = sign(γ) |γ| pour avoir < v2 , w2 >= 1 et ainsi de suite on

construit les autres éléments.
Algorithme
1 : On choisit 2 vecteurs v1 , w1 avec < v1 , w1 >= 1.
2 : Fixant β1 = δ1 = 0, w0 = v0 = 0.
3 : for j = 1 . . . m
4: αj =< Avj , wj >
5: v̂j+1 = Avj − αj vj − βj vj−1
6: ŵj+1 =pAT wj − αj wj − δj wj−1
7 : δj+1 = |< v̂j+1 , ŵj+1 >|. If δj+1 = 0 stop
8 : βj+1 =< v̂j+1 , ŵj+1 > / δj+1
9 : wj+1 = ŵj+1 /βj+1 et vj+1 = v̂j+1 /δj+1
59/97
10 : end Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Proposition
Les deux bases Vm et Wm sont biorthogonale, i.e.,
< vj , wi >= δij 1 ≤ i, j ≤ m
{vi }i=1,2,...,m est une base de Km (A, v1 ) et {wi }i=1,2,...,m est une
base de Km (AT , w1 ), et on a les relations suivantes :
T
AVm = Vm Tm + δm+1 vm+1 em (3)
AT Wm = Wm TmT + βm+1 wm+1 em
T
(4)
WmT AVm = Tm (5)

60/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Preuve
Par hypothèse < v1 , w1 >= 1. Suppposons que les vecteurs
v1 , . . . , vj et w1 , . . . , wj sont biorthogonaux, montrons que les
vecteurs v1 , . . . , vj+1 et w1 , . . . , wj+1 restent biorthogonaux. On
montre d'abord que (v̂j+1 , wi ) = 0 pour i ≤ j. Pour i = j , on a :
(v̂j+1 , wj ) = (Avj , wj ) − αj (vj , wj ) − βj (vj−1 , wj )

Or (vj−1 , wj ) = 0 et (vj , wj ) = 1.
Par suite
(v̂j+1 , wj ) = 0

61/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Preuve
Pour i < j on a :
(v̂j+1 , wi ) = (Avj , wi ) − αj (vj , wi ) − βj (vj−1 , wi )
= (vj , AT wi ) − βj (vj−1 , wi )
= (vj , βi+1 wi+1 + αi wi + δi wi−1 ) − βj (vj−1 , wi )

donc (v̂j+1 , wi ) = 0. Pour i < j − 1, tous les produits scalaires sont

nuls, par suite (v̂j+1 , wi ) = 0. Pour i = j − 1, on a :
(v̂j+1 , wj−1 ) = (vj , βj wj + αj−1 wj−1 + δj−1 wj−2 ) − βj (vj−1 , wj−1 )
= βj (vj , wj ) − βj (vj−1 , wj−1 )
= 0

62/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Preuve
De la même façon on montre que (vi , ŵj+1 ) = 0 pour i ≤ j.
Reste a montrer que (vj+1 , wj+1 ) = 1.
En eet :  
v̂j+1 ŵj+1
(vj+1, wj+1 ) = ,
βj+1 δj+1
Or δj+1 vj+1 = v̂j+1 et βj+1 wj+1 = ŵj+1
Avec : q
δj+1 = |(v̂j+1 , ŵj+1 )|

(v̂j+1 , ŵj+1 )
βj+1 =
δj+1
Par suite (vj+1 , wj+1 ) = 1.
63/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Remarque
La méthodes de Lanczos Bi-orthogonale présente les avantages
suivants :
1 Moins de stockage car à l'étape (k) on a seulement besoin de

vk et vk−1 . au lieu de vi , i = 1, · · · , k dans Arnoldi.

2 On résoud à la foi le système linéaire associé à la matrice A et

celui associé à A⊤ .
3 On parle de Happy Breakdown lorsque zk = 0 et du

serious breakdown lorsque zk ⊥ tk .

64/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Résolution de Ax = b
Pour résoudre le système linéaire Ax = b partons d'une donnée
initiale x0 de résidu r (0) = b − Ax0 .
(0)
1 r (0) = b − Ax0 , β = ∥r (0) ∥ et v1 = r
β
2 on construit w1 tel que < w1 , v1 >= 1

3 on utilise Lanczos Bi-orthogonale pour calculer Vm et Wm les

bases bi-orthogonale de Km (A, v1 ) et Km (A⊤ , w1 )

4 on eectue la projection sur Km (A, v1 ) orthogonalement à

Km (A⊤ , w1 ) c'est-à-dire on a :
 
r (m) = b − A x0 + Vm y (m) ⊥ Km (A⊤ , w1 )

65/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Résolution de Ax = b
D'où
r (m) = r (0) − Vm Tm y (m) − δm (em
⊤
· y (m) )vm+1 ⊥ Wm

d'après cela on a :
Wm⊤ r (m) = 0 ⇒ Wm⊤ r (0) − Tm y (m) = 0
⇒ βe1 − Tm y (m) = 0

dans ce cas r (m) = −δm ym(m) vm+1 . De même pour le calcul de

l'approximation du système A⊤ x = 0
66/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Lanczos et le Gradient Conjugué

Algorithme : Lanczos symétrique
1. Choisir un vecteur v1 unitaire.
2. For j=1,...,m
3. wj := Avj − βj vj−1
4. αj := (wj , vj )
5. wj := wj − αj vj
6. βj+1 := ||wj ||2 . si βj+1 = 0 Stop
7. vj+1 := wj /βj+1
8. End
Cet algorithme retourne une famille de vecteurs (vi )1≤i≤m
orthogonale, base du sous espace de Krylov Km
67/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

L'algorithme du Gradient Conjugué (GC), Conjugate Gradient

(CG), est l'une des meilleurs méthodes itératives pour la résolution
des systèmes linéaires symétriques dénis positifs. C'est une
méthode de projection orthogonale sur le sous espace de Krylov
Km (r0 , A). Elle est donc mathématiquement équivalente á la
méthode FOM. Cependant, en présentant les choses diéremment
nous allons retrouver l'algorithme du gradient conjugué.

68/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

La solution approchée obtenue par la méthode de projection

orthogonale sur Km est donnée par :
xm = x0 + Vm ym , ym = Tm−1 (βe1 ).

69/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme : Méthode de Lanczos pour les systèmes linéaires

1. Calculer r0 = b − Ax0 , β := ||r0 ||2 , et v1 := r0 /β
2. For j=1,...,m
3. wj := Avj − βj vj−1
(Si j = 1 on pose β1 v0 ≡ 0)
4. αj := (wj , vj )
5. wj := wj − αj vj
6. βj+1 := ||wj ||2 . Si βj+1 = 0, on pose m := j et on passe
à 9
7. vj+1 := wj /βj+1
8. End
9. On pose Tm = Tridiag (βi , αi , βi+1 ) et Vm = [v1 , . . . , vm ]
10. On calcule ym = Tm−1 (βe1 ) et xm = x0 + Vm ym
70/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Tm = Lm Um la factorisation LU de la matrice Tm . La matrice Lm

étant bidiagonale inférieure à diagonale unitaire et Um est
bidiagonale supérieure. Donc la factorisation de Tm va être sous la
forme :

1
   
η1 β2
λ 2 1   η2 β3 
... ... ... ...
   
Tm =  ×
   

1
   
 λm−1   ηm−1 βm 
λm 1 ηm

71/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

La solution approchée est donné par

−1 −1
xm = x0 + Vm Um Lm (βe1 )

Posons :
−1
Pm ≡ Vm Um
et
zm = L− 1
m (βe1 )

alors
xm = x0 + Pm zm

72/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Notons par pm la dérniere colonne de Pm . On a :

−1
pm = η m [vm − βm pm−1 ]

avec βm est un scalaire calculé par l'algorithme de Lanczos, tandis

que ηm résulte de la factorisation LU de Tm ;

βm
λm = (6)
ηm−1
ηm = αm − λm βm (7)

73/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Due à la structure de Lm , on a la relation

 
zm−1
zm =
ζm
avec
ζm = −lm,m−1 ζm−1
par conséquent, on peut écrire la solution approchée comme suit :
 
zm−1
xm = x0 + [Pm−1 , pm ] = x0 + Pm−1 zm−1 + ζm pm
ζm
On remarque que x0 + Pm−1 zm−1 = xm−1 , il s'ensuit donc que
l'approximation xm peut être mise à jour à chaque étape par la
relation
xm = xm−1 + ζm pm
74/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Il en résulte l'algorithme suivant, que l'on appelle la version directe

de l'algorithme de Lanczos (ou le D-Lanczos) pour les systèmes
linéaires.

75/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme de D-Lanczos
1.Calcul de r0 = b − Ax0 , ζ1 := β := ||r0 ||, et v1 := r0 /β
2.on pose λ1 = β1 = 0, p0 = 0
3.For m = 1, 2, . . .,
4.Calcul de w := Avm − βm vm−1 et αm = (w , vm )
5.si m > 1 alors on calcule λm = ηm− βm
1
et ζm = −ζm−1 λm
6.ηm = αm − λm βm
−1 (v − β p
7.pm = ηm m m m−1 )
8.xm = xm−1 + ζm pm
9.si xm converge alors Stop
10.w := w − αm vm
11.βm+1 = ||w ||2 , vm+1 = w /βm+1
12.EndDo
76/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Proposition
Soit rm = b − Axm , m = 1, . . . , le vecteur résidu obtenu par
L'algorithme D-Lanczos et pm m = 1, . . . , le vecteur auxiliaire,
alors :
1. rm est tel que rm = σm vm+1 , où σm est un scalaire. Comme
résultat immédiat les vecteurs résidu sont orthogonaux entre eux.
2. les vecteurs auxiliaires pi forment un ensemble A-conjugué ; i.e.,
(Api , pj ) = 0 pour i ̸= j

77/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Preuve
Pour la deuxième partie, on doit prouver que PmT APm est diagonale,
où Pm = Vm Um−1
T
Pm −T T
APm = Um −1
Vm AVm Um (8)
= −T
Um −1
Tm Um (9)
= −T
Um Lm (10)
−T L
Um m est une triangulaire inférieur, symétrique, puisqu' elle est
égale à PmT APm . Donc elle est diagonale.

78/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

De cette proposition dérive l'algorithme du GC. Le vecteur xj+1

peut être exprimé comme suit
xj+1 = xj + αj pj

le vecteur résidu satisfait la relation

rj+1 = rj − αj Apj

79/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Puisque les rj sont orthogonales, alors (rj − αj Apj , rj ) = 0. Donc

(rj , rj )
αj =
(Apj , rj )
Et comme la direction de descente pj+1 est une combinaison
linéaire de r j + 1 et pj .
pj+1 = rj+1 + βj pj .
Il s'enssuit que
(Apj , rj ) = (Apj , pj − βj−1 pj−1 ) = (Apj , pj ),
car Apj est orthogonal à pj−1 . D'où
(rj , rj )
αj =
(Apj , pj )
80/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Par ailleurs, pj+1 est orthogonal à Apj , d'après la relation ci-dessus,

(rj+1 , Apj )
βj = −
(pj , Apj )

Observons que
1
Apj = − (rj+1 − rj )
αj
donc on a la simplication suivante :
1 (rj+1 , (rj+1 − rj )) (rj+1 , rj+1 )
βj = =
αj (Apj , pj ) (rj , rj )

81/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme du GC
1.Calcul de r0 = b − Ax0 , p0 := r0
2.For j = 0, 1, . . . , jusqu'à convergence,
3.αj := (rj , rj )/(Apj , pj )
4.xj+1 := xj + αj pj
5.rj+1 := rj − αj Apj
6.βj := (rj+1 , rj+1 )/(rj , rj )
7.pj+1 := rj+1 + βj pj
8.End

82/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Lanczos Biorthogonalisation (Rappel)

Lanczos Biorthogonalisation est une généralisation au cas non

symétrique de Lanczos symétrique.
Km (A, q1 ) = vect{q1 , Aq1 , . . . , Am−1 q1 }

Km (AT , p1 ) = vect{p1 , AT p1 , . . . , Am−1 p1 }

{q1 , . . . , qm } base deKm (A, q1 ) et {p1 , . . . , pm } base de
Km (AT , p1 ) sont biorthogonaux.

1 si j = i

qiT pj = δij =
0 si j ̸= i

83/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme
1 : Donner deux vecteurs v1 , w1 telsque (v1 , w1 ) = 1.
2 : Posons β1 = δ1 = 0, w0 = v0 = 0.
3 :for j = 1 . . . m
4: αj = (Avj , wj )
5: v̂j+1 = Avj − αj vj − βj vj−1
6: ŵj+1 =pAT wj − αj wj − δj wj−1
7 : δj+1 = |v̂j+1 , ŵj+1 |. Si δj+1 = 0, alors stop
8 : βj+1 = (v̂j+1 , ŵj+1 ) / δj+1
9 : wj+1 = ŵj+1 /βj+1
10 : vj+1 = v̂j+1 /δj+1
11 : end

84/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Proposition
Les deux bases Vm et Wm sont biorthogonales,
(vj , wi ) = δij 1 ≤ i, j ≤ m
{vi }i=1,2,...,m est une base de Km (A, v1 ) et {wi }i=1,2,...,m une base
de Km (AT , w1 ) et on on a :
T
AVm = Vm Tm + δm+1 vm+1 em (11)
AT Wm = Wm TmT + βm+1 wm+1 em
T
(12)
WmT AVm = Tm (13)

85/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Gradient BiConjugué (BiConjugate Gradients)

L'algorithme gradient biconjugué (BiCG) peut être déduit de
Lanczos biorthogonale de la même manière que la méthode du
gradient conjugué dérive de Lanczos symétrique. L'algorithme
permet de résoudre non seulement le systéme d'origine Ax = b,
mais aussi le systéme linéaire dual AT x ∗ = b∗ .

86/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme gradient biconjuqué

Le gradient biconjugué (BiCG) est une projection sur :
Km (A, v1 ) = vect{v1 , Av1 , . . . , Am−1 v1 }
orthogonalement à :
Km (AT , w1 ) = vect{w1 , AT w1 , . . . , (AT )m−1 w1 }

87/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

r
On prend v1 = 0 . Le vecteur w1 est telque < v1 , w1 ≯= 0
||r0 ||
souvent choisie égale à v1 . Si on souhaite résoudre un systéme dual
AT x ∗ = c , alors on prend w1 égale au résidu c − AT x0 .

88/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Donnons la décomposition LU de Tm :
Tm = Lm Um

On pose
−1
Pm = Vm Um
La solution est alors exprimé par :
xm = x0 + Vm Tm−1 (βe1 )

=x0 + Vm Um−1 L−m1 (βe1 )

=x0 + Pm L−m1 (βe1 )

89/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

xm peut être calculé à partir de xm−1 d'une manière similaire à ce

qu'on a fait pour le gradient conjugué. Dans le cas du gradient
conjugué les vecteurs rj et rj∗ sont dans la même direction que vj+1
et wj+1 respectivement (rj∗ est le résidu dual). Par conséquent, ils
forment une séquence biorthogonale.
On dénit de manière similaire la matrice :
∗
Pm = Wm L−T
m
Les vecteurs colonnes pj∗ de la matrice Pm∗ et les vecteurs pi de Pm
sont A-conjugués :
∗ T
(Pm ) APm = L− 1 T −1 −1 −1
m Wm AVm Um = Lm Tm Um = I
Ce résultat nous permet de déduire un algorithme de gradient
biconjugué à partir de la procédure de Lanczos.
90/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Algorithme
1. r0 = b − Ax0 et r0∗ choisis tel que < r0 , r0∗ > ¬0
2. Initialiser p0 := r0 et p0∗ := r0∗
3. Pour j = 0, 1 .∗. . jusqu'á convergence
4. αj = <Apj j ,pj j∗ >
<r ,r >

5. xj+1 = xj + αj pj
6. rj+1 = rj − αj Apj
7. rj+ ∗ = r ∗ − α AT p ∗
1 j j j
∗ >
8. βj = <rj ,rj∗ >
<rj+1 ,rj+ 1

9. pj+1 = rj+1 + βj pj
10. pj+ ∗ ∗
1 = rj+1 + βj pj
∗

11. Fin
91/97 Abdeslem Had Bentbib Méthode de Lanczos
 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

De Lanczos biortogonal au BiCG

Si un système dual est à résoudre, alors à la ligne 1 r0∗ doit être
dénie comme r0∗ = c − AT x0 et xj+∗
1 = xj + αj pj mise à jour de
∗ ∗

la solution approchée du systéme dual doit être calculée après la

ligne 5.
D'une manière similaire au gradient conjugué on montre que :
xj = xj−1 + αj pj etxj∗ = xj−
∗ ∗
1 + αj pj

rj+1 = rj − αj Apj etrj+

∗ ∗ T ∗
1 = rj − αj A pj

92/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

La direction pj+1 et combinaison linéaire de pj et le résidu rj+1 :

pj+1 = rj+1 + βj pj (14)

∗
pj+ ∗ ∗
1 = rj+1 + βj pj (15)
Or les rj et ri∗ sont biorthogonaux et les pj et pj∗ sont A-conjuqué.
Donc,
(rj+1 , rj∗ ) = 0

93/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Ce qui donne
(rj , rj∗ )
αj =
(Apj , rj∗ )
d'après (7) : rj∗ = pj∗ − βj−1 pj−
∗
1
On remplace rj on trouve :
(rj , rj∗ )
αj =
(Apj , pj∗ )

94/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

d'autre part on a les pj et pj∗ sont A-conjuqué, donc

1 , Apj ) = 0
∗
(pj+

d'après (7) on trouve,

1 + βj pj , Apj ) = 0
∗ ∗
(rj+

d'où ∗ , Ap )
(rj+ 1 j
βj = −
(pj∗ , Apj )

95/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

d'après (4) on a :
1
Apj = − (rj+1 − rj )
αj
d'où ∗ ,r
(rj+ 1 j+1 )
βj =
(rj∗ , rj )

96/97 Abdeslem Had Bentbib Méthode de Lanczos

 Introduction
Méthodes de projection
Méthode de type sous-espaces de Krylov
Méthode d'Arnoldi : Full Orthogonalization Method (FOM)
Méthode de GMRES : Generalized Minimal Residual Method Gradient biconjugué
Méthode de Lanczos
Lanczos Bi-orthogonalisation
Lanczos et le Gradient Conjugué
Le Gradient Biconjugué variante de Lanczos Biorthogonal

Proposition
Les vecteurs produits par l'algorithme gradient biconjugué satisfont
les propriétés d'orthogonalité suivantes :
(rj , ri∗ ) = 0 pour j ̸= i
(Apj , pi∗ ) = 0 pour j ̸= i

97/97 Abdeslem Had Bentbib Méthode de Lanczos