Paper received: 17.5.2007 Paper accepted: 19.12.2007
Hyper-Chaotic Mapping Newton Iterative Method to Mechanism Synthesis
Youxin Luo1 - Xianfeng Fan2 - Dazhi Li1 - Xiao Wu1 'Hunan University of Arts & Science, Department of Mechanical Engineering, P.R.China University of Ottawa, Department of Mechanical Engineering, Canada
The synthesis and approximate synthesis problems for planar mechanism can be transformed into a system of multivariablepolynomial equations or general nonlinear equations. Newton iterative method is an important technique to one dimensional and multidimensional variables and iterative process exhibits sensitive dependence on initial guess point. Based on utilizing multi-start point technique and hyper-chaotic mapping (Henon hyper-chaotic system) as initial points of Newton iterative method, an innovative new method to find all solutions of general nonlinear equations in kinematics quickly and effectively was proposed. The computing step and method was given. The numerical examples in linkage synthesis and approximate synthesis show that the method is correct and effective.
© 2008 Journal of Mechanical Engineering. All rights reserved.
Keywords: hyper-chaotic systems, linkage mechanism, mechanism synthesis, nonlinear equations
0 INTRODUCTION
Kinematic motion analysis and design of mechanical systems lead naturally to system of nonlinear algebraic and/or transcendental equations. One of the most frequently occurring problems in kinematics is to find solutions to this system of equations [1] and [2]. The research of analysis and synthesis for planar mechanisms refers the solution of nonlinear equations and this has not commendably resolved [3]. How to find out all solutions of nonlinear equations quickly and effectively is important to mechanisms analysis & synthesis and engineering fields, so mathematics worker and engineering expert have paid attention to it. The solution approaches for such equations can be broadly divided into two classes: closed-form (analytical) techniques and numerical (iterative) methods.
Analytical or closed-form solutions to kinematics equations can be obtained by using elimination theories based on resultants [4], Grobner-Sylvester hybrid method [1] and [5] to [7] or Wu elimination [6] and [7] and so on. The analytical solution approaches entail successive elimination of problem unknowns to reduce a multivariable system into a single variable equation or triangular equations. These can find all solutions.
*Corr. Author's Address: Hunan University of Arts &
In elimination process with resultant, it may be possible to express the resultant as a quotient of one determinant divided by another. The divisor is the extraneous factor. Since it is difficult to identify whether or not extraneous factors exist, it is impossible to insure that a resultant is devoid of extraneous solutions. For homogeneous systems, extraneous factors can be identified and eliminated as demonstrated by Macaulay [8]. However, problems arising in synthesis and analysis of mechanism often result in a system of non-homogeneous polynomials. Hence, Macaulay's approach is not suitable for such problems because the system of equations has extraneous solutions including solutions at infinity, and thus the eliminant matrix is degenerate [1]. For kinematics problems of "reasonable" complexity [1], Wu elimination method, Grobner base method are quite inefficient because of their excessive computation times and exploding intermediate results [1] and
[8].	For a comprehensive contents of Grobner base method and Wu elimination method see [6] to [8]. Specially, in general, analytical or closed-form solutions are effective to polynomial equations.
The numerical (iterative) methods mainly include Newton method and its improved methods
[9]	and [10], continuation iteration method [9] to [11], interval analysis method [12], universal gray
Science, Department of Mechanical Engineering, Changde,
Hunan, 415000, P.R.China, LLyx123@126.com
analysis method [13] to [15], optimum method [10] and [16] and so on. These numerical methods are adaptive to polynomials equations as well as non-polynomials equations in kinematics. Using numerical methods, a kinematics problem is considered solved if a tight upper bound on the number of solutions can be established, and an efficient algorithm for computing all solutions can be implemented. The commonly used iterative methods are variants of the Newton, conjugate gradient methods or optimum methods. These methods require an initial guess to the solution. If the initial guess is not close enough to a solution, the iterations may converge slowly, converge to an unacceptable solution or may diverge altogether, and, in general, these methods can only find a solution. However, Newton's method is a valuable tool and is used as the building block for numerical continuous methods, interval iterative method or universal gray method. Interval method can find all solutions, but some algebraic nature of interval mathematics cannot be extended and compiling program is very complicated [14] and [17], so that this limits its application. The universal gray analysis method also can find all solutions of kinematics problem [14] in which, algebraic nature of universal mathematics can be extended like general algebra and overcome the disadvantages of interval analysis, but the universal number operator is also complicated [13], so the efficiency of solution-finding is not very high. Numerical continuation (homotopy) methods have been used in solving kinematics equations of motion for planar as well as spatial mechanisms. If the system of equations to be solved can be cast in a polynomial form, numerical continuous methods are capable of finding all possible solutions and eliminating the need for a good initial estimate to the solution. But computing efficiency is not high, and it is difficult to deal with non-polynomial equations in kinematics [10].
To overcome the difficulties of the above approaches, it is necessary to explore innovate approaches to find out all solutions quickly and effectively. The Newton iteration technique possesses two-order convergence speed, its computing speed is fast, its iteration function is clearly understood, and its dynamics specific property is relatively easy to be hold, so that it is widely used in engineering and science research. But it is comparatively sensitive to initial value,
its calculation capacity is great, and it can only get one solution. All the improved work on Newton methods put the emphases on computing arithmetic and the researchers do not notice that these numerical iteration system are discrete dynamical system resulted from numerical iteration process. Recently, the finding-solution methods based on chaos have made some progress. Xie and Chen [18] had proposed an innovative chaos method for the all solutions of nonlinear equations and Luo [19] had proposed an improved method for enhancing its efficiency by rough and accurate iteration. However, the chaos method related in [18] and [19] assumed the lumped Julia points of Newton iteration method to appear in the neighborhood where the Jacobian matrix of resolved equation set is zero. Nevertheless, it has not been tested and its resolving procedure is complex. Recently, Jovanonic et al. [20] proposed an innovative Newton chaos iteration method to obtain all resolutions of nonlinear equation set to mechanism synthesis. The method assumes Newton iteration method be a nonlinear discrete dynamic system to obtain the chaos fractal sensitive region of the Newton iteration method with the exclusive two-cycle point to make inverse image iteration to find Julia points and then take initial points in the neighborhood of Julia points. But Luo [21] found that its efficiency is to be further enhanced when the Julia points are researched by using the exclusive two-cycle point to operate inverse image iteration. And thus, Luo [22] proposed an innovative three-cycle chaos orbit method to find the Julia points of non-linear equations in kinematics, but its validity and adaptability to find Julia points with three-cycle inverse image iteration method are valuable to be researched ulteriorly. On the other hand, multi-start technique is a sort of technique in global optimization. The biggest difficulty of Newton iterative method is how to define initial value. To take chaos sequences as initial points of Newton iterative method, it can find all solutions of nonlinear equations. Liao et al. [23] proposed two dimension chaos mapping Newton iterative method which is applied to found all solutions of linkage accurate points movement synthesis.
To overcome the difficulties of approaches, this paper presents a new method for solving algebraic system of equations in kinematics, which utilizes Hénon hyper-chaotic mapping system to
produce sensitive initial points of Newton iterative method and find all solutions of nonlinear equations. After analyzing hyper-chaotic the characteristic of Henon hyper-chaotic mapping system, the simulation is done with MATLAB software, and the step and methods of finding equations in kinematics are also given. Numerical examples for linkage synthesis & approximate synthesis are presented. At last, the comparison with other methods to find all solutions of nonlinear equations in kinematics is given. The examples show the new method is verified to be correct and effective.
1 HENON HYPER-CHAOTIC SYSTEM
Lyapunov exponent is one of effective method depicting the Chaos specific property of nonlinear system, and the number of Lyapunov exponents is identical with the dimension n of system state space. If one of the Lyapunov exponents is positive, system is chaotic. If system has two or more positive Lyapunov exponents, system is hyper-chaotic. The more positive number of Lyapunov exponents, the higher in-stability has the system [24]. In general, if the systematic state variable number is more (for high dimension system, e.g. the discrete system, n > 2), it probably appeares the unsteady level is higher.
The Ref. [25] designed a general Henon mapping:
xi,k+1 lfa - 4-u - bxn,k j	(1)
xi,k+1[ xi-1kk
where, i = 2,3,•••,n express the dimension of system; k is discrete time; a and b are adjustable parameters. When i = 2, the above mapping is called as famous Henon mapping. When fixed parameters a = 1.76, b = 0.1 and the dimensions vary from 2 to 10, after computing, the ref. [25] found that with increasing n, the simple relation of the number N of positive Lyapunov exponents with the system dimension n is N = n -1, namely, when the system dimension is larger of two, system is hyper-chaotic. For n > 10 situation, we also have done simulating study and we also obtained the same results N = n -1.
For example, n = 5, we compiled program MATLAB with time series method [24] and we obtain four positive Lyapunov exponents, shown in Figure 1. When n = 13, the simulating result is that the system has twelve positive Lyapunov exponents with lesser values, shown in Figure 2.
2 NEWTON ITERATION FUNCTION
To find solution of nonlinear equations:
f (x) = 0	(2).
Newton iterative method can be described as follows roughly:
(1)	To select initial value x0
(2)	To take iteration by formation
Xk+1 = Xk	k = 0,1,2,- (3),
f(xk)
where flx^ is the function value of f(x) at the point xk, f"(xk), is one-order derivative of f(x) at the point xk, also called as Jacobian matrix of f(xk)
M 5
c
c -1 -o a. x
<» -1.5>
0
1
re
-2.5
-3.5_L
• =0.1238 ' =0.10933 A3=0.10805 3.4=0.090167 a = -2.7339
100 200 300 400 500 600 700 800 900 1000 Number of iteration
Fig.1. Lyapunov exponent of Henon maps with n=5
A. ,=0.027205
• =0.020526 A13= -2.6977
400 500 600 Number of iteration
300
900
1000
Fig.2. Lyapunov exponent of Hénon maps with n = 13
and it is denoted by J. f(x) is Newton iteration function value. When some conditions are satisfied, Newton iterative method is two-order convergent [9]. We must note that when using Newton iterative method, we want to avoid f'(xk) = 0, otherwise singularity will be produced. To improve the performance of Newton iterative method, there have some improved methods, but the improved methods pay attention to arithmetic study and not mechanism study. In other words, these methods avoid singularity and do not make use of singularity.
3 NEWTON ITERATIVE METHOD BASED ON HENON HYPER-CHAOTIC MAPPING
Based on hyper-chaotic mapping, the process of the finding all solutions of nonlinear equations is as follows:
(1)	By formulation (1), to construct hyper-chaotic
set x0(i + 1, j) (i = 1, 2.....n, n + 1 is the variable
number of hyper-chaotic system, n is the positive number of Lyapunov exponents, n is
also the number of variables, j = 1, 2.....N, N
is the length of hyper-chaotic sequences) and obtain x0(i, j);
(2)	Suppose the interval of x(i) is [a(i), b(i)] , to map hyper-chaotic sequences to variable interval with x(i, j) = (b(i) - a(i))/2 + x0(i, j)(b(i) + a(i))/2 and produce jth x(i, j) of x(i).
(3)	To take jth x(i, j) of x(i) as initial value of Newton iterative method, and implement j time operations of Newton iterative method with formulation (3) to find all solutions x*. Note
that: in computing process, X is used to save all solutions, when some solution x* is in X, x* is abandoned, otherwise, x* is saved in X.
4 APPLICATION TO MECHANISM SYNTHESIS
For four-linkage function mechanism synthesis, in general, it's input angles j and the output angles (¡\j satisfy some function relation, we construct orthogonal system (shown in Fig. 3) and take the coordinate of C point is (1,0). Suppose the coordinates Ax, A, B,, By of pin-joined points A and B are design variables, denoted by x1, x , x , x4 respectively.
According to constrained condition of the invariable length of linkage and displacement matrix, we can deduce the synthesis equation as follows:
fj (x) = j x3 + P2 jxlx4 + P3jx2 x3 +
(4),
+ PA jx2 x4 + P5 jxi + P6 jx2 + Pj jx3 jx4 + P§ j where j = 2, 3,... m, m is point number of synthesis.
P, = 1 -cos(0!,-0l,);P2, =-sin(0!,j)
P3 j = sin(0! j -faj); P4 j = 1 - cos^! j - j)

4 j

P5j = cos(01j - faj) - cos(01j)
P6 j = sin(0i j -ft j ) + sin(0i j )
P j = cos(ftij) -1; P j = -sin(fti j)
P9 j = 1 - cos(ft1 j) There have four design variables m-1 and
design equations in formulation (4), the most
accurate point synthesis number is five points.
In most situations, the problem of mechanism synthesis and approximate synthesis can be transformed into an unconstrained optimum problem, namely:
111
min F (x) (fj (x))2
(5).
j=i
And the essential condition of min objective function is the grads dF(x) / dx = 0 , namely:
m-1
Ifj-1( PjX3 + P2 jX4 + P5 j ) = 0 j =2 m-1
ifj -1( P3 jX3 + P4 jX4 + p j ) = 0 j =2 m-1
£ fj-1(PjX1 + P3jx2 + P7j) = 0
j =2
(6),
£ fj-1 (PjX1 + P4jx2 + P8j) = 0 . j=2
where m is synthesis point number.
For example, given plane four-linkage mechanism synthesis problem, the data of input 01 j and output are shown in Table 1. Using Newton iteration method based on Henon hyper-chaotic sequences, we transform nonlinear equations (4) into iterative form of formulation (3), take variable intervals all [-20, 20]T, and produce initial point of hyper-chaotic sequences with random number method and for example, x0 =
Fig.3. The diagram of linkage mechanism Table 1. Five group data of input and output
j	1	2	3	4	5
Ou (0)	0	60	130	200	280
Vu (0)	0	17	44	61	50
[0.37948, 0.8318, 0.50281, 0.70947, 0.42889]T. To
take n = 5 for general Hénon hyper-chaos system expressed by formulation (1), and, with initial value x0 of hyper-chaotic sequences, produce hyper-chaotic sequences with four positive Lyapunov exponents (to take the length N = 20), then map variable intervals and obtain initial values of Newton iterative method and obtain all solutions, the first to fourth solution (Table 2). The solutions are accordant with methods in [10], but it dissipative time is 0.16 second less that time 0.4 second with Logistic chaos mapping Newton iterative method (only initial points of Newton iterative method produced by Logistic chaos mapping). If we produce initial point x0 of hyper-chaotic sequences with random number method and for example, x0 = [0.28973, 0.34119, 0.53408, 0.72711, 0.30929]T, the length of hyper-chaotic sequences is N = 200, the accurate synthesis problem is dealt with approximate synthesis method in formulation (6), and results are shown in Table 2, besides the first to fourth solution, there have other approximate solutions. Notes that with different initial point of hyper-chaotic sequences and the length of hyper-chaotic sequences, approximate solutions may be different.
5 CONCLUSIONS
In this paper, using Hénon hyper-chaos sequences and mapping sequences into variable intervals as initial values of Newton iterative method, an innovative new method to find all solutions of nonlinear equations in kinematics is proposed. The computing steps are presented. Numerical examples of mechanism synthesis and approximate synthesis are given. It shows that this method is effective and correct. This method overcomes the shortcomings of the existing methods, namely, extraneous solutions of resultant method, low computing efficiency of existing analytical solutions, and, low computing efficiency to find all solutions with existing numerical methods or only finding a solution with Newton method & optimum method. Newton method is adaptive to polynomials nonlinear equations as well as the general non-polynomial non-linear equations, so, the proposed method is also adaptive to the general non-polynomial non-linear equations. The hyper-chaos iterative method effectively resolves the dependent on initial guess of Newton
Table 2. The results of synthesis
^\Variables					
Seria^v number	x1	x2	x3	x4	Notes
1	0.34688351864093	0.15532289223008	2.37621431901423	1.07108276520215	Satisfy request
2	0.33802375122182	0.35284403147775	1.52301342502732	1.46008672456456	Satisfy request
3	0.00876050327329	0.19878954898663	0.24358820102367	0.42972805218513	Satisfy request
4	0.00000000000000	0.00000000000000	1.00000000000000	0.00000000000000	Degenerate solution
5	0.24810590331448	0.09742519788478	0.62411520956186	0.49721188127604	Approximate solution
6	0.35261614308389	0.17452815063814	2.35195172736808	1.14692673024341	Approximate solution
7	0.36183730535318	0.25046832860287	2.06025448656341	1.35405078472152	Approximate solution
8	0.35262221231194	0.17455139128299	2.35192171459211	1.14701706830115	Approximate solution
9	-0.05656808459818	0.10789498343339	0.45524276496406	0.22173945773667	Approximate solution
10	0.26879875742049	0.34866142549433	0.37945885805080	0.74548350193159	Approximate solution
11	0.33698078149853	0.35516826106660	1.51946559173426	1.46634536242020	Approximate solution
12	0.36143253460429	0.26070352447913	2.00210092194291	1.36915944896681	Approximate solution
iterative method based on multi-start point technique and hyper-chaos sequences. This method also overcomes the deficiency of existing chaos iterative method. Besides, compared with chaos Newton iterative method, hyper-chaos Newton iterative method has high computing speed and can obtain all solutions of nonlinear equations. It can quickly and effectively find out all solutions of nonlinear equations in kinematics, set up basis for other engineering application and optimization, and provide beneficial idea for chaos characteristic study of other iterative method.
Acknowledgement
This research is supported by the grant of the 11th Five-Year Plan for the construct program of the key discipline (Mechanical Design and Theory) in Hunan province (XJT2006180), Hunan Provincial Natural Science Foundation of China (07JJ3093), Hunan Province Foundation Research Program (2007FJ3030,2007GK3058) and Scientific Research Fund of Ministry of Education of China (02108).
6 REFERENCES
[1]	Dhingra, A.K., Almadi , A.N., et al. A GrobnerSylvester hybrid method for closed-form displacement analysis of mechanisms. ASME J. Mech. Des., 122(4), 2000, p. 431-438.
[2]	Norton, L.R. An introduction to the synthesis and analysis of mechanisms and machines. McGraw-Hill Companies, Inc., Asia, 2001.
[3]	Waldron, K.J., Sreenivasan, S.V. A study of the solvability of the position problem for multi-circuit mechanisms by way of example of the double butterfly linkage. ASME J. Mech. Des., 118(3), 2996, p. 390-395.
[4]	Dhingra, A.K., Almadi, A.N., et al. A closed-form approach to coupler-curves of multi-loop mechanisms. ASME J. Mech. Des., 122(4), 2000, p.464-471.
[5]	Bhubaneswar M. Algorithmic algebra. New York: Springer-Verlag Inc., 1993.
[6]	Wang D.M. Elimination method and its application. Beijing: Chinese Science Press, 2002. (in Chinese).
[7]	Wu, W. T. Mathematics mechanization. London: Kluwer Academic Publishers, 2000.
[8]	Macaulay, F.S. The algebraic theory of modular systems. New York: Cambridge University Press, 1994.
[9]	Burden, L.R., Faires D.J. Numerical analysis, 8th Ed. Brooks-Cole Publishing, USA, 2004.
[10]	Yang, T.L. The basic theory of mechanical system. Beijing: Chinese Machine Press, 1996.
[11]	Liu A.X., Yang T.L. Finding all solutions to unconstrained nonlinear optimization for approximate synthesis of planar linkages using continuation method. ASME J. Mech. Des., 121(3), 1999, p. 368-374.
[12]	Moore, R.E. Interval analysis. Englewood Cliffs: Prentice-Hall, 1966.
[13]	Luo, Y.X. Universal grey mathematics and its application to interval analysis of uncertain structural systems. Advances in Systems Science and Applications, 3(4), 2003, p. 522-530.
[14]	Luo, Y.X., Guo, H.X., Zhang, L.T. The application of universal grey mathematics to the analysis of mechanism errors. Journal of Machine Design, 19(2), 2002, p. 11-14. (in Chinese).
[15]	Luo, Y.X., Huang, H.Z., Fan, X.F. Universal grey transfer matrix method and its application to natural frequencies calculation of systems. ASME J. Mech. Eng., 52(9), 2006, p. 592-598.
[16]	Nokleby, B.S., Podhorodeski, R.P. Optimization-based synthesis of Grashof geared five-bar mechanisms. ASME J. Mech. Des., 123(4), 2001, p. 529-534.
[17]	Eldonhansen, G., Walster, W. Global optimization using interval analysis, 2nd Ed. Monticello, NewYork: Marcel Dekker, Inc., 2004.
[18]	Xie, J., Chen, Y. Application of chaos theory to synthesis of plane rigid guidance. Mechanical science and technology, 19(4), 2002, p. 524-526. (in Chinese).
[19]	Luo, Y.X. Chaos method for function synthesis of planar crank—slider mechanism. Journal of machine design, 20(7), 2003, p. 27-30. (in Chinese).
[20]	Jovanonic, V. T., Kazerounian, K. Using chaos to obtain global solutions in computational kinematics. ASME J. Mech. Des., 120(7), 1998, p. 299-304.
[21]	Luo, Y.X. The research of Newton chaos iteration solution method and its application to mechanism synthesis. Machine design and research, 21(5), 2005, p. 19-22.
[22]	Luo, Y.X. A new 3-cycle Newton chaos iteration solution method and its application to mechanism synthesis. The International Conference on Mechanical Transmissions, Chongqing, China, 2006, p. 102-105.
[23]	Liao, D.G., Luo, Y.X. Two dimension chaos mapping Newton iterative method and its application to function analysis of planar linkage mechanism. Journal of Mechanical Transmission, 30(3), 2006, p. 21-23. (in Chinese).
[24]	Wolf, A., Swift, J.B., Swinney, H.L., et al. Determining Lyapunov exponents from a time series. Physica D: Nonlinear Phenomena, 16(3), 1985, p. 285-317.
[25]	Richter H. The generalized Henon maps: examples for higher-dimensional chaos. International Journal of Bifurcation and Chaos, 12, 2002, p. 1371-1381.