Classroom Tips and Techniques: Solving Algebraic Equations by the Dragilev Method
Robert J. Lopez
Emeritus Professor of Mathematics and Maple Fellow
Maplesoft
Introduction
On February 13, 2013, Markian Hirnyk posted an animation to MaplePrimes, one frame of which is shown in Figure 1. He asked how this animation might be coded in Maple.
A reply on February 14 by one_man contained a link to the worksheet MECAN1.mw in which the source of the red curve in Figure 1, and a full coding of the animation, appeared. In passing, he commented "The Draghilev method is used in my animation."
On April 2, 2013, Markian Hirnyk made two posts to MaplePrimes, the first detailing the Dragilev method; and the second, Maple code for the animation - essentially the same as found in the MECAN1.mw worksheet.
Figure 1 One frame of Hirnyk's animation
(The alternate spelling Draghilev appears in some references.)
This month's article examines the Dragilev method for solving certain systems of algebraic equations, and details how it is used to obtain a parametrization of the red curve in Figure 1, the curve of intersection of two surfaces. The reader should feel free to study Hirnyk's own description of the method.
Parametrizing the Intersection of Two Surfaces
The red curve in Figure 1 is the intersection of the surfaces defined by two equations , , where and are given respectively by
and
The first equation defines a sphere with center at and with radius 3; the second, a box-like closed surface drawn in green in Figure 2. The curve of intersection, drawn by Maple's intersectplot command, can be seen in Figure 2.
Figure 2 Surfaces defined by
Figure 3 Curve of intersection:
When the algebra is tractable, the following procedure would provide a parametric representation of the curve of intersection of two surfaces defined respectively by equations of the form and .
Solve for , so that becomes . Solve for , so that . Then, the parametrization is .
Applied to the given functions and , this process meets two difficulties. First, the attempt to obtain results in , so this will result in a piecewise-defined parametrization. Second, and more important, solving for requires finding the roots of polynomials of degree greater than five. Maple uses the RootOf construct to represent these solutions, but computationally, they are intractable.
A naive approach to obtaining a computationally useful parametric representation of the curve in Figure 3 is out of the question.
A Numeric Approach to the Parametrization
Since the surface defined by is a sphere, a conversion to spherical coordinates suggests itself. Table 1 contains the details.
Table 1 The functions and converted to spherical coordinates
Unfortunately, extracting either or from results in complicated RootOf expressions that can only be evaluated numerically and with great difficulty. Instead, a direct numeric solution for, say, , given a value of , would result in a numeric parametrization of the intersection curve shown in red in Figure 1.
Because the function has two branches (upper and lower), some method of returning a continuous value of as varies is needed. The circle drawn in black in Figure 4 is the basis of the numeric approach taken. For each point on , compute the nearest point on the graph of , the green curve in Figure 4.
Let be the circle defined by
For each pair on determined by the parameter , the nearest point on the curve defined by is to be computed. The commands in the Optimization package minimize this distance numerically, but the most successful approach is to solve numerically the analytic equations and
where is computed implicitly from .
XC := 3.9+cos(s): YC := 1.56+sin(s): P1 := plots:-implicitplot(S,theta=0..2*Pi,phi=0..Pi,gridrefine=2,scaling=constrained,color=green): P2 := plot([XC,YC,s=0..2*Pi],color=black): plots:-display(P1,P2,scaling=constrained); unassign('XC','YC','P1','P2'):
Figure 4 Graph of and circle
This equation is nothing more that the derivative of the square of the distance between on and on , since this is the objective function to be minimized. The expedient of starting Newton iteration from is the magic that lets Maple's fsolve command quickly and robustly return a unique -pair on for each value of on . The function , defined in Table 2 and which returns the Cartesian point
employs this approach to compute .
Table 2 The function that returns on the intersection of and
Figure 5 shows a graph of the intersection of and drawn by Maple's pointplot3d command with 500 points generated by the function . (The command itself is hidden input in the table containing the figure.) It would be difficult to distinguish between the curves in Figures 3 and 5.
Figure 5 Numerically parametrized intersection of and
The Dragilev Method
Markian Hirnyk's April 2, 2013, post to MaplePrimes details the Dragilev method. For the reader's convenience, the highlights of that post are paraphrased here.
In principle, equations , in variables , can solved for, say, the first of the unknowns in terms of . This amounts to a parametrization of the solution of the equations.
The Dragilev method obtains this parametrization by assuming , and solving the following initial-value problem.
If F is the vector whose components are the functions , and x is the vector whose components are the parametrized variables , then the left-hand sides of the first differential equations can be realized as the product of the Jacobian matrix for F (taken with with respect to x) times . The right-hand side of the last differential equation is the negative of the Jacobian of F taken with respect to . The numbers , are the coordinates of one solution of .
Table 3 displays the Dragilev differential equations for the case . Note that the right-hand side of the last equation is the negative of the Jacobian of and considered as functions of just and .
= =
Table 3 The equations of the Dragilev method for
If Cramer's rule is used to solve for and in the first two equations of Table 3, the equations for Dragilev's method when can be written as the explicit equations in Table 4.
=
Table 4 Explicit equations for Dragilev's method when
Notice that the right-hand side of each equation is actually a Jacobian. An application of the formalism in Table 4 to the equations and results in the equations listed in Table 5, where subscripts indicate partial derivatives.
Table 5 The Dragilev differential equations for and
Table 6 lists the Dragilev differential equations in the case .
Table 6 The Dragilev differential equations for , where
It should be easy to visualize the right-hand sides of the Dragilev differential equations when ; each is a Jacobian with the variables of differentiation systematically varied with the pattern in Cramer's rule.
Example
To apply Dragilev's method to the equations and , the initial solution , computed in Table 7, is first found.
Table 7 Calculation of an initial point for Dragilev's method
The right-hand sides of the differential equations required for applying Dragilev's method to the equations , are listed in Table 8.
Table 8 Right-hand sides of the differential equations needed when applying Dragilev's method to
The numeric solutions for are found with the calculations in Table 9.
Table 9 Numeric solutions for
Figures 3 and 5 show that , defines a closed curve in . One way to determine is suggested by Figure 6, a graph of .
Figures 3 and 5 show that , , defines a closed curve in , provided .
One way to determine an appropriate value of is suggested by Figure 6, a graph of .
The zero of in the interval is the first for which the loop in Figures 3 and 5 closes.
Apply the fsolve command to determine this value of .
Figure 6 Graph of
Figure 7 is a graph of the intersection of and drawn from the parametric representation determined by the Dragilev method.
Figure 7 Graph of the intersection of and drawn from the parametric representation obtained with the Dragilev method
The graph in Figure 7 is consistent with the graphs in Figures 3 and 5.
Legal Notice: © Maplesoft, a division of Waterloo Maple Inc. 2013. Maplesoft and Maple are trademarks of Waterloo Maple Inc. This application may contain errors and Maplesoft is not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact Maplesoft for permission if you wish to use this application in for-profit activities.
