# The Preconditioned SOR Iterative Method for Positive Definite Matrices

Authors: Yu-Qin Bai; Yan-Ping Xiao; Wei-Yuan Ma
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We present several iterations for preconditioners introduced
by Tarazaga and Cuellar (2009), and
study the convergence of the method for solving a linear system whose coefficient
matrix is positive definite matrices, and we also find that they complete
very well with the SOR iteration, which is shown through numerical examples.


---

## Body

## 1. Introduction

For solving the large sparse linear system(1)Ax=b,x,b∈Rn,
where A∈Rn×n is a square nonsingular positive definite matrix, an iteration method is often considered. For any splitting, A=M-N with det(M)≠0, the basic iterative method for system (1) is
(2)xk+1=M-1Nxk+M-1b,k=0,1,….To improve the convergence rate of the basic iterative method, transform the original systems (1) into the preconditioner form
(3)PAx=Pb,
where P is called the preconditioner or a preconditioning matrix. several preconditioned iterative methods have been proposed [1–6]. Since P is nonsingular, (1) and (3) have the same solutions. We are considering here systems with a unique solution. It is well known that system (3) can be transformed by an iteration as follows:
(4)xk+1=(I-PA)xk+Pb.
This iteration is called the Richardson iteration for preconditioning system (3). In this paper, we consider the iteration methods by the following form:
(5)xk+1=Txk+f,
where T represents the iteration matrix.Lemma 1 (see [7, 8]).
For the iteration formula (5) to produce a sequence converging to (I-B)-1b, for any starting point x0, it is necessary and sufficient that the spectral radius of B be less than one.We will use the following notations. A matrixA=(aij) is called a row diagonally dominant if
(6)∑i≠j‍|aij|<|aii|fori=1,…,n,
and column diagonally dominant if
(7)∑i≠j‍|aij|<|ajj|forj=1,…,n.
The Frobenius inner product of A and B is defined by
(8)〈A,B〉F=trace(ATB),
where trace (A) denotes the trace of a matrix A, and AT stands for the transpose of A, and the spectral radius of a matrix A is denoted by ρ(A). Let A be decomposed as A=D-L-U in which D is the diagonal of A, L is the strict lower part of A, and U is the strict upper part of A.Using the Frobenius norm, the preconditioning matrix in [6] is given by
(9)Pf=(a11∥a1∥22a22∥a2∥22⋱ann∥an∥22),
where ai stands for the ith row of the matrix A.The second preconditioning matrix isP1=αI and α is computed to minimize the infinity norm of the iteration matrix.The small gap for a matrixA is defined by
(10)sg(A)=minj=1,…,n(|ajj|-∑i≠jn‍|aij|).
Obviously, sg(A) is positive for diagonally dominant matrices. we can also suppose the diagonal entries are positive, else, it is true by multiplying the corresponding rows with -1.Then, the preconditioner obtained by minimizing the infinity norm is given by(11)α=2∥A∥∞+sg(A).
We can easily find that the diagonal preconditioner is constant diagonal. Using the idea in [9], we can obtain the iterations associated with the preconditioners Pf and P∞ as follows.Solving the iteration(12)xk+1=(I-ωPfA)xk+ωPfb,
the matrix A is decomposed by A=D+L+U and ωPfA is moved to the left-hand side, we obtain
(13)(I+ωPfL)xk+1=(I-ωPf(D+U))xk+ωPfb.
Because I+ωPfL is inverse, we can easily get
(14)xk+1=(I-(Pf-1+ωL)-1A)xk+(Pf-1+ωL)-1ωb
or
(15)xk+1=(I-ω(I+ωPfL)-1PfA)xk+(I+ωPfL)-1ωPfb.
This iteration is considered as sequential Frobenius norm iteration.Similarly, we obtained and built the infinity norm iteration associated withP∞ as follows:
(16)xk+1=(I-(P∞-1+ωL)-1A)xk+(P∞-1+ωL)-1ωb
or
(17)xk+1=(I-ω(I+ωP∞L)-1P∞A)xk+(I+ωP∞L)-1ωP∞b.
Now, we have set two preconditioned SOR iterative methods which use Pf and P∞ as a preconditioner.In this paper, first in Section2, we discuss the convergence of the preconditioned SOR iterative method which uses Pf and P∞ as a preconditioner. In Section 3, we provide numerical experiments to illustrate the theoretical results obtained in Section 2, and we find if we choose the set of parameters; then our method has smaller spectral radii of the iterative matrices than the SOR method, which is shown through numerical examples.


## 2. Main Results

### 2.1. The Sequential Frobenius Norm Iteration

Theorem 2.
Suppose1≤ω<2 and A is positive definite; then the iteration
(18)xk+1=(I-(Pf-1+ωL)-1A)xk+(Pf-1+ωL)-1ωb,
converges for any starting point x0.Proof.
By simple calculation, the iteration matrix can be written as(19)(Pf-1+ωL)-1(Pf-1-(D+U)+(ω-1)L),
let λ be corresponding eigenvalue; then
(20)(Pf-1-(D+U)+(ω-1)L)x=λ(Pf-1+ωL)x
or
(21)(Pf-1-A+L+(ω-1)L)x=λ(Pf-1+ωL)x,
we get that
(22)-Ax=(λ-1)(Pf-1+ωL)x,
then
(23)-x*Ax=(λ-1)x*(Pf-1+ωL)x.
The following proof is similar in [9], so we omit it; then the theorem is obtained.


### 2.2. The Sequential Infinity Norm Iteration

Theorem 3.
Suppose1≤ω<2 and A is positive definite. If every diagonal entry of A satisfies
(24)∥A∥∞+sg(A)>ωaii,
then the iteration
(25)xk+1=(I-(P∞-1+ωL)-1A)xk+(P∞-1+ωL)-1ωb,
converges for any starting point x0.Proof.
The proof of this theorem is similar to the previous one. We notice the diagonal entries of the matrix2P∞-1-ωD are
(26)∥A∥∞+sg(A)-ωaii,
by the assumption ∥A∥∞+sg(A)>ωaii, so the diagonal entries of matrix 2P∞-1-ωD are positive which completes the proof.Now, we modify the infinity norm preconditioner for diagonally dominant matrices. Since the eigenvalues of a positive definite matrixA lie in the interval (0,ω∥A∥∞+ϵ) for arbitrarily small number ϵ, the preconditioning matrix P is defined by
(27)P^∞=2ω∥A∥∞+ϵ,
for any ϵ>0. Especially, ϵ=0 if ρ(A)<∥A∥∞.Theorem 4.
For anyϵ>0, if A is positive definite; then the iteration
(28)xk+1=(I-(P∞-1+ωL)-1A)xk+(P∞-1+ωL)-1ωb,
converges for any starting point x0, where 1≤ω<2.Proof.
The proof is similar to Theorem2, we notice the condition of
(29)2P∞-1-ωD+ωA≻A
or 2P∞-1-ωD≻0, and the diagonal entries are
(30)2(ω∥A∥∞+ϵ2)-ωaii=ω∥A∥∞+ϵ-ωaii>0.
Hence, we obtain this result.Next, we will obtain a general result for previously positive definite preconditioners.Theorem 5.
Suppose positive definite matrices ofA and P satisfy
(31)2P-1-ωD≻0,
where D is the diagonal of A and 1≤ω<2; then the iteration
(32)xk+1=(I-(P-1+ωL)-1A)xk+(P-1+ωL)-1ωb,
converges for any starting point x0.Remark 6.
In Theorem5, the matrix P just satisfies the condition needed in the proof of Theorem 2; hence, this theorem is a general result for previous preconditioners.


## 2.1. The Sequential Frobenius Norm Iteration

Theorem 2.
Suppose1≤ω<2 and A is positive definite; then the iteration
(18)xk+1=(I-(Pf-1+ωL)-1A)xk+(Pf-1+ωL)-1ωb,
converges for any starting point x0.Proof.
By simple calculation, the iteration matrix can be written as(19)(Pf-1+ωL)-1(Pf-1-(D+U)+(ω-1)L),
let λ be corresponding eigenvalue; then
(20)(Pf-1-(D+U)+(ω-1)L)x=λ(Pf-1+ωL)x
or
(21)(Pf-1-A+L+(ω-1)L)x=λ(Pf-1+ωL)x,
we get that
(22)-Ax=(λ-1)(Pf-1+ωL)x,
then
(23)-x*Ax=(λ-1)x*(Pf-1+ωL)x.
The following proof is similar in [9], so we omit it; then the theorem is obtained.


## 2.2. The Sequential Infinity Norm Iteration

Theorem 3.
Suppose1≤ω<2 and A is positive definite. If every diagonal entry of A satisfies
(24)∥A∥∞+sg(A)>ωaii,
then the iteration
(25)xk+1=(I-(P∞-1+ωL)-1A)xk+(P∞-1+ωL)-1ωb,
converges for any starting point x0.Proof.
The proof of this theorem is similar to the previous one. We notice the diagonal entries of the matrix2P∞-1-ωD are
(26)∥A∥∞+sg(A)-ωaii,
by the assumption ∥A∥∞+sg(A)>ωaii, so the diagonal entries of matrix 2P∞-1-ωD are positive which completes the proof.Now, we modify the infinity norm preconditioner for diagonally dominant matrices. Since the eigenvalues of a positive definite matrixA lie in the interval (0,ω∥A∥∞+ϵ) for arbitrarily small number ϵ, the preconditioning matrix P is defined by
(27)P^∞=2ω∥A∥∞+ϵ,
for any ϵ>0. Especially, ϵ=0 if ρ(A)<∥A∥∞.Theorem 4.
For anyϵ>0, if A is positive definite; then the iteration
(28)xk+1=(I-(P∞-1+ωL)-1A)xk+(P∞-1+ωL)-1ωb,
converges for any starting point x0, where 1≤ω<2.Proof.
The proof is similar to Theorem2, we notice the condition of
(29)2P∞-1-ωD+ωA≻A
or 2P∞-1-ωD≻0, and the diagonal entries are
(30)2(ω∥A∥∞+ϵ2)-ωaii=ω∥A∥∞+ϵ-ωaii>0.
Hence, we obtain this result.Next, we will obtain a general result for previously positive definite preconditioners.Theorem 5.
Suppose positive definite matrices ofA and P satisfy
(31)2P-1-ωD≻0,
where D is the diagonal of A and 1≤ω<2; then the iteration
(32)xk+1=(I-(P-1+ωL)-1A)xk+(P-1+ωL)-1ωb,
converges for any starting point x0.Remark 6.
In Theorem5, the matrix P just satisfies the condition needed in the proof of Theorem 2; hence, this theorem is a general result for previous preconditioners.


## 3. Numerical Experiments

In this section, we provide numerical experiments to illustrate the theoretical results obtained in Section2. All numerical experiments are carried out using MATLAB 7.1. The spectral radii of various iteration matrices are shown in Figures 1 and 2. For simplicity of comparison, suppose that all of ω=1.9. Let (o) denote the spectral radii of the SOR iteration matrices, let (·) denote the spectral radii of the Frobenius norm preconditioner iteration matrices, let (*) denote the spectral radii of the infinity norm preconditioner, and let (∇) denote the spectral radii of the infinity-ϵ preconditioner with ϵ=0.1.Spectral radius for random PSD matricesATA+diag(rand(n,1)) of size n=50 (a), ATA+10*diag(rand(n,1)) of size n=50 (b) and ATA+30*diag(rand(n,1)) (c) of size n=150.
(a)
(b)
(c)Figure 2
Spectral radius of random PSD matricesATA+10*diag(rand(n,1)) with nearly half of the entries of A negative and n=50.Remark 7.
The previous numerical experiments indicate that the spectral radii of iterative matrices with three proposed preconditioners achieve significant improvement over the spectral radii of SOR iterative matrices.Remark 8.
As the proportion of negative to positive entries is increased, the spectral radius of random positive PSD matricesATA+10*diag(rand(n,1)) with half of the entries of A negative with infinity norm preconditioner (*) becomes larger than 1. But both of infinity norm preconditioners have faster convergence rates than SOR method.Remark 9.
Here, we maintain both of infinity norm iterations because there are cases whenP∞=(2/(∥A∥∞+sg(A)))(*) works better than P^∞=(2/(ω∥A∥∞+ϵ))(∇).



---

*Source: 732834-2013-09-19.xml*