ABSTRACT
The traditional Newton method is a well-known and popular method for solving non-linear equation. It has high efficient in the convergence speed. However, we always need to guess the initial value in the iteration process. Good initial guess value can solve the equation quickly. Bad initial guess value usually will yield divergence. Homotopy continuation method is a kind of perturbation method. It can guarantee the answer by a certain path if we choose the auxiliary homotopy functions, or call the start system, well. This study presents some useful techniques for the choice of the auxiliary homotopy functions to avoid divergence and time-consuming computation when solving the planar and spatial simultaneous non-linear equations.
PDF Abstract XML References Citation
How to cite this article
DOI: 10.3923/jas.2005.1036.1040
URL: https://scialert.net/abstract/?doi=jas.2005.1036.1040
INTRODUCTION
Homotopy continuation method was known as early as in the 1930s. This method was used by kinematician in the 1960s at U.S. for solving mechanism synthesis problems. The latest development was done by Morgan[1,2] at GM. We also have two important literatures: Garcia[3] and Allgower[4]. Continuation method gives a set of certain answers and some simple iteration process to obtain our solutions more exactly. Wu[6] provided some rules for the choice of the auxiliary homotopy functions to avoid divergence of traditional Newton method for one-dimensional non-linear algebraic equation. Wu[5] also applied the homotopy continuation method to search all the roots of inverse kinematics problem of robot and obtained more but not all convergence answers than the traditional numerical methods. Therefore, present research attempts to study some robust rules and provide the choice method of the auxiliary homotopy functions for homotopy continuation method to avoid the problem of divergence of traditional Newton method when solving the non-linear equations.
NEWTON-HOMOTOPY CONTINUATION METHOD
Before the study of the auxiliary homotopy functions, we consider the following simultaneous non-linear equations
(1) |
To solve the equations system, we have many different methods such as Newton-Raphson method, etc. As we known, the numerical iteration formula of Newtons method for solving the equations system was given as:
(2) |
Observing Eq. 2, we find that when the determinant
(3) |
The [Δx1, Δx2, , Δxn]T values will become infinite. Now, we will apply the homotopy continuation method and develop some useful techniques for the choice of the auxiliary homotopy functions to avoid divergence of iteration results in Eq. 2.
Given a set of equations in n variables x1, x2, , xn. We modify the equations by omitting some of the terms and adding new ones until we have a new system of equations, the solutions to which may be easily guessed/given/known. We then deform the coefficients of the new system into the coefficients of the original system by a series of small increments and we follow the solution through the deformation, using methods such as Newton-Raphson. This is called Newton-homotopy continuation original system.
If we wish to find the solution vector in Eq. 1, we choose a new simple start system or call the auxiliary homotopy functions:
(4) |
The auxiliary homotopy functions F(X) must be known or controllable and easy to solve. Then, we define the homotopy continuation as:
(5) |
Where t is an arbitrary parameter and varies from 0 to 1, i.e. t∈[0,1]. Therefore, we have the following two boundary conditions
(6) |
This is the famous homotopy continuation method. It is also called Bootstrap method or Parameter-Perturbation method, but these names did not become popular.
Our goal in this study is to solve H(X,t) = 0 instead of F(X) = 0 by varying parameter t from 0 to 1 and avoid the situation of divergence. So we rewrite Eq. 2 as:
(7) |
Where the situation of divergence still may occurs at
(8) |
To avoid divergence, we have to let Det(H) ≠ 0 or not → 0. In this study, we develop a new technique for this purpose.
Planar problem: Firstly, consider the planar problem
(9) |
The determinant Det(H) therefore is
(10) |
Where,
(11) |
If we let A-B+C = 0 and B-2C = 0, we can avoid many situations of divergence and economize the computation time. This technique yields
(12) |
To satisfy this equation, we have four cases. They are
(13) |
But case 1 or case 2 will yield useless result, i.e. f = f, g = g. Since the auxiliary homotopy functions f and g must be different from the original functions f and g. Hence we just can apply case 3 or case 4. If we choose case 3, then we have
(14) |
Substituting this equation into A = C, we obtain the following formula for the choice of the auxiliary homotopy functions f and g
(15) |
So we conclude that
(16) |
By this way, the determinant Det(H) becomes only f1g2 - f2g1. Therefore, we only need to judge and avoid this form not equal to zero or not approach to infinite to guarantee the convergence.
Spatial problem: Secondly, consider the spatial problem
(17) |
The determinant Det(H) is
(18) |
We would like to apply the character developed in planar problem, so we must expand the Det(H) as the combination of three two-order forms.
(19) |
By the same manner, the three two-order forms can be expressed as:
(20) |
Where:
(21) |
Similarly, we let Ai-Bi+Ci = 0 and Bi-2Ci = 0, i = 1,2,3. We can also obtain the following formula for the choice of the auxiliary homotopy functions f, g and h
(22) |
And
(23) |
Also the determinant Det(H) will become
(24) |
Above are the techniques for choosing the appropriate auxiliary homotopy functions F(X). In the following section, we will run two examples to compare the improved Newton-homotopy method and traditional Newton method.
Example 1: Consider a planar robot defined by Wu[5]:
(25) |
Where, C = Cos, S = Sin. L1, L2, Px and Py are givens and assuming that L1 = 2, L2 = 1, Px = -1, Py = 1.5. θ1 and θ2 are unknowns. By the formula, we have
(26) |
The divergence condition f1g2 - f2g1 in this example is:
(27) |
Since the domain θ1,θ2∈[0°,360°], we have the singular points (θ1,θ2) = (0°,0°), (180°,0°) or (360°,0°) in the above equation.
Table 1: | The number of divergence of the traditional Newton and the improved Newton-homotopy method |
Solving Eq. 26 by the Newton-homotopy iteration formula, Eq. 7 and avoiding the three singular points, we obtain the number of divergence of the traditional Newton and the improved Newton-homotopy method, respectively in Table 1.
Observing Table 1, we find that the number of divergence will increase with the initial guesses increasing in the traditional Newton method. Whereas, we can guarantee the convergence whatever how many initial guesses we have in the improved Newton-homotopy method just only the singular points being eliminated.
Example 2: Consider a spatial robot defined by Wu[5]:
(28) |
Where, L, Px, Py and Py are givens and their values are assumed that L = 2, Px = -2, Py = 1.5, Pz = 1. θ1, θ2 and S are unknowns, their domains in this example are θ1,θ2∈[0°,360°] and S∈[-3,3], respectively. Using formula (23), we have
(29) |
According to Eq. 24, the determinant Det(H) is
(30) |
By means of the domains of θ1,θ2 and S, we obtain the singular points occur at initial condition t = 0, i.e. initial singular point guesses, are S = 0 or S = -2tanθ2.
Similarly, solving Eq. 29 by the Newton-homotopy iteration formula, Eq. 7, and avoiding these initial singular point guesses, we obtain the number of divergence of the traditional Newton and the improved Newton-homotopy method respectively in Table 1 (dS = 1).
Clearly, we also find the use of traditional Newton method will easily become divergence when the bad initial guesses been chosen. However, this situation can be avoided in the improved Newton-homotopy continuation method.
CONCLUSIONS
Typically, it is usually a big trouble and disadvantage for us to do the algebraic operation, for example, solving the non-linear equations. Fortunately, by the aid of computer science, the non-linear equations will be solved no more difficulty. With the computer improved and the numerical technique developed, the solutions of non-linear equations become easier. We can use current high-speed processor to determine the solutions quickly.
Although, we already have many different numerical methods can help us to treat these non-linear equations. The traditional Newton-Raphson method is a popular numerical method. However, it still has some well-known critical defects. By means of the development of numerical continuation technique, the defects in traditional numerical methods such as the acquirement of a good initial guess, the problems of convergence and the computing time will be avoided. Homotopy continuation method is one of the famous improved numerical continuation methods. Its convergence speed is fast, also the algorithm is clear and easy.
This study combines Newtons and homotopy continuation method and proposes some robust rules for the choice of the auxiliary homotopy function for the Newton-homotopy continuation method to avoid the problem of divergence of many traditional numerical methods when solving the non-linear equations. We can get well outcome by this new method. The new interesting method will provide another numerical approach. It is hoped that the study presented here will contribute towards progress in the numerical techniques and other relative fields for scientists or engineers.
REFERENCES
- Wu, T.M., 2005. Searching all the roots of inverse kinematics problem of robot by homotopy continuation method. J. Applied Sci., 5: 666-673.
CrossRefDirect Link - Wu, T.M., 2005. A study of convergence on the newton-homotopy continuation method. Applied Math. Comput., 168: 1169-1174.
Direct Link