Pure and Applied Mathematics Journal
Volume 5, Issue 4, August 2016, Pages: 103-107

The 3-Block KSOR Method for Full Rank Rectangular Systems

I. K. Youssef, Salwa M. Ali, M. A. Naser

Math Department, Faculty of Science, Ain Shams University, Cairo, Abbassia, Egypt

Email address:

(I. K. Youssef)
(M. A. Naser)

To cite this article:

I. K. Youssef, Salwa M. Ali, M. A. Naser. The 3-Block KSOR Method for Full Rank Rectangular Systems. Pure and Applied Mathematics Journal. Vol. 5, No. 4, 2016, pp. 103-107. doi: 10.11648/j.pamj.20160504.13

Received: May 24, 2016; Accepted: June 2, 2016; Published: June 21, 2016


Abstract: A new version of the KSOR method is considered to introduce the least squares solution of a full rank over determinant system of linear algebraic equations. The treatment depends on introducing an augmented non-singular square system through splitting the coefficient matrix A into two matrices A1, A2 with non-singular part, A1. Accordingly, a new version of the 3-block SOR method is introduced, the 3-block KSOR method. Selection of the relaxation parameter which guarantees the convergence in the sense of reducing the spectral radius of the iteration matrix is considered. Application of the theoretical results to a numerical example has confirmed the expected behaviour of the 3-block KSOR method.

Keywords: SOR, KSOR, 3 Block SOR Method, Rectangular Systems


1. Introduction

Large linear systems of algebraic equations has appeared in many applications of science and engineering problems. The selection of the method of solution depends on the structure of the linear algebraic system under consideration. Iterative techniques especially the successive over-relaxation (SOR) method is highly recommended in the treatment of large sparse systems. The efficient use of the SOR methods depends on the selection of the relaxation parameters. The theory of SOR method for square nonsingular systems is well established, [1]. In 2012, Youssef introduced the KSOR method as a new version of the SOR method, [2] and in 2013 Youssef and Taha introduced the MKSOR versions of the MSOR method, [3]. We adapt the KSOR to treat full rank rectangular system.

Consider the linear system

(1)

Or

(2)

where  is nonsingular matrix and has no zero diagonal elements. The following splitting of the coefficient matrix  is used in iterative treatments,

(3)

where  is the diagonal part,  is the strictly lower triangular part and  is the strictly upper triangular part of the matrix .

The main idea in the KSOR is the assumption of using the current component in the evaluation process in addition to the use of most recent calculated components used in the SOR methods.

Let  the sth approximation of solution of (2) then the KSOR, [2, 3] method is given by

Or

(4)

 is the Gauss –Seidel solution.

The matrix formulation of KSOR method is

(5)

where,  is the iteration matrix

(6)

The main objective in this work is the treatment of the full rank rectangular system, [4,5,6].

(7)

where . such systems are known as over-determinant systems. In general, Over-determinant systems do not admit classical unique solutions, [7, 8]. The general treatment for such systems is to seek for solutions in a pre-described sense. For example one can write, [5, 7]

(8)

Where,  is the well-known Moore Penrose generalized inverse.

There is many interesting trials to reformulate the iterative techniques to be suitable for such systems, [9, 10].

The least squares technique is also one of the interesting approaches. The least squares solution of the system (7) is a vector  such that

(9)

It is well known that for full rank systems the least squares solution coincident with the generalized inverse solution, and the least squares solution is unique. An equivalent formulation of the least squares problem (9) can be written in the form, [11,12,13]:

Find  and  such that

(10)

where .

One can use the nonsingular part of the matrix  to write the system (10) in the following partitioned block form

(11)

(12)

where, , ,  also  and  are partitioned conformably with .

(13)

2. The Three Block Coefficient Matrix

The block formulation of the system (11-13) is

(14)

This formulation can be treated with different attitudes. We focus on the three block formulation. The system in (14) is known as the augmented system, it can be rearranged in the form

(15)

Or, in full as

(16)

Where,

(17)

The coefficient matrix  is square non-singular matrix. Accordingly the system (16) possesses a unique solution and suitable for the use of iterative techniques. Solving  system (16) gives the least squares solution  of the original system as understood from the following theorem

Theorem 1, [4, 6]: a vector  is a least squares solution for (7) if and only if the residual vector  satisfies the orthogonality condition, .

3. The Three Block KSOR Method

The three block SOR method was introduced by Chen in 1975, [5]. Plemmons [11], Niethammer, de Pillis and Varga [6], later developed this method and specify SOR convergence properties. The 3-block KSOR iterative method can be introduced in the same approach illustrated in (5) and (6) as follows:

Consider the three block matrix  given in (17) and consider the splitting

(18)

where

The three block KSOR method for system (7) can be defined as

(19)

(20)

Where

(21)

is the iteration matrix of three block the KSOR method.

(22)

The theoretical characterization of the KSOR methods is strongly dependent on the corresponding Jacobi method. The three block Jacobi iteration matrix is given by

(23)

(24)

As in the three block SOR method the spectrum of  is very important in the convergence of the 3-block KSOR method.

Theorem 2: The eigenvalues of  lie in the real interval  where

Proof: suppose that  is an eigenvalue of  then  is an eigenvalue of

From  as defined in (24) one can easily see that

(25)

Where

So that  is similar to a block diagonal matrix with blocks , which is real symmetric negative semidefinite matrix. Therefore

So the eigenvalues of  lie in the real interval .

It is clear from this theorem that

Algorithm for three block KSOR method

Set.

Compute  and.

Compute the iterative parameter.

Iterate for  until convergence.

Theorem 3: consider the three block KSOR method of (19) for system of (7) and consider the parameter . Then the three block KSOR method converges for parameter  in some interval if and only if

in particular, if

then (19) converges for all  in the interval

(26)

and if Then (19) converges for all  in the interval

(27)

and if , then (19) converges for all  in the interval

(28)

and if , then (19) converges for all  in the interval

(29)

and it is diverging for other values of .

When , the optimum relaxation parameter is given by

the proof is similar to the proof which is introduced by Niethammer, de Pills and Varga [6].

4. Numerical Calculation

In order to illustrate the theoretical discussions, we introduce the following full rank over-determinant system

with . The unique least squares solution of this system is the vector

Define the splitting of  as

and the splitting of  as

The augmented linear system of order  is

It is clear that the coefficient matrix is nonsingular, and the augmented system has a unique solution and .

The 3-block SOR method converges for all  in the interval  and  can be calculated to be,, 0.

Figure 1 illustrates the behavior of the spectral radius of the iteration matrix of the SOR method.

Figure 1. The behavior of the spectral radius of 3-block SOR.

The 3-block KSOR method is convergent for all  in the interval

by computing the  by theorem 3, we get

Equivalently, it can be approximated from Figure 2, which shows the behavior of the spectral radius of the iteration matrix of the 3 block KSOR method.

Figure 2. The behavior of the spectral radius of 3-block KSOR.

The table summarizes the results

Table 1. Comparison between 3-blok SOR and KSOR.

Method Number of iterations
3-block SOR 0.7520 0.4950 19
3-block KSOR 3.0350 0.4950 19

5. Conclusion

Square augmented systems obtained from full rank over determinant systems possesses unique solution, which can be obtained efficiently with iterative methods.

The structure of the three block system possesses a very nice property (large number of zeros) which illustrates the efficient use of iterative techniques. It is clear from the system (16) that for the first n equations each equation has at most (n+1) non-zero (at least (m-1) zeros), also this is the same for the next (m-n) equations and the last n equations each equation has at most m non-zeros.

The three block KSOR has the same interesting properties as the three block SOR.

The optimum values of the relaxation parameter can be calculated, and the calculated values in a good agreement with the spectral behavior of the iteration matrix

The calculated numerical results in the given example has confirmed the theoretical results.

From figures 1 and 2, the calculated optimum relaxation parameters is in a good agreement with the behavior of the spectral radius of the iteration matrices.


References

  1. D. M. Young, Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.
  2. I. K. Youssef, On the Successive Overrelaxation Method, Journal of Mathematics and Statistics. 8 (2): 176-184, 2012.
  3. I. K. Youssef, A. A. Taha, On the Modified Successive Overrelaxation method, Applied Mathematics and Computation. 219, 4601-4613, 2013.
  4. T. L. Markham, M. Neumann, R. J. Plemmons, Convergence of a Direct-Iterative Method for Large-Scale Least-Squares Problems, Linear Algebra and Its Applications. 69: 155-167, 1985.
  5. V. A. Miller, M. Neumann, Successive Over Relaxation Methods for Solving the Rank Deficient Least Squares Problem, Linear Algebra Appl. 88-89: 533-557, 1987.
  6. W. Niethammer, J. de pillis, R. S. Varga, Convergence of Block Iterative Methods Applied to Sparse Least-Squares Problems, Linear Algebra and Its Applications. 58: 327-341, 1984.
  7. A. Bjorck, Numerical Methods for Least Squares Problems, SIAM, Philadelphia, 1996.
  8. A. Berman, R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, 1979.
  9. C. H. Santos, B. P. B. Silva, J. Y. Yuan, Block SOR Methods for Rank-Deficient Least-Squares Problems, Journal of Computational and Applied Mathematics. 100: 1-9, 1998.
  10. M. T. Darvishi, F. Khani, S. Hamedi-Nezhad, B. Zheng, Symmetric Block-SOR Methods for Rank-Deficient Least Squares Problems, Journal of Computational and Applied Mathematics. 215: 14-27, 2007.
  11. R. J. Plemmons, Adjustment by Least Squares in Geodesy Using Block Iterative Methods for Sparse Matrices, in Proceeding of the U. S. Army Conference on Numerical Analysis and Computers, EL Paso, Texas, 1979.
  12. A. Berman, M. Neumann, Proper Splittings of Rectangular Matrices, SIAM J. Apll. math. 31: 307-312, 1976.
  13. C. L. Lawson, R. J. Hanson, Solving Least Squares Problems, SIAM, Philadelphia, 1995.

Article Tools
  Abstract
  PDF(278K)
Follow on us
ADDRESS
Science Publishing Group
548 FASHION AVENUE
NEW YORK, NY 10018
U.S.A.
Tel: (001)347-688-8931