Preconditioner

4. Spectral analysis of the preconditioned matrix

In this section we investigate a regularization preconditioner for solving (1). The idea of preconditioning is to transform the linear system (1) into another one is easier to solve. Left preconditioning (1) gives the following new linear system :

α,S^ˆ

α,S^ˆ
P⁻¹ X = P⁻¹ b. (9)

Although right preconditioning can be used in our context, we will focus only on left preconditioning thoughout this work. We describe a block factorization and some prop- erties of the preconditioner P_α,Sˆ.

Proposition 2. The preconditioner (7) has the block-triangular factorization

^Pα,S^{ˆ =}
A B

C αS^ˆ
I O

⁼ CA⁻¹ I
A O


O S_s
I A⁻¹B O I


, (10)

where S_s = αS^ˆ − CA⁻¹B .






The inverse of the preconditioner matrix P_α,Sˆ is given by

_P−1 _{=
A B} −1
ˆ
I −A⁻¹B


_A−1 _O
−1
^{I O} . (11)
−1

α,S^ˆ
C αS
O I O S_s
CA I

α,S^ˆ

=
The eigenvalue and eigenvector distributions of the preconditioned matrix relate closely to the convergence rate of Krylov subspace methods. Therefore, it is meaningful to investigate the spectral properties of the preconditioned matrix P⁻¹ A. In the following
theorem, we will deduce the eigenvalue distribution of the following preconditioned matrix

α,S^ˆ

0 K_2
P−1 _{A =} ^{In K1}
. (12)

Where: S_s = αS^ˆ − CA⁻¹B , K₁ = (I + A⁻¹BS_s⁻¹C) A⁻¹B and K₂ = −S_s⁻¹CA⁻¹B.

Theorem 1. Let the preconditioned matrix be defined as in (12) and B has a full colmn rank. Then P⁻¹ A has m₁ +1 distincts eigenvalues {1, λ₁, . . . , λ_m } and (n+m) linearly
α,S^{ˆ 1}
independent eigenvectors, where 1 ≤ m₁ ≤ m. Moreover.

• 
  1 is an eigenvalue with multiplicity n.
  
• 
  
  2
  If ^α > Real(µ), then |λ_i| < 1 , for i = 1, .., m₁, where µ is the eigenvalue of the matrix S^ˆ−1CA⁻¹B.
  
• 
  
  2
  If ^α < Real(µ), then |λ_i| > 1 , for i = 1, .., m₁.
  
• 
  
  α,S^ˆ
  If S^ˆ−1CA⁻¹B is diagonalizable, then P⁻¹ A is diagonalizable.
  

α,S^ˆ
Proof. Let λ be an eigenvalue of the preconditioned matrix P⁻¹ A and [x^T , y^T ]^T be the corresponding eigenvector. To derive the eigenvector distribution, we consider the following generalized eigenvalue problem:

α,S^ˆ

y

0 K_2
P−1 _A ^x ₌ ^{In K1
x} = λ ^x . (13)

y

y
Equation (12) can be equivalently rewritten as

−1


αλ


ˆ


(14)

^_(1 − λ)x = −K₁y,

^CA
By = Sy.
(λ − 1)

If λ = 1 holds true, then from the second equation of (14), we can easily get y = 0.

Thus there are n linearly independent eigenvectors
_u(i)
0
, (i = 1, .., n) corresponding

to the eigenvalue 1, where u⁽ⁱ⁾ are arbitrary linearly independent vectors.

/
If λ = 1 and y = 0, then we obtain from the first equation of (14) that x = 0. This contradicts the assumption that [x^T , y^T ]^T is an eigenvector of the preconditioned matrix

α,S^ˆ
P⁻¹ A and then y
0. If y satisfies the second equation of (14), then


CA⁻¹By = µS^ˆy, (15)

where
We deduce that


αλ
µ = .
(λ − 1)


µ

(16) can be rewritten as follow:
λ =
µ − α
. (16)

a + ib
λ =
a − α + ib
, (17)

−
where i is the imaginary complex number (i² = 1), a and b are the real part and the
α

imaginary part of µ. Hence if
following inequality :


α
> a, then after some manipulations, λ must hold the
2
|λ| < 1.

If < a, then 2
|λ| > 1.
S^ˆ−1CA⁻¹By = µy. (18)

Since S^ˆ−1CA⁻¹B is a diagonalizable, then there are m linearly independent eigenvec- tors, of the form w⁽ⁱ⁾, (i = 1, .., m). U , V and W are matrices whose columns are u⁽¹⁾, ..., u⁽ⁿ⁾ , v⁽¹⁾, ..., v^(m) and w⁽¹⁾, ..., w^(m) , respectively, where v⁽ⁱ⁾ (i = 1, .., m) are given by the following relation
v⁽ⁱ⁾ = ^K1 w⁽ⁱ⁾. (19)

(λ − 1)

Since U and W are nonsingular matrices, we infer that det ^{U V}
O W
= det(U )det(W ) /=

α,S^ˆ
0 and P⁻¹ A is diagonalizable.

{ }
When the hypotheses of the preceding theorem are satisfied, the preconditioned Krylov subspace methods converge in at most m₁ + 1 iterations. Moreover, in Theo- rem 1, we can see that the bound depends only on the distribution of the eigenvalues 1, λ₁, ..., λ_m1 and on the matrix of eigenvectors.
The preconditioned matrix can be rewritten as follow :


P_α,Sˆ = H + S.
Where the following matrices are Hermitian matrix

K


1


2


2
" _In _K1 #

H =
and skew-Hermitian matrix
^T K₂+K^T
2 2
, (20)

2


2

S
" _{O K}1 #

= _K^T

_— 1
2
K ₂−K^T
2
. (21)

Assume that B has a full column rank and H be defined as in (20), D = O and S^ˆ = S. Then the matrix H is positive definite, for α^∗ = 2 if and only if :
λ_min < 3. (22)
Where λ_min is the minimal eigenvalue of the matrix B^T A^−T A⁻¹B.

_KT

=

O S_H
Proof. H has the block-triangular factorization

K +K₂₌

2

2

1
2

K₂+K₂
2

H =

, (23)
" _In _K1

# " _{I O}

# I O
_{I K1}

1

2
T _KT _K1

4

2

H
where S_H − . From (23), we infer that det(H) = det(S ), then the
matrix H is positive definite if and only if S_H is positive definite matrix. Now we show
that S_H is SPD, by proving that for all vector y 0, we have the following inequality :
y^T S_Hy > 0.

Which can be written as
_T 1 α² _T

−T −1

^y α + 1 ⁻ 4(α + 1)^{2 B A}
y
A B y > 0. (24)

Premultiplying (24) with gives
y^T y
1 α²


_yT _BT _A−T _A−1_By

α + 1 ^> 4(α + 1)²
_{yT y} . (25)

Then after some manipulations and by using the fact that α^∗ = 2 is the minimum of

4(α+1)²
the function g(α) = ^α2
, the matrix H is positive definite, for α^∗ = 2 if and only if :
λ_min < 3. (26)

Where λ_min is the minimal eigenvalue of the matrix B^T A^−T A⁻¹B. Thus, the proof of Lemma 4 is completed.
Let S be defined as in (21), then S is purely imaginary.
Proof. Let X = [x^T , y^T ]^T /= 0 satisfying the following equality:

T
_{x T} ^" _{O K1} ^# _x

2

X SX = _y
K^T K₂−K^T

_— 1

2
2 2
_y . (27)

Which can be written as :


X^T SX = y^T
T

K − K₂
² y,
2

= iz₂,
where y^T K₂y = z₁ + iz₂. Thus, the proof of Lemma 4 is completed.
The following theorem readily follows from Lemmas 4 − 4.

α,S^ˆ
Theorem 2. Let the preconditioned matrix be defined as in (12) and B has a full colmn rank. Then the real part of the eigenvalues of P⁻¹ A is strictly positive.

5.