HOMOTOPY ANALYSIS METHODSession 2016-2020Submitted byNida Iqbal 2016-CE-63Ayesha Umar 2016-CE-66Submitted toMiss Sehar waqarDepartment of computer science and engineeringUniversity of engineering and technology Lahore-Pakistan?AcknowledgmentsAll praises are due to Allah, the True Lord and Creator of all that exists in the universe and His blessings on the seal of messengers. Foremost, we would like to express our deepest and sincerest gratitude to our supervisor Miss Sehar Waqar for her motivation, patience, and constant support throughout the project period. Her words of encouragement and motivation really helped us in keeping our pace. We could not have envisaged having a better supervisor and mentor for our project.
Not to be forgotten, special thanks to our friends and all those who indirectly make their contribution up to this point. Last but not least, appreciation and gratitude for all our family members who always pray for our success and future. We are nothing without their support, help and protection… Dedicated to ourbeloved parents and respected teachers,who always picked us up on timeand encouraged us to go on every adventure,especially this one…
?Contents Non-linear equations Methods for solving non-linear equations Iterative Method Newton-Raphson Method Secant Method Regula Falsi Method Bisection Method Conclusion Homotopy analysis method Basic concept of homotopy Background of homotopy Homotopy Explanation of homotopy Homotopy Parameter HAM for non-linear equations Maclaurin Series Homotopy derivative Operator Homotopy Series Homotopy Series Solution Deformation Equations Zeroth order deformation equation 1st order deformation equation Newton Iteration Formula Derivation Analysis Examples Newton homotopy continuation method (hcm) Examples Characteristics of homotopy analysis Final Conclusion Homotopy Analysis Method in Nonlinear EquationsNONLINEAR EQUATIONS A nonlinear system of equations is a set of equations where one or more terms have a variable of degree two or higher and/or there is a product of variables in one of the equations.ANALYSIS OF DIFFERENT METHODS USED FOR SOLVING NON-LINEAR EQUATIONSITERATIVE METHODIteration means a process is repeated until an answer is achieved. An iterative procedure may be defined as the trial and error method in which the subsequent trials are selected by a systematic technique for finding the root to a desired accuracy, based on some initial approximation to the real root of f(x) = 0. As finding the root of an equation is equivalent to finding the value of x for which f(x) = 0.Let us proceed to find a real root, say ?, of f(x) = 0.To start with, we need an approximation, say xo to ?. In the simple iterative procedure, one of the ways is to rewrite f(x) = 0 in the following form:X = ?(x) ………. (1)Substituting the value of xo for ? in the right hand side of (1), we proceed as follows:x1 = ?(xo)x2 = ?(x1)x3 = ?(x2).
..Xn+1 = ?(xn); n>=0 ……… (2)If the numbers tend to a limit, then something has achieved:Lt n-> ? = ?(?)Hence, x = ? satisfies the equation (1). This does not mean that we necessarily have not found the root, but under the given conditions we cannot improve approximations using this process. This procedure of finding successive approximations to an initial approximation is called an iterative procedure, each use of this procedure is called an iteration and each approximation achieved is called an iterate.
Disadvantages:Many iterative techniques for the solution of nonlinear equations have the drawback that convergence depends on a good initial value approximation to the solution. Correspondingly, most convergence results only guarantee the existence of a well-defined convergent sequence of iterates for very restricted sets of starting points.NEWTON-RAPHSONThe Newton-Raphson (or simply Newton’s) method is one of the most powerful and well-known method, used for finding a root of f(x) = 0.
We can derive the formula by using the first two terms in the Taylor series expansion of the form, f(xn+1) = f(xn) + (xn+1 – xn)f'(xn)Setting f(xn+1) = gives,f(xn) + (xn+1 – xn)f'(xn) = 0 Thus, on simplification, we get,xn+1 = xn – f(xn) / f'(xn)Advantages:Newton-Raphson method has quadratic convergence order. In practical terms, this means that the number of accurate significant figures is approximately doubled with each iteration. For example, if we start with ine correct digit for an approximation, then after one iteration we should have two correct digits; after three iterations, eight correct digits. So, if proper care has been observed, we need to use Newton-Raphson only three or four times.Disadvantages:Several problems may arise using Newton-Raphson method: xo must often be chosen very close to a root for convergence to the result. F'(x) must not be very easy to compute. This is a major difficulty in this method.
If |f'(x)| is very small compared to |f(x)|, there could be slow convergence or even divergence.SECANT METHODThe secant method is a modified form of Newton-Raphson method. If in Newton-Raphson method, we replace the derivative f'(xn) by the following difference ratio, i.e.,f'(xn) = f(xn) – f(xn-1) / xn – xn-1Where xn and xn-1 are two approximations of the root, we get.xn+1 = xn – f(xn)( xn – xn-1 ) / f(xn) – f(xn-1 )xn+1 = xn f(xn) – xn f(xn-1) – f(xn)(xn – xn-1) / f(xn) – f(xn-1 )xn+1 = xn-1 f(xn) – xn f(xn-1) / f(xn) – f(xn-1)provided f(xn) ? f(xn-1)The secant method requires two starting values xo and x1 ; values of f(xo) and f(x1) are calculated which give two points on the curve. The new point x2 is obtained using above formula. We can continue this process to get better estimates of the root.
So, in this formula, we do not need f'(xn). Disadvantages:Secant method does not always converge. It is likely to have difficulty if f?(?) = 0. This means the x-axis is tangent to the graph of y = f (x) at x = ?REGULA-FALSI METHOD A simple modification of the secant method produces a method which is usually converges. The new method is called Regula Falsi and also linear interpolation.
The formula for the regula falsi is as follows:xn+1 = xn-1 f(xn) – xn f(xn-1) / f(xn) – f(xn-1)The regula falsi method is the same as the secant method, except that the condition f(xn) f(xn-1) ; 0 should meet at each step. Convergence may be more rapid than by the bisection method, but there is no assurance that this will always be the case. The number of iterations required for satisfactory convergence will depend on the shape of the graph of the function in the interval that has been found to contain a root.BISECTION METHOD The bisection method is probably the most primitive procedure for finding a real root of f(x) = 0. This method is very simple, very slow to converge, always works for real roots when there is an odd number of roots in an interval a, b, but the convergence is guaranteed. For this reason, this method is often used for solving non-linear equations.
This method is particularly useful when we have to find the roots using a computer program. Most commercial root finding routines use a combination of the Newton-Raphson and the bisection methods. If one fails to converge, the routines switch to the other method to obtain a new estimate of the root. In some cases to avoid the pitfalls of Newton-Raphson method is to use this combination.
We can use bisection to obtain an estimate of the root and then use Newton-Raphson method to find a more exact solution. Bisection method is also known as the half-interval method and the Bolzano method. Bisection method always converge but the convergence rate of bisection method is slow as it is simply based on halving the interval. Moreover, it is time consuming. CONCLUSIONTo overcome the problems as discussed in the methods above, a new method is introduced which is called homotopy method to solve nonlinear equations. Let us discuss this method in detail.HOMOTOPY ANAYLSIS METHOD Nonlinear equations are difficult to solve, especially analytically.
Perturbation techniques are widely applied in science and engineering, and do great contribution to help us understand many nonlinear phenomena. However, it is well known that perturbation methods are strongly dependent upon small/large physical parameters, and therefore are valid in principle only for weakly nonlinear problems. The so-called non-perturbation techniques, such as the Lyapunov’s artificial small parameter method, the d-expansion method, Adomian’s decomposition method, and so on, are formally independent of small/large physical parameters. But, all of these traditional non-perturbation methods cannot ensure the convergence of solution series: they are in fact only valid for weakly nonlinear problems, too. The homotopy analysis method (HAM) is a general analytic approach to get series solutions of various types of nonlinear equations, including algebraic equations, ordinary differential equations, partial differential equations, differential-integral equations, differential-difference equation, and coupled equations of them. Unlike perturbation methods, the HAM is independent of small/large physical parameters, and thus is valid no matter whether a nonlinear problem contains small/large physical parameters or not. More importantly, different from all perturbation and traditional non-perturbation methods, the HAM provides us a simple way to ensure the convergence of solution series, and therefore, the HAM is valid even for strongly nonlinear problems.
Besides, different from all perturbation and previous non-perturbation methods, the HAM provides us with great freedom to choose proper base functions to approximate a nonlinear problem.BASIC CONCEPT OF HOMOTOPY The Homotopy Analysis method, is another method used to derive an analytic solution for nonlinear operators. It consists of introducing embedding parameters and embedding operators where the solution is assumed to depend continuously on these parameters. The method has been used by several authors and proved to be very effective in deriving an analytic solution of nonlinear differential equations. Let now see how this method works.
BACKGROUN OF HOMOTOPY It is well-known that nonlinear ordinary differential equations and partial differential equations for boundary-value problems are much more difficult to solve than linear differential equations and partial differential equations especially by means of analytic methods due to which we have various methods to solve them There are many methods to solve linear equations, such as newton method, iterative method, bisection method, regula-falsi method, secant method etc. One of the method to solve nonlinear equations is homotopy method. The HAM was first devised in 1992 by Liao Shijun of Shanghai Jiaotong University .After all these methods were purposed, question arises which method should we use.
Solving non-linear equations and optimization requires good initial conditions. Where do there comes from?Nonlinear equations can have multiple roots, optimization problems can have multiple minima. How can we find them all?To answer all these questions let us first examine which method is accurate to fulfill all the conditions.HOMOTOPY Shortly speaking, a homotopy describes a kind of continuous variation or deformation in mathematics. For example, a circle can be continuously deformed into a square or an ellipse.
Homotopy defines a connection between different things in mathematics.”A homotopy between two continuous functions f (x) and g(x) from a X to Y is formally defined to be a continuous function H : X × 0,1?Y From the product of the space X with the unit interval 0,1 to Y such that, if x ? X then H (x;0) = f (x) and H (x;1) = g(x).”EXPLANATIONLet C a , b denote a set of all continuous real functions in the interval a ? x ? b.In general, if a continuous function f ? C a , b can be deformed continuously into another continuous function g ? C a, b , one can construct a homotopyH : f (x) ? g(x)in the way H ( x ; q ) = (1?q) f (x)+ (q)g(x), x ? a,bwhere q ? 0,1 is called the embedding parameter. Note that H ( x ; q ) depends on not only the independent variable x ? 0,1 but also the embedding parameter q ? 0,1.
Especially, when q = 0, we haveH ( x ; 0 ) = f(x) , x ? 0,1,and when q = 1, it holdsH ( x ; 1 ) = g(x), x ? 0,1,respectively. So, as the embedding parameter q ? 0,1 increases from 0 to 1, the real function H ( x ; q ) varies continuously from a f(x) to g(x).HOMOTOPY PARAMETERThe embedding parameter q ? 0,1 in a homotopy of functions or equations is called homotopy-parameterTHE HOMOTOPY ANALYSIS METHOD FOR THE SOLUTION OF THE NONLINEAR DIFFERENTIAL EQUATION Now we will see how we can solve a non-linear equation by homotopy method. The basic steps which are involved in this procedure are:Let us first consider a nonlinear algebraic equationf (x) = 0where f (x) ? C a , b is a continuous real function. Assume that the above equation has at least one solution which lies in the region x ? a ,b. Let x0 ? a , b denote an initial guess of the unknown solution x. Obviously, f (x)? f (x0) ? C a , b can be deformed continuously to f (x) ? C a , b , i.e.
they are homotopic. Thus, we can construct such a homotopy of function H ( x ; q ) = (1?q ) f (x)? f (x0) + q f (x)………(1)where q ? 0,1 is the embedding parameter or homotopy-parameter.When q = 0 we have H ( x ; 0 ) = f (x)? f (x0)and q = 1, we have H ( x ; 1 ) = f (x)We observed that as q increases from 0 to 1, H ( x ; q ) varies continuously from f (x)? f (x0) to f(x).
Now taking H ( x ; q ) = 0 , equation (1) becomes(1?q ) f (x)? f (x0) + q f (x) = 0………….(2)Now as we can see that the solution of above equation does not only depends on x , but also on embedding parameter q , so we can replace it as x = ?x (q) , so equation 2 can be written as (1?q ) f (?x (q)) ? f (x0) + q f (?x (q)) = 0………(3)When q = 0 , we have f (?x (0)) ? f (x0) = 0Whose solution is ?x (0) = x0When q = 1 , we have ?x (1) = 0which is exactly the same as the original algebraic equation f (x) = 0. ?x (1) = xSo we observed that as the homotopy-parameter q increases from 0 to 1, ? x(q) deforms from the initial guess x0 to the solution x of the original equation f (x) = 0. So, Equation(2) defines a homotopy of function ?x(q) : x0 ? x Equations (2) is called the zeroth-order deformation equation, because it defines a continuous deformation from the initial guess x0 to the solution x of the original equation f (x) = 0.MACLAURIN SERIESBecause ?x(q) is now a function of the homotopy-parameter q, we can expand it into Maclaurin series ?x(q) = x0 +???(+?@k=1) xk qk ………………(4) Where ?x (0) = x0 is employed xk=1/k! (dk?x (q)/dqk)|q=D ?x(q)………….
(5)Here, the series equation (4) is called homotopy-Maclaurin series.HOMOTOPY DERIVATIVE OPERATOR Dk is called the homotopy derivative operator, and Dk ?x(q) is called the kth-order homotopy-derivative of x(q) . HOMOTOPY SERIES Hence equation (3) is called homotopy seriesHOMOTOPY SERIES SOLUTION Then the homotopy series) is convergent at q = 1 to ?x(1) Thus, using the relationship ?x(1) = x, we have the so-called homotopy-series solution ?x(q) = x0 +???(+?@k=1) xk DEFORMATION EQUATIONSZEROTH- ORDER DEFORMATION EQUATION Given an equation denoted by E1, which has at least one solution. Let E0 denote a proper, simpler equation, called the initial equation, whose solution u0 is known. If one can construct such a homotopy of equationE(q) : E0 ? E1 that, as the homotopy-parameter q ? 0,1 increases from 0 to 1, E(q) deforms (or varies) continuously from the initial equation E0 to the original equation E1, while its solution varies continuously from the known solution u0 of E0 to the unknown solution u of E1, then this kind of homotopy of equations is called the zeroth-order deformation equation.1ST- ORDER DEFORMATION EQUATION According to the fundamental theorem in calculus about Taylor series, the coefficient xk of the homotopy-Maclaurin series is unique. Therefore, the governingequation of xk is unique, too, and can be deduced directly from the zeroth-order deformation equation.The zeroth order deformation equation is(1?q ) f (?x (q)) ? f (x0) + q f (?x (q)) = 0Solving it we have f (?x (q)) ? f (x0) ?q f (?x (q) + qf (x0) +q f (?x (q)) =0Now, differentiating the zeroth-order deformation with respect to the homotopy-parameter q, we have f'(?x (q)) (d(?x (q)))/dq + f(x0) = 0Then, setting q = 0 in the above equation and using the relationship ?x (0) = x0, we have f'(?x (q)) (d(?x (q)))/dq |q =0 + f(x0) = 0According to the definition in equation (5) we hav (d(?x (q)))/dq |q =0 = x1Thus, we obtain the so-called 1st-order deformation equation x1 f ?(x0)+ f (x0) = 0whose solution is x1 = ( f (x0))/(f '(x0))DERIVATION OF NEWTON ITERATION FORMULA Now for the derivation of newton iteration formula we have:We have the 1st-order homotopy-approximation x ? x0 +x1 = x0 – ( f (x0))/(f '(x0))………(6)Note that (6) is exactly the famous Newton’s iteration formula.
In fact, one cangive a family of iteration formulas in a similar way. This shows the potential of thehomotopy approach.ANALYSISThe above approach has some interesting characteristics. First of all, it is independent of any physical parameters at all: no matter whether a nonlinear problem contains small/large physical parameters or not, one can always introduce the homotopy-parameter q ? 0,1 to construct a zeroth-order deformation equation and then to obtain the homotopy-series solution or a homotopy approximation. Secondly,as mention above, all high-order deformation equations are linear and thus are easy to solve.
In this way, this approach transforms a nonlinear equation into an infinite number of linear sub-problems, but without any small/large physical parameters. Giving up the dependence on small/large physical parameters, the HAM can be applied to solve more complicated nonlinear problems.EXPLANATION OF HOMOTOPY THROUGH EXAMPLES Let us now explain the above theory through some examples.
EXAMPLE: 1 Let us consider an example of two functionsFor example, the two different real functions sin(?x) and 8x(x?1) in the intervalx ? 0,1 can be connected by homotopy ( x ; q ) = ( 1 – q ) sin (?x) + q 8 x (1?x) when q = 0, we haveH ( x ; 0 ) = sin(?x ) , x ? 0,1,and when q = 1, it holdsH ( x ; 1) = 8 x (x?1), x ? 0,1,So, as the embedding parameter q ? 0,1 increases from 0 to 1, the real function H ( x ; q ) varies continuously from a trigonometric function sin(?x) to a polynomial 8x(x?1).H( x ; q ) is called a homotopy, sin(?x) and 8x(x?1) are called homotopic, denoted byH : sin(?x) ? 8x(x?1).The concept of 1ST order homotopy derivative is given as H ( x ; q ) = sin(?x)+8x(x?1)?sin(?x) q and thus we have dH ( x ; q )/d q= 8x(x?1)?sin(?x), q ? 0,1,This is called called the 1st-order homotopy-derivative Fig:1 Continuous deformation of the homotopyH (x;q) : sin(p-x)?8x(x?1). Dashed line: q = 0; Dot dashed line: q = 1/4; Solid line: q = 1/2; Dot-dot-dashed line: q = 3/4; Long-dottedline: q = 1.EXAMPLE: 2 Let us now consider another example of two equationsE (q): (1+3q) x2 + (y2 /(1+3q))= 1, q ? 0,1When q = 0, we have the circle equation E0 : x 2 + y2 = 1whose solution is a circle y = ± ?(1-x)2When q = 1, we have the ellipse equationE1: 4×2+y2/4 = 1 whose solution is an ellipse y = ±2?(1-4x)2So, more precisely speaking, the solution y of is dependent not only on x but also on q ? 0,1, and thus it should be expressed more precisely in the formE (q): (1+3q) x2+ (y2 x ; q ) / (1+3q)) = 1, q ? 0,1The concept of zeroth-order deformation equation given as In other words, the solution y (x ; q ) also a homotopy , so Y (x; q) = ± ?(1-x)2 ~ ±2?(1-4x)2This forms the zeroth-order deformation equation. Fig 2: Continuous deformation of the solution y(x;q) ofthe homotopy equation Solid line: q = 0; Dashed line:q = 1/4; Dash-dotted line:q = 1/2; Dash-dot-dotted line q = 1.NEWTON HOMOTOPY CONTINUATION METHOD (HCM)Homotopy continuation method (HCM) provide a useful approach to find the zeros of each function in term of convergent way in finding the approximate solutions.
Here are also several HCMs such as Newton-HCM, secant-HCM For basic learning purpose, we choose Newton-HCM as our method to solve nonlinear equations. The formula of Newton-HCM can be written as followsH(x , q) = (1-q)g(x) + qf(x)H(x, 0) = g(x) = initial start systemH(x , 1) = f(x) = target solutiong(x) = x- x0xi+1 = xi – (H (xi ,q))/(H '(xi,q))where i = 1 , 2, 3….. and q ? 0 , 1STEPSThe steps to find the root of nonlinear equation we have following steps To find a solution of f(x) = 0 by using Newton Homotopy Continuation Method, starting with one initial guess x0 Initially apply the formula given above with xi = x0 and q = 0 Then you will get new xi , also increase the value of q after every iteration by the difference of 0.1 or by any difference Stop the iteration when you get , the answer up to your given toleranceEXPLANATION THROUGH EXAMPLE Let us take an example of a nonlinear equation and solve it by newton method and newton homotopy continuation method. F(x) = x2 + 8x – 9Solution By solving with quadratic formula the roots are 1 and -9 Below is the table in which in have put the results of newton method and newton homotopy continuation method.Taking initial guess x0= -3 G(x) = x- a a = x0TABLENewton method Newton HCM X0 = -3 X0 = -3X1 = 9 X1 = 0.
70634741359X2 = 3.4615323987 X2 = 1.00000000070X3 = 1.4046045789 X4 = 1.01522344566 X5= 1.00002317845 X6 = 1.00000006780 OBSERVATIONSThe results from Table shows performance of Newton method and Newton-HCM when both methods are implemented at x0 = -3.
Newton’s method requires six iterations whilst Newton-HCM needs only two iterations to converge to the actual root GRAPH Fig 3: Performance of no. of iterations required for Newton method and Newton-HCMOTHER EXAMPLESNow for better understanding let us take some more examples F(x) = 1/3×3 – 1/2×2 -6x + 2 = 0Initial value Newton method Newton HCM-4 Diverge 3-3 6 2 F(x) = x4 + 6x – 40 = 0Initial value Newton method Newton HCM-2 Diverge 33 Diverge 3 F(x) = x5 + x4- x2 – 7x + 4Initial value Newton method Newton HCM-1 13 40 9 3 F(x) = x-cosx = 0Initial value Newton method Newton HCM1 Diverge 310 12 4CONCLUSIONBased on the results for seven examples of nonlinear equations, Newton homotopy continuation method can solve the drawbacks of newton method. Note that homotopy continuation method can solve the divergence problem for nonlinear equations and it has lesser number of iterations.
The number of iterations required is measured based on stopping criterion specified. The best method is measured based on which method has lesser number of iterations. Obviously, we can see this benefit from the result of Newton homotopy continuation method.CHARACTERISTICS OF HOMOTOPY ANALYSIS METHOD (HAM)The HAM distinguishes itself from various other analytical methods in four important aspects. It is a series expansion method that is not directly dependent on small or large physical parameters. Thus, it is applicable for not only weakly but also strongly nonlinear problems, going beyond some of the inherent limitations of the standard perturbation methods. The HAM gives excellent flexibility in the expression of the solution and how the solution is explicitly obtained. It provides great freedom to choose the basis functions of the desired solution and the corresponding auxiliary linear operator of the homotopy.
Unlike the other analytic approximation techniques, the HAM provides a simple way to ensure the convergence of the solution series.The homotopy analysis method is also able to combine with other techniques employed in nonlinear differential equations. It may further be combined with computational methods, to allow the linear method to solve nonlinear systems. Different from the numerical technique of homotopy continuation, the homotopy analysis method is an analytic approximation method as opposed to a discrete computational method. Further, the HAM uses the homotopy parameter only on a theoretical level to demonstrate that a nonlinear system may be split into an infinite set of linear systems which are solved analytically, while the continuation methods require solving a discrete linear system as the homotopy parameter is varied to solve the nonlinear system.The HAM is always valid no matter whether there exist small physical parameter or not. It provides a convenient way to guarantee the convergence of approximation series and great freedom to choose the equation type of linear sub-problems and the base functions of solution.
The HAM methods overcome the problem that convergence depends on only good initial value approximation. Moreover it is producing solutions over a large range of the independent variables. This is a tool in overcoming the local convergence of iterative processes. This method is used to widen the domain of convergence or a procedure to obtain the good starting points. FINAL CONCLUSIONHAM overcomes the problem we are facing in old methods for solving non-linear equations.
But it must be emphasized that the HAM is not valid for all nonlinear problems, since our aim is to develop an analytic approach valid for as many nonlinear problems as possible only. It is even an open question if there exists an analytic approximation method valid for all nonlinear problems. In essence, it is rather hard to understand complicated nonlinear phenomena, especially those related to chaos and turbulence. However, although nonlinear ODEs and PDEs are still more difficult to solve than linear ones, the HAM provides us a useful, alternative tool to investigate them.REFERENCE: https://www.
researchgate.net/publication/301776880_Newton_Homotopy_Continuation_Method_for_Solving_Nonlinear_Equations_using_Mathematica accessed May 12, 2018. https://en.wikipedia.org/wiki/Homotopy_analysis_method accessed April 30, 2018. https://www.sciencedirect.com/science/article/pii/S089396591000193X accessed May 12, 2018.
http://numericaltank.sjtu.edu.
cn/IntroductionHAM.htm accessed May 2, 2018. https://www.researchgate.net/publication/265088900_Iterative_Methods_for_Nonlinear_Equations_Using_Homotopy_Perturbation_Technique accessed May 10, 2018.
https://pdfs.semanticscholar.org/a495/32b5fb6547e77b796533d5c0fa8141f413e0.pdf accessed May 5, 2018.
https://www.researchgate.net/publication/301776880_Newton_Homotopy_Continuation_Method_for_Solving_Nonlinear_Equations_using_Mathematica accessed May, 11 2018. A first course in numerical analysis with C++ by SA Bhatti accessed April 30, 2018. Homotopy Analysis Method in Nonlinear Differential Equations by Shijun Liao accessed May 3, 2018.
