Back
 AM  Vol.12 No.7 , July 2021
Linear and Quadratic Leap-and-Land Trajectory Tracking Algorithms
Abstract: Considered in this note are numerical tracking algorithms for the accurate following of implicit curves. We start with a fixed point on the curve, and then systematically place on it additional points, one after the other. In this note we first go over the basic procedure of moving forward tangentially from an already placed point then orthogonally returning to the curve. Next, we further consider higher order forward stepping procedures for greater accuracy. We note, however, that higher order methods, desirable for greater accuracy, may harbor latent instabilities. This note suggests ways of holding such instabilities in check, to have stable and highly accurate tracing methods. The note has several supporting numerical examples, including the rounding of a dynamical “snap-through” point.

1. Introduction

Pursuing a smooth implicit trajectory such as an energy level line is of great interest in numerical analysis and has attracted considerable attention [1] [2] [3] [4] [5] in recent years. In principle, such tracing entails marking close points on an implicit curve. Once a point is secured on the curve, a short distance forward leap is executed to place an initial point in the vicinity of the curve. Then, a returning iterative procedure is carried out to come back and land on the curve. To stay close to the curve, this stepping-out from the curve to the next initial guess is plausibly made by a tangential move at a prescribed step size. Orthogonal [2] iterative corrections are then carried out to bring the initially placed point ever closer to the curve.

The method, by dint of its orthogonal descent, is successful in rounding sharp bends as it follows the twists and turns of contorted trajectories. Still, the predictor leap ignores all previous information about the curving of the trajectory.

We propose here to improve the accuracy of the leap-out with a higher order parametrization of the trajectory by Bezier-like polynomial approximations. With their ability to bend, these approximations are likely to deposit an initial guess closer to the traced implicit curve for a hopefully quicker correction. We have shown that positioning an initial guess closer to the traced trajectory may well have both advantages of reducing the initial error in the following Newton-Raphson [6] correction, and also of improving the orthogonality of the landing approach along a gradient closer to the true one at landfall.

2. Linear Leap

Consider the implicit function z = f ( x , y ) of which the level curve z = 0 we desire to trace. Let A ( x 0 , y 0 ) be a point on the curve such that f ( A ) = f ( x 0 , y 0 ) = 0 . See Figure 1 below.

Let f x = f / x and f y = f / y be the partial derivatives of f with respect to x and y, respectively, at point A ( x 0 , y 0 ) . The total differential d z = f x d x + f y d y , for differentials d x , d y , is reduced along the level line to

d z = 0 = f x d x + f y d y (1)

or in vector form

( f x , f y ) ( d x , d y ) = 0 (2)

where the first vector in the dot product is the gradient f to f at point A, and where the second vector is colinear with the tangent line to f = 0 at point A on the curve.

Thus, the equation of the tangent line to the curve at point A is

( f x ) A d x + ( f y ) A d y = 0 or ( f x ) A ( x x 0 ) + ( f y ) A ( y y 0 ) = 0 (3)

and we propose to leap forward from point A and place predicted point B on the tangent line at distance ε . Evidently, for any such d x , d y point B ( x 0 + d x , y 0 + d y ) is on the tangent line to f ( x , y ) = f ( x 0 , y 0 ) = 0 at point A.

Stepping out from point A to point B is what we term a linear tangential leap.

Figure 1. Implicit level curves.

Restricting the differentials to d x 2 + d y 2 = ε 2 , namely, to a tangential forward leap of size ε , results in

d x = ε f y f x 2 + f y 2 , d y = ε f x f x 2 + f y 2 (4)

with signs chosen to produce a clockwise tracking.

For instance, if

f ( x , y ) = x 2 + y 2 1, (5)

then

f x = 2 x , f y = 2 y (6)

and

d x = ε y 0 , d y = ε x 0 . (7)

Thus, a tangential leap originating at A ( x 0 , y 0 ) terminates here at point B ( x 1 , y 1 ) = B ( x 0 + ε y 0 , y 0 ε x 0 ) , such that

x 1 2 + y 1 2 = ( x 0 2 + y 0 2 ) ( 1 + ε 2 ) = 1 + ε 2 (8)

and f ( x 0 , y 0 ) = 0 , f ( x 1 , y 1 ) = ε 2 . See also [7].

3. Linearized Orthogonal Landing

We consider point B ( x 1 , y 1 ) as situated on the curve f ( x , y ) = f ( B ) = f ( x 1 , y 1 ) , having the tangent line

( f x ) B d x + ( f y ) B d y = 0 or ( f x ) B ( x x 1 ) + ( f y ) B ( y y 1 ) = 0. (9)

See Figure 1.

Point C is the intersection point of the line orthogonal to this tangent line and the curve f = 0 . To reach point C from point B we seek the corrections dx and dy such that

f ( x 1 + d x , y 1 + d y ) = 0 under the restriction that ( f y ) B d x ( f x ) B d y = 0. (10)

This system of equations is approximately solved with the differential linearization

f ( x 1 + d x , y 1 + d y ) = f ( x 1 , y 1 ) + ( f x ) B d x + ( f y ) B d y = 0 (11)

to yield

d x = f f x 2 + f y 2 f x , d y = f f x 2 + f y 2 f y (12)

in which function f and its partial derivatives f x and f y are evaluated at point B ( x 1 , y 1 ) .

If | f ( C ) | is deemed not sufficiently small, then point C is taken in place of point B and the linearization is repeated.

For the unit circle the coordinates of point C are x 2 = x 1 + d x , y 2 = y 1 + d y , where ( x 1 , y 1 ) are the coordinates of predicted point B, and where d x , d y are from Equation (12). Now

f ( x 2 , y 2 ) = x 2 2 + y 2 2 1 = 1 4 ( 1 + ε 2 ) ε 4 (13)

which is indeed tiny if ε 1 .

To summarize: if point A ( x 0 , y 0 ) is on the curve, then point B ( x 1 , y 1 ) is the point reached by a tangential leap of size ε away from point A, and point C ( x 2 , y 2 ) is the point reached by a single orthogonal correction away from point B and towards the curve. For the unit circle

f ( A ) = 0 , f ( B ) = O ( ε 2 ) , f ( C ) = O ( ε 4 ) . (14)

See also [7].

4. A Detailed Numerical Example

Consider the implicit function

z = f ( x , y ) = y 2 + x y + 2 x 2 4 = 0 (15)

which we may turn here explicit, by a mere solution of a quadratic equation, to have

y = 1 2 x ± 1 2 16 7 x 2 , 2.2857 x 2.2857. (16)

At first, we look for the critical points of function f. For this we differentiate f explicitly with respect to x to have

2 y y + y + x y + 4 x = 0 (17)

in which y = d y / d x . Zero slope, or y = 0 , occurs at y + 4 x = 0 , which with f ( x , y ) = 0 yields

x = 2 7 = 0.5345 , y = 4 2 7 = 2.138. (18)

To determine the nature of the critical point, we implicitly differentiate Equation (17) once more with respect to x to have

2 y y + 2 y y + y + y + x y + 4 = 0. (19)

At the critical point y = 0 , and with x and y from Equation (18), we have from Equation (19) that

y = 2 7 14 > 0 (20)

implying that the nature of the critical point is a local minimum.

Now to the leap-and-land. The equation of the tangent line to this curve at point A ( x 0 , y 0 ) is

( f x ) 0 d x + ( f y ) 0 d y = 0 , d x = x x 0 , d y = y y 0 (21)

or here

( 4 x 0 + y 0 ) d x + ( x 0 + 2 y 0 ) d y = 0. (22)

Specifically, for point A ( 0,2 )

2 d x + 4 d y = 0 , or y = 1 2 x + 2. (23)

A leap of ε = 1.2 brings us to point B ( 1.07331,1.46334 ) on the tangent line. At point B we write the function

f ( x , y ) = y 2 + x y + 2 x 2 k = 0 , k = y 1 2 + x 1 y 1 + 2 x 1 2 = 6.016. (24)

The tangent line to this curve at point B is

( f x ) 1 d x + ( f y ) 1 d y = 0 , d x = x x 1 , d y = y y 1 (25)

or specifically

5.75659 d x + 4 d y = 0. (26)

The line orthogonal to this second tangent line is

4 d x 5.75659 d y = 0. (27)

All as seen in Figure 2.

Next we apply the landing correction

f ( x 1 + d x , y 1 + d y ) = 0 (28)

by the constrained linearization

( f x ) 1 d x + ( f y ) 1 d y = 0 , 4 d x 5.75659 d y = 0 (29)

Figure 2. Level curve of an implicit function.

and obtain

d x = 0.236176 , d y = 0.164108 or x 2 = 0.837137 , y 2 = 1.29924 (30)

for point C, which is indeed nearly on the curve. In fact f ( C ) = 0.177248 instead of zero. To get point C closer to the curve, we may apply another orthogonalization and linearization. Also, a smaller leap ε would have resulted in point C closer to the curve.

5. Higher Order Leaps

For a quadratic leap, we start with three points already placed on the curve, say P 1 ( x 1 , y 1 ) , P 2 ( x 2 , y 2 ) , P 3 ( x 3 , y 3 ) . Parametrization of the interpolant to the trajectory over the three points is achieved with

x ( t ) = x 1 ϕ 1 ( t ) + x 2 ϕ 2 ( t ) + x 3 ϕ 3 ( t ) , y ( t ) = y 1 ϕ 1 ( t ) + y 2 ϕ 2 ( t ) + y 3 ϕ 3 ( t ) (31)

where ϕ 1 , ϕ 2 , ϕ 3 are the three Lagrange interpolation functions

ϕ 1 ( t ) = 1 2 ( t 1 ) ( t 2 ) , ϕ 2 ( t ) = t ( t 2 ) , ϕ 3 ( t ) = 1 2 t ( t 1 ) (32)

with parameter t = 0 , t = 1 and t = 2 , at P 1 , P 2 and P 3 , respectively. At t = 3 , Equation (31) predicts the coordinates

x 4 = x ( t = 3 ) = x 1 + 3 ( x 3 x 2 ) , y 4 = y ( t = 3 ) = y 1 + 3 ( y 3 y 2 ) . (33)

A higher order, cubic, parametrization of an interpolant to the trajectory over four points similarly produces

x 5 = x ( t = 4 ) = x 1 + 4 x 2 6 x 3 + 4 x 4 , y 5 = y ( t = 4 ) = y 1 + 4 y 2 6 y 3 + 4 y 4 . (34)

6. Bézier Curve Leaps

Use of partial derivatives allows the construction of a quadratic Bézier-like approximation to the trajectory [8] over only two points. Let P 1 ( x 1 , y 1 ) and P 2 ( x 2 , y 2 ) be two such points on the trajectory. The quadratic parametric approximation to both x and y between P 1 and P 2 is of the general form

x = a 0 + a 1 t + a 2 t 2 , y = b 0 + b 1 t + b 2 t 2 , 0 t 1 (35)

where the coefficients of the approximation are to be determined from the initial and end conditions at P 1 and P 2 . Let x ˙ and y ˙ denote the derivatives of x and y with respect to parameter t. At any point t on the trajectory x = x ( t ) , y = y ( t ) , and f x x ˙ + f y y ˙ = 0 . For the quadratic approximation of Equation (35), x ˙ = a 1 + 2 a 2 t , y ˙ = b 1 + 2 b 2 t . Requiring x , y , x ˙ , and y ˙ at P 1 where t = 0 and at P 2 where t = 1 produces the equations

x 1 = a 0 , y 1 = b 0

x 2 = a 0 + a 1 + a 2 , y 2 = b 0 + b 1 + b 2 (36)

f x 1 a 1 + f y 1 b 1 = 0 , f x 2 ( a 1 + 2 a 2 ) + f y 2 ( b 1 + 2 b 2 ) = 0

that are solved to yield the coefficients

x 1 = a 0 , y 1 = b 0

a 1 = 2 Δ f y 1 ( f x 2 δ x + f y 2 δ y ) , b 1 = 2 Δ f x 1 ( f x 2 δ x + f y 2 δ x ) (37)

a 2 = δ x a 1 , b 2 = δ y b 1

where Δ = f x 1 f y 2 f y 1 f x 2 , where δ x = x 2 x 1 , and where δ y = y 2 y 1 . At t = 2 we then have

x 3 = x ( t = 2 ) = 3 x 1 + 4 x 2 3 a 1 , y 3 = 3 y 1 + 4 y 2 3 b 1 . (38)

7. Improved Accuracy with a Quadratic Leap

Consider the circular level line z = f ( x , y ) = x 2 + y 2 1 = 0 . A linear leap of size ε from point P ( 0,1 ) on top of the circle sends us to point Q ( ε ,1 ) that is at distance 1 2 ε 2 from the circle, provided that ε 1 . A quadratic approximation through points P 1 ( sin 2 θ , cos 2 θ ) , P 2 ( sin θ , cos θ ) , P 3 ( 0,1 ) with a relatively small θ produces out of Equation (33) the predictions

x 4 = x ( θ ) = θ + 5 6 θ 3 and y 4 = y ( θ ) = 1 1 2 θ 2 (39)

for the coordinates of point P 4 , that is at the mere distance of ( 23 / 24 ) θ 4 from the circle.

8. Now the Landing

Let P ( x 0 , y 0 ) now be a point not on the trajectory, f ( x 0 , y 0 ) 0 . Point P can be considered as being on the level curve z = f ( x , y ) = f ( x 0 , y 0 ) , with a gradient f = ( f x 0 , f y 0 ) that is orthogonal to the level curve f ( x , y ) = f ( x 0 , y 0 ) and therefore also nearly orthogonal to f ( x , y ) = 0 . Linearizing the correction f ( x 0 + d x , y 0 + d y ) = 0 we get f 0 + f x 0 d x + f y 0 d y = 0 . To achieve an orthogonal aim for the landing of the corrected point we require the colinearity condition ( d x , d y ) = λ ( f x 0 , f y 0 ) for scalar λ . The linearization fixes λ as

λ = f 0 f x 0 2 + f y 0 2 and d x = λ f x 0 , d y = λ f y 0 . (40)

The coordinates of point P are corrected thereby to x 1 = x 0 + d x , y 1 = y 0 + d x , and the procedure may be repeated.

Figure 3(a) below shows a fourteen-step tracking of the unit circle f ( x , y ) = x 2 + y 2 1 = 0 by linear leaps of ε = 0.49 and a single orthogonal Newton-Raphson landing correction.

9. A Full Numerical Experiment and a Warning

Figure 3(a) shows a fourteen-step tracking of the unit circle

f ( x , y ) = x 2 + y 2 1 = 0 by linear leaps of ε = 0.49 and a single orthogonal linear (actually Newton-Raphson) correction. The vectorial plot clearly shows the tangential leap and the orthogonal landing on the drawn circle. Figure 3 (b)

Figure 3. A leap and one orthogonal land on a unit circle.

is a vectorial plot of a nine-step quadratic leap carried out according to Equation (33), coupled with a single, linearized, orthogonal Newton-Raphson correction. Notice the relentless, undesirable growth of the step size in the quadratic method.

10. An Unstable Leap and Its Stabilization

Unfortunately, recursive formula (33) used to obtain the tracing of Figure 3(b) is unstable. Indeed, writing it in the general form

x n + 3 3 x n + 2 + 3 x n + 1 x n = 0 , n = 1 , 2 , 3 , (41)

we observe that it is solved by x n = z n for number z that satisfies the cubic characteristic equation

z 3 3 z 2 + 3 z 1 = ( z 1 ) 3 = 0. (42)

Since this equation has three equal roots z 1 = z 2 = z 3 = 1 ,

x n = c 1 + c 2 n + c 3 n 2 (43)

where c 1 , c 2 , c 3 depend on the initial conditions x 1 , x 2 , x 3 . In fact, from

x 1 = c 1 + c 2 + c 3 , x 2 = c 1 + 2 c 2 + 4 c 3 , x 3 = c 1 + 3 c 2 + 9 c 3 (44)

we obtain that

c 1 = 3 x 1 3 x 2 + x 3 , c 2 = 1 2 ( 5 x 1 + 8 x 2 3 x 3 ) , c 3 = 1 2 ( x 1 2 x 2 + x 3 ) . (45)

Now, if x 1 = 0 , x 2 = 1 and x 3 = 2 , then c 1 = 1 , c 2 = 1 , c 3 = 0 , and x n = 1 + n so that x n + 1 x n = 1 for all n. But if x 1 = 0 , x 2 = 1 and x 3 = 2 + ε , then c 1 = 1 + ε , c 2 = 1 3 2 ε , c 3 = 1 2 ε and x n = n 1 + 1 2 ε ( n 1 ) ( n 2 ) , so that

x n + 1 x n = 1 + ε ( n 1 ) with a growing factor of n + 1 . To control and subdue the parasitic linear growth, or contraction, of the distance between x n and x n + 1 , a proper value for the predicting t has to be chosen in Equations (31) and (32) to maintain a nearly constant step size. Instead of t = 3 we set t = 3 + ε in the Lagrange interpolation functions (32) to have the prediction

x 4 = x 4 ( ε ) = x 1 ( 1 + 3 2 ε + 1 2 ε 2 ) + x 2 ( 3 4 ε ε 2 ) + x 3 ( 3 + 5 2 ε + 1 2 ε 2 ) (46)

or

x 4 x 3 = x 1 3 x 2 + 2 x 3 + ε ( 3 2 x 1 4 x 2 + 5 2 x 3 ) + ε 2 ( 1 2 x 1 x 2 + 1 2 x 3 ) (47)

and a similar expression for y 4 y 3 . Compactly written

x 4 x 3 = a 1 + a 2 ε + a 3 ε 2 , y 4 y 3 = b 1 + b 2 ε + b 3 ε 2 (48)

from which we obtain

( x 4 x 3 ) 2 + ( y 4 y 3 ) 2 = a 1 2 + b 1 2 + 2 ( a 1 a 2 + b 1 b 2 ) ε + ( a 2 2 b 2 2 + 2 a 1 a 3 + 2 b 1 b 3 ) ε 2 + 2 ( a 2 a 3 + b 2 b 3 ) ε 3 + ( a 3 2 + b 3 2 ) ε 4 (49)

that we equate to ( x 2 x 1 ) 2 + ( y 2 y 1 ) 2 to have a quartic equation for ε . For well placed initial points | ε | 1 we may ignore the ε 3 and ε 4 terms in Equation (49) to be left with a quadratic equation for ε . Employing this stabilization procedure, we traced the unit circle as shown in Figure 3(c), using the three starting points P 1 ( 0 , 1 ) , P 2 ( sin θ , cos θ ) , P 2 ( sin 2 θ , cos 2 θ ) , with θ = π / 15 . The typically computed ε hovered around 0.04.

11. A “Snap-Through” Oscillation of a Pre-Stressed Double Rod System

Figure 4(a) shows a system of two equal, pin-joint, supposedly massless, elastic rods of elastic constant k, fixed at pivots A and B. At their junction the rods carry a mass m that is initially held at distance x 0 from midpoint M on line AB. At this position the length of each rod is l ( x 0 ) = 1 + x 0 2 . It is assumed that at length l 0 the rods are free of stress. If l ( x 0 ) > l 0 , then an initial restoring pull is being exerted on m with the intention of propelling it towards point M. Assuming that the rods obey Hook's law, the energy equation of the system becomes

2 k m ( 1 + y 0 2 l 0 ) 2 = 2 k m ( 1 + x 2 l 0 ) 2 + x ˙ 2 . (50)

The unstressed length of the rods has a critical value

l 0 c r i t = 1 2 x 0 2 1 + x 0 2 1 (51)

Figure 4. (a) A spring-mass system and (b) its computed phase portrait.

for which mass m reaches point M with zero velocity but with the rods still packing the potential energy k ( 1 l 0 ) 2 . The system comes to an unstable symmetrical standstill waiting for a disturbance to trigger a snap-up or a snap-down. For l 0 < l 0 c r i t mass m arrives at point M with a residual velocity that helps carry it over past line AB, allowing m to complete its travel to x = x 0 , and then back in a periodic motion.

In fact, if l 0 = l 0 c r i t ( 1 ε ) , ε > 0 , then mass m reaches point M with a velocity

x ˙ ( x = 0 ) = 2 k m ε x 0 2 (52)

and through implicit differentiation of Equation (50) we have further that

x ¨ ( x = 0 ) = 0 , and x ( x = 0 ) = l 0 1 ε x 0 2 (53)

indicating that x ( x = 0 ) as ε 0 . The butterfly-shaped phase portrait of the spring-mass system in Figure 4(b) is, indeed, seen to have a waist of diminishing girth as l 0 l 0 c r i t with a turning-back that tends to become critically sharp. The computation described in Figure 4(b) was carried out with a tangential search step of size ε = 0.1 , for x 0 = tan ( 60 ˚ ) , for which l 0 c r i t = 1.5 , with l 0 = 1.499 , and 85 steps. Observe the deftness with which the gradient landing scheme sparsely places successive hits on flat sections of the curve, but clusters them closer around sharp bends.

12. Conclusion

We have considered in this paper the basic tangential leap followed by an orthogonal landing method for tracing implicit curves. We have then suggested a more accurate quadratic forward leap. However, such a leap may become unstable and we have shown how to restrain these possible instabilities to have a stable and accurate method. It would be of interest to consider next how to economize on the differentiations to have a more efficient method.

Cite this paper: Fried, I. (2021) Linear and Quadratic Leap-and-Land Trajectory Tracking Algorithms. Applied Mathematics, 12, 587-597. doi: 10.4236/am.2021.127042.
References

[1]   Yu, Z., et al. (2006) Efficient Method for Tracing Planar Implicit Curves. Journal of Zhejiang University—Science A: Applied Physics and Engineering, 7, 1115-1123.
https://doi.org/10.1631/jzus.2006.A1115

[2]   Fried, I. (1984) Orthogonal Trajectory Accession to the Nonlinear Equilibrium Curve. Computer Methods in Applied Mechanics and Engineering, 47, 283-297.
https://doi.org/10.1016/0045-7825(84)90080-X

[3]   Riks, E. (1979) An Incremental Approach to the Solution of Snapping and Buckling Problems. International Journal of Solids and Structures, 15, 329-551.
https://doi.org/10.1016/0020-7683(79)90081-7

[4]   Crisfield, M.A. (1981) A Fast Incremental/Iterative Solution Procedure That Handles “Snap-Through”. Computers and Structures, 13, 55-62.
https://doi.org/10.1016/0045-7949(81)90108-5

[5]   Crisfield, M.A. (1983) An Arc-Length Method Including Line Searches and Accelerations. International Journal for Numerical Methods in Engineering, 19, 1269-1289.
https://doi.org/10.1002/nme.1620190902

[6]   Padorean, J. and Tovichackhaikul, S. (1983) Operating Characteristics of Hyperbolically and Elliptically Constrained Self-Adaptive Incremental Newton-Raphson Algorithms. Journal Franklin Institute, 316, 197-223.
https://doi.org/10.1016/0016-0032(83)90041-8

[7]   Watson, L.T. and Holzer, S.M. (1983) Quadratic Convergence of Crisfield Method. Computers and Structures, 17, 69-72.
https://doi.org/10.1016/0045-7949(83)90030-5

[8]   Ahn, Y.J. (2004) Approximation of Circular Arcs and Offset Curves by Bezier Curves of High Degree. Journal of Computational and Applied Mathematics, 167, 405-416.
https://doi.org/10.1016/j.cam.2003.10.008

 
 
Top