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:
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 A_{1}, A_{2} with non-singular part, A_{1}. 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 s^{th} 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.
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.
The table summarizes the results
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