Preface


This section gives an introduction to the homotopy pertubation method, first proposed by Ji-Huan He in 1998.

Return to computing page for the first course APMA0330
Return to computing page for the second course APMA0340
Return to Mathematica tutorial for the second course APMA0340
Return to the main page for the course APMA0330
Return to the main page for the course APMA0340
Return to Part III of the course APMA0330

Homotopy method


Ji-Huan He.
To find the solution x* of a nonlinear equation
\[ f(x) =0 \]
in the interval I = [a, b], we consider the homotopy
\[ H(x,p) = p\, f(x) + \left( 1- p \right) g(x) , \qquad x\in I, \quad p \in [0,1], \]
which is a mapping I × [0,1] ↦ I. Here g(x) is an auxiliary function for which we know the solution g(x) = 0, and p is an embedding parameter. Usually, the function g is chosen in two forms: It is obvious that
\[ H(x,0) = g(x) = 0, \qquad H(x,1) = f(x) = 0, [0,1], \]
and the changing process of p from 0 to 1 corresponds to moving H(x, p) from g(x) to f(x). In topology, this is called deformation.

Assuming that p is a small parameter from the interval [0,1], we can assume that the zero of the function H(x, p) can be expressed as a series in p:

\[ x= x_0 + p\,x_1 + p^2 x_2 + p^3 x_3 + \cdots . \]
When p &maps; 1, we obtain (hopefully) the true solution of f(x) = 0, that is,
\[ x^{\ast} = \lim_{p\to 1} x = x_0 + x_1 + x_2 + x_3 + \cdots . \]
To obtain its approximate solution of H(x, p) = 0, we first expand it into Taylor series
\begin{align*} f(x) &= f(x_0 ) + f' (x_0 ) \left( p\,x_1 + p^2 x_2 + p^3 x_3 + \cdots \right) + \frac{1}{2!}\,f'' \left( x_0 \right) \left( p\,x_1 + p^2 x_2 + p^3 x_3 + \cdots \right) + \cdots , \\ g(x) &= g\left( x_0 \right) + g' \left( x_0 \right) \left( p\,x_1 + p^2 x_2 + p^3 x_3 + \cdots \right) + \frac{1}{2!}\,g'' \left( x_0 \right) \left( p\,x_1 + p^2 x_2 + p^3 x_3 + \cdots \right) + \cdots . \end{align*}
Substituting these expansions into the equation H(x, p) = 0 and equating the coefficients of like powers of p, we get
\begin{align*} p^0 \,&: \ g\left( x_0 \right) =0; \\ p^1 \,&: \ g'\left( x_0 \right) x_1 + f\left( x_0 \right) - g\left( x_0 \right) =0; \\ p^2 \,&: \ g'\left( x_0 \right) x_2 + \left[ f'\left( x_0 \right) - g'\left( x_0 \right) \right] x_1 + \frac{1}{2}\, g'' \left( x_0 \right) x_1^2 =0; \\ p^3 \,&: \ g'\left( x_0 \right) x_3 + \left[ f'\left( x_0 \right) - g'\left( x_0 \right) \right] x_2 + \frac{1}{2}\left[ f'' \left( x_0 \right) - g'' \left( x_0 \right) \right] x_1 + \frac{1}{3!}\, g''' \left( x_0 \right) x_1^3 =0; \end{align*}
and so on. If \( g'\left( x_0 \right) \ne 0 , \) then the above equations can be solved to obtain
\begin{align*} x_0 & \ \mbox{ is exact null of the auxiliary function } \ g(x) = 0; \\ x_1 &= - \frac{f\left( x_0 \right)}{g'\left( x_0 \right)} ; \\ x_2 &= \frac{\left[ g'\left( x_0 \right) - f'\left( x_0 \right) \right] x_1 - \frac{1}{2}\, g'' \left( x_0 \right) x_1^2}{g'\left( x_0 \right)} ; \\ x_3 &= \frac{\frac{1}{2} \left[ g'' \left( x_0 \right) - f'' \left( x_0 \right) \right] x_1 - \left[ f'\left( x_0 \right) - g'\left( x_0 \right) \right] x_2 - g'' \left( x_0 \right) x_1 x_2 - \frac{1}{3!}\, g''' \left( x_0 \right) x_1^3}{g'\left( x_0 \right)} . \end{align*}
Particularly, if we choose the function \( g(x) = f(x) - f\left( x_0 \right) , \) where x0 is an initial approximation, then
\begin{align*} x_1 &= - \frac{f\left( x_0 \right)}{g'\left( x_0 \right)} ; \\ x_2 &= - \frac{1}{2!}\,\frac{f'' \left( x_0 \right)}{f'\left( x_0 \right)} \, x_1^2 = - \frac{1}{2!}\,\frac{f'' \left( x_0 \right)}{f'\left( x_0 \right)} \left\{ \frac{f\left( x_0 \right)}{g'\left( x_0 \right)} \right\}^2 ; \\ x_3 &= - \frac{1}{2!}\,\frac{f'' \left( x_0 \right)}{f'\left( x_0 \right)} \, x_1 x_2 - \frac{1}{3!} \, \frac{f''' \left( x_0 \right)}{f'\left( x_0 \right)} \, x_1^3 . \end{align*}
Therefore, we can obtain
\[ x= x_0 + x_1 \quad\mbox{with first order approximation}, \]
and
\[ x= x_0 + x_1 + x_2 \quad\mbox{with second order approximation}, \]
and
\[ x= x_0 + x_1 + x_2 + x_3 \quad\mbox{with third order approximation}, \]
From above, we can write down the iteration forms:
\begin{align*} x_{n+1} &= x_n - \frac{f\left( x_n \right)}{f'\left( x_n \right)} ; \\ x_{n+1} &= x_n - \frac{f\left( x_n \right)}{f'\left( x_n \right)} - \frac{f'' \left( x_n \right)}{2\,f'\left( x_n \right)} \left\{ \frac{f\left( x_n \right)}{f'\left( x_n \right)} \right\}^2 ; \\ x_{n+1} &= x_n - \frac{f\left( x_n \right)}{f'\left( x_n \right)} - \frac{f'' \left( x_n \right)}{2\,f'\left( x_n \right)} \left\{ \frac{f\left( x_n \right)}{f'\left( x_n \right)} \right\}^2 + \left\{ \frac{f''' \left( x_n \right)}{6\, f'\left( x_n \right)} - \frac{1}{2} \left[ \frac{f'' \left( x_n \right)}{f' \left( x_n \right)} \right]^2 \right\} \left\{ \frac{f\left( x_n \right)}{f'\left( x_n \right)} \right\}^3 . \end{align*}
Obviously, the first iteration formula is the well-known Newton's iteration formula. In order to avoid computing derivatives, we replace \( f'\left( x_n \right) \) and \( f'' \left( x_n \right) \) by the centered differences
\[ \frac{f \left( x_n +h \right) -f \left( x_n -h \right) }{2h} \qquad\mbox{and} \qquad \frac{f \left( x_n +h \right) + f \left( x_n -h \right) - 2\,f \left( x_n \right)}{h^2} , \]
respectively, where \( h = \alpha\, f\left( x_n \right) \) is a step size and α ≠ 0 is a parameter. So we get the following second-order iterative method:
\[ x_{n+1} = x_n - \frac{2h\,f\left( x_n \right) }{f\left( x_n +h \right) - f\left( x_n -h \right)} \]
and the third order iterative method
\[ x_{n+1} = x_n - \frac{2h\,f\left( x_n \right) }{f\left( x_n +h \right) - f\left( x_n -h \right)} - \frac{4h\,f^2 \left( x_n \right) \left[ f\left( x_n +h \right) + f\left( x_n -h \right) -2\,f\left( x_n \right) \right]}{\left[ f\left( x_n +h\right) - f\left( x_n -h \right) \right]^3} , \]
respectively.

Example: Suppose that we need to solve the rtanscendent equation

\[ e^{\cos x} -1-x =0 , \qquad x\in [0,1]. \]
Of course, Mathematica can find its root:
FindRoot[Exp[Cos[x]] == 1 + x, {x, 1}]
{x -> 0.884511}
which is an approximation to 0.8845106161658526.    ■

Example: Solve the polynomial equation

\[ x^9 = 1+x \quad\mbox{in the interval} \quad [1,2]. \]
FindRoot[x^9 == 1 + x, {x, 1}]
{x -> 1.08507}
which is an approximation to 1.085070245491451.    ■

 

  1. Chun, C., Ham, Y.M., Some fourth-order modifications of Newton’s method, Applied Mathematics and Computation, 2008, Vol. 197, pp. 654--658.
  2. Feng, X.L., He, Y.N., High order iterative methods without derivatives for solving nonlinear equations, Applied Mathematics and Computation, 2007, Vol. 186, pp. 1617--1623.
  3. He, J.H., A new iterative method for solving algebraic equations, Applied Mathematics and Computation, 2003, Vol. 135, pp. 81--84. https://doi.org/10.1016/S0096-3003(01)00313-7
  4. Ide, N.A.D., Some new iterative algorithms by using homotopy pertubation method for solving nonlinear algebraic equations, Asean Journal of Mathematics and Compute Research, No 2395-4205 (online), Vol. 5, Issue 3. 2015.
  5. Noor, M.A., Some iterative methods for solving nonlinear equations using homotopy perturbation method, International Journal of Computer Mathematics, Vol. 87, No. 1, January 2010, pp. 141–149

 

Return to Mathematica page
Return to the main page (APMA0330)
Return to the Part 1 (Plotting)
Return to the Part 2 (First Order ODEs)
Return to the Part 3 (Numerical Methods)
Return to the Part 4 (Second and Higher Order ODEs)
Return to the Part 5 (Series and Recurrences)
Return to the Part 6 (Laplace Transform)
Return to the Part 7 (Boundary Value Problems)