Erschienen in:

Open Access 01.12.2016 | Research

A selected method for the optimal parameters of the AOR iteration

verfasst von: Luna Ren, Fujiao Ren, Ruiping Wen

Erschienen in: Journal of Inequalities and Applications | Ausgabe 1/2016

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Patentsuche

Aus

Abstract

In this paper, we present an optimization technique to find the optimal parameters of the AOR iteration, which just needs to minimize the 2-norm of the residual vector and avoids solving the spectral radius of the iteration matrix of the SOR method. Meanwhile, numerical results are provided to indicate that the new method is more robust than the AOR method for larger intervals of the parameters ω and γ.

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

1 Introduction

In recent years, the iterative solvers of a large sparse linear system of equations

$$ Ax=b $$

(1.1)

are considered in many scientific computing and engineering problems, where the coefficient matrix $A\in\mathcal{R}^{n\times n}$ is a nonsingular matrix, $b\in\mathcal{R}^{n}$ is a given right-hand vector, and $x\in\mathcal{R}^{n}$ is an unknown vector.

The accelerated overrelaxation (AOR) method, which have been proven to be a powerful tool for solving the linear system of equations (1.1), was introduced firstly by Hadjidimos [1]. In particular, he showed that when the two parameters are easily obtainable, the AOR method converges faster than the other methods of the same type. Thus, the matter about the determination of the optimal acceleration and overrelaxation parameters has to be further investigated. Lots of significant results about the optimal parameters of the AOR method were given by Hadjidimos [2]. Analytic formulas about the optimal parameters were put forward by Martins [3] in the cases where the coefficient matrix A is a weakly diagonally dominant matrix or an H-matrix. Besides, analytic formulas for optimal parameters were also provided by Hadjidimos [1, 4] in those cases where the coefficient matrix A is a consistently ordered 2-cyclic matrix, an irreducibly weakly diagonally dominant matrix, an L-matrix, or a real symmetric positive definite matrix. In order to compute the optimal parameters, the spectral radius of the corresponding SOR iteration matrix is required, which may greatly decrease the computing efficiently of the AOR iteration. In addition, the computation of this spectral radius is usually a difficult task. Furthermore, the choice of an analytic formula for a general nonsymmetric matrix is little known to us. Thus, applications of the AOR method to widespread real problems are seriously restricted.

The asymptotically optimal successive overrelaxation method of choosing the optimal factor in a dynamic fashion according to known information at the current iterate step was proposed by Bai and Chi [5]. Besides, a quasi-Chebyshev accelerated iteration method for solving a linear system was presented by Wen, Meng, and Wang [6], who obtained the optimal parameter by an optimization model. Similarly, a method of determining the optimal parameter of the SOR method was also introduced by Meng [7]. Based on the facts mentioned, an optimization technique relating to choosing the optimal parameters is put forward. Here, the optimal parameters ω and γ are computed by solving a lower-order nonlinear system that is determined by the residual vector and the coefficient matrix A. Furthermore, the optimal parameters are selected by the Newton iteration method instead of specific analytic formulas in [1, 3, 4]. In this study, applying this optimization technique to the AOR iteration, we present a modified method called the asymptotically optimal AOR (AOAOR) method, which is more stable and effective for large linear systems than the AOR method.

In Section 2, we first briefly review the AOR method and its properties. Then we put forward the AOAOR method in Section 3. In Section 4, we use numerical experiments to show the stability of the AOAOR method. We end the paper with conclusions in Section 5.

2 AOR method and its properties

Hadjidimos [1] proposed the following splitting method with two parameters of the coefficient matrix A:

$$A=\mathcal{M}_{\gamma,\omega}-\mathcal{N}_{\gamma,\omega} $$

with

$$ \mathcal{M}_{\gamma,\omega}=\frac{1}{\omega}(A_{D}- \gamma A_{L}),\quad \quad \mathcal{N}_{\gamma,\omega}=\frac{1}{\omega} \bigl[(1-\omega)A_{D}+(\omega -\gamma)A_{L}+\omega A_{U}\bigr], $$

(2.1)

where $\gamma,\omega\neq0$, $A_{D}$ is the diagonal part of A, and $-A_{L}$ and $-A_{U}$ are strictly lower and strictly upper triangular parts of A, respectively. The iteration format of the AOR method for solving the linear systems (1.1) is

$$x^{p+1}=\mathcal{L}_{\gamma,\omega}x^{p}+g_{\gamma,\omega}, $$

where

$$\mathcal{L}_{\gamma,\omega}=(A_{D}-\gamma A_{L})^{-1} \bigl[(1-\omega )A_{D}+(\omega-\gamma)A_{L}+\omega A_{U}\bigr],\quad \quad g_{\gamma,\omega}=\omega (A_{D}- \gamma A_{L})^{-1}b. $$

We observe the specific values of the parameters γ and ω in [1] when the AOR method can be reduced into:

the Jacobi method if $\omega=0$, $\gamma=1$;
the Simultaneous Overrelaxtion method if $\gamma=0$;
the Gauss-Seidel method if $\omega=1$, $\gamma=1$;
the Successive Overrelaxation method if $\omega=\gamma$.

The various generalizations and/or modifications of the AOR method can be found in [1‐4, 8]. More precisely, we survey the following conclusions.

Theorem 2.1

(Theorems 4.2, 4.4, 4.6, and 4.9 of [4])

Let A be a nonsingular matrix with nonzero diagonal entries. Then $\{x^{p}\}_{p=0}^{\infty}$ generated by the AOR method converges to the unique solution $x_{*}$ of the linear system (1.1) in the following cases:

(a)

if A is an irreducibly weakly diagonally dominant matrix; for $0<\gamma\leq1$, a sufficient condition is $0<\omega<2\gamma/[1+\rho (\mathcal{L}_{\gamma,\gamma})]$;

(b)

if A is a real symmetric positive definite matrix; for $0<\gamma<2$, a sufficient condition is $0<\omega<2\gamma/[1+\rho (\mathcal{L}_{\gamma,\gamma})]$;

(c)

if A is an L-matrix; for $0<\gamma\leq1$, sufficient conditions are (i) $0<\omega<2\gamma/[1+\rho(\mathcal{L}_{\gamma,\gamma })]$, (ii) A is an M-matrix;

(d)

if A is an M-matrix; for $0\leq\gamma\leq1$, a sufficient condition is $0<\omega\leq\max\{1,\frac{2\gamma}{1+\rho(\mathcal {L}_{\gamma,\gamma})}\}$.

Remark

In order to compute the optimal parameters, the $\rho (\mathcal{L}_{\gamma,\omega})$ is quite expensive and may greatly decrease the computing efficiency of the AOR iteration method from Theorem 2.1. Hence, the formulas for the optimal parameters in Theorem 2.1 are only of theoretical meaning and far away from practical applications. To further derive a reasonably applicable rule for choosing the optimal parameters, the properties of the errors or residuals of the AOR method need to be still investigated.

Let $\varepsilon^{p}$ and $r^{p}$ denote the error and residual vectors of the AOR method at the pth iterate step, respectively, that is, $\varepsilon^{p}=x^{p}-x_{*}$, $r^{p}=b-Ax^{p}$, and let

$$ \mathcal{H}_{\gamma,\omega}=A\mathcal{M}_{\gamma,\omega}^{-1}-I, $$

(2.2)

where $\mathcal{M}_{\gamma,\omega}^{-1}$ has been defined by (2.1). Then we have the following results.

Theorem 2.2

For the AOR method,

(a)

if A is a symmetric positive definite matrix, then:

$$\begin{aligned}& \bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2} = \bigl(r^{p}\bigr)^{T}\mathcal {H}_{\gamma,\omega}^{T}A^{-1} \mathcal{H}_{\gamma,\omega}r^{p}, \\& \frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2} = \frac {2}{\omega}\bigl(r^{p} \bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T}\mathcal{M}_{\gamma ,\omega}^{-1}A_{L} \mathcal{M}_{\gamma,\omega}^{-1}r^{p}, \\& \frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2} = \frac {2}{\omega}\bigl(r^{p} \bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T}\mathcal{M}_{\gamma ,\omega}^{-1}r^{p}; \end{aligned}$$

(b)

if A is a general nonsymmetric matrix, then:

$$\begin{aligned}& \bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} = \bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma ,\omega}^{T} \mathcal{H}_{\gamma,\omega}r^{p}, \\& \frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} = \frac{2}{\omega }\bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T}A \mathcal{M}_{\gamma,\omega }^{-1}A_{L}\mathcal{M}_{\gamma,\omega}^{-1}r^{p}, \\& \frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} = \frac{2}{\omega}\bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T}A \mathcal {M}_{\gamma,\omega}^{-1}r^{p}. \end{aligned}$$

Proof

By computing we have

$$\begin{aligned} \bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2} = & \bigl(\varepsilon ^{p+1},A\varepsilon^{p+1}\bigr)=\bigl( \varepsilon^{p}+\mathcal{M}_{\gamma,\omega }^{-1}r^{p},A \varepsilon^{p}+A \mathcal{M}_{\gamma,\omega}^{-1}r^{p} \bigr) \\ = &\bigl(A^{-1}\bigl(-r^{p}+A \mathcal{M}_{\gamma,\omega}^{-1}r^{p} \bigr),-r^{p}+A \mathcal{M}_{\gamma,\omega}^{-1}r^{p} \bigr) \\ =&\bigl(A^{-1} \mathcal{H}_{\gamma,\omega}r^{p}, \mathcal{H}_{\gamma,\omega }r^{p}\bigr) \\ =&\bigl(r^{p}\bigr)^{T} \mathcal{H}_{\gamma,\omega}^{T}A^{-1} \mathcal {H}_{\gamma,\omega}r^{p} \end{aligned}$$

and

$$\begin{aligned} \bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} = & \bigl(r^{p}-A\mathcal{M}_{\gamma ,\omega}^{-1}r^{p},r^{p}-A \mathcal{M}_{\gamma,\omega}^{-1}r^{p}\bigr) \\ = &\bigl(-\mathcal{H}_{\gamma,\omega}r^{p},-\mathcal{H}_{\gamma,\omega }r^{p} \bigr) \\ =&\bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T} \mathcal{H}_{\gamma,\omega}r^{p}. \end{aligned}$$

Because of the equalities

$$\begin{aligned}& \frac{\partial (\mathcal{M}_{\gamma,\omega}^{-1})}{\partial \gamma}=- \mathcal{M}_{\gamma,\omega}^{-1}\frac{\partial (\mathcal{M}_{\gamma,\omega})}{\partial \gamma}\mathcal{M}_{\gamma,\omega}^{-1} \quad\mbox{and}\quad \frac{\partial (\mathcal{M}_{\gamma,\omega})}{\partial \gamma}=- \frac{1}{\omega}A_{L}, \\& \frac{\partial (\mathcal{M}_{\gamma,\omega}^{-1})}{\partial \omega}=- \mathcal{M}_{\gamma,\omega}^{-1}\frac{\partial (\mathcal{M}_{\gamma,\omega})}{\partial \omega}\mathcal{M}_{\gamma,\omega}^{-1} \quad\mbox{and}\quad \frac{\partial (\mathcal{M}_{\gamma,\omega})}{\partial \omega}=- \frac{1}{\omega ^{2}}(A_{D}-\gamma A_{L}), \end{aligned}$$

we have

$$\begin{aligned}& \frac{\partial(\mathcal{M}_{\gamma,\omega}^{-1})}{\partial\gamma }=\frac{1}{\omega}\mathcal{M}_{\gamma,\omega}^{-1}A_{L} \mathcal {M}_{\gamma,\omega}^{-1} \quad\mbox{and}\quad\frac{\partial(\mathcal{H}_{\gamma ,\omega})}{\partial\gamma}= \frac{1}{\omega}A\mathcal{M}_{\gamma,\omega }^{-1}A_{L} \mathcal{M}_{\gamma,\omega}^{-1}, \\& \frac{\partial(\mathcal{M}_{\gamma,\omega}^{-1})}{\partial\omega }=\frac{1}{\omega}\mathcal{M}_{\gamma,\omega}^{-1} \quad\hbox{and}\quad\frac{\partial(\mathcal{H}_{\gamma,\omega})}{\partial\omega }=\frac{1}{\omega}A\mathcal{M}_{\gamma,\omega}^{-1}. \end{aligned}$$

Thus,

$$\begin{aligned}& \begin{aligned} \frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}&= \bigl(r^{p}\bigr)^{T}\biggl( \frac{\partial\mathcal{H}_{\gamma,\omega}}{\partial\omega }\biggr)^{T}A^{-1}\mathcal{H}_{\gamma,\omega}r^{p}+ \bigl(r^{p}\bigr)^{T}\mathcal {H}_{\gamma,\omega}^{T}A^{-1} \frac{\partial\mathcal{H}_{\gamma,\omega }}{\partial\omega}r^{p} \\ &= \frac{1}{\omega}\bigl(\bigl(r^{p}\bigr)^{T} \mathcal{M}_{\gamma,\omega}^{-T}\mathcal {H}_{\gamma,\omega}r^{p}+ \bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma,\omega }^{T} \mathcal{M}_{\gamma,\omega}^{-1}r^{p}\bigr) \\ &= \frac{2}{\omega}\bigl(r^{p}\bigr)^{T} \mathcal{H}_{\gamma,\omega}^{T}\mathcal {M}_{\gamma,\omega}^{-1}r^{p}, \end{aligned}\\& \begin{aligned} \frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}&= \bigl(r^{p}\bigr)^{T}\biggl( \frac{\partial\mathcal{H}_{\gamma,\omega}}{\partial\gamma }\biggr)^{T}A^{-1}\mathcal{H}_{\gamma,\omega}r^{p}+ \bigl(r^{p}\bigr)^{T}\mathcal {H}_{\gamma,\omega}^{T}A^{-1} \frac{\partial\mathcal{H}_{\gamma,\omega }}{\partial\gamma}r^{p} \\ &= \frac{1}{\omega}\bigl(\bigl(r^{p}\bigr)^{T} \mathcal{M}_{\gamma,\omega }^{-T}A_{L}^{T} \mathcal{M}_{\gamma,\omega}^{-T}\mathcal{H}_{\gamma ,\omega}r^{p}+ \bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T} \mathcal {M}_{\gamma,\omega}^{-1}A_{L}\mathcal{M}_{\gamma,\omega}^{-1}r^{p} \bigr) \\ &= \frac{2}{\omega}\bigl(r^{p}\bigr)^{T} \mathcal{H}_{\gamma,\omega}^{T}\mathcal {M}_{\gamma,\omega}^{-1}A_{L} \mathcal{M}_{\gamma,\omega}^{-1}r^{p}, \end{aligned}\\& \begin{aligned} \frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}&= \bigl(r^{p}\bigr)^{T}\biggl(\frac {\partial\mathcal{H}_{\gamma,\omega}}{\partial\omega} \biggr)^{T}\mathcal {H}_{\gamma,\omega}r^{p}+ \bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T} \frac {\partial\mathcal{H}_{\gamma,\omega}}{\partial\omega}r^{p} \\ &= \frac{1}{\omega}\bigl(\bigl(r^{p}\bigr)^{T} \mathcal{M}_{\gamma,\omega }^{-T}A^{T}\mathcal{H}_{\gamma,\omega}r^{p}+ \bigl(r^{p}\bigr)^{T}\mathcal {H}_{\gamma,\omega}^{T}A \mathcal{M}_{\gamma,\omega}^{-1}r^{p}\bigr) \\ &= \frac{2}{\omega}\bigl(r^{p}\bigr)^{T} \mathcal{H}_{\gamma,\omega}^{T}A\mathcal {M}_{\gamma,\omega}^{-1}r^{p}, \end{aligned}\\& \begin{aligned} \frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}&= \bigl(r^{p}\bigr)^{T}\biggl(\frac {\partial\mathcal{H}_{\gamma,\omega}}{\partial\gamma} \biggr)^{T}\mathcal {H}_{\gamma,\omega}r^{p}+ \bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T} \frac {\partial\mathcal{H}_{\gamma,\omega}}{\partial\gamma}r^{p} \\ &= \frac{1}{\omega}\bigl(\bigl(r^{p}\bigr)^{T} \mathcal{M}_{\gamma,\omega }^{-T}A_{L}^{T} \mathcal{M}_{\gamma,\omega}^{-T}A^{T}\mathcal{H}_{\gamma ,\omega}r^{p}+ \bigl(r^{p}\bigr)^{T}\mathcal{H}_{\gamma,\omega}^{T}A \mathcal {M}_{\gamma,\omega}^{-1}A_{L}\mathcal{M}_{\gamma,\omega}^{-1}r^{p} \bigr) \\ &= \frac{2}{\omega}\bigl(r^{p}\bigr)^{T}\mathcal{H} _{\gamma,\omega}^{T}A\mathcal{M}_{\gamma,\omega}^{-1}A_{L} \mathcal {M}_{\gamma,\omega}^{-1}r^{p}. \end{aligned} \end{aligned}$$

The theorem is proved. □

The asymptotically optimal AOR (AOAOR) method for both cases of symmetric positive definite and general nonsymmetric linear systems can be established by Theorem 2.2.

3 The asymptotically optimal AOR method

In this section, we establish the asymptotically optimal AOR method by using the idea of [5‐7].

Since $(A_{D}-\gamma A_{L})^{-1}=(I-\gamma L)^{-1}A_{D}^{-1}$ with $L=A_{D}^{-1}A_{L}$ is a strictly lower triangular matrix, $L^{n}=O$ (the zero matrix), and $\rho(\gamma L)<1$, $(I-\gamma L)^{-1}$ can be written in the form of Taylor expansion ([9]). Then

$$ (I-\gamma L)^{-1}=\sum_{k=0}^{n-1}( \gamma L)^{k}. $$

(3.1)

Therefore, $\mathcal{M}_{\gamma,\omega}^{-1}$ can be expressed as

$$ \mathcal{M}_{\gamma,\omega}^{-1}=\omega(A_{D}-\gamma A_{L})^{-1}=\omega (I-\gamma L)^{-1}A_{D}^{-1}= \omega\sum_{k=0}^{n-1}(\gamma L)^{k}A_{D}^{-1}. $$

(3.2)

Evidently, $\mathcal{M}_{\gamma,\omega}^{-1}$ can be approximated by a lower-order truncation of the matrix series on the right-hand side of (3.2). In general,

$$ \mathcal{M}_{\gamma,\omega}^{-1}\approx\omega\bigl(I+\alpha\gamma L+ \beta ^{2} \gamma^{2} L^{2}\bigr)A_{D}^{-1} \equiv\mu(\gamma,\omega,\alpha,\beta), $$

(3.3)

where α and β are two real parameters.

In terms of (2.2) and (3.3), we have

$$ \mathcal{H}_{\gamma,\omega}=A\mathcal{M}_{\gamma,\omega}^{-1}-I=\omega A \bigl(I+\alpha\gamma L+\beta^{2} \gamma^{2} L^{2} \bigr)A_{D}^{-1}-I\equiv\nu (\gamma,\omega,\alpha,\beta). $$

(3.4)

Now, applying (3.2) and (3.3) to Theorem 2.2, we get the following results:

(a)

when A is a symmetric positive definite matrix,

$$\begin{aligned}& \frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2} \approx \frac{2}{\omega}\bigl(r^{p} \bigr)^{T}\nu(\gamma,\omega,\alpha,\beta )^{T}\mu(\gamma, \omega,\alpha,\beta)A_{L}\mu(\gamma,\omega,\alpha,\beta )r^{p} \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}} = 2\bigl(-\omega\bigl(r^{p}\bigr)^{T}LA_{D}^{-1}r^{p}-2 \omega\gamma\alpha \bigl(r^{p}\bigr)^{T}L^{2}A_{D}^{-1}r^{p}+ \omega ^{2}\bigl(r^{p}\bigr)^{T}A_{D}^{-1}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}}\quad{} +\omega^{2}\gamma\bigl(2\alpha \bigl(r^{p} \bigr)^{T}A_{D}^{-1}AL^{2}A_{D}^{-1}r^{p}+ \alpha \bigl(r^{p}\bigr)^{T}A_{D}^{-1}L^{T}ALA_{D}^{-1}r^{p} \bigr) \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}}\quad{} +\omega^{2}\gamma^{2}\bigl(2\alpha^{2}+\beta ^{2}\bigr) \bigl(r^{p}\bigr)^{T}A_{D}^{-1} \bigl(L^{T}\bigr)^{2}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}}\quad{} +2\omega^{2}\gamma^{3}\alpha\beta ^{2} \bigl(r^{p}\bigr)^{T}A_{D}^{-1} \bigl(L^{T}\bigr)^{2}AL^{2}A_{D}^{-1}r^{p} \bigr) \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}}=2\bigl(-\eta_{3}\omega-2\alpha\eta_{4}\omega\gamma+ \eta_{5}\omega ^{2}+(2\alpha\eta_{6}+\alpha \eta_{7})\omega^{2}\gamma \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}}\quad{} +\bigl(2\alpha^{2}+\beta^{2}\bigr)\eta_{8} \omega^{2}\gamma^{2}+2\alpha\beta ^{2} \eta_{9}\omega^{2}\gamma^{3}\bigr), \\& \frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2} \approx\frac{2}{\omega}\bigl(r^{p} \bigr)^{T}\nu(\gamma,\omega,\alpha,\beta )^{T}\mu(\gamma, \omega,\alpha,\beta)r^{p} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}} = 2\bigl(-\bigl(r^{p}\bigr)^{T}A_{D}^{-1}r^{p}+ \omega \bigl(r^{p}\bigr)^{T}A_{D}^{-1}AA_{D}^{-1}r^{p}- \gamma\alpha \bigl(r^{p}\bigr)^{T}LA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}} \quad{} -\gamma^{2}\beta^{2}\bigl(r^{p} \bigr)^{T}L^{2}A_{D}^{-1}r^{p}+2 \omega\gamma \alpha\bigl(r^{p}\bigr)^{T}A_{D}^{-1}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}} \quad{} +\omega\gamma^{2}\bigl(2\beta ^{2}\bigl(r^{p} \bigr)^{T}A_{D}^{-1}AL^{2}A_{D}^{-1}r^{p}+ \alpha ^{2}\bigl(r^{p}\bigr)^{T}A_{D}^{-1}L^{T}ALA_{D}^{-1}r^{p} \bigr) \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}} \quad{} +2\omega\gamma^{3}\alpha\beta ^{2}\bigl(r^{p} \bigr)^{T}A_{D}^{-1}\bigl(L^{T} \bigr)^{2}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}}\quad{} +\omega\gamma^{4}\beta ^{4}\bigl(r^{p} \bigr)^{T}A_{D}^{-1}\bigl(L^{T} \bigr)^{2}AL^{2}A_{D}^{-1}r^{p} \bigr) \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}} =2\bigl(-\eta_{1}+\eta_{2}\omega-\alpha \eta_{3}\gamma-\beta^{2} \eta _{4} \gamma^{2}+2\alpha\eta_{5}\omega\gamma+\bigl(2 \beta^{2}\eta_{6}+\alpha ^{2}\eta_{7} \bigr)\omega\gamma^{2} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert \varepsilon^{p+1}\bigr\Vert _{A}^{2}} \quad{} +2\alpha\beta^{2}\eta_{8}\omega\gamma^{3}+ \beta^{4}\eta_{9}\omega \gamma^{4}\bigr), \end{aligned}$$

where

$$\left \{ \textstyle\begin{array}{l} \eta_{1}=(r^{p})^{T}A_{D}^{-1}r^{p},\\ \eta_{2}=(r^{p})^{T}A_{D}^{-1}AA_{D}^{-1}r^{p},\\ \eta_{3}=(r^{p})^{T}LA_{D}^{-1}r^{p},\\ \eta_{4}=(r^{p})^{T}L^{2}A_{D}^{-1}r^{p},\\ \eta_{5}=(r^{p})^{T}A_{D}^{-1}ALA_{D}^{-1}r^{p},\\ \eta_{6}=(r^{p})^{T}A_{D}^{-1}AL^{2}A_{D}^{-1}r^{p},\\ \eta_{7}=(r^{p})^{T}A_{D}^{-1}L^{T}ALA_{D}^{-1}r^{p},\\ \eta_{8}=(r^{p})^{T}A_{D}^{-1}(L^{T})^{2}ALA_{D}^{-1}r^{p},\\ \eta_{9}=(r^{p})^{T}A_{D}^{-1}(L^{T})^{2}AL^{2}A_{D}^{-1}r^{p}; \end{array}\displaystyle \right . $$

(b)

when A is a general nonsymmetric matrix,

$$\begin{aligned}& \frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} \approx \frac {2}{\omega}\bigl(r^{p} \bigr)^{T}\nu(\gamma,\omega,\alpha,\beta)^{T}A\mu(\gamma , \omega,\alpha,\beta)A_{L}\mu(\gamma,\omega,\alpha,\beta)r^{p} \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} } = 2\bigl(-\omega\bigl(r^{p}\bigr)^{T}ALA_{D}^{-1}r^{p}-2 \omega\gamma\alpha \bigl(r^{p}\bigr)^{T}AL^{2}A_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} }\quad{} + \omega ^{2}\bigl(r^{p}\bigr)^{T}A_{D}^{-1}A^{T}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} }\quad{} +\omega^{2}\gamma\bigl(2\alpha \bigl(r^{p} \bigr)^{T}A_{D}^{-1}A^{T}AL^{2}A_{D}^{-1}r^{p}+ \alpha \bigl(r^{p}\bigr)^{T}A_{D}^{-1}L^{T}A^{T}ALA_{D}^{-1}r^{p} \bigr) \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} }\quad{} +\omega^{2}\gamma^{2}\bigl(2\alpha^{2}+\beta ^{2}\bigr) \bigl(r^{p}\bigr)^{T}A_{D}^{-1} \bigl(L^{T}\bigr)^{2}A^{T}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} }\quad{} +2\omega^{2}\gamma^{3}\alpha\beta ^{2} \bigl(r^{p}\bigr)^{T}A_{D}^{-1} \bigl(L^{T}\bigr)^{2}A^{T}AL^{2}A_{D}^{-1}r^{p} \bigr) \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} } = 2\bigl(-\xi_{3}\omega-2\alpha\xi_{4}\omega\gamma+ \xi_{5}\omega ^{2}+(2\alpha\xi_{6}+\alpha \xi_{7})\omega^{2}\gamma \\& \hphantom{\frac{\partial}{\partial\gamma}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} }\quad{} +\bigl(2\alpha^{2}+\beta^{2}\bigr)\xi_{8} \omega^{2}\gamma^{2}+2\alpha\beta ^{2} \xi_{9}\omega^{2}\gamma^{3}\bigr), \\& \frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2} \approx \frac {2}{\omega}\bigl(r^{p}\bigr)^{T}\nu(\gamma, \omega,\alpha,\beta)^{T}A\mu(\gamma ,\omega,\alpha,\beta)r^{p} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}} = 2\bigl(-\bigl(r^{p}\bigr)^{T}AA_{D}^{-1}r^{p}+ \omega \bigl(r^{p}\bigr)^{T}A_{D}^{-1}A^{T}AA_{D}^{-1}r^{p}- \gamma\alpha \bigl(r^{p}\bigr)^{T}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}}\quad{} -\gamma^{2}\beta^{2}\bigl(r^{p} \bigr)^{T}AL^{2}A_{D}^{-1}r^{p}+2 \omega\gamma \alpha\bigl(r^{p}\bigr)^{T}A_{D}^{-1}A^{T}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}}\quad{} +\omega\gamma^{2}\bigl(2\beta ^{2}\bigl(r^{p} \bigr)^{T}A_{D}^{-1}A^{T}AL^{2}A_{D}^{-1}r^{p}+ \alpha ^{2}\bigl(r^{p}\bigr)^{T}A_{D}^{-1}L^{T}A^{T}ALA_{D}^{-1}r^{p} \bigr) \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}}\quad{} +2\omega\gamma^{3}\alpha\beta ^{2}\bigl(r^{p} \bigr)^{T}A_{D}^{-1}\bigl(L^{T} \bigr)^{2}A^{T}ALA_{D}^{-1}r^{p} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}}\quad{} +\omega\gamma^{4}\beta ^{4}\bigl(r^{p} \bigr)^{T}A_{D}^{-1}\bigl(L^{T} \bigr)^{2}A^{T}AL^{2}A_{D}^{-1}r^{p} \bigr) \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}}= 2\bigl(-\xi_{1}+\xi_{2}\omega-\alpha\xi_{3} \gamma-\beta^{2} \xi_{4}\gamma ^{2}+\alpha \xi_{5}\omega\gamma+\bigl(2\beta^{2}\xi_{6}+ \alpha^{2}\xi _{7}\bigr)\omega\gamma^{2} \\& \hphantom{\frac{\partial}{\partial\omega}\bigl\Vert r^{p+1}\bigr\Vert _{2}^{2}}\quad{} +2\alpha\beta^{2}\xi_{8}\omega\gamma^{3}+ \beta^{4}\xi_{9}\omega \gamma^{4}\bigr), \end{aligned}$$

where

$$\left \{ \textstyle\begin{array}{l} \xi_{1}=(r^{p})^{T}AA_{D}^{-1}r^{p}, \\ \xi_{2}=(r^{p})^{T}A_{D}^{-1}A^{T}AA_{D}^{-1}r^{p}, \\ \xi_{3}=(r^{p})^{T}ALA_{D}^{-1}r^{p},\\ \xi_{4}=(r^{p})^{T}AL^{2}A_{D}^{-1}r^{p},\\ \xi_{5}=(r^{p})^{T}A_{D}^{-1}A^{T}ALA_{D}^{-1}r^{p},\\ \xi_{6}=(r^{p})^{T}A_{D}^{-1}(L^{T})^{2}A^{T}AA_{D}^{-1}r^{p},\\ \xi_{7}=(r^{p})^{T}A_{D}^{-1}L^{T}A^{T}ALA_{D}^{-1}r^{p},\\ \xi_{8}=(r^{p})^{T}A_{D}^{-1}(L^{T})^{2}A^{T}ALA_{D}^{-1}r^{p},\\ \xi_{9}=(r^{p})^{T}A_{D}^{-1}(L^{T})^{2}A^{T}AL^{2}A_{D}^{-1}r^{p}. \end{array}\displaystyle \right . $$

Our discussion can be summarized as the following theorems.

Theorem 3.1

Let A be a symmetric positive definite matrix. Then reasonable approximations $\gamma^{p}$, $\omega^{p}$ satisfying ${\arg\min} _{2>\omega\geq\gamma>0}\Vert \varepsilon^{p+1}\Vert _{A}$ are given by solving the nonlinear system

$$ \left \{ \textstyle\begin{array}{l} -\hat{\eta}_{3}\omega-2\alpha\hat{\eta}_{4}\omega\gamma+\hat{\eta }_{5}\omega^{2}+(2\alpha\hat{\eta}_{6}+\alpha\hat{\eta}_{7})\omega ^{2}\gamma+(2\alpha^{2}+\beta^{2}) \hat{\eta}_{8}\omega^{2}\gamma^{2} \\ \quad{} +2\alpha\beta^{2}\hat{\eta}_{9}\omega^{2}\gamma^{3}=0, \\ -\hat{\eta}_{1}+\hat{\eta}_{2}\omega-\alpha\hat{\eta}_{3}\gamma-\beta ^{2}\hat{\eta}_{4}\gamma^{2}+2\alpha\hat{\eta}_{5}\omega\gamma+(2\beta ^{2}\hat{\eta}_{6}+\alpha^{2} \hat{\eta}_{7})\omega\gamma^{2} \\ \quad{} +2\alpha\beta^{2}\hat{\eta}_{8}\omega\gamma^{3}+\beta^{4}\hat{\eta }_{9}\omega\gamma^{4}=0, \end{array}\displaystyle \right . $$

(3.5)

where

$$ \begin{aligned} &\rho_{1}=A_{D}^{-1}r^{p},\quad\quad \rho_{2}=L\rho_{1},\quad\quad \rho_{3}=A\rho_{1},\\ &\rho_{4}=A\rho_{2},\quad\quad \rho_{5}=L\rho_{2},\quad\quad \rho_{6}=A\rho_{5}. \end{aligned} $$

(3.6)

Hence,

$$ \left \{ \textstyle\begin{array}{l} \hat{\eta}_{1}=(r^{p})^{T}\rho_{1}, \quad\quad \hat{\eta}_{2}=\rho_{1}^{T}\rho _{3}, \quad\quad \hat{\eta}_{3}=(r^{p})^{T}\rho_{2},\\ \hat{\eta}_{4}=(r^{p})^{T}\rho_{5}, \quad\quad \hat{\eta}_{5}=\rho_{1}^{T}\rho_{4}, \quad\quad \hat{\eta}_{6}=\rho_{1}^{T}\rho_{6},\\ \hat{\eta}_{7}=\rho_{4}^{T}\rho_{4}, \quad\quad \hat{\eta}_{8}=\rho_{5}^{T}\rho_{4}, \quad\quad \hat{\eta}_{9}=\rho_{5}^{T}\rho_{6}. \end{array}\displaystyle \right . $$

(3.7)

Theorem 3.2

Let A be a general nonsymmetric matrix. Then reasonable approximations $\gamma^{p}$, $\omega^{p}$ satisfying ${\arg\min} _{2>\omega \geq\gamma>0}\Vert r^{p+1}\Vert _{2}$ are given by solving the nonlinear system

$$ \left \{ \textstyle\begin{array}{l} -\hat{\xi}_{3}\omega-2\alpha\hat{\xi}_{4}\omega\gamma+\hat{\xi }_{5}\omega^{2}+(2\alpha\hat{\xi}_{6}+\alpha\hat{\xi}_{7})\omega ^{2}\gamma+(2\alpha^{2}+\beta^{2})\hat{\xi}_{8}\omega^{2}\gamma^{2} \\ \quad{} +2\alpha\beta^{2}\hat{\xi}_{9}\omega^{2}\gamma^{3}=0,\\ -\hat{\xi}_{1}+\hat{\xi}_{2}\omega-\alpha\hat{\xi}_{3}\gamma-\beta ^{2}\hat{\xi}_{4}\gamma^{2}+2\alpha\hat{\xi}_{5}\omega\gamma+(2\beta ^{2}\hat{\xi}_{6}+\alpha^{2}\hat{\xi}_{7})\omega\gamma^{2} \\ \quad{} +2\alpha\beta^{2}\hat{\xi}_{8}\omega\gamma^{3}+\beta^{4}\hat{\xi }_{9}\omega\gamma^{4}=0, \end{array}\displaystyle \right . $$

(3.8)

where

$$ \begin{aligned} &\delta_{1}=A_{D}^{-1}r^{p}, \quad\quad \delta_{2}=A\delta_{1}, \quad\quad \delta_{3}=L\delta _{1}, \\ & \delta_{4}=A\delta_{3}, \quad\quad \delta_{5}=L\delta_{3}, \quad\quad \delta _{6}=A\delta_{5}. \end{aligned} $$

(3.9)

Hence,

$$ \left \{ \textstyle\begin{array}{l} \hat{\xi}_{1}=(r^{p})^{T}\delta_{2}, \quad\quad \hat{\xi}_{2}=\delta _{2}^{T}\delta_{2}, \quad\quad \hat{\xi}_{3}=(r^{p})^{T}\delta_{4},\\ \hat{\xi}_{4}=(r^{p})^{T}\delta_{6}, \quad\quad \hat{\xi}_{5}=\delta _{2}^{T}\delta_{4}, \quad\quad \hat{\xi}_{6}=\delta_{2}^{T}\delta_{6},\\ \hat{\xi}_{7}=\delta_{4}^{T}\delta_{4}, \quad\quad \hat{\xi}_{8}=\delta _{6}^{T}\delta_{4}, \quad\quad \hat{\xi}_{9}=\delta_{6}^{T}\delta_{6}. \end{array}\displaystyle \right . $$

(3.10)

By Theorems 3.1-3.2 the asymptotically optimal AOR (AOAOR) method can be constructed for the cases where A is a symmetric positive definite matrix or a general nonsymmetric matrix.

Method 3.1

(AOAOR method for a symmetric positive definite matrix)

S0.

Given an initial vector $x^{0}\in\mathcal{R}^{n}$, a precision $\varepsilon_{1}$, and two parameters α, β, for $p=0,1,2,\ldots $ :

S1.

Compute $r^{p}=b-Ax^{p}$.

S2.

Compute (3.6).

S3.

Compute (3.7).

S4.

Solve (3.5) by the Newton method (see [10]) for obtaining $\gamma ^{p}$, $\omega^{p}$.

S5.

Determine $\gamma^{p}$, $\omega^{p}$ that make the Hessian matrix positive definite.

S6.

Solve $(A_{D}-\gamma A_{L})y^{p}=r^{p}$ to get $y^{p}$.

S7.

Compute $x^{p+1}=x^{p}+\omega y^{p}$.

Method 3.2

(AOAOR method for a nonsymmetric matrix)

S0.

Given an initial vector $x^{0}\in\mathcal{R}^{n}$, a precision $\varepsilon_{2}$, and two parameters α, β, for $p=0,1,2,\ldots $ :

S1.

Compute $r^{p}=b-Ax^{p}$.

S2.

Compute (3.9).

S3.

Compute (3.10).

S4.

Solve (3.8) by the Newton method (see [10]) for obtaining $\gamma ^{p}$, $\omega^{p}$.

S5.

Determine $\gamma^{p}$, $\omega^{p}$ that make the Hessian matrix positive definite.

S6.

Solve $(A_{D}-\gamma A_{L})y^{p}=r^{p}$ to get $y^{p}$.

S7.

Compute $x^{p+1}=x^{p}+\omega y^{p}$.

Methods 3.1-3.2 both shared the same cost. Method 3.1 requires nine vectors x, y, r, $\rho_{i}$ ($i=1,2,\ldots,6$) stored, and each iteration requires seven matrix-vector products $(Ax,Lx)$, nine inner products (S3 of Method 3.1), three operations of the form ζx, three operations of the form $x+y$, and no operations of the form ζκ, where ζ and κ are scalars. Thus, if the number of nonzero entries on each row of the matrix A is m and that of the matrix L is $m_{l}$, then the details are listed in Table 1.

Table 1

Operation forms and flops at each step of the iteration

Oper. form	Number of iteration steps						Total flops
Oper. form	Step 1	Step 2	Step 3	Step 6	Step 7	Total	Total flops
Ax	1	3	0	0	0	4	4[(2m − 1)n]
Lx	0	2	0	1	0	3	$3[(2m_{l}-1)n-m_{l}(m_{l}-1)]$
(x,y)	0	0	9	0	0	9	9[(2n − 1)]
ζy	0	0	0	2	1	3	3[n]
x + y	1	0	0	1	1	3	3[n]
ζ⋅κ	0	0	0	0	0	0	0

4 Numerical experiments

The test example is the following two-dimensional partial differential equation with Dirichlet boundary condition ([5]):

$$ \left \{ \textstyle\begin{array}{l} -\frac{\partial^{2}u}{\partial t_{1}^{2}}-\frac{\partial ^{2}u}{\partial t_{2}^{2}}+\xi\frac{\partial u}{\partial t_{1}}+\zeta \frac{\partial u}{\partial t_{1}}+4\sigma u = f(t_{1},t_{2}), \quad (t_{1},t_{2})\in\Omega,\\ u(t_{1},t_{2}) = 0, \quad (t_{1},t_{2})\in\partial\Omega, \end{array}\displaystyle \right . $$

(4.1)

where ξ, ζ, and σ are all constants, Ω is the unit square $(0,1)\times(0,1)$ in $\mathcal{R}^{2}$, ∂Ω is the boundary of the domain Ω, and $f(t_{1},t_{2}): \Omega \rightarrow\mathcal{R}^{1}$ is a given function.

If $u_{i,j}$ and $f_{i,j}$ denote the approximate solution of (4.1) and an approximation of the function $f(t_{1},t_{2})$ at the grid point $(i h,j h)$, respectively, then a discretized approximation of (4.1) is the following linear system of equations:

$$ \mu_{1} u_{i+1,j}+\eta_{1} u_{i-1,j}+ \mu_{2} u_{i,j+1}+\eta_{2} u_{i,j-1}+ \mu_{0} u_{i,j}=h^{2}f_{i,j}, \quad i,j=1,2, \ldots,N, $$

(4.2)

where $(N+1)h=1$, and

$$ \left \{ \textstyle\begin{array}{l} \mu_{0}=4(1+\sigma h^{2}), \quad\quad \mu_{1}=-(1-\frac{1}{2}\xi h), \quad\quad \mu _{2}=-(1-\frac{1}{2}\zeta h),\\ \eta_{1}=-(1+\frac{1}{2}\xi h), \quad\quad \eta_{2}=-(1+\frac{1}{2}\zeta h). \end{array}\displaystyle \right . $$

Let

$$x^{T}=(u_{1,1},\ldots,u_{1,N},u_{2,1}, \ldots,u_{2,N},\ldots,u_{N,1},\ldots,u_{N,N}). $$

The linear system (4.2) can be written as the linear system (1.1) with

$$A=\left ( \textstyle\begin{array}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c} T & \mu_{2}I & & & \\ \eta_{2}I & T & \mu_{2}I & & \\ & \ddots & \ddots & \ddots & \\ & & \eta_{2}I & T & \mu_{2}I \\ & & & \eta_{2}I & T \end{array}\displaystyle \right )\in\mathcal{R}^{n\times n} $$

with

$$T=\left ( \textstyle\begin{array}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c} \mu_{0} & \mu_{1} & & & \\ \eta_{1} & \mu_{0} & \mu_{1} & & \\ & \ddots & \ddots & \ddots & \\ & & \eta_{1} & \mu_{0} & \mu_{1} \\ & & & \eta_{1} & \mu_{0} \end{array}\displaystyle \right )\in\mathcal{R}^{N\times N} $$

and

$$b^{T}=h^{2}(f_{1,1},\ldots,f_{1,N},f_{2,1}, \ldots,f_{2,N},\ldots ,f_{N,1},\ldots,f_{N,N}), $$

where $n=N\times N$.

In practical computations, the right-hand side b is generated by $b=Ae$, in which $e=(1,1,\ldots,1)^{T}\in\mathcal{R}^{n}$, the initial vector $x^{0}\in\mathcal{R}^{n}$ is taken to be zero, and all runs are terminated if the current iteration satisfies either the value of residual

$$ \mathrm{RES} \equiv\bigl\Vert r^{p}\bigr\Vert _{2}\leq \varepsilon\bigl\Vert r^{0}\bigr\Vert _{2} $$

(4.3)

or the number of iteration steps exceeds $20{,}000$. The iteration index p, namely, the number of iteration steps satisfying (4.3), is particularly denoted as “IT”, and the running time in seconds is denoted as “CPU”. In addition, all experiments are performed in MATLAB R2012a on PC with 3.4 GHz processor, 4 GB memory, and 32-bit operating system, “†” indicates that the number of iterations is greater than 20,000, that is, the iteration fails, “-” indicates that the computing is out of memory.

With different selections of ξ, ζ, σ, different forms of the coefficient matrix are given. Particularly, the coefficient matrix A is a symmetric matrix when $\xi=\zeta=\sigma=0.0$ or $\xi=\zeta =0.0$, $\sigma=2.5$, and it is a nonsymmetric matrix for $\xi=30.0$, $\zeta =0.0$, $\sigma=10.0$ or $\xi=0.0$, $\zeta=30.0$, $\sigma=10.0$. In Tables 2-5, we list the numbers of iteration steps, the 2-norms of the residual vectors, and the computing times for different choices of ξ, ζ, σ.

Table 2

Numerical results when $\pmb{\xi=\zeta=\sigma=0.0}$ ( $\pmb{\varepsilon=h^{2}/5}$ )

Methods		$\boldsymbol{h^{-1}}$
Methods		32	64	128	256	288	300
AOR	IT	41	89	-	-	-	-
	RES	1.9e−3	7.38e−4
	CPU	0.20	4.18
AOAOR	IT	216	895	3,816	16,200	†	†
	RES	2.1e−3	7.68e−4	2.76e−4	9.71e−5
	CPU	10.84	58.96	275.80	2,300.30

Table 3

Numerical results when $\pmb{\xi=\zeta=0}$ , $\pmb{\sigma=2.5}$ ( $\pmb{\varepsilon =h^{2}/5}$ )

Methods		$\boldsymbol{h^{-1}}$
Methods		32	64	128	256	288	300
AOR	IT	36	78	-	-	-	-
	RES	1.86e−3	7.0e−4
	CPU	0.18	4.08
AOAOR	IT	154	641	2,688	11,613	†	†
	RES	2.1e−3	7.8e−4	2.7e−4	9.75e−5
	CPU	7.74	40.31	189.08	1,560.23

Table 4

Numerical results when $\pmb{\xi=30.0}$ , $\pmb{\zeta=0.0}$ , $\pmb{\sigma=10.0}$ ( $\pmb{\varepsilon=h^{2}}$ )

Methods		$\boldsymbol{h^{-1}}$
Methods		32	64	128	256	288	300
AOR	IT	23	51	-	-	-	-
	RES	9.99e−3	3.42e−3
	CPU	0.18	3.64
AOAOR	IT	61	259	1,078	4,526	5,772	6,279
	RES	1.18e−2	3.9e−3	1.38e−3	4.8e−4	4.1e−3	3.86e−4
	CPU	2.54	13.21	52.06	288.58	379.42	434.97

Table 5

Numerical results when $\pmb{\xi=0.0}$ , $\pmb{\zeta=30.0}$ , $\pmb{\sigma=10.0}$ ( $\pmb{\varepsilon=h^{2}}$ )

Methods		$\boldsymbol{h^{-1}}$
Methods		32	64	128	256	288	300
AOR	IT	10	20	-	-	-	-
	RES	9.36e−3	2.6e−3
	CPU	0.28	5.70
AOAOR	IT	30	126	537	2,261	2,884	3,137
	RES	1.09e−2	3.8e−3	1.37e−3	4.8e−4	4.09e−4	3.86e−4
	CPU	3.80	31.29	132.69	400.02	560.39	1,092.20

From Tables 2-5 we can see that although the IT and CPU of the AOR method are less than those of the AOAOR method when $h^{-1}< 128$, the AOR method is out of memory, whereas the AOAOR method can continue to run for $h^{-1}\geq128$. Moreover, in the iteration process, $(A_{D}-\gamma A_{L})^{-1}$ of dimension $N^{2}$ requires to be solved for the AOR method. The AOAOR method, however, only needs to solve the inverse of N-dimensional T. Thus, the AOAOR method is better than the AOR method with respect to the increase of the size of the coefficient matrix.

The rates of convergence of the AOR and AOAOR methods are determined by the choice of the initial guesses ω and γ. If $\omega\in (0,2)$ and $\gamma\leq\omega$, then the AOR method is convergent. Therefore, we choose $\omega\in(0,2)$ and $\gamma\leq\omega$, where ω changes with step size of 0.1, and γ changes with step size of 0.01 in computation. It is well known that $\omega>1$ is a wise choice since it is the overrelaxation iteration. Hence, Tables 6-9 only list the ITs of the AOAOR and AOR methods for $\omega\in(1,2)$. We further choose two points $\omega=1.9$ and $\omega=1$ as examples to approach two extremal points and $\omega=1.4$ close to an intermediate point to explain that the IT of the AOR method changes greatly and that of the AOAOR method is almost unchanged for the larger intervals of the parameters ω and γ. In Tables 6-9, we have provided the gap of the iteration numbers with respect to different ξ, ζ, σ, and ε.

Table 6

The gap of IT when $\pmb{\xi=\zeta=\sigma=0.0}$ ( $\pmb{\varepsilon=h^{2}/5}$ )

Methods	ω	γ	$\boldsymbol{h^{-1}}$
Methods	ω	γ	32	64	128	256
AOR	1.9	[1.9: − 0.01:0]	[95,782]	[120,2,822]
	1.4	[1.4: − 0.01:0]	[121,1,699]	[513,8,265]
	1	[1: − 0.01:0]	[282,573]	[1,197,2,438]
AOAOR	1.9	[1.9: − 0.01:0]	216	[895,916]	[3,904,3,907]	16,200
	1.4	[1.4: − 0.01:0]	216	[896,903]	3,907	16,200
	1	[1: − 0.01:0]	216	[896,906]	[3,901,3,907]	16,200

From Tables 6-9 we note that:

(a)

When ω is a specific value, as for $\omega=1.9$ and $h^{-1}=32$, the IT of the AOR method is thrown into $[199,1{,}824]$, much more than the IT of the AOAOR method in Table 8. Thus, the AOAOR method is superior to the AOR method. In Table 7, the IT increased from 95 to 529 for the AOR method, but it is 154 for the AOAOR method. Although a lot of ITs of the AOR method are less than 154, the AOR method is more efficient only by choosing an appropriate γ. Consequently, for the same ω, the AOAOR method does not depend on γ;

Table 7

The gap of IT when $\pmb{\xi=\zeta=0.0}$ , $\pmb{\sigma=2.5}$ ( $\pmb{\varepsilon=h^{2}/5}$ )

Methods	ω	γ	$\boldsymbol{h^{-1}}$
Methods	ω	γ	32	64	128	256
AOR	1.9	[1.9: − 0.01:0]	[95,529]	[120,4,585]
	1.4	[1.4: − 0.01:0]	[87,7,872]	[365,1,305]
	1	[1: − 0.01:0]	[202,405]	[852,1,715]
AOAOR	1.9	[1.9: − 0.01:0]	154	641	[2,689,2,709]	11,613
	1.4	[1.4: − 0.01:0]	154	641	[2,693,2,701]	11,613
	1	[1: − 0.01:0]	154	641	[2,688,2,703]	11,613

(b)

When ω is variable and γ is a suitable fixed value, the minimal IT of the AOR method is 199 for $\omega=1.9$ and $h^{-1}=32$, and it is 50 for $\omega=1$ and $h^{-1}=32$ in Table 8. Therefore, the result for $\omega=1$ is better. But whether $\omega=1$ or $\omega=1.9$, the minimal IT ($\omega=1.4$, $\mathrm{IT} = 23$) is not reached. Thus, the IT of the AOR method can reach the minimum point only when ω is appropriate, whereas the ITs of the AOAOR method for $\omega =1.9$, $\omega=1.4$, and $\omega=1$ are fixed at 61. Hence, the AOAOR method is independent of the choice of ω.

Table 8

The gap of IT when $\pmb{\xi=30.0}$ , $\pmb{\zeta=0.0}$ , $\pmb{\sigma=10.0}$ ( $\pmb{\varepsilon=h^{2}}$ )

Methods	ω	γ	$\boldsymbol{h^{-1}}$
Methods	ω	γ	32	64	128	288	300
AOR	1.9	[1.9: − 0.01:0]	[199,1,824]	[215,526]
	1.4	[1.4: − 0.01:0]	[23,2,765]	[84,1,137]
	1	[1: − 0.01:0]	[50,96]	[196,387]
AOAOR	1.9	[1.9: − 0.01:0]	61	259	[1,078,1,081]	5,772	6,279
	1.4	[1.4: − 0.01:0]	61	259	[1,079,1,081]	5,772	6,279
	1	[1: − 0.01:0]	61	259	[1,079,1,081]	5,772	6,279

Table 9

The gap of IT when $\pmb{\xi=0.0}$ , $\pmb{\zeta=30.0}$ , $\pmb{\sigma=10.0}$ ( $\pmb{\varepsilon=h^{2}}$ )

Methods	ω	γ	$\boldsymbol{h^{-1}}$
Methods	ω	γ	32	64	128	288	300
AOR	1.9	[1.9: − 0.01:0]	[68,1,860]	[82,534]
	1.4	[1.4: − 0.01:0]	[10,1,039]	[48,3,191]
	1	[1: − 0.01:0]	[31,92]	[160,388]
AOAOR	1.9	[1.9: − 0.01:0]	30	126	537	2,884	[3,137,3,139]
	1.4	[1.4: − 0.01:0]	30	126	537	2,884	3,137
	1	[1: − 0.01:0]	30	126	537	2,884	3,137

Consequently, we obtain the obvious conclusion that the IT of the AOR method is sensitive to the guesses of ω and γ. Furthermore, Figures 1-3 according to Tables 6-9 are given to distinctly illustrate the sensitivity of the AOR and AOAOR methods.

Figure 1 clearly depicts the variation with respect to ω. We notice that the graph of the AOR method is vertically descending, whereas that of the AOAOR method is completely flat, which shows that the IT of the AOAOR method is independent of the choice of γ. So does Figure 2.

When ω is not an exact value, the numbers of IT of the AOR method are dramatically different for invariable γ, that is, it depends on the choice of ω. However, the IT of the AOAOR method remains at 61. Therefore, the conclusion that the IT of the AOAOR method is independent of the choice of ω is illustrated in Figure 3.

Thus, from Figures 1-3 we see that both AOR and AOAOR methods are sensitive to the parameters ω and γ. For the larger intervals of the parameters ω and γ, the IT of the AOR method varies according to the curve wave; however, that of the AOAOR method is almost at the same level. This means that the AOR method is more sensitive to the initial guesses of the optimal parameters ω and γ, whereas the AOAOR method is more stable.

5 Conclusions

The asymptotically optimal accelerated overrelaxation (AOAOR) method for linear systems (1.1) has been presented. Especially, the optimal parameters are discussed. The numerical experiments have shown that the AOAOR method is efficient when the dimension of the coefficient matrix is over 2¹². Furthermore, the AOAOR method is more stable with respect the initial guesses of relaxation factors ω and γ.

Acknowledgements

The authors are very much indebted to the anonymous referees for their helpful comments and suggestions, which greatly improved the original manuscript of this paper. This work is supported by grants from the NSF of Shanxi Province (201601D011004).

Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Competing interests

The authors declare that they have no competing interests.

Authors’ contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Vorheriger Artikel The ratio log-concavity of the Cohen numbers

Nächster Artikel Convergence of a space-time continuous Galerkin method for the wave equation

Springer Professional

Abstract

Competing interests

Authors’ contributions

1 Introduction

2 AOR method and its properties

3 The asymptotically optimal AOR method

4 Numerical experiments

5 Conclusions

Acknowledgements

Competing interests

Authors’ contributions

Weitere Artikel der Ausgabe 1/2016

Weak convergence of a Mann-like algorithm for nonexpansive and accretive operators

Topics on the spectral properties of degenerate non-self-adjoint differential operators

On the stability of finding approximate fixed points by simplicial methods

Two new lower bounds for the minimum eigenvalue of M-tensors

Weak contractive integral inequalities and fixed points in modular metric spaces

Perturbation bounds for eigenvalues of diagonalizable matrices and singular values