main-content

## Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.12.2016 | Research | Ausgabe 1/2016 Open Access

# A selected method for the optimal parameters of the AOR iteration

Zeitschrift:
Journal of Inequalities and Applications > Ausgabe 1/2016
Autoren:
Luna Ren, Fujiao Ren, Ruiping Wen
Wichtige Hinweise

## 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 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 [ 14, 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 [ 57].
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
Step 1
Step 2
Step 3
Step 6
Step 7
Total
Ax
1
3
0
0
0
4
4[(2 m − 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[(2 n − 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}}$$

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}}$$

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}}$$

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}}$$

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}}$$
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}}$$
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}}$$
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}}$$
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 12. 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).

## 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.
Literatur
Über diesen Artikel

Zur Ausgabe