
Research Article


Quartersweep Modified SOR Iterative Algorithm and Cubic Spline Basis for the Solution of Second Order Twopoint Boundary Value Problems 

N.I.M. Fauzi
and
J. Sulaiman



ABSTRACT

The aim of this study is to describe the formulation of QuarterSweep Modified Successive OverRelaxation (QSMSOR) iterative method using cubic polynomial spline scheme for solving second order twopoint linear boundary value problems. To solve the problems, a linear system will be constructed via discretization process by using cubic spline approximation equation. Then the generated linear system has been solved using the proposed QSMSOR iterative method to show the superiority over FullSweep Modified Successive OverRelaxation (FSMSOR) and HalfSweep Modified Successive OverRelaxation (HSMSOR) methods. Computational results are provided to illustrate the effectiveness of the proposed method.





Received: March 20, 2012;
Accepted: July 19, 2012;
Published: September 04, 2012


INTRODUCTION
Presently, seeking the approximate and/or exact solutions of twopoint Boundary
Value Problems (BVPs) play an essential role in science and engineering problems.
For instance, modeling of chemical reactions and heat transfer can be governed
by these problems. In addition to that, obtaining accurate and fast numerical
solution of twopoint BVPs is of great importance due to its wide application
in scientific and engineering research. Therefore, many numerical methods intensively
have been proposed to solve twopoint boundary value problems such as finite
difference, finite element and finite volume methods (Fang
et al., 2002), extended ADM (EADM) (Jang, 2008),
Differential Quadrature method (Sari, 2008), Precise
Time Integration (PTI) method (Chen et al., 2006),
shooting method (Ha, 2001), using Legendre polynomials
and function approximation (Hoseini et al., 2009),
Galerkin and Collocation methods (Mohsen and Gamel, 2008;
Tasci, 2003) and using interpolation (Sophianopoulos
and Asteris, 2004). In this study, however, discretization schemes based
on cubic spline scheme was used to discretize the problems. Precisely, the cubic
spline scheme will be taken into account in constructing a cubic spline approximation
equation towards twopoint linear boundary value problems.
Actually based on previous studies of spline solutions, the development and
analysis of the methods towards twopoint boundary value problems have also
been discussed by many researchers (Albasiny and Hoskins,
1969; Aziz and Khan, 2002; Ramadan
et al., 2007; Rashidinia et al., 2008).
These spline schemes are used to discretize twopoint boundary value problems
and then derive their corresponding spline approximation equations. Then each
of these approximation equations yields a large and sparse linear system. Since
the attributes of linear systems are large and sparse, iterative methods are
the natural options for efficient solutions. As a matter of fact, various iterative
methods also have been studied to yield fast numerical solution of linear systems
(Young, 1971; Hackbusch, 1995; Saad,
2003; Jin et al., 2010). Apart from those
iterative methods, the finding of the halfsweep iteration concept has been
introduced by Abdullah (1991) via., Explicit Decoupled
Group (EDG) iterative method in solving twodimensional Poisson equations. The
essential characteristic of this concept is that the halfsweep iterative method
includes the reduction technique in order to reduce the computational complexity
of linear systems generated from corresponding approximation equations. Following
to this concept, further investigations have been extensively conducted by Yousif
and Evans (1995), Akhir et al. (2011), Aruchunan
and Sulaiman (2011) and Hasan et al. (2011)
for demonstrating the capability of the halfsweep iteration. Beside these onestage
iteration methods, combinations between halfsweep iteration concept with twostage
iterative methods namely HSIADE (Sulaiman et al.,
2004), HSAM (Muthuvalu and Sulaiman, 2011) and HSGM
(Muthuvalu and Sulaiman, 2012) have also been constructed
and implemented for solving linear systems. They pointed out that these proposed
twostage iterative methods are one of most efficient iterative methods in solving
any system of linear equations. Due to the low computational complexity, again,
this concept has been used to develop the formulation of various multigrid methods
(Othman et al., 2000; Sulaiman
et al., 2008). In addition to that, Hasan et
al. (2005, 2007) have established a family of
FDTD methods using this concept in solving wave propagation problems. They pointed
out that the proposed FDTD method is more superior compared to the standard
FDTD method. For robotic problems, Saudi and Sulaiman (2009,
2010) have used this concept to solve the robotic path
planning.
Differently from the halfsweep iteration approach, Othman
and Abdullah (2000) have expanded this approach to initiate the Modified
Explicit Group (MEG) method based on the quartersweep approach. It is proved
that this method is one of most efficient block iterative methods in solving
any linear systems as compared with EG and EDG iterative methods. Also many
studies have been carried out to demonstrate the capability of the quartersweep
iteration (Jha and Srivastava, 2008; Sulaiman
et al., 2005, 2009, 2010;
Muthuvalu and Sulaiman, 2010).
Due to the advantage of quartersweep approach, the main purpose of this paper is to examine the efficiency of Modified Successive OverRelaxation (MSOR) iterative methods namely FSMSOR, HSMSOR and QSMSOR for solving twopoint boundary value problems by using spline approximation equation based on cubic spline scheme. Consider twopoint linear boundary value problem be defined in general form as: subject to the boundary conditions:
y(a) = A_{1}, y(b) = A_{2}
where l(x), f(x) and g(x) are continuous on the interval [a, b], through A_{i}, i = 1,2 are finite real constants and l(x), f(x) and g(x) are known functions.
Based on Fig. 1, we use the finite grid network to facilitate
us in formulating the full, halfand quarter sweep cubic spline approximation
equations.

Fig. 1(ac): 
Distribution of uniform solid node points for (a) Full, (b)
Half and (c) Quartersweep cases 
Later, the implementations of full, halfand quartersweep iterative methods
will be executed to solve the linear system generated by using the corresponding
spline approximation equation. However, we just consider to obtain approximate
values onto node points only until convergence test will be figured out. Meanwhile,
the approximation solutions for the remaining points can be computed by using
direct method (Abdullah, 1991; Ibrahim
and Abdullah, 1995).
DERIVATION OF QUARTERSWEEP CUBIC SPLINE APPROXIMATION EQUATION By using full, half and quartersweep cubic spline approximation equations for solving problem (1), a finite set of grid points x_{i}, i = 1,2,…,n1, n is established by partitioning the interval [a, b] into (n+1) uniformly subinterval:
Let y(x) be the exact solution of problem (1) and S_{i} be an approximation to y_{i} = y(x_{i}) determine by the segments of Q_{i}(x) are passing through to the points (x_{i}, S_{i}) and (x_{i+1}, S_{i+1}). The spline approximation in general form can be expressed as:
for n = 1, 2, …, n where C_{m} are the coefficient which must
be determined in each interval, while suppose that n refer to the order of spline.
Then let the cubic polynomial spline from Eq. 2 be defined
as Q_{i}(x) which is denoted in general form as:
for i = 0p, 1p, 2p, …, np, n with a_{i}, b_{i} and c_{i} are constant coefficients. The value of p which equals to 1, 2 and 4, represents for the full, half and quartersweep cases, respectively. In order to get the expression of three coefficients, a_{i}, b_{i} and c_{i}, the cubic spline segments Q_{i} in terms of S_{i+p} and M_{i+p} can be manipulated to derive by the following conditions: Then the following expressions can be obtained by the straightforward substitution: with i = 0p, 1p, 2p, …, np, n. Now by mean of the expressions in Eq. 5 and the continuity conditions:
where k = 1, 2, we get the following relations for i = 0p, 1p, 2p, …, np: From Eq. 1, we substitute M_{i} = y^{n}(x_{i}) and obtain the following expression: where l_{i} = l(x_{i}), f_{i} = f(x_{i}) and g_{i} = g(x_{i}). According to Eq. 6, we can write the expression in Eq. 7 at the grid points x_{k}, k = ip, i, i+p as follows: To approximate the first order derivative of y with respect to x in Eq. 8, we consider the following second order finite difference approximation equations: Substituting Eq. 9 into 8, we have the following expression: Again substituting Eq. 10 into 6, we obtain the following:
cubic spline approximation equations in case of full, halfand quartersweep for i = 1p, 2p, 3p, …, np can be stated as: Where:
Let us rewrite the linear system (11) in matrix form as follows: Where:
FORMULATION OF MODIFIED SUCCESSIVE OVERRELAXATION ITERATIVE ALGORITHMS
As aforementioned in the second section, the coefficient matrix, A of linear
systems in Eq. 12 is sparse and large. Consequently, iterative
methods are proposed being as the natural options for efficient solutions of
sparse linear system. In this section, we show on how to construct FSMSOR, HSMSOR
and QSMSOR iterative methods being applied to solve linear systems (12).
To derive the formulation for FSMSOR, HSMSOR and QSMSOR iterative methods,
let the coefficient matrix, A in Eq. 12 be decomposed as:
where, L, D and U are lower triangular, diagonal and upper triangular matrices,
respectively. By using the decomposition in Eq. 13, therefore,
the general scheme for SOR method can be stated as (Young,
1971):
where, ω and
represent as a relaxation factor and an unknown vector at the kth iteration
respectively. In fact, the formulation of the QSMSOR iterative scheme is the
same to the SOR iteration scheme by considering the implementation of redblack
ordering strategy through the use of two different weighted parameters, ω
and ω’. For example, parameter ω’ was performed on the order
of red and the next parameter ω was applied to black rule. Based on Eq.
14, QSMSOR iterative scheme can be expressed as (Young,
1971; Kincaid and Young, 1972):
As taking ω = ω’, the schematic of Eq. 15
is known as SOR iterative method with the RedBlack ordering strategy. Therefore
by determining values of matrices D, L and U as stated in Eq.
13, the general algorithm of FSMSOR, HSMSOR and QSMSOR iterative methods
would be generally described in Algorithm 1:
Algorithm 1: 
FSMSOR, HSMSOR and QSMSOR schemes 

NUMERICAL EXPERIMENTS
Here, we have applied QSMSOR methods on the following three problems, whose
exact solutions are known to us and have compared the results with the FSMSOR
and HSMSOR methods in order to demonstrate the effectiveness of QSMSOR method
based on cubic spline approach. For the sake of comparison, there are three
parameters considered in numerical comparison namely number of iterations, execution
time and maximum absolute error. Throughout the numerical simulations, the initial
value of vector
is used in all proposed iterative methods and the iterations were terminated
stopped when the absolute error tolerance, ε = 10^{10} was achieved
at several different values of n.
Example 1 (Mohsen and Gamel, 2008):
The exact solution for Eq. 16 is given by:
y(x) = cos h(2x1)cosh1
Example 2:
Table 1: 
Comparison of No. of iterations K, the execution time (seconds)
and maximum absolute errors for the iterative methods using example 1 

Table 2: 
Comparison of number of iterations K, the execution time
(seconds) and maximum absolute errors for the iterative methods using example
2 

The exact solution for Eq. 17 is given by:
y(x) = cosh(2x1)cosh1
Example 3 (Aziz and Khan, 2002):
And the exact solution for Eq. 18 is given by:
According to above three examples, the results of numerical experiments obtained from implementation of the FSMSOR, HSMSOR and QSMSOR iterative methods have been tabulated in Table 13, whereas, Table 4 indicates depreciation percentage of number of iterations and execution time.
COMPUTATIONAL COMPLEXITY ANALYSIS
To compare the computational complexity of three proposed MSOR iterative methods, we need to calculate an estimation amount of the computational works needed for implementation of FSMSOR, HSMSOR and QSMSOR methods. The computational work is evaluated by analysing arithmetic operation achieved per iteration for each of proposed MSOR iterative methods. Based on Algorithm 1, it can be seen that there are:
addition/subtraction (ADD/SUB) and:
Multiplication/division (MUL/DIV) operations in computing a value for each
node point in the solution of cubic spline approximation equation.
Table 3: 
Comparison of number of iterations K, the execution time
(seconds) and maximum absolute errors for the iterative methods using example
3 

Table 4: 
Depreciation percentage of number of iterations and execution
time for HSMSOR and QSMSOR iterative methods compared to FSMSOR using three
examples 

Table 5: 
Total number of arithmetic operations per iteration for FSMSOR,
HSMSOR and QSMSOR methods 

Based on the order of coefficient matrix, A, the total number of arithmetic
operation per iteration for the FSMSOR, HSMSOR and QSMSOR iterative methods
in solving Eq. 1 has been recorded in Table
5. Clearly it shows that the computational complexity of HSMSOR and QSMSOR
methods is lesser than FSMSOR method.
CONCLUSION
The efficiency of the family of MSOR iterative methods namely FSMSOR, HSMSOR
and QSMSOR with the corresponding cubic spline approximation equations was employed
successfully for solving twopoint linear boundary value problems. Clearly it
can be observed that the general cubic spline approximation equation in Eq.
11 has been used to form linear system which has been solved by the proposed
MSOR iterative methods. Through numerical experiments results from Table
14, it clearly shows that QSMSOR method managed to converge
faster than FSMSOR and HSMSOR methods. This is because of the QSMSOR method
has less computational complexity, see in Table 5.

REFERENCES 
1: Abdullah, A.R., 1991. The four point Explicit Decoupled Group (EDG) method: A fast poisson solver. Int. J. Comput. Math., 38: 6170. CrossRef  Direct Link 
2: Akhir, M.K.M., M. Othman, J. Sulaiman, Z.A. Majid and M. Suleiman, 2011. Halfsweep modified successive overrelaxation for solving iterative method twodimensional helmholtz equations. Aust. J. Basic Applied Sci., 5: 30333039. Direct Link 
3: Albasiny, E.L. and W.D. Hoskins, 1969. Cubic spline solutions to twopoint boundary value problems. Comput. J., 12: 151153. CrossRef  Direct Link 
4: Aruchunan, E. and J. Sulaiman, 2011. Halfsweep conjugate gradient method for solving first order linear fredholm integrodifferential equations. Aust. J. Basic Applied Sci., 5: 3843. Direct Link 
5: Aziz, T. and A. Khan, 2002. A spline method for secondorder singularly perturbed boundaryvalue problems. J. Comput. Applied Math., 147: 445452. CrossRef  Direct Link 
6: Chen, B., L. Tong and Y. Gu, 2006. Precise time integration for linear twopoint boundary value problems. Applied Math. Comput., 175: 182211. CrossRef  Direct Link 
7: Fang, Q., T. Tsuchiya and T. Yamamoto, 2002. Finite difference, finite element and finite volume methods applied to twopoint boundary value problems. J. Comput. Applied Math., 139: 919. CrossRef  Direct Link 
8: Hackbusch, W., 1995. Iterative Solution of Large Sparse Systems of Equations. SpringerVerlag, New York.
9: Hasan, M.K., M. Othman, Z. Abbas, J. Sulaiman and R. Johari, 2005. The HSLO (3)FDTD with directdomain and temporarydomain approaches on infinite space wave propagation. Proceedings of the 13th IEEE International Conference on Networks and 7th IEEE Malaysia International Conference on Communication, November 1618, 2005, IEEE Computer Society, Kuala Lumpur, Malaysia, pp: 10021007.
10: Hasan, M.K., J. Sulaiman, S.A.A. Karim and M. Othman, 2011. Development of some numerical methods applying complexity reduction approach for solving scientific problem. J. Applied Sci., 11: 12551260. CrossRef  Direct Link 
11: Ibrahim, A. and A.R. Abdullah, 1995. Solving The two dimensional diffusion equation by the four point Explicit Decoupled Group (EDG) iterative method. Int. J. Comput. Math., 58: 253256. CrossRef  Direct Link 
12: Jang, B., 2008. Twopoint boundary value problems by the extended adomian decomposition method. J. Comput. Applied Math., 219: 253262. CrossRef  Direct Link 
13: Jha, N. and P.R. Srivastava, 2008. Application of QSAGE solver for the computation of state variable models in software test process. Int. J. Mathe. Model. Simul. Appl., 1: 305312.
14: Jin, Y., G. Jin and T. Ma, 2010. New parallel threelevel iterative method for diffusion equation. Inform. Technol. J., 9: 11841189. CrossRef  Direct Link 
15: Kincaid, D.R. and D.M. Young, 1972. The modified successive over relaxation method with fixed parameters. Mathe. Comput., 26: 705717. Direct Link 
16: Mohsen, A. and M. ElGamel, 2008. On the galerkin and collocation methods for twopoint boundary value problems using sinc bases. Comput. Math. Applic., 56: 930941. CrossRef  Direct Link 
17: Hoseini, S.M., M. Hoseini and H. Orooji, 2009. Numerical solution of twopoint boundary value problem in linear differential equation. Applied Math. Sci., 3: 14931499. Direct Link 
18: Muthuvalu, M.S. and J. Sulaiman, 2010. Quartersweep iteration for first kind linear Fredholm integral equations. Int. J. Open Prob. Compt. Math., 3: 357367. Direct Link 
19: Muthuvalu, M.S. and J. Sulaiman, 2011. HalfSweep arithmetic mean method with composite trapezoidal scheme for solving linear fredholm integral equations. Applied Math. Comput., 217: 54425448. CrossRef  Direct Link 
20: Muthuvalu, M.S. and J. Sulaiman, 2012. HalfSweep geometric mean iterative method for the repeated simpson solution of second kind linear fredholm integral equations. Proyecciones J. Math., 31: 6579. Direct Link 
21: Othman, M., J. Sulaiman and A.R. Abdullah, 2000. A parallel halfsweep multigrid algorithm on the shared memory multiprocessors. Malaysian J. Comput. Sci., 13: 16. Direct Link 
22: Othman, M. and A.R. Abdullah, 2000. An efficient four points modified explicit group poisson solver. Int. J. Comput. Math., 76: 203217. CrossRef 
23: Ramadan, M.A., I.F. Lashien and W.K. Zahra, 2007. Polynomial And nonpolynomial spline approaches to the numerical solution of second order boundary value problems. Applied Math. Comput., 184: 476484. CrossRef  Direct Link 
24: Rashidinia, J., R. Mohammadi and R. Jalilian, 2008. Cubic spline method for twopoint boundary value problems. IUST Int. J. Eng. Sci., 19: 3943. Direct Link 
25: Saad, Y., 2003. Iterative Methods for Sparse Linear Systems. 2nd Edn., Society for Industrial and Applied Mathematics, Philadelpha, PA., USA., ISBN13: 9780898715347, Pages: 528.
26: Sari, M., 2008. Differential quadrature method for singularly perturbed twopoint boundary value problems. J. Applied Sci., 8: 10911096. CrossRef  Direct Link 
27: Saudi, A. and J. Sulaiman, 2009. Path planning for mobile robot with HalfSweep Successive OverRelaxation (HSSOR) iterative method. Proceedings of the Symposium on Progress in Information and Communication Technology, December 78, 2009, Kuala Lumpur, Malaysia, pp: 5762.
28: Saudi, A. and J. Sulaiman, 2010. Redblack strategy for mobile robot path planning. Proc. Int. Multi Conf. Eng. Comput. Sci., 3: 22152220. Direct Link 
29: Sophianopoulos, D.S. and P.G. Asteris, 2004. Interpolation based numerical procedure for solving twopoint nonlinear boundary value problems. Int. J. Nonlinear Sci. Numer. Simul., 5: 6778. Direct Link 
30: Sulaiman, J., M. Othman and M.K. Hasan, 2008. HalfSweep Algebraic Multigrid (HSAMG) Method Applied to Diffusion Equations. In: Modeling, Simulation and Optimization of Complex Processes, Bock, H.G., H.X. Phu, R. Rannacher and J.P. Schloder (Eds.). Springer, Germany, ISBN13: 9783540794080, pp: 547556.
31: Sulaiman, J., M. Othman and M.K. Hasan, 2004. Quartersweep iterative alternating decomposition explicit algorithm applied to diffusion equations. Int. J. Comput. Math., 81: 15591565. CrossRef  Direct Link 
32: Sulaiman, J., M. Othman and M.K. Hasan, 2009. A new QuarterSweep Arithmetic Mean (QSAM) method to solve diffusion equations. Chamchuri J. Math., 1: 8999. Direct Link 
33: Sulaiman, J., M.K. Hasan, M. Othman and S.A.A. Karim, 2010. MEGSOR iterative method for the triangle element solution of 2D poisson equations. Procedia Comput. Sci., 1: 377385. CrossRef  Direct Link 
34: Ha, S.N., 2001. A nonlinear shooting method for twopoint boundary value problems. Comput. Math. Appl., 42: 14111420. CrossRef 
35: Tasci, F., 2003. On the approximative solution of boundary value problems by collocation. J. Applied Sci., 3: 210215. CrossRef  Direct Link 
36: Young, D.M., 1971. Iterative Solution of Large Linear Systems. Academic Press, London.
37: Yousif, W.S. and D.J. Evans, 1995. Explicit decoupled group iterative methods and their parallel implementations. Paral. Algorithms Appli., 7: 5371. CrossRef 
38: Hasan, M.K., M. Othman, Z. Abbas, J. Sulaiman and F. Ahmad, 2007. Parallel solution of high speed low order FDTD on 2D free space wave propagation. Proceedings of the 2nd International Conference on Computational Science and Its Applications, August 2629, 2007, Kuala Lumpur, Malaysia, pp: 1324.
39: Sulaiman, J., M.K. Hasan and M. Othman, 2005. The halfsweep iterative alternating decomposition explicit (HSIADE) method for diffusion equation. Proceedings of the 1st International Symposium on Computational and Information Science, December 1618, 2004, Shanghai, China, pp: 5763.



