Subscribe Now Subscribe Today
Research Article
 

Quarter-sweep Modified SOR Iterative Algorithm and Cubic Spline Basis for the Solution of Second Order Two-point Boundary Value Problems



N.I.M. Fauzi and J. Sulaiman
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

The aim of this study is to describe the formulation of Quarter-Sweep Modified Successive Over-Relaxation (QSMSOR) iterative method using cubic polynomial spline scheme for solving second order two-point 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 Full-Sweep Modified Successive Over-Relaxation (FSMSOR) and Half-Sweep Modified Successive Over-Relaxation (HSMSOR) methods. Computational results are provided to illustrate the effectiveness of the proposed method.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

N.I.M. Fauzi and J. Sulaiman, 2012. Quarter-sweep Modified SOR Iterative Algorithm and Cubic Spline Basis for the Solution of Second Order Two-point Boundary Value Problems. Journal of Applied Sciences, 12: 1817-1824.

DOI: 10.3923/jas.2012.1817.1824

URL: https://scialert.net/abstract/?doi=jas.2012.1817.1824
 
Received: March 20, 2012; Accepted: July 19, 2012; Published: September 04, 2012



INTRODUCTION

Presently, seeking the approximate and/or exact solutions of two-point 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 two-point 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 two-point 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 two-point linear boundary value problems.

Actually based on previous studies of spline solutions, the development and analysis of the methods towards two-point 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 two-point 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 half-sweep iteration concept has been introduced by Abdullah (1991) via., Explicit Decoupled Group (EDG) iterative method in solving two-dimensional Poisson equations. The essential characteristic of this concept is that the half-sweep 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 half-sweep iteration. Beside these one-stage iteration methods, combinations between half-sweep iteration concept with two-stage 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 two-stage 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 half-sweep iteration approach, Othman and Abdullah (2000) have expanded this approach to initiate the Modified Explicit Group (MEG) method based on the quarter-sweep 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 quarter-sweep iteration (Jha and Srivastava, 2008; Sulaiman et al., 2005, 2009, 2010; Muthuvalu and Sulaiman, 2010).

Due to the advantage of quarter-sweep approach, the main purpose of this paper is to examine the efficiency of Modified Successive Over-Relaxation (MSOR) iterative methods namely FSMSOR, HSMSOR and QSMSOR for solving two-point boundary value problems by using spline approximation equation based on cubic spline scheme.

Consider two-point linear boundary value problem be defined in general form as:

(1)

subject to the boundary conditions:

y(a) = A1, y(b) = A2

where l(x), f(x) and g(x) are continuous on the interval [a, b], through Ai, 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-, half-and quarter- sweep cubic spline approximation equations.

Fig. 1(a-c): Distribution of uniform solid node points for (a) Full-, (b) Half- and (c) Quarter-sweep cases

Later, the implementations of full-, half-and quarter-sweep 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 QUARTER-SWEEP CUBIC SPLINE APPROXIMATION EQUATION

By using full-, half- and quarter-sweep cubic spline approximation equations for solving problem (1), a finite set of grid points xi, i = 1,2,…,n-1, 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 Si be an approximation to yi = y(xi) determine by the segments of Qi(x) are passing through to the points (xi, Si) and (xi+1, Si+1). The spline approximation in general form can be expressed as:

(2)

for n = 1, 2, …, n where Cm 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 Qi(x) which is denoted in general form as:

(3)

for i = 0p, 1p, 2p, …, n-p, n with ai, bi and ci are constant coefficients. The value of p which equals to 1, 2 and 4, represents for the full-, half- and quarter-sweep cases, respectively. In order to get the expression of three coefficients, ai, bi and ci, the cubic spline segments Qi in terms of Si+p and Mi+p can be manipulated to derive by the following conditions:

(4)

Then the following expressions can be obtained by the straightforward substitution:

(5)

with i = 0p, 1p, 2p, …, n-p, 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, …, n-p:

(6)

From Eq. 1, we substitute Mi = yn(xi) and obtain the following expression:

(7)

where li = l(xi), fi = f(xi) and gi = g(xi). According to Eq. 6, we can write the expression in Eq. 7 at the grid points xk, k = i-p, i, i+p as follows:

(8)

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:

(9)

Substituting Eq. 9 into 8, we have the following expression:

(10)

Again substituting Eq. 10 into 6, we obtain the following:

cubic spline approximation equations in case of full-, half-and quarter-sweep for i = 1p, 2p, 3p, …, n-p can be stated as:

(11)

Where:

Let us rewrite the linear system (11) in matrix form as follows:

(12)

Where:

FORMULATION OF MODIFIED SUCCESSIVE OVER-RELAXATION 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:

(13)

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):

(14)

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 red-black 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):

(15)

As taking ω = ω’, the schematic of Eq. 15 is known as SOR iterative method with the Red-Black 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):

(16)

The exact solution for Eq. 16 is given by:

y(x) = cos h(2x-1)-cosh-1

Example 2:

(17)


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(2x-1)-cosh-1

Example 3 (Aziz and Khan, 2002):

(18)

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 1-3, 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 two-point 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 1-4, 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: 61-70.
CrossRef  |  Direct Link  |  

2:  Akhir, M.K.M., M. Othman, J. Sulaiman, Z.A. Majid and M. Suleiman, 2011. Half-sweep modified successive overrelaxation for solving iterative method two-dimensional helmholtz equations. Aust. J. Basic Applied Sci., 5: 3033-3039.
Direct Link  |  

3:  Albasiny, E.L. and W.D. Hoskins, 1969. Cubic spline solutions to two-point boundary value problems. Comput. J., 12: 151-153.
CrossRef  |  Direct Link  |  

4:  Aruchunan, E. and J. Sulaiman, 2011. Half-sweep conjugate gradient method for solving first order linear fredholm integro-differential equations. Aust. J. Basic Applied Sci., 5: 38-43.
Direct Link  |  

5:  Aziz, T. and A. Khan, 2002. A spline method for second-order singularly perturbed boundary-value problems. J. Comput. Applied Math., 147: 445-452.
CrossRef  |  Direct Link  |  

6:  Chen, B., L. Tong and Y. Gu, 2006. Precise time integration for linear two-point boundary value problems. Applied Math. Comput., 175: 182-211.
CrossRef  |  Direct Link  |  

7:  Fang, Q., T. Tsuchiya and T. Yamamoto, 2002. Finite difference, finite element and finite volume methods applied to two-point boundary value problems. J. Comput. Applied Math., 139: 9-19.
CrossRef  |  Direct Link  |  

8:  Hackbusch, W., 1995. Iterative Solution of Large Sparse Systems of Equations. Springer-Verlag, New York.

9:  Hasan, M.K., M. Othman, Z. Abbas, J. Sulaiman and R. Johari, 2005. The HSLO (3)-FDTD with direct-domain and temporary-domain approaches on infinite space wave propagation. Proceedings of the 13th IEEE International Conference on Networks and 7th IEEE Malaysia International Conference on Communication, November 16-18, 2005, IEEE Computer Society, Kuala Lumpur, Malaysia, pp: 1002-1007.

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: 1255-1260.
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: 253-256.
CrossRef  |  Direct Link  |  

12:  Jang, B., 2008. Two-point boundary value problems by the extended adomian decomposition method. J. Comput. Applied Math., 219: 253-262.
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: 305-312.

14:  Jin, Y., G. Jin and T. Ma, 2010. New parallel three-level iterative method for diffusion equation. Inform. Technol. J., 9: 1184-1189.
CrossRef  |  Direct Link  |  

15:  Kincaid, D.R. and D.M. Young, 1972. The modified successive over relaxation method with fixed parameters. Mathe. Comput., 26: 705-717.
Direct Link  |  

16:  Mohsen, A. and M. El-Gamel, 2008. On the galerkin and collocation methods for two-point boundary value problems using sinc bases. Comput. Math. Applic., 56: 930-941.
CrossRef  |  Direct Link  |  

17:  Hoseini, S.M., M. Hoseini and H. Orooji, 2009. Numerical solution of two-point boundary value problem in linear differential equation. Applied Math. Sci., 3: 1493-1499.
Direct Link  |  

18:  Muthuvalu, M.S. and J. Sulaiman, 2010. Quarter-sweep iteration for first kind linear Fredholm integral equations. Int. J. Open Prob. Compt. Math., 3: 357-367.
Direct Link  |  

19:  Muthuvalu, M.S. and J. Sulaiman, 2011. Half-Sweep arithmetic mean method with composite trapezoidal scheme for solving linear fredholm integral equations. Applied Math. Comput., 217: 5442-5448.
CrossRef  |  Direct Link  |  

20:  Muthuvalu, M.S. and J. Sulaiman, 2012. Half-Sweep geometric mean iterative method for the repeated simpson solution of second kind linear fredholm integral equations. Proyecciones J. Math., 31: 65-79.
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: 1-6.
Direct Link  |  

22:  Othman, M. and A.R. Abdullah, 2000. An efficient four points modified explicit group poisson solver. Int. J. Comput. Math., 76: 203-217.
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: 476-484.
CrossRef  |  Direct Link  |  

24:  Rashidinia, J., R. Mohammadi and R. Jalilian, 2008. Cubic spline method for two-point boundary value problems. IUST Int. J. Eng. Sci., 19: 39-43.
Direct Link  |  

25:  Saad, Y., 2003. Iterative Methods for Sparse Linear Systems. 2nd Edn., Society for Industrial and Applied Mathematics, Philadelpha, PA., USA., ISBN-13: 978-0898715347, Pages: 528.

26:  Sari, M., 2008. Differential quadrature method for singularly perturbed two-point boundary value problems. J. Applied Sci., 8: 1091-1096.
CrossRef  |  Direct Link  |  

27:  Saudi, A. and J. Sulaiman, 2009. Path planning for mobile robot with Half-Sweep Successive Over-Relaxation (HSSOR) iterative method. Proceedings of the Symposium on Progress in Information and Communication Technology, December 7-8, 2009, Kuala Lumpur, Malaysia, pp: 57-62.

28:  Saudi, A. and J. Sulaiman, 2010. Red-black strategy for mobile robot path planning. Proc. Int. Multi Conf. Eng. Comput. Sci., 3: 2215-2220.
Direct Link  |  

29:  Sophianopoulos, D.S. and P.G. Asteris, 2004. Interpolation based numerical procedure for solving two-point nonlinear boundary value problems. Int. J. Nonlinear Sci. Numer. Simul., 5: 67-78.
Direct Link  |  

30:  Sulaiman, J., M. Othman and M.K. Hasan, 2008. Half-Sweep 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, ISBN-13: 9783540794080, pp: 547-556.

31:  Sulaiman, J., M. Othman and M.K. Hasan, 2004. Quarter-sweep iterative alternating decomposition explicit algorithm applied to diffusion equations. Int. J. Comput. Math., 81: 1559-1565.
CrossRef  |  Direct Link  |  

32:  Sulaiman, J., M. Othman and M.K. Hasan, 2009. A new Quarter-Sweep Arithmetic Mean (QSAM) method to solve diffusion equations. Chamchuri J. Math., 1: 89-99.
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: 377-385.
CrossRef  |  Direct Link  |  

34:  Ha, S.N., 2001. A nonlinear shooting method for two-point boundary value problems. Comput. Math. Appl., 42: 1411-1420.
CrossRef  |  

35:  Tasci, F., 2003. On the approximative solution of boundary value problems by collocation. J. Applied Sci., 3: 210-215.
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 de-coupled group iterative methods and their parallel implementations. Paral. Algorithms Appli., 7: 53-71.
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 26-29, 2007, Kuala Lumpur, Malaysia, pp: 13-24.

39:  Sulaiman, J., M.K. Hasan and M. Othman, 2005. The half-sweep iterative alternating decomposition explicit (HSIADE) method for diffusion equation. Proceedings of the 1st International Symposium on Computational and Information Science, December 16-18, 2004, Shanghai, China, pp: 57-63.

©  2021 Science Alert. All Rights Reserved