# On the application of homotopy perturbation method for solving systems of linear equations.

1. IntroductionConsider the following convection-diffusion equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

On the unit square domain [OMEGA] = [0,1] x [0,1],with constant coefficients [delta], [tau], subject to Dirichlet boundary conditions. Discretization by a five-point finite difference operator leads to the following linear system:

AX = b, (2)

where X denotes a vector in a finite-dimensional space and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. With discretization on a uniform n x n grid, using standard second-order differences for the Laplacian and either centered or upwind differences for the first derivatives, the coefficient matrix has the form

A = tridiagonal [bl, tridiagonal [c, a,d],eI],

b = -(1 + [partial derivative]); c = -(l + [gamma]); a = 4; (3)

d = -(1-[gamma]); e = -(1 - [partial derivative]).

Or with Kronecker product ([cross product]) we obtain

A = I [cross product][T.sub.x] + I [cross product][T.sub.y],

[T.sub.x] = tridiagonal [c, a, d], (4)

[T.sub.y] = tridiagonal [bI, 0, eI],

where [partial derivative] = [tau]h/2; [gamma] = [delta]h/2 are Reynolds numbers. Also, the equidistant step-size h = 1/n is used in the discretization and the natural lexicographic ordering is employed to the unknowns and the right hand side satisfies [b.sub.ij] = [h.sup.2][f.sub.ij] (x,y). For details, we refer to [1, 2] and the references therein. Convection-diffusion equations appear in many fields of science and engineering and there are some reliable methods for solving this class of problems ([1, 2] and the references therein). Here, we use alternative approach to solve (2) based on homotopy perturbation method (HPM). The HPM was first proposed by the Chinese mathematician He in 1999 [3] and was further developed and improved by him [4-6]. He presented a homotopy perturbation technique based on the introduction of homotopy in topology coupled with the traditional perturbation method for the solution of algebraic equations and ODEs. This technique provides a summation of an infinite series with easily computable terms, which converges to the solution of the problem. In the literature, various authors have successfully applied this method for many kinds of different problems such as nonlinear partial differential equations [7, 8], nonlinear wave equations [5], nonlinear integral and integrodifferential equations [9], fractional IVPs [10], and optimization [11]. Nevertheless, to our knowledge, a few papers have considered this analytical method for system of linear equations. Keramati [12] presented an efficient method for solving system of linear equations based on HPM. Liu [13] by using HPM and splitting methods proposed a new method for linear systems. Saberi Najafi et al. [14] based on HPM proposed a new algorithm for fuzzy linear systems and compared it with Adomian's decomposition method. They also in [15] show that solving linear systems by using a new method called modified HPM, presented by Noor et al. [16], is impractical.

In this paper, by combination of HPM and preconditioning technique, we will present a new model for solving linear systems and apply this method to the above convection-diffusion equation.

2. Homotopy Perturbation Method for Linear Systems

Consider linear system (2). HPM procedure for solving of this system is a continuous map from the interval [0,1] to a function space where it is as follows:

H(u,p) = (1 - p)F (m) + pL (u) = 0, (5)

and p [member of] [0,1] is an embedding parameter.

Keramati [12] applied a HPM to solve linear systems by the following definitions.

Let L(u) = Au-b and F(u) = u-[w.sub.0], where [w.sub.0] is a known vector. Then homotopy H(u, p) is

H(u,p) = (1 - p)(u - [w.sub.0]) + p (Au - b) = 0. (6)

Obviously, we will have

H(u,0) = F(u), H(u,1) = L(u). (7)

According to the HPM, we can first use the embedding parameter p as a small parameter and assume that the solution of (2) can be written as a power series in p:

u = [u.sub.0] + p[u.sub.1] + [p.sup.2] [u.sub.2] + ***, (8)

and the exact solution is obtained as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

Putting (8) into (5) and comparing the coefficients of identical degrees of p on both sides, we find

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

And in general

[u.sub.n+1] = -(A-I)[u.sub.n], n= 1,2, .... (11)

Taking [u.sub.0] = [w.sub.0] = 0 yields

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

Therefore, the solution can be of the form

x = [[infinity].summation over (i=0)][(-1).sup.i] [(A-I).sup.i] b. (13)

This method is efficient for solving system of linear equations but, however, does not converge for some systems when the spectral radius is greater than one. To make the method useful, Liu in [13] added the auxiliary parameter and the auxiliary matrix to the HPM. This method is as follows:

H(u,p) = (1 - p)F (u) + (qH) pL (u) = 0, (14)

where

L (u) = Au -b, F (u) = Qu - [w.sub.0]. (15)

Here, q is an auxiliary parameter, H is the auxiliary matrix, and the operator F(u) is decided by the splitting matrix Q. Then his iterative scheme for u is

[u.sub.n+1] = [(I - q[Q.sup.-1]HA).sup.n] (q[Q.sup.-1]H) b. (16)

Therefore,

u = [[infinity].summation over (i=0)] [u.sub.i][p.sup.i] = [[infinity].summation over (i=0)] [(I- q[Q.sup.-1]HA).sup.i] (q[Q.sup.-1]H) b] [p.sup.i]. (17)

And finally by setting p = 1, he obtained the solution as follows:

u = [[infinity].summation over (i=0)][u.sub.i] = [[infinity].summation over (i=0)][(I- q[Q.sup.-1]HA).sup.i] (q[Q.sup.- 1]Hb). (18)

This author has adapted the Richardson, Jacobi, and the Gauss-Seidel methods to choose the splitting matrix and obtained that the homotopy series converged rapidly for a large sparse system with a small spectral radius. But to improve the rate of convergence, he does not present on a method for choosing H (see [13], conclusion). The main goal on this paper is studying this problem and doing some modifications for having very effective and straightforward results.

Our idea for choosing H is preconditioning technique. Preconditioning methods are the most authoritative techniques to improve poor properties of the basic iterative methods. The main aim of preconditioning method for AX = b is to substitute the original matrix A with an equivalent one [A.sup.prec] which has better properties concerning the computation of a solution (generally by a certain iterative method). The two matrices are equivalent in the sense that they have the same solution. Simple preconditioners of this type are the left matrix preconditioners. The left preconditioned matrix is a nonsingular matrix M and the preconditioned matrix is defined by [A.sup.prec] = MA, where M [approximately equal to] [A.sup.-1].

In this paper, we consider H as a preconditioner and if the auxiliary matrix H is properly chosen, we can be able to achieve the best results. To improve the convergence rate of the basic iterative method, various models of preconditioning systems have been proposed [17-19]. In the literature, various authors have suggested different models of (I + S)-Type preconditioned [20-28], where all of these models are left preconditioners. We can consider all of the models in [17-28] for H.

Here we consider Usui et al. [22] model of (I + S)-Type preconditioners for H, where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

Let A = D - L-U, where D is the diagonal matrix and L, U are strictly lower and strictly upper triangular matrices of A, respectively. Then the preconditioned matrix is as follows:

[A.sup.prec] = HL(u) = HAu-[b.sup.prec],

[b.sup.prec] = Hb (20)

We know that H = (I + S), where

S = ([s.sub.ij]) = (-[a.sub.ij]/[a.sub.jj]), [for all] > i. (21)

Then we have

HA=(I + S)(D-L-U)

= (D-L-U) + SD-SL-SU. (22)

Thus,

HA=(D- [D.sub.1]) -(L + [L.sub.1])-(U-SD + [U.sub.1] + SU), (23)

where [D.sub.1], [L.sub.1], and [U.sub.1] are, respectively, the diagonal, strictly lower, and strictly upper triangular parts of SL = [D.sub.1]+[L.sub.1]+[U.sub.1].

Therefore, we have

[bar.D]= (D-[D.sub.1]),

[bar.L]= (L + [L.sub.1]),

[bar.U] = (U-SD + [U.sub.1] +SU). (24)

Furthermore, for more convergence speed in Jacobi-HPM and Gauss-Seidel-HPM we choose Q as follows.

In Jacobi-HPM,

Q = [bar.D]. (25)

In Gauss-Seidel-HPM,

Q = [bar.D]-[bar.L]. (26)

Now, we will show that by this choice of H, Q these methods are faster than of the basic methods form point of view of the convergence speed.

Definition 1 (see [29, 30]). (a) A matrix A = [a.sub.ij] is called a Z-matrix if for any i [not equal to] j, [a.sub.ij] [less than or equal to] 0.

(b) A Z-matrix is an M-matrix, if A is nonsingular and [A.sup.-1] [greater than or equal to] 0.

Definition 2 (see [29,30]). Let A be a real matrix. The splitting A = M -N is called

(a) convergent if [rho]([M.sup.-1]N) < 1 ([rho](*) is the spectral radius of matrix);

(b) regular if [M.sup.-1] [greater than or equal to] 0 and N [greater than or equal to] 0.

Lemma 3 (see [29]). Let Abe a Z-matrix. Then A is M-matrix ifand only ifthere is a positive vector X such that AX > 0.

Lemma 4 (see [31]). Let A, B be Z-matrix and A an M-matrix; if A [less than or equal to] B, then B is an M-matrix too.

Lemma 5 (see [32]). Let A = M - N be a regular splitting. Then [rho]([M.sup.-1]N) < 1 if and only if A is nonsingular and [A.sup.-1] is nonnegative.

Lemma 6 (see [24], Theorem 2.7, Remark 2.20). Let A = [D-(L+U)] = [(D-L)-U] and HA = [[bar.D]-([bar.L]+ [bar.U]) = ([bar.D]- [bar.L])- [bar.U]] be regular splittings of A and HA where H is (19). If A is M-matrix, then

[rho] ([[bar.D].sup.-1] ([bar.L] + [bar.U])) [less than or equal to] [rho]([D.sup.-1] (L + U))< 1, (27)

[rho]([([bar.D]- [bar.L]).sup.-1] [bar.U]) [less than or equal to] [rho]([(D -L).sup.-1] U)< 1. (28)

By applying Lemma 3, we can achieve thefollowing results.

Theorem 7. Let A be M-matrix. If we use H in (19) and Q in (25) and (26), then convergence rate of (18) is faster than of the convergence rate in [[SIGMA].sup.[infinity].sub.i=0] (I - q[[??].sup.-1]A) (q[Q.sup.-1] b), ([??] = D or [??] = D-L).

Proof. Since A is an M-matrix, by Lemma 3 it is easy to see that HA also is M-matrix, and thus by Lemma 4 Q is M-matrix and Q - qHA is nonnegative. Then by Lemmas 5 and 6 we can obtain [rho](I - q[Q.sup.-1]HA) [less than or equal to] p(I - q[[??].sup.-1] A) < 1.

Therefore by [13, Theorem 2.1] the proof is completed.

3. Numerical Experiments

In this section, we give an example to illustrate the obtained results in the previous sections.

We test convection-diffusion equation (1) when [delta]=1, [tau] = 2.

Then, we solved the [n.sup.2] x [n.sup.2] M-matrix yielded by Jacobi-HPM and Gauss-Seidel-HPM.

In this experiment, we choose the right hand side vector, such that X = [(1,1, ..., 1).sup.T] is solution of AX = b. The stopping criterion with tolerance [epsilon] = [10.sup.-10] is [parallel]Au - b[parallel] < [epsilon].

In Tables 1 and 2 we report the CPU time and number of iterations (Iter) for the Jacobi-HPM and Gauss-Seidel-HPM methods, respectively.

From the tables, we can see that if H is (19), then the mentioned methods are superior to the basic methods.

4. Conclusions

In this paper, we have applied a new method for solving convection-diffusion equations based on the HPM. We can see that how HPM method is influenced for solving system of linear equation, if combined by preconditioning technique. Finally, from theoretical speaking and numerical experiment, it may be concluded that the convergence behaviors of this method is superior to some other methods in the frame of HPM.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

http://dx.doi.org/10.1155/2014/143512

References

[1] H. C. Elman and G. H. Golub, "Iterative methods for cyclically reduced non-self-adjoint linear systems," Mathematics of Computation, vol. 54, no. 190, pp. 671-700,1990.

[2] H. C. Elman and G. H. Golub, "Iterative methods for cyclically reduced nonselfadjoint linear systems. II," Mathematics of Computation, vol. 56, no. 193, pp. 215-242,1991.

[3] J.-H. He, "Homotopy perturbation technique," Computer Methods in Applied Mechanics and Engineering, vol. 178, no. 3-4, pp. 257-262, 1999.

[4] J.-H. He, "Homotopy perturbation method: a new nonlinear analytical technique," Applied Mathematics and Computation, vol. 135, no. 1, pp. 73-79, 2003.

[5] J.-H. He, "Application of homotopy perturbation method to non-linear wave equations," Chaos, Solitons & Fractals, vol. 26, no. 3, pp. 695-700, 2005.

[6] J.-H. He, "Homotopy perturbation method for solving boundary value problems," Physics Letters A, vol. 350, no. 1-2, pp. 87-88, 2006.

[7] L. Cveticanin, "Application of homotopy-perturbation to nonlinear partial differential equations," Chaos, Solitons & Fractals, vol. 40, no. 1, pp. 221-228, 2009.

[8] M. Dehghan and F. Shakeri, "The numerical solution of the second Painleve equation," Numerical Methods for Partial Differential Equations, vol. 25, no. 5, pp. 1238-1259, 2009.

[9] J. Saberi-Nadjafi and A. Ghorbani, "He's homotopy perturbation method: an effective tool for solving nonlinear integral and integro-differential equations," Computers & Mathematics with Applications, vol. 58, no. 11-12, pp. 2379-2390, 2009.

[10] O. Abdulaziz, I. Hashim, and S. Momani, "Application of homotopy-perturbation method to fractional IVPs," Journal of Computational and Applied Mathematics, vol. 216, no. 2, pp. 574-584, 2008.

[11] H. Saberi Najafi and S. A. Edalatpanah, "Homotopy perturbation method for linear programming problems," Applied Mathematical Modelling, vol. 38, no. 5-6, pp. 1607-1611, 2014.

[12] B. Keramati, "An approach to the solution of linear system of equations by He's homotopy perturbation method," Chaos, Solitons & Fractals, vol. 41, no. 1, pp. 152-156, 2009.

[13] H.-K. Liu, "Application of homotopy perturbation methods for solving systems of linear equations," Applied Mathematics and Computation, vol. 217, no. 12, pp. 5259-5264, 2011.

[14] H. Saberi Najafi, S. A. Edalatpanah, and A. H. Refahi Sheikhani, "Application of homotopy perturbation method for fuzzy linear systems and comparison with Adomian's decomposition method," Chinese Journal of Mathematics, vol. 2013, Article ID 584240, 7 pages, 2013.

[15] H. S. Najafi, S. A. Edalatpanah, and N. Vosoughi, "A discussion on the practicability of an analytical method for solving system of linear equations," American Journal of Numerical Analysis, vol. 2, no. 3, pp. 76-78, 2014.

[16] M. A. Noor, K. I. Noor, S. Khan, and M. Waseem, "Modified homotopy perturbation method for solving system of linear equations," Journal of the Association of Arab Universities for Basic and Applied Sciences, vol. 13, no. 1, pp. 35-37, 2013.

[17] D. J. Evans, Preconditioned Iterative Methods, vol. 4 of Topics in Computer Mathematics, Gordon and Breach Science, Lausanne, Switzerland, 1994.

[18] M. Benzi, "Preconditioning techniques for large linear systems: a survey," Journal of Computational Physics, vol. 182, no. 2, pp. 418-477, 2002.

[19] O. Axelsson, "A survey of preconditioned iterative methods for linear systems of algebraic equations," BIT Numerical Mathematics, vol. 25, no. 1, pp. 166-187,1985.

[20] J. P. Milaszewicz, "Improving Jacobi and Gauss-Seidel iterations," Linear Algebra and Its Applications, vol. 93, pp. 161-170, 1987.

[21] A. D. Gunawardena, S. K. Jain, and L. Snyder, "Modified iterative methods for consistent linear systems," Linear Algebra and Its Applications, vol. 154-156, pp. 123-143,1991.

[22] M. Usui, H. Niki, and T. Kohno, "Adaptive Gauss Seidel method for linear systems," International Journal of Computer Mathematics, vol. 51, no. 1, pp. 119-125,1994.

[23] L.-Y. Sun, "Some extensions of the improved modified GaussSeidel iterative method for H-matrices," Numerical Linear Algebra with Applications, vol. 13, no. 10, pp. 869-876, 2006.

[24] L. Wang and Y. Song, "Preconditioned AOR iterative methods for M-matrices," Journal of Computational and Applied Mathematics, vol. 226, no. 1, pp. 114-124, 2009.

[25] H. S. Najafi and S. A. Edalatpanah, "Iterative methods with analytical preconditioning technique to linear complementarity problems: application to obstacle problems," RAIRO-Operations Research, vol. 47, no. 1, pp. 59-71, 2013.

[26] H. S. Najafi and S. A. Edalatpanah, "Modification of iterative methods for solving linear complementarity problems," Engineering Computations, vol. 30, no. 7, pp. 910-923, 2013.

[27] H. Saberi Najafi and S. A. Edalatpanah, "A collection of new preconditioners for solving linear systems," Scientific Research and Essays, vol. 8, no. 31, pp. 1522-1531, 2013.

[28] H. SaberiNajafi and S. A. Edalatpanah, "A new family of (I+S) type preconditioner with some applications," Computational and Applied Mathematics, 2014.

[29] R. S. Varga, Matrix Iterative Analysis, Springer, Berlin, Germany, 2nd edition, 2000.

[30] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, Academic Press, New York, NY, USA, 1994.

[31] A. Frommer and D. B. Szyld, "H-splittings and two-stage iterative methods," Numerische Mathematik, vol. 63, no. 3, pp. 345-356, 1992.

[32] Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, Pa, USA, 2nd edition, 2003.

S. A. Edalatpanah (1) and M. M. Rashidi (2)

(1) Department of Applied Mathematics, Islamic Azad University, Tonekabon Branch, Tonekabon, Iran

(2) Mechanical Engineering Department, Engineering Faculty ofBu-Ali Sina University, Hamedan, Iran

Correspondence should be addressed to S. A. Edalatpanah; saedalatpanah@gmail.com

Received 29 June 2014; Revised 9 October 2014; Accepted 13 October 2014; Published 16 November 2014

Academic Editor: Jose A. Ferreira

Table 1: The results of experiment for Jacobi-HPM. Method Algorithm for Algorithm for q = 1, q = 1, H = I H = (I + S) in (19) n N Iter CPU Iter CPU 5 25 42 0.015893 24 0.003804 10 100 63 0.501852 37 0.231103 15 225 81 8.018167 47 3.844972 20 400 96 71.971452 56 35.328229 Table 2: The results of experiment for Gauss-Seidel-HPM. Method Algorithm for Algorithm for q = 1, q = 1, H = I H = (I + S) in (19) n N Iter CPU Iter CPU 5 25 24 0.007968 10 0.001203 10 100 38 0.255449 17 0.069256 15 225 51 4.428433 22 1.424873 20 400 62 40.541738 27 13.336331

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Edalatpanah, S.A.; Rashidi, M.M. |

Publication: | International Scholarly Research Notices |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 3097 |

Previous Article: | Synthesis, characterization, and thermal kinetics of mixed gadolinium: calcium heptamolybdate system. |

Next Article: | Aspect ratio model for radiation-tolerant dummy gate-assisted n-MOSFET layout. |

Topics: |