ABSTRACT

In different fields in space researches, Scientists are in need to deal with the product of matrices. In this paper, we develop conditions under which a product of matrices chosen from a possibly infinite set of matrices converges. There exists a vector norm such that all matrices in M are no expansive with respect to this norm and also a subsequence of the sequence of nonnegative integers such that the corresponding sequence of operators converges to an operator which is paracontracting with respect to this norm. The continuity of the limit of the product of matrices as a function of the sequences is deduced. The results are applied to the convergence of inner-outer iteration schemes for solving singular consistent linear systems of equations, where the outer splitting is regular and the inner splitting is weak regular.

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 z_o. 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 i_k 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 z_o. 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 Cⁿ 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

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

and

a situation which we shall write as

.

Recall further that according to [9] the powers of a matrix converges if and only if

and

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,

E is called paracontracting with respect to if for all

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

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

and

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:

where as, in the introduction, and

If there are splitting and such that for infinitely many is and simultaneously, then for any,

Now, suppose is a range monotone and that and are regular and weak regular splitting for A and T respectively, then and

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

so that, and hence

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

Now we know that. Thus if either or, then it follows that so that inductively,

Let. Then from the relation

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

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.

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

from which it follows that x is a positive vector for which

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.

REFERENCES