1. Introduction
We consider the problem of finding a solution
to the nonsymmetric linear systems [1] [2]
(1)
where
is a real separable Hilbert space with inner product
and norm
and
is a bounded linear operator. We further assume that A is invertible on its range
, that is, for any
, the Equation (1) has a unique solution
.
The generalized minimal residual (GMRES) method, proposed by Saad and Schultz [3] , is one of the most popular iterative methods for solving large linear systems of equations with a square nonsymmetric matrix. It is an extension of the minimal residual method (MINRES) for symmetric systems. In the past four decades, numerous variants of GMRES appeared. In 1988, Walker [4] proposed the Householder GMRES, which uses an algorithm that uses the House-holder reflections to orthogonalize the basis vectors and thus has better numerical stability. Saad [5] in 1993 proposed to accelerate the GMRES by using the variable preconditioner at each iteration step. Morgan [6] established the GMRES with deflated restarting by deflating the eigenvalues of small magnitude, which maybe hampers the convergence of GMRES.
For a nonzero vector
, the Krylov subspace
is defined by
Let the initial guess
. At the m-th step, the GMRES method obtains an approximation
, where
solves the linear least-squares problem
In the implementations of GMRES, the Arnoldi process [7] is used to establish an orthonormal basis of the Krylov subspace
. The Arnoldi process based on the modified Gram-Schmidt procedure is described as follows.
Algorithm 1 Arnoldi process
1) Let
.
2) For
3)
.
4) For
5)
.
6)
.
7) End For
8)
.
9)
.
10) End For
Obviously, if
then
and the Arnoldi process breaks down after the basis
of
has been determined.
Calvetti, Lewis, and Reichel have showed that the GMRES method has the following important property ( [8] , Lemma 2.3).
Theorem 1. Let the linear operator
be invertible on
. Assume that
. Then the iterate
generated by the GMRES method applied to the Equation (1) with the initial approximate solution
satisfies
Conversely, assume that
with
. Then the Arnoldi process breaks down after the orthonormal basis
of
has been determined.
The range-restricted GMRES (RRGMRES) method [9] [10] [11] [12] is also an important iterative method for solving general nonsymmetric linear systems. This method uses the Krylov subspace
and has several advantages over the GMRES method especially for linear ill-posed problems. Since
, the RRGMRES method restricts the computational solution to
.
However, the following example shows that the second half of Theorem 1 does not hold for the RRGMRES method.
Example. Let
The matrix A is invertible, and thus the equation
has a unique solution. The solution is
We have
Clearly,
. However, since
, the Arnoldi process does not break down after the orthonormal basis
of
has been generated.
2. Main Results
In this section we shall show that a result slightly different from Theorem 1 holds for the RRGMRES method. For deducing the result, we require the following lemma. Although its proof is similar to that of ( [8] , Lemma 2.2), we include the proof for completeness.
Lemma 2. Assume that the linear operator
is invertible on its range
. Then
Proof. It is obvious that
. Now we assume that
. Then, there is a
,
such that
. Since A is invertible on its range
, it follows that
if and only if
. This contradiction shows that
.
We are in a position to present the main result of this note.
Theorem 3. Let the linear operator
be invertible on
. Assume that
. Then the iteration
generated by the RRGMRES method applied to the Equation (1) with the initial approximate solution
satisfies
Conversely, we assume that
with
and
. Then the Arnoldi process breaks down after the orthonormal basis
of
or the orthonormal basis
of
has been generated.
Proof. It is clear that
. Under the assumption that
, we have
It follows from Lemma 2 that
, which together with
shows that
. Thus, we have
and
. It shows that there is a
such that
, i.e.,
. Since A is invertible on
, it follows that
. Note that
. Thus, there exists an
such that
.
Conversely, we assume that there exists an
such that
. If
, the result holds naturally, i.e., the Arnoldi process breaks down after the orthonormal basis
of
has been generated. Thus, we only need to consider the case
. Since
, it follows that
. Then,
, which shows that
and
. Moreover, by Lemma 2, we obtain
Therefore,
and
, which proves that the Arnoldi process breaks down after the orthonormal basis
of
has been generated.
We note that the first half of Theorem 3 has been given out in ( [13] , Theorem 2.3) as A is a nonsingular matrix. However, the second half of Theorem 3 is a new result, which shows a main difference between GMRES and RRGMRES.
The example from the previous section can verify the second part of Theorem 3. In this example,
and
. Thus, the Arnoldi process in RRGMRES don’t break down until the orthonormal basis of
has been generated.
We can validate the other case of the second part of Theorem 3 by setting the coefficient matrix A as the identity matrix. In this case,
,
. Thus, the Arnoldi process in RRGMRES breaks down after the orthonormal basis of
has been generated.
In linear discrete ill-posed problems, the right-hand side vector of the nonsymmetric linear systems (1) is usually contaminated by an error. We denote the perturbed linear system by
(2)
where
is an error vector, and
with
. If
or its fairly accurate estimate is known, the discrepancy principle is used to estimate a regularization parameter. When the GMRES method is applied to solve the perturbed linear system (2), the iterations will be terminated as soon as
(3)
where
is the
-th iterate, and
is an appropriate positive number.
The following theorem [8] shows that the usual GMRES method is a regularization method for solving linear ill-posed problems.
Theorem 4. Let
satisfy
with
being an appropriate positive number, and let
. Choose the initial solution to be
. Let
be determined by the usual GMRES method with the discrepancy principle (3). Then
where x is the solution of (1).
We point out that Theorem 1 is an essential result for proving Theorem 4, see [8] .
Extensive numerical experiments have shown that the RRGMRES method may yield better approximate solutions than the usual GMRES method, see, for example, [9] [11] [14] [15] [16] . However, as far as we know, analysis of the regularization property of the RRGMRES method has not been done theoretically. We find out that by making use of Theorem 3 and following almost the same arguments in [8] , it can be shown that when the associated error-free right-hand side lies in a finite-dimensional Krylov subspace, the RRGMRES method is also a regularization method for solving linear ill-posed problems. So, we present the result in the following theorem and omit its proof.
Theorem 5 Let
satisfy
with
being an appropriate positive number, and let
. Choose the initial solution to be
. Let
be determined by the RRGMRES method with the discrepancy principle (3). Then
where x is the solution of (1).
3. Conclusion
The RRGMRES method uses the range-restricted Krylov subspace, and has some advantages over the usual GMRES method for linear ill-posed problems. In this paper, we have shown that the result about the break-down of the Arnoldi process in the RRGMRES may be different from the one in the usual GMRES. The result can be used to show that the RRGMRES is a regularization iterative method.
Acknowledgements
This research was funded by the Natural Science Foundation of Hunan Province under grant 2017JJ2102.