1. Introduction
Let the standard iterative method for solving the system of linear equations
(1)
where
and x, b are n-vectors [1], be induced by the splitting of A into
, where T is a nonsingular matrix. Starting with an arbitrary vector
, the recurrence relation
(2)
is used to compute a sequence of iterations whose limit should be the solution to equation (1).
If A is a nonsingular matrix, to obtain a good approximation to the solution of Equation (1), one need not to even solve the system (2) exactly for each
. For each
, we solve the system (2) by iterations. Then split the matrix T into
(3)
where the matrix G is invertible. Then, starting with
inner iterations
(4)
are computed after which one resets
. The entire inner-outer iteration process can then be expressed as follows [2-4]
(5)
where
(6)
If the spectral radius of both
and
are smaller than 1 so that the powers of both iteration matrices converge to zero, then for sufficiently large positive integer t we have that if
[5], the sequence
produced by the inner-outer iterations converges to the solution of equation (1) from all initial vectors zo. If A and T have a nonnegative inverse and both iteration matrices
and
are nonnegative matrices, with the former induced by a regular splitting of A and the latter induced by a weak regular splitting of T, then the sequence
converges to the solution of Equation (1) whenever
with no restrictions on t [4]. The process of inner-outer iterations can be represented by means of an iteration matrix at every stage, the spectral radius of such a matrix can no longer be less than 1. Furthermore, even if the spectral radius of the iteration matrix at each stage is 1, this does not ensure the convergence of the inner-outer iteration process even if a fixed number of iterations are used between every two outer iterations [6]. If the number of inner iterations, between every two outer iterations, is allowed to vary, the problem is further compounded [7,8]. Here we shall examine some connections between the work here and problems of convergence of infinite products of matrices such as considered by [6].
If one is going to employ the inner-outer iteration scheme, then it is very reasonable that often between any two outer iterations only a relatively small number of inner iterations will be computed and only in rare cases much more inner iteration will be allowed. This effectively means that there is a number
, such that infinitely often at most n inner iterations will be carried out between any two outer ones. This implies that there exists an index
such that for an infinite subsequence ik of the positive integers,
, infinitely often,
. We shall prove that under certain convergence properties of
such as
is paracontracting with respect to a vector norm in respect of which all the
are no expansive, the inner-outer iteration (5) for any initial vector zo. This implies that the inner-outer iteration scheme is convergent when the system (1) is consistent.
Now let we have an infinite set of matrices
, and there exists a vector norm
on Cn such that each matrix in M is no expansive with respect to
. From M select an infinite sequence of matrices
. Then if
contains a subsequence
which converges to a matrix H which is paracontracting with respect to
and such that the null space
is contained in the intersection of the null spaces
, then
. Finally, let D be the set of all sequences
of integers such that each sequence
contains an integer
such that
for infinitely many
. Then, according to Th. 3.1 if corresponding to the sequence
, the matrix
is paracontracting, then
![](https://www.scirp.org/html/10-5300279\7562f456-69f6-44ca-8056-dc2a43d90673.jpg)
We shall show that the function
is continuous.
2. Preliminaries
Let
. We shall denote both of the null space and the range of E by
and
respectively. Recall that the Jordan blocks of E corresponding to 0 are 1 × 1 if and only if
![](https://www.scirp.org/html/10-5300279\26fc2aec-8eec-4ddd-9c95-e4fb11ea446c.jpg)
and
a situation which we shall write as
.
Recall further that according to [9] the powers of a matrix
converges if and only if
![](https://www.scirp.org/html/10-5300279\c87c7a83-7cc6-434d-b6ed-42ac4a43797b.jpg)
and
![](https://www.scirp.org/html/10-5300279\5332e04d-6e10-4a60-af04-c24065f180ca.jpg)
where
denotes the spectrum of a matrix.
For a vector
we shall write that
if all the entries of x are positive numbers. Also, let
enote a vector norm in. An n × n matrix E is no expansive with respect to
if for all
,
![](https://www.scirp.org/html/10-5300279\22168b39-7d1f-492f-8a32-c254c3fbc55b.jpg)
E is called paracontracting with respect to
if for all ![](https://www.scirp.org/html/10-5300279\af81f975-bb84-4ddf-b96a-50aeeaee74c0.jpg)
![](https://www.scirp.org/html/10-5300279\a343aaae-fb48-4e81-b06e-5a0f246e332b.jpg)
We denote by
the set of all matrices in
which are paracontracting with respect to
. Two examples of paracontracting matrices are as follows. For the Euclidian norm it is known that any Hermitian matrix whose eigenvalues lie in (−1, 1] is paracontracting. Suppose now that E is an n × n positive matrix whose spectral radius is 1 and with a Perron vector
. We claim that such a matrix is paracontracting with respect to
, the monotonic vector norm induced by x. Let
be any vector satisfying
or, equivalently, not being a multiple of x. We know that
![](https://www.scirp.org/html/10-5300279\d87d96da-ce37-4e7f-95d6-e652794985d5.jpg)
By the positively of E and because
, it follows that for any
such that
, so that
.
The concept of paracontraction was introduced by [4] who showed that the product of any number of matrices in
is again an element of
. Moreover, they used a result of [3] to show that the powers of any matrix
converge. Thus, in particular such matrix has the property that
.
Finally, recall that a splitting of A into A = T – Q is called regular if T is nonsingular,
and
. Regular splitting where introduced by [10], who showed that for a regular splitting,
if and only if A is nonsingular and
. A splitting A = T – Q is called weak regular if T is nonsingular,
and
. This concept was introduced by [11] who showed that, even allowing for this weakening of the assumption on regular splitting,
if and only if A is nonsingular and
. If A = T – Q is a regular splitting of A, then
![](https://www.scirp.org/html/10-5300279\167d25a2-ce58-4789-9af2-159be6e85c42.jpg)
and
![](https://www.scirp.org/html/10-5300279\37ec7c4e-faae-4869-99ef-bed5ce0d05d8.jpg)
if and only if A is range monotone [12], that is,
.
Moreover, they showed that if there exists a vector
such that
, then
and
, and such a positive vector always exists if A is a singular and irreducible M-matrix.
3. Applications to Singular Systems
As we mentioned before, if
is a regular splitting for
and
is range monotone, then
and
.
Now, let
is a weak regular splitting for
and consider the inner-outer iteration process
(7)
where
(8)
We observe at once that since
is a regular splitting for
and
is a weak regular splitting for
, any of the inner-outer iteration operators
, is a nonnegative matrix. Already Nichols in [3] essentially showed the following relation holds:
(9)
Suppose that the n x n coefficient matrix A (assumed to be nonsingular) in the system (1) is monotone. For each
, let
be a regular splitting of
and
be a weak regular splitting. Consider the inner-outer iteration process:
![](https://www.scirp.org/html/10-5300279\1030143f-ea88-4276-b2a7-67dbc8f2f0ad.jpg)
where as, in the introduction,
and
![](https://www.scirp.org/html/10-5300279\795bf688-6a56-41ac-8233-eca32a87b52e.jpg)
If there are splitting
and
such that for infinitely many is
and
simultaneously, then for any
,
![](https://www.scirp.org/html/10-5300279\3191026b-49d0-4762-9eda-0df974b0f0b6.jpg)
Now, suppose
is a range monotone and that
and
are regular and weak regular splitting for A and T respectively, then
and
![](https://www.scirp.org/html/10-5300279\7158b820-b0b8-4ad6-a5fe-8c7983e918bf.jpg)
for all
[2,10,13].
Once again, suppose that
and
are regular and weak regular splitting for A and T respectively. Note that the range monotone of A was used only to deduce that
is an M-matrix of index at most 1. Another condition which ensures that
is an M-matrix of index at most 1 is that there exists a positive vector x such that
for then
. Furthermore, such a vector exists when A is a singular and irreducible M-matrix. When A is such an M-matrix, then, in fact, there exists a positive vector x such that
. But then also
![](https://www.scirp.org/html/10-5300279\cd202f91-5f32-4c94-9816-3b35f325bd79.jpg)
so that
, and hence
![](https://www.scirp.org/html/10-5300279\27ab6ed0-fb7e-4962-9de2-19f61924573b.jpg)
We can thus conclude that when A is an irreducible M-matrix, not only the conclusions of the above result hold, but
so that
. Hence for each
is no expansive with respect to the norm
. We also see that
![](https://www.scirp.org/html/10-5300279\a3d2dd1b-c705-4b44-b966-6ff602b4fd01.jpg)
Now we know that
. Thus if either
or
, then it follows that
so that inductively,
![](https://www.scirp.org/html/10-5300279\2428c021-99a2-4bd6-b05e-fca676365b5b.jpg)
Let
. Then from the relation
![](https://www.scirp.org/html/10-5300279\dce2aa03-7407-45fc-83cd-8b498139539a.jpg)
we see that, not only
, (10)
a fact that already follows from
, but that the rate of convergence behaves as
.
Theorem: Let
be a set of matrices in
, let
be a sequence of matrices chosen from M, and consider the iteration scheme
![](https://www.scirp.org/html/10-5300279\30fa5e94-0c79-49c5-95ad-2b5d854b0d1f.jpg)
Suppose that all
are no expansive with respect to the same vector norm
and there exists a subsequence
of the sequence
such that
where V is a matrix with the following properties:
• V is paracontracting with respect to
.
![](https://www.scirp.org/html/10-5300279\0156760e-2c74-47fc-a1f8-3b9e0a66bd39.jpg)
Then for any
the sequence
is convergent and
.
The proof is given in [2].
From the above analysis and previous theorem we can now state the following result concerning the convergence of the inner-outer iteration process:
Theorem: Let
and suppose that
and
are a regular splitting and a weak regular splitting for A and T, respectively, and consider the inner-outer iteration process (7) for solving the consistent linear system Ax = b. Suppose there exists a vector
such that
and one of the following conditions is satisfied:
1) For some integer j,
is paracontracting and for infinitely many integers k,
.
2)
is paracontracting with respect to
, the sequence
is unbounded, and either
or
.
The sequence of iterations
generated by the scheme given in (7) converges to a solution of the system Ax = b.
Proof. We have the identity that
![](https://www.scirp.org/html/10-5300279\75519d8f-1b31-4b29-baf9-768cc0ae3c1a.jpg)
from which it follows that x is a positive vector for which
![](https://www.scirp.org/html/10-5300279\9577f2a7-70ef-4791-b32c-2c95b0d92618.jpg)
showing that for each
is no expansive with respect to the monotonic vector norm induced by x. Also the proof of (2) is clear because the unboundness of the sequence
together with the existence of the limit in Equation (10) now means that the sequence of matrices
contains an infinite subsequence of matrices which converges to the paracontracting matrix V.
4. Conclusion
The conditions under which the product
of matrices converges are explained and we apply the results for the convergence of inner-outer iteration schemes for solving singular consistent linear system of equations.