Modied AOR iterative methods to solve linear systems

Abstract

Solving the linear system Ax = b is an active area of research in engineering. Many researchers have applied preconditioners to the linear system Ax = b. In this work, we introduce two new preconditioners for solving linear systems. The best property of the introduced preconditioners is that they can be used under weaker conditions than the previous preconditioners in the literature. We propose preconditioned associated accelerated overrelaxation (AOR) iterative methods with these two new preconditioners, and give the corresponding convergence results. Numerical examples show an improvement in the convergence rate of the AOR preconditioned iterative matrices.

Keywords

AOR iterative method spectral radius preconditioner iteration matrix irreducible matrix

1. Introduction

Consider the following linear system

Ax = b

(1)

where A ∈ ℛ^n×n, b ∈ ℛⁿ are given and x ∈ ℛⁿ is unknown. For any splitting, A = M − N with det(M) ≠ 0, the iterative method for solving equation (1) is

x^{(i + 1)} = M^{- 1} {Nx}^{(i)} + M^{- 1} b, i = 0, 1, 2, \dots

(2)

For simplicity, without loss of generality, we assume throughout this paper that

A = I - L - U

where I is the identity matrix, and L and U are strictly lower and upper triangular matrices obtained from A, respectively. The AOR iterative method (Hadjidimos, 1978) is defined as follows

x^{(i + 1)} = (I - rL)^{- 1} [(1 - w) I + (w - r) L + wU] x^{(i)} + (I - rL)^{- 1} wb

where i = 0, 1, 2,…. Its iteration matrix is

L (r, w) = (I - rL)^{- 1} [(1 - w) I + (w - r) L + wU]

(3)

where w and r are real parameters with w ≠ 0.

It is well known that, for certain values of the parameters w and r, we obtain the Jacobi, the Gauss–Seidel and the successive overrelaxation (SOR) methods.

We now transform the original system in equation (1) into the preconditioned form

PAx = Pb

Then, we can define the basic iterative scheme

M_{p} x^{(i + 1)} = N_{p} x^{(i)} + Pb i = 0, 1, 2 \dots . .

(4)

where PA = M_p − N_p and M_p is nonsingular.

A large number of papers have been written about iterative methods for solving linear systems (Evans and Martins, 1992; Li and Sun, 2000; Evans et al., 2001; Li, 2002; Ding and Chen, 2005a, 2005b, 2006; Li et al., 2007; Wang et al., 2007; Wu et al., 2007; Yun and Kim, 2008; Dehghan and Hajarian, 2010a, 2010b, 2011a, 2011b). Milaszewics (1987) presented the modified Jacobi and Gauss–Seidel iterative methods using the preconditioned matrix $P = I + \bar{S}$ where

\bar{S} = (00 . . . 0 - a_{21} 0 . . . 0 . . . . . . . . . . . 0 - a_{n 1} 0 . . . 0)

(5)

In Milaszewics (1987) the matrix A has to be an L-matrix with

a_{i, i + 1} a_{i + 1, i} > 0 and 0 < a_{1 i} a_{i 1} < 1, for i = 2, 3, \dots, n

(6)

To date, several kinds of preconditioner P have been presented in which the matrix A has been an L-matrix with equation (6). In many practical problems, the assumption in equation (6) is somewhat too strong. The purpose of this paper is to introduce two new preconditioners under weaker conditions than equation (6).

We propose two new preconditioners P₁ = I + S₁ and P₂ = I + S₂ where

S_{1} = (00 . . . 0 - (a_{21} + α_{2}) 0 . . . 0 - (a_{31} + α_{3}) . . . . . . . . . . 0 - (a_{n 1} + α_{n}) 0 . . . 0)

(7)

S_{2} = (00 . . . - (a_{1 n} + β_{1}) 00 . . . - (a_{2 n} + β_{2}) . . . . . . . . . . . - (a_{n - 1, n} + β_{n - 1}) 00 . . . 0)

(8)

and α_v and β_s are real parameters for v = 2, 3, … , n and s = 1, 2, … , n − 1. Assume that

A_{1} = P_{1} A = (I + S_{1}) A = D_{1} - L_{1} - U_{1}

(9)

where

D_{1} = I + D_{11}, L_{1} = L - S_{1} + L_{11}, U_{1} = U + U_{11}

(10)

and

A_{2} = P_{2} A = (I + S_{2}) A = D_{2} - L_{2} - U_{2}

(11)

where

D_{2} = I + D_{22}, L_{2} = L + L_{22}, U_{2} = U + U_{22}

(12)

Note that D₁₁, L₁₁ and U₁₁ (D₂₂, L₂₂ and U₂₂) are diagonal, strictly lower and strictly upper triangular parts of S₁U = −D₁₁ + L₁₁ + U₁₁(S₂A = S₂ − S₂U − S₂L = D₂₂ − L₂₂ − U₂₂), respectively. From P₁ and P₂, we can obtain

(A_{1})_{ij} = {a_{1 j}, i = 1 a_{ij} - a_{1 j} (a_{i 1} + α_{i}), i \neq 1

(13)

and

(A_{2})_{ij} = {a_{nj}, i = n a_{ij} - a_{nj} (a_{in} + β_{i}), i \neq n

(14)

Here we consider the AOR splitting for A₁ and A₂

A_{1} = 1 w (I + D_{11} - r (L - S_{1} + L_{11})) - 1 w [(1 - w) (I + D_{11}) + (w - r) (L - S_{1} + L_{11}) + w (U + U_{11})]

(15)

A_{1} = 1 w (I - r (L - S_{1} + L_{11})) - 1 w [(1 - w) I + (w - r) (L - S_{1} + L_{11}) + w (U + U_{11} - D_{11})]

(16)

A_{2} = 1 w (I + D_{22} - r (L + L_{22})) - 1 w [(1 - w) (I + D_{22}) + (w - r) (L + L_{22}) + w (U + U_{22})]

(17)

and

A_{2} = 1 w (I - r (L + L_{22})) - 1 w [(1 - w) I + (w - r) (L + L_{22}) + w (U + U_{22} - D_{22})]

(18)

By considering equations (15)–(18), the AOR iteration matrices associated with A_t are

{\tilde{L}}_{t} (r, w) = (D_{t} - {rL}_{t})^{- 1} [(1 - w) D_{t} + (w - r) L_{t} + {wU}_{t}]

(19)

and

{\bar{L}}_{t} (r, w) = (I - {rL}_{t})^{- 1} [(1 - w) I + (w - r) L_{t} + w (U_{t} - D_{tt})]

(20)

for t = 1, 2, respectively. In the following sections, we will use the above results.

The rest of this paper is outlined as follows: in Section 2, we propose some definitions and lemmas which are essential tools for obtaining our main results. The comparison results are given in Section 3. In Section 4, we employ some numerical examples to support the theoretical results of this paper. In Section 5 we give some concluding remarks to end the paper.

2. Preliminaries

In this section, we give some definitions and lemmas which are essential tools for describing our main results (Berman and Plemmons, 1994; Datta, 1995).

Definition 2.1

A matrix A is a Z-matrix if a_ij ≤ 0 for all i, j = 1, 2, … , n such that i ≠ j. Also if a_ii > 0 i = 1, 2, … , n, the matrix is called an L-matrix. Furthermore, a Z-matrix is a nonsingular M-matrix, if A is nonsingular and A⁻¹ ≥ 0.

Definition 2.2

Let A be a real matrix. The representation A = M − N is called a splitting of A if M is a nonsingular matrix. The splitting is called:

convergent if ρ(M⁻¹N) < 1;

regular if M⁻¹ ≥ 0 and N ≥ 0;

nonnegative if M⁻¹N ≥ 0;

M-splitting if M is a nonsingular M-matrix and N ≥ 0.

Definition 2.3

(Schneider, 1977 ) An n × n matrix A = (a_ij) is reducible if we may partition 1, … , n into two nonempty subsets E, F such that a_ij = 0 if i ∈ E and j ∈ F. If A is not a reducible matrix, we call A is an irreducible matrix.

Lemma 2.1

(Varga, 1981 ) Let A ≥ 0 be an irreducible matrix. Then

A has a positive real eigenvalue equal to its spectral radius.

To ρ(A) there corresponds an eigenvector x > 0.

ρ(A) is a simple eigenvalue of A.

ρ(A) increases when any entry of A increases.

Lemma 2.2

(Varga, 1981 ) Let A be a nonnegative matrix. Then

If αx ≤ Ax for some nonnegative vector x, x ≠ 0, then α ≤ ρ(A).

If Ax ≤ βx for some positive vector x, then ρ(A) ≤ β. Moreover, if A is irreducible and if 0 ≠ αx ≤ Ax ≤ βx for some nonnegative vector x, then α ≤ ρ(A) ≤ β and x is a positive vector.

Lemma 2.3

(Li and Sun, 2000 ) Let A = M − N be an M-splitting of A. Then ρ(M⁻¹N) < 1 if and only if A is a nonsingular M-matrix.

Lemma 2.4

Let θ ∈ (0, 1], y ∈ (−∞, 0), and z ∈ (−∞, 0), then the set Q

Q = (θ - yz y, - z) \cap (0, - z)

(21)

is nonempty.

Proof

If we show that $- z - θ - yz y > 0$ , the proof will be complete. We can write

- z - θ - yz y = - z - θ y + z

= - θ y

> 0

Therefore Q ≠ φ.

Theorem 2.1

Let L(r, w), ${\tilde{L}}_{t} (r, w)$ and ${\bar{L}}_{t} (r, w)$ (t = 1, 2) be the iteration matrices of the AOR method given by equations (3), (19) and (20) associated with P₁ and P₂, respectively. If A is an irreducible L-matrix with a_1va_v1 > 0 and a_nsa_sn > 0, then for $α_{v} \in (θ - a_{1 v} a_{v 1} a_{1 v}, - a_{v 1}) \cap (0, - a_{v 1})$ , $β_{s} \in (θ - a_{sn} a_{ns} a_{ns}, - a_{sn}) \cap (0, - a_{sn})$ (v = 2, 3, … , n and s = 1, 2, … , n − 1), 0 < θ ≤ 1 and 0 ≤ r ≤ w ≤ 1 (w ≠ 0) (r ≠ 1), L(r, w), ${\tilde{L}}_{t} (r, w)$ , ${\bar{L}}_{t} (r, w)$ (t = 1, 2) are nonnegative irreducible matrices.

Proof

Because A is an irreducible L-matrix, L is a nonnegative strictly lower triangular matrix and U is a nonnegative strictly upper triangular matrix. By equation (3), we have

L (r, w) = (I - rL)^{- 1} [(1 - w) I + (w - r) L + wU] = [I + rL + r^{2} L^{2} + \dots + r^{n - 1} L^{n - 1}] \times [(1 - w) I + (w - r) L + wU] = (1 - w) I + w (1 - r) L + wU + nonnegative terms

Since 0 ≤ r ≤ w ≤ 1 (w ≠ 0) (r ≠ 1), we have L(r, w) is nonnegative. We can also get that (1 − w)I + w(1 − r) L + wU is irreducible for irreducible A, hence L(r, w) is also irreducible.

Now, we show that D_t > 0, L_t ≥ 0, U_t ≥ 0, and D_tt ≤ 0. By equations (13) and (14), we can obtain

D_{1} = diag (1, 1 - a_{12} (a_{21} + α_{2}), 1 - a_{13} (a_{31} + α_{3}), \dots, 1 - a_{1 n} (a_{n 1} + α_{n}))

L_{1} = (0 α_{2} 0 α_{3} - a_{32} + a_{12} (a_{31} + α_{3}) 0 : : : 0 α_{n} - a_{n 2} + a_{12} (a_{n 1} + α_{n}) \dots \dots 0)

(22)

U_{1} = (0 - a_{12} - a_{13} \dots - a_{1 n} 0 - a_{23} + a_{13} (a_{21} + α_{2}) \dots - a_{2 n} + (a_{21} + α_{2}) 0 : : 0 - a_{n - 1, n} + a_{1 n} (a_{n - 1, 1} + α_{n - 1}) 0)

(23)

D_{2} = diag (1 - a_{n 1} (a_{1 n} + β_{1}), 1 - a_{n 2} (a_{2 n} + β_{2}), \dots, 1)

L_{2} = (0 - a_{21} + a_{n 1} (a_{2 n} + β_{2}) 0 - a_{31} + a_{n 1} (a_{3 n} + β_{3}) - a_{32} + a_{n 2} (a_{3 n} + β_{3}) 0 : : : 0 - a_{n 1} - a_{n 2} \dots \dots 0)

(24)

U_{2} = (0 - a_{12} + a_{n 2} (a_{1 n} + β_{1}) - a_{13} + a_{n 3} (a_{1 n} + β_{1}) \dots β_{1} 0 - a_{23} + a_{n 3} (a_{2 n} + β_{2}) \dots β_{1} 0 : : 0 β_{n - 1} 0)

(25)

D_{11} = diag (0, - a_{12} (a_{21} + α_{2}), - a_{13} (a_{31} + α_{3}), \dots, - a_{1 n} (a_{n 1} + α_{n}))

and

D_{22} = diag (- a_{n 1} (a_{1 n} + β_{1}), - a_{n 2} (a_{2 n} + β_{2}), \dots, 0)

For

α_{v} \in (θ - a_{1 v} a_{v 1} a_{1 v}, - a_{v 1}) \cap (0, - a_{v 1})

β_{s} \in (θ - a_{sn} a_{ns} a_{ns}, - a_{sn}) \cap (0, - a_{sn})

(v = 2, 3, … , n and s = 1, 2, … , n − 1), we can write

1 - a_{1 v} (a_{v 1} + α_{v}) > 1 - a_{1 v} (a_{v 1} + θ - a_{1 v} a_{v 1} a_{1 v})

= 1 - θ a_{1 v}

> 0

(26)

and

1 - a_{ns} (a_{sn} + β_{s}) > 1 - a_{ns} (a_{sn} + θ - a_{ns} a_{sn} a_{ns})

= 1 - θ a_{ns}

> 0

(27)

By considering equations (26) and (27), we can get D_t > 0 and D_tt ≤ 0 for t = 1, 2. We can also write

- a_{ij} + a_{1 j} (a_{i 1} + α_{i}) \geq - a_{ij} + a_{1 j} (a_{i 1} - a_{i 1})

\geq - a_{ij}

\geq 0

(28)

and

- a_{ij} + a_{nj} (a_{in} + β_{i}) \geq - a_{ij} + a_{nj} (a_{in} - a_{in})

\geq - a_{ij}

\geq 0

(29)

Therefore L_t ≥ 0 and U_t ≥ 0 for t = 1, 2. Now from equation (19), we have

{\tilde{L}}_{t} (r, w) = (D_{t} - {rL}_{t})^{- 1} [(1 - w) D_{t} + (w - r) L_{t} + {wU}_{t}] = (I - {rD}_{t}^{- 1} L_{t})^{- 1} [(1 - w) I + (w - r) D_{t}^{- 1} L_{t} + {wD}_{t}^{- 1} U_{t}] = [I + {rD}_{t}^{- 1} L_{t} + r^{2} (D_{t}^{- 1} L_{t})^{2} + \dots + r^{n - 1} (D_{t}^{- 1} L_{t})^{n - 1}] \times [(1 - w) I + (w - r) D_{t}^{- 1} L_{t} + {wD}_{t}^{- 1} U_{t}] = (1 - w) I + w (1 - r) D_{t}^{- 1} L_{t} + {wD}_{t}^{- 1} U_{t} + nonnegative terms

By the above results, we can see

{\tilde{L}}_{t} (r, w)

are nonnegative irreducible matrices for t = 1, 2. Similar to the above proofs, we can show that

{\bar{L}}_{t} (r, w)

are nonnegative irreducible matrices for t = 1, 2. The proof is complete. □

Notice that, similar to the proof of the above theorem and using equations (28) and (29), we can conclude that L_tt ≥ 0 for t = 1, 2.

In the next section, applying the above results, we will present the main theorems in this work.

3. Comparison theorems

The spectral radius of the iterative matrix is conclusive for the convergence and stability of the method, and the smaller it is, the faster the method converges when the spectral radius is smaller than 1. In this section, some results for the AOR iterative method with preconditioners P₁ and P₂ are given.

Theorem 3.1

Let L(r, w), ${\tilde{L}}_{1} (r, w)$ be defined by equations (3) and (19) for t = 1, respectively. If A is an irreducible L-matrix with a_1va_v1 > 0, then for $α_{v} \in (θ - a_{1 v} a_{v 1} a_{1 v}, - a_{v 1}) \cap (0, - a_{v 1})$ , (v = 2, 3, … , n), 0 < θ ≤ 1 and 0 ≤ r ≤ w ≤ 1 (w ≠ 0) (r ≠ 1) we have

$ρ ({\tilde{L}}_{1} (r, w)) < ρ (L (r, w))$ , if ρ(L(r, w)) < 1

$ρ ({\tilde{L}}_{1} (r, w)) = ρ (L (r, w))$ , if ρ(L(r, w)) = 1

$ρ ({\tilde{L}}_{1} (r, w)) > ρ (L (r, w))$ , if ρ(L(r, w)) > 1

Proof

Theorem 2.1 implies that L(r, w) is a nonnegative irreducible matrix, hence there exists a positive vector x, such that

L (r, w) x = ξ x

(30)

where ρ(L(r, w)) = ξ or equivalently

[(1 - w) I + (w - r) L + wU] x = ξ (I - rL) x

(31)

It follows from S₁L = 0 and equation (31) that

{wS}_{1} Ux = (ξ + w - 1) S_{1} x

(32)

Now using equations (9)–(12), (19) and (32) we can obtain

{\tilde{L}}_{1} (r, w) x - ξ x = (D_{1} - r L_{1})^{- 1} [(1 - w) D_{1} + (w - r) L_{1} + w U_{1}] x - ξ x = (D_{1} - r L_{1})^{- 1} [(1 - w) D_{1} + (w - r) L_{1} + {wU}_{1} - ξ (D_{1} - r L_{1})] x = (D_{1} - r L_{1})^{- 1} [(1 - w - ξ) D_{1} + (w - r + ξ r) L_{1} + {wU}_{1}] x = (D_{1} - r L_{1})^{- 1} [(1 - w - ξ) D_{11} + (w - r + ξ r) (L_{11} - S_{1}) + {wU}_{11}] x = (D_{1} - r L_{1})^{- 1} [(1 - ξ) D_{11} + (w - r + ξ r) (L_{11} - S_{1}) - {wL}_{11} + {wS}_{1} U] x = (D_{1} - r L_{1})^{- 1} [(1 - ξ) (D_{11} + {rL}_{11}) + (- w + r - ξ r) S_{1} + (ξ + w - 1) S_{1}] x = (ξ - 1) (D_{1} - r L_{1})^{- 1} [- D_{11} + {rL}_{11} + (1 - r) S_{1}] x

Now let

F = (D_{1} - r L_{1})^{- 1} [- D_{11} + {rL}_{11} + (1 - r) S_{1}] x

From −D₁₁ ≥ 0, L₁₁ ≥ 0, and S₁ ≥ 0, we have [−D₁₁ + rL₁₁ + (1 − r)S₁] ≥ 0. Let R = D₁ − rL₁, we have D₁ is a nonsingular M-matrix and rL₁ ≥ 0. From Definition 2.2, we have the splitting R = D₁ − rL₁ as an M-splitting of R. Since

{rD}_{1}^{- 1} L_{1}

is a strictly lower triangular matrix so that

ρ ({rD}_{1}^{- 1} L_{1}) = 0 < 1

. By considering Lemma 2.3, we have R is a nonsingular M-matrix. Therefore (D₁ − rL₁)⁻¹ ≥ 0, then F ≥ 0.

If ξ < 1, then ${\tilde{L}}_{1} (r, w) x - ξ x \leq 0$ . Therefore ${\tilde{L}}_{1} (r, w) x \leq ξ x$ . By using Lemma 2.2, we get $ρ ({\tilde{L}}_{1} (r, w)) < ξ = ρ (L (r, w))$ ;

If ξ = 1, then ${\tilde{L}}_{1} (r, w) x - ξ x = 0$ . Therefore ${\tilde{L}}_{1} (r, w) x = ξ x$ . By using Lemma 2.2, we obtain $ρ ({\tilde{L}}_{1} (r, w)) = ξ = ρ (L (r, w))$ ;

If ξ > 1, then ${\tilde{L}}_{1} (r, w) x - ξ x \geq 0$ . Therefore ${\tilde{L}}_{1} (r, w) x \geq ξ x$ . By using Lemma 2.2, we get $ρ ({\tilde{L}}_{1} (r, w)) > ξ = ρ (L (r, w))$ .

The proof is complete. □

Theorem 3.2

Let L(r, w), ${\tilde{L}}_{2} (r, w)$ be defined by equations (3) and (19) for t = 2, respectively. If A is an irreducible L-matrix with a_nsa_sn > 0, then for $β_{s} \in (θ - a_{sn} a_{ns} a_{ns}, - a_{sn}) \cap (0, - a_{sn})$ (s = 1, 2, … , n − 1), 0 < θ ≤ 1 and 0 ≤ r ≤ w ≤ 1 (w ≠ 0) (r ≠ 1) we have

$ρ ({\tilde{L}}_{2} (r, w)) < ρ (L (r, w))$ , if ρ(L(r, w)) < 1

$ρ ({\tilde{L}}_{2} (r, w)) = ρ (L (r, w))$ , if ρ(L(r, w)) = 1

$ρ ({\tilde{L}}_{2} (r, w)) > ρ (L (r, w))$ , if ρ(L(r, w)) > 1

Proof

By equation (31) we can obtain

{\tilde{L}}_{2} (r, w) x - ξ x = (D_{2} - r L_{2})^{- 1} [(1 - w) D_{2} + (w - r) L_{2} + w U_{2}] x - ξ x = (D_{2} - r L_{2})^{- 1} [(1 - w) D_{2} + (w - r) L_{2} + {wU}_{2} - ξ (D_{2} - r L_{2})] x = (D_{2} - r L_{2})^{- 1} [(1 - w) (I + D_{22}) + (w - r) (L + L_{22}) + w (U + U_{22}) - ξ (I + D_{22} - r (L + L_{22})] x = (D_{2} - r L_{2})^{- 1} [(1 - w) (I + D_{22}) + (w - r) (L + L_{22}) + w (U + U_{22}) - ξ (I - rL) - ξ D_{22} + ξ {rL}_{22}] x = (D_{2} - r L_{2})^{- 1} [(1 - w) (I + D_{22}) + (w - r) (L + L_{22}) + w (U + U_{22}) - (1 - w) I - (w - r) L - wU - ξ D_{22} + ξ {rL}_{22}] x = (D_{2} - r L_{2})^{- 1} [(1 - w) D_{22} + (w - r) L_{22} + {wU}_{22} - ξ D_{22} + ξ {rL}_{22}] x = (D_{2} - r L_{2})^{- 1} [w (- D_{22} + L_{22} + U_{22}) + (1 - ξ) D_{22} + r (ξ - 1) L_{22}] x = (D_{2} - r L_{2})^{- 1} [(1 - w) S_{2} I + (w - r) S_{2} L + {wS}_{2} U - S_{2} (I - rL) - (ξ - 1) D_{22} + r (ξ - 1) L_{22}] x = (D_{2} - r L_{2})^{- 1} [ξ S_{2} (I - rL) - S_{2} (I - rL) - (ξ - 1) D_{22} + r (ξ - 1) L_{22}] x = (D_{2} - r L_{2})^{- 1} (ξ - 1) ξ [(1 - w) S_{2} I + (w - r) S_{2} L + {wS}_{2} U - ξ D_{22} + r ξ L_{22}] x

(33)

Now let

H = (D_{2} - r L_{2})^{- 1} [(1 - w) S_{2} I + (w - r) S_{2} L + {wS}_{2} U - ξ D_{22} + r ξ L_{22}] x

By a similar proof to the previous theorem we can show that H ≥ 0.

If ξ < 1, then ${\tilde{L}}_{1} (r, w) x - ξ x \leq 0$ . Therefore ${\tilde{L}}_{1} (r, w) x \leq ξ x$ . By considering Lemma 2.2, we get $ρ ({\tilde{L}}_{1} (r, w)) < ξ = ρ (L (r, w))$ ;

If ξ = 1, then ${\tilde{L}}_{1} (r, w) x - ξ x = 0$ . Therefore ${\tilde{L}}_{1} (r, w) x = ξ x$ . By considering Lemma 2.2, we obtain $ρ ({\tilde{L}}_{1} (r, w)) = ξ = ρ (L (r, w))$ ;

If ξ > 1, then ${\tilde{L}}_{1} (r, w) x - ξ x \geq 0$ . Therefore ${\tilde{L}}_{1} (r, w) x \geq ξ x$ . By considering Lemma 2.2, we get $ρ ({\tilde{L}}_{1} (r, w)) > ξ = ρ (L (r, w))$ .

The proof is complete. □

Theorem 3.3

Let L(r, w), ${\bar{L}}_{1} (r, w)$ be defined by equations (3) and (20) for t = 1, respectively. If A is an irreducible L-matrix with a_1va_v1 > 0, then for $α_{v} \in (θ - a_{1 v} a_{v 1} a_{1 v}, - a_{v 1}) \cap (0, - a_{v 1})$ , (v = 2, 3, … , n), 0 < θ ≤ 1 and 0 ≤ r ≤ w ≤ 1 (w ≠ 0) (r ≠ 1) we have

$ρ ({\bar{L}}_{1} (r, w)) < ρ (L (r, w))$ , if ρ(L(r, w)) < 1

$ρ ({\bar{L}}_{1} (r, w)) = ρ (L (r, w))$ , if ρ(L(r, w)) = 1

$ρ ({\bar{L}}_{1} (r, w)) > ρ (L (r, w))$ , if ρ(L(r,w)) > 1

Proof

By equations (31) and (32) we can get

{\bar{L}}_{1} (r, w) x - ξ x = (I - L_{1})^{- 1} [(1 - w) I + (w - r) L_{1} + w (U_{1} - D_{11})] x - ξ x = (I - {rL}_{1})^{- 1} [(1 - w) I + (w - r) L_{1} + w (U_{1} - D_{11}) - ξ (I - {rL}_{1})] x = (I - {rL}_{1})^{- 1} [(1 - w - ξ) I + (w - r + ξ r) L_{1} + {wU}_{1} - {wD}_{11}] = (I - {rL}_{1})^{- 1} [(1 - w - ξ) I + (w - r + ξ r) (L - S_{1} + L_{11}) + w (U + U_{11}) - {wD}_{11}] = (I - {rL}_{1})^{- 1} [(w - r + ξ r) (- S_{1} + L_{11}) + {wU}_{11} - {wD}_{11}] = (I - {rL}_{1})^{- 1} [(w - r + ξ r) (- S_{1} + L_{11}) + {wS}_{1} U - {wL}_{11}] = (I - {rL}_{1})^{- 1} [(- r + ξ r) L_{11} + (r - ξ r + ξ - 1) S_{1}] = (ξ - 1) (I - {rL}_{1})^{- 1} [{rL}_{11} + (1 - r) S_{1}]

Let

J = (I - {rL}_{1})^{- 1} [{rL}_{11} + (1 - r) S_{1}]

Similar to proof of the previous theorem we can conclude that J ≥ 0.

If ξ < 1, then ${\bar{L}}_{1} (r, w) x - ξ x \leq 0$ . Therefore ${\bar{L}}_{1} (r, w) x \leq ξ x$ . Using Lemma 2.2 implies that $ρ ({\bar{L}}_{1} (r, w)) < ξ = ρ (L (r, w))$ ;

If ξ = 1, then ${\bar{L}}_{1} (r, w) x - ξ x = 0$ . Therefore ${\bar{L}}_{1} (r, w) x = ξ x$ . Using Lemma 2.2 implies that $ρ ({\bar{L}}_{1} (r, w)) = ξ = ρ (L (r, w))$ ;

If ξ > 1, then ${\bar{L}}_{1} (r, w) x - ξ x \geq 0$ . Therefore ${\bar{L}}_{rw} x \geq ξ x$ . Using Lemma 2.2 implies that $ρ ({\bar{L}}_{1} (r, w)) > ξ = ρ (L (r, w))$ .

The proof is complete. □

Theorem 3.4

Let L(r, w), ${\bar{L}}_{2} (r, w)$ be defined by equations (3) and (20) for t = 2, respectively. If A is an irreducible L-matrix with a_nsa_sn > 0, then for $β_{s} \in (θ - a_{sn} a_{ns} a_{ns}, - a_{sn}) \cap (0, - a_{sn})$ (s = 1, 2, … , n − 1), 0 < θ ≤ 1 and 0 ≤ r ≤ w ≤ 1 (w ≠ 0) (r ≠ 1) we have

$ρ ({\bar{L}}_{2} (r, w)) < ρ (L (r, w))$ , if ρ(L(r, w)) < 1

$ρ ({\bar{L}}_{2} (r, w)) = ρ (L (r, w))$ , if ρ(L(r, w)) = 1

$ρ ({\bar{L}}_{2} (r, w)) > ρ (L (r, w))$ , if ρ(L(r,w)) > 1

Proof

By equation (31) we can get

{\bar{L}}_{2} (r, w) x - ξ x = (I - L_{2})^{- 1} [(1 - w) I + (w - r) L_{2} + w (U_{1} - D_{22})] x - ξ x = (I - {rL}_{2})^{- 1} [(1 - w) I + (w - r) L_{2} + w (U_{2} - D_{22}) - ξ (I - {rL}_{2})] x = (I - {rL}_{2})^{- 1} [(1 - w) I + (w - r) (L + L_{22}) + w (U + U_{22} - D_{22}) - ξ (I - r (L + L_{22}))] x = (I - {rL}_{2})^{- 1} [(1 - w) I + (w - r) (L + L_{22}) + w (U + U_{22} - D_{22}) - ξ (I - rL) + ξ {rL}_{22}] x = (I - {rL}_{2})^{- 1} [(1 - w) I + (w - r) (L + L_{22}) + w (U + U_{22} - D_{22}) - (1 - w) I - (w - r) L - wU + ξ {rL}_{22}] x = (I - {rL}_{2})^{- 1} [- {wD}_{22} + (w - r) L_{22} + {wU}_{22} + ξ {rL}_{22}] x = (I - {rL}_{2})^{- 1} [w (- D_{2} + L_{2} + U_{2}) - {rL}_{2} + ξ {rL}_{2}] x = (I - {rL}_{2})^{- 1} [w (- D_{22} + L_{22} + U_{22}) + r (ξ - 1) L_{22}] x = (I - r \overset{\land}{L})^{- 1} [w (S_{2} L + S_{2} U - S_{2}) + r (ξ - 1) L_{2}] x = (I - {rL}_{2})^{- 1} [(1 - w) S_{2} + (w - r) S_{2} L + {wS}_{2} U - S_{2} (I - rL) + r (ξ - 1) L_{22}] x = (I - {rL}_{2})^{- 1} [ξ S_{2} (I - rL) - S_{2} (I - rL) + r (ξ - 1) L_{22}] x = (I - {rL}_{2})^{- 1} (ξ - 1) ξ [(1 - w) S_{2} I + (w - r) S_{2} L + {wS}_{2} U + r ξ L_{22}] x

(34)

Let

Z = (I - {rL}_{2})^{- 1} [(1 - w) S_{2} I + (w - r) S_{2} L + {wS}_{2} U + r ξ L_{22}] x

Similarly we have Z ≥ 0.

If ξ < 1, then ${\bar{L}}_{2} (r, w) x - ξ x \leq 0$ . Therefore ${\bar{L}}_{2} (r, w) x \leq ξ x$ . By using Lemma 2.2, we get $ρ ({\bar{L}}_{2} (r, w)) < ξ = ρ (L (r, w))$ ;

If ξ = 1, then ${\bar{L}}_{2} (r, w) x - ξ x = 0$ . Therefore ${\bar{L}}_{2} (r, w) x = ξ x$ . By using Lemma 2.2, we obtain $ρ ({\bar{L}}_{2} (r, w)) = ξ = ρ (L (r, w))$ ;

If ξ > 1, then ${\bar{L}}_{2} (r, w) x - ξ x \geq 0$ . Therefore ${\bar{L}}_{2} (r, w) x \geq ξ x$ . By using Lemma 2.2, we get $ρ ({\bar{L}}_{2} (r, w)) > ξ = ρ (L (r, w))$ .

The proof is complete. □

We know, when w = r the AOR method reduces to the SOR method. For w = r, L(r, w), ${\tilde{L}}_{t} (r, w)$ and ${\bar{L}}_{t} (r, w)$ (t = 1, 2) are presented by T(w), ${\tilde{T}}_{t} (w)$ , and ${\bar{T}}_{t} (w)$ (t = 1, 2) as follows

T (w) = (I - wL)^{- 1} [(1 - w) I + wU]

(35)

{\tilde{T}}_{t} (w) = (D_{t} - {wL}_{t})^{- 1} [(1 - w) D_{t} + {wU}_{t}]

(36)

and

{\bar{T}}_{t} (w) = (I - {wL}_{t})^{- 1} [(1 - w) I + w (U_{t} - D_{tt})]

(37)

From Theorems 3.1–3.4, we can obtain the following corollaries.

Corollary 3.1

Let T(w), ${\tilde{T}}_{1} (w)$ be defined by equations (35) and (36) for t = 1, respectively. If A is an irreducible L-matrix with a_1va_v1 > 0, then for $α_{v} \in (θ - a_{1 v} a_{v 1} a_{1 v}, - a_{v 1}) \cap (0, - a_{v 1})$ , (v = 2, 3, … , n), 0 < θ ≤ 1 and 0 < w < 1 we have

$ρ ({\tilde{T}}_{1} (w)) < ρ (T (w))$ , if ρ(T(w)) < 1

$ρ ({\tilde{T}}_{1} (w)) = ρ (T (w))$ , if ρ(T(w)) = 1

$ρ ({\tilde{T}}_{1} (w)) > ρ (T (w))$ , if ρ(T(w)) > 1

Corollary 3.2

Let T(w), ${\tilde{T}}_{2} (w)$ be defined by equations (35) and (36) for t = 2, respectively. If A is an irreducible L-matrix with a_nsa_sn > 0, then for $β_{s} \in (θ - a_{sn} a_{ns} a_{ns}, - a_{sn}) \cap (0, - a_{sn})$ (s = 1, 2, … , n − 1), 0 < θ ≤ 1 and 0 < w < 1 we have

$ρ ({\tilde{T}}_{2} (w)) < ρ (T (w))$ , if ρ(T(w)) < 1

$ρ ({\tilde{T}}_{2} (w)) = ρ (T (w))$ , if ρ(T(w)) = 1

$ρ ({\tilde{T}}_{2} (w)) > ρ (T (w))$ , if ρ(T(w)) > 1

Corollary 3.3

Let T(w), ${\bar{T}}_{1} (w)$ be defined by equations (35) and (37) for t = 1, respectively. If A is an irreducible L-matrix with a_1va_v1 > 0, then for $α_{v} \in (θ - a_{1 v} a_{v 1} a_{1 v}, - a_{v 1}) \cap (0, - a_{v 1})$ , (v = 2, 3, … , n), 0 < θ ≤ 1 and 0 < w < 1 we have

$ρ ({\bar{T}}_{1} (w)) < ρ (T (w))$ , if ρ(T(w)) < 1

$ρ ({\bar{T}}_{1} (w)) = ρ (T (w))$ , if ρ(T(w)) = 1

$ρ ({\bar{T}}_{1} (w)) > ρ (T (w))$ , if ρ(T(w)) > 1

Corollary 3.4

Let T(w), ${\bar{T}}_{2} (w)$ be defined by equations (35) and (37) for t = 2, respectively. If A is an irreducible L-matrix with a_nsa_sn > 0, then for $β_{s} \in (θ - a_{sn} a_{ns} a_{ns}, - a_{sn}) \cap (0, - a_{sn})$ (s = 1, 2, … , n − 1), 0 < θ ≤ 1 and 0 < w < 1 we have

$ρ ({\bar{T}}_{2} (w)) < ρ (T (w))$ , if ρ(T(w)) < 1

$ρ ({\bar{T}}_{2} (w)) = ρ (T (w))$ , if ρ(T(w)) = 1

$ρ ({\bar{T}}_{2} (w)) > ρ (T (w))$ , if ρ(T(w)) > 1

In the next section, several numerical examples are given to show the efficiency of the presented preconditioners.

4. Numerical examples

Now let us consider the following examples to illustrate the results obtained in the previous section.

Example 4.1

The coefficient matrix A of equation (1) is given by

A = (1.0000 - 0.2000 - 0.1000 - 0.1000 - 0.1000 - 0.1000 - 0.2000 1.0000 000 - 0.2000 - 0.2000 - 0.1000 1.0000 - 0.3000 - 0.1000 - 0.2000 - 0.1000 0 - 0.2000 1.0000 - 0.3000 - 0.1000 - 0.3000 - 0.2000 - 0.1000 - 0.1000 1.0000 - 0.1000 - 0.2000 - 0.3000 - 0.2000 - 0.1000 - 0.2000 1.0000)

We can see easily, matrix A does not satisfy in equation (6). But we can apply the proposed methods. Tables 1 and 2 display the spectral radii of the corresponding iterative matrices with different parameters w, r, α_v, and β_s (v = 2, 3, … , 6 and s = 1, 2, … , 5).

Table 1.

The spectral radii of L(r, w), ${\tilde{L}}_{1} (r, w)$ , ${\tilde{L}}_{2} (r, w)$ , ${\bar{L}}_{1} (r, w)$ , and ${\bar{L}}_{2} (r, w)$ iterative matrices for θ = 1, α_v = 0.0001, and β_s = 0.0001 (v = 2, 3,…, 6 and s = 1, 2,…, 5)

(w, r)	L(r, w)	${\tilde{L}}_{1} (r, w)$	${\bar{L}}_{1} (r, w)$	${\tilde{L}}_{2} (r, w)$	${\bar{L}}_{2} (r, w)$
(0.5, 0.1)	0.8504	0.8226	0.8267	0.8175	0.8227
(0.8, 0.5)	0.7170	0.6685	0.6776	0.6626	0.6737
(0.6, 0.3)	0.8058	0.7710	0.7768	0.7656	0.7727
(0.9, 0.8)	0.6254	0.5661	0.5803	0.5634	0.5802
(0.3, 0.3)	0.9029	0.8855	0.8884	0.8828	0.8863
(0.7, 0.7)	0.7254	0.6808	0.6905	0.6774	0.6891

Table 2.

The spectral radii of L(r, w), ${\tilde{L}}_{1} (r, w)$ , ${\tilde{L}}_{2} (r, w)$ , ${\bar{L}}_{1} (r, w)$ , and ${\bar{L}}_{2} (r, w)$ iterative matrices for θ = 1, α_v = 0.001, and β_s = 0.001 (v = 2, 3,…, 6 and s = 1, 2,…, 5)

(w, r)	L(r, w)	${\tilde{L}}_{1} (r, w)$	${\bar{L}}_{1} (r, w)$	${\tilde{L}}_{2} (r, w)$	${\bar{L}}_{2} (r, w)$
(0.5, 0.1)	0.8504	0.8227	0.8269	0.8178	0.8229
(0.8, 0.5)	0.7170	0.6688	0.6778	0.6631	0.6740
(0.6, 0.3)	0.8058	0.7712	0.7769	0.7659	0.7730
(0.9, 0.8)	0.6254	0.5664	0.5805	0.5639	0.5806
(0.3, 0.3)	0.9029	0.8856	0.8885	0.8830	0.8865
(0.7, 0.7)	0.7254	0.6810	0.6907	0.6778	0.6894

Example 4.2

Let

A = (1.0000 - 0.2000 - 0.2000 - 0.1000 - 0.2500 - 0.4000 - 0.2000 1.0000 000 - 1.0000 - 0.3000 - 0.5000 1.0000 - 0.0500 - 0.2500 - 0.1000 - 0.2500 - 0.1000 - 0.5500 1.0000 - 0.3000 - 0.1000 - 0.2000 - 0.1500 - 0.3000 - 0.0500 1.0000 - 0.5000 - 0.3000 - 0.2500 - 0.2500 - 0.1000 - 0.3000 1.0000)

The spectral radii of the corresponding iterative matrices with different parameters w, r, α_v, and β_s (v = 2, 3, … , 6 and s = 1, 2, … , 5) are shown in Table 3.

Table 3.

(w, r)	L(r, w)	${\tilde{L}}_{1} (r, w)$	${\bar{L}}_{1} (r, w)$	${\tilde{L}}_{2} (r, w)$	${\bar{L}}_{2} (r, w)$
(0.4, 0.2)	1.0903	1.1228	1.1126	1.1572	1.1331
(0.5, 0.1)	1.1050	1.1420	1.1310	1.1815	1.1554
(0.8, 0.3)	1.1948	1.2670	1.2430	1.3420	1.2859
(0.9, 0.8)	1.3520	1.5047	1.4365	1.6440	1.4926
(0.2, 0.2)	1.0451	1.0614	1.0563	1.0786	1.0665
(0.8, 0.8)	1.3129	1.4486	1.3880	1.5724	1.4379

5. Concluding remarks

In this paper, we first proposed two new preconditioners, then applied an AOR iterative scheme to a preconditioned linear system. Second, under mild assumptions, we have introduced a preconditioned AOR method and presented comparison theorems on the preconditioned iterative method for solving linear systems with L-matrices. We have shown that the spectral radius of the proposed methods is smaller than that of the basic AOR method. Numerical examples were also presented to illustrate our results.

Footnotes

Acknowledgements

The authors would like to express their heartfelt thanks to the editor and anonymous referees for their useful comments and constructive suggestions which substantially improved the quality and presentation of this paper.

Funding

This work received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

References

Berman

Plemmons

(1994) Nonnegative Matrices in the Mathematical Sciences, Philadelphia: SIAM.

Datta

(1995) Numerical Linear Algebra and Applications, Pacific Grove: Cole Publishing Co.

Dehghan

Hajarian

(2010a) The general coupled matrix equations over generalized bisymmetric matrices. Linear Algebra and its Applications 432: 15311552.

Dehghan

Hajarian

(2010b) An efficient algorithm for solving general coupled matrix equations and its application. Mathematical and Computer Modelling 51: 11181134.

Dehghan

Hajarian

(2011a) On the generalized bisymmetric and skew-symmetric solutions of the system of generalized Sylvester matrix equations. Linear and Multilinear Algebra 59: 12811309.

Dehghan

Hajarian

(2011b) Analysis of an iterative algorithm to solve the generalized coupled Sylvester matrix equations. Applied Mathematical Modelling 35: 32853300.

Ding

Chen

(2005a) Iterative least squares solutions of coupled Sylvester matrix equations. Systems & Control Letters 54: 95107.

Ding

Chen

(2005b) Hierarchical least squares identification methods for multivariable systems. IEEE Transactions on Automatic Control 50: 397402.

Ding

Chen

(2006) On iterative solutions of general coupled matrix equations. SIAM Journal on Control and Optimization 44: 22692284.

10.

Evans

Martins

(1992) On the convergence of the extrapolated AOR method. International Journal of Computer Mathematics 43: 161171.

11.

Evans

Martins

Trigo

(2001) The AOR iterative method for new preconditioned linear systems. Journal of Computational and Applied Mathematics 132: 461466.

12.

Hadjidimos

(1978) Accelerated overrelaxation method. Mathematics of Computation 32: 149157.

13.

(2002) Preconditioned AOR iterative methods for linear systems. International Journal of Computer Mathematics 79: 89101.

14.

Sun

(2000) Modified Gauss–Seidel type methods and Jacobi type methods forZ-matrices. Linear Algebra and its Applications 317: 227240.

15.

(2007) Improvements of preconditioned AOR iterative method forL-matrices. Journal of Computational and Applied Mathematics 206: 656665.

16.

Milaszewics

(1987) Improving Jacobi and Gauss–Seidel iterations. Linear Algebra and its Applications 93: 161170.

17.

Schneider

(1977) The concepts of irreducibility and full indecomposability of a matrix in the works of Frobenius, König and Markov. Linear Algebra and its Applications 18: 139162.

18.

Varga

(1981) Matrix Iterative Analysis, Englewood Cliffs: Prentice-Hall.

19.

Wang

Huang

(2007) Comparison results on preconditioned SOR-type iterative method forZ-matrices linear systems. Journal of Computational and Applied Mathematics 206: 726732.

20.

Wang

Song

(2007) Preconditioned AOR iterative method for linear systems. Applied Numerical Mathematics 57: 672685.

21.

Yun

Kim

(2008) Convergence of the preconditioned AOR method for irreducibleL-matrices. Applied Mathematics and Computation 201: 5664.