Three Surface Intersection Problem Analysis

This document may be copied and/or distributed.

This is one of three inter-related files. To locate the other two files, access Three Surface Intersection Problem.

The following is a local copy of the author's reply posted to sci.math.num-analysis. Subject line of the thread is "Nonlinear equations - analytical solution?", and the start date was October 17, 2011.

--------------------------

On Oct 17, 3:16 am, Gib Bogle <g.bo...@auckland.ac.nz> discussed the possibility of solving a certain system (System A, see below) of three non-linear equations in three variables, in closed form. On the basis of informal reasoning (and using a reasonable standard for what is "closed form"), I conjecture that this is not possible in any reasonable way.

System A: System A is the system of three equations as given by the OP (I have made some minor changes in notation). They are:

Db + Dc = e1
Da + Db = e2
Da + Db + Dc + Dd = e3

where Da is a notation for: sqrt( sum(m=1 to 3; (x[m]-a[m])^2) ), and Db, Dc, and Dd are similar notations.

a, b, c, d, e and x are all points in three-space. x is the unknown. a, b, c, d and e are constants (presently left undetermined). Now, substitute equation two into equation three and obtain:

System B:

Db + Dc = e1
Da + Db = e2
Dc + Dd = e3 - e2

Note that: System B iff System A. Elsewhere, I refer to System B as the "basic set". Now for each equation in System B, isolate one of the radicals and square. Then, isolate the remaining radical and square again. This gives:

System C:

   
(Db^2 -      e1^2 - Dc^2)^2 -      4*e1^2*Dc^2 = 0 
(Db^2 -      e2^2 - Da^2)^2 -      4*e2^2*Da^2 = 0 
(Dc^2 - (e3-e2)^2 - Dd^2)^2 - 4*(e3-e2)^2*Dd^2 = 0     

Note that: System B implies System C. Now eliminate the Da, etc. notations and carry out the squares of the sums.

This gives: System D.

System D is a system of three polynomials in x[1], x[2], and x[3]. The equations are fairly lengthy (about 20 lines long) and should be obtained using a computer algebra system (a CAS). Due to cancellation, each D equation typically has degree two. Note that: System C iff System D. Thus, System B implies System D. Due to the two square operations, the D roots are a mixture of B roots and extraneous roots.

System D is the launching point for the remaining development, and is referred to elsewhere as the "polynomial set". According to Bezout's Theorem, System D should have a maximum number of distinct solutions equal to the product of the degrees of each equation (the Bezout bound), that is, typically, 2*2*2 = 8.

In addressing the original question, "is there a closed form solution for B?", we will assume that any such analytic solution can only be obtained by forming an analytic solution of D. (I have no proof that this is so.) We will also assume that the only way to obtain an analytic solution of D is by the method of "polynomial reduction". (Again, I have no proof that this is so.) Perhaps it is well to mention that success of power series reversion to solve System D rests on how well we choose the "expansion point". In other words, the expansion point must be sufficiently close to one of the eight solutions so that the reversion power series converges to that solution. On that basis, therefore, power series reversion is not completely analytic -- it requires some degree of searching to locate good expansion points.

Polynomial reduction consists of finding a univariate polynomial, call it E, such that: the original square system of polynomials (in this case, D.1, D.2, and D.3) implies E. Hereafter, we refer to E as the eliminant. Polynomial E is a univariate polynomial in one of the D variables. This surviving variable can be chosen at will.

To solve D, we go through three rounds: 1st, compute the first eliminant by eliminating x[2] and x[3], solve the eliminant and obtain one of the x[1] roots; 2nd, put the root into two of the D equations (such as D.2 and D.3), compute the eliminant for this two equation system by eliminating x[3], solve the eliminant and obtain one of the x[2] roots; 3rd, put the two roots now available into one of the D equations (such as D.3), solve it, and obtain one of the x[3] roots. The root triple so obtained _may_ be a solution of System D. For each round, there will be as many roots as the degree of the "eliminant" (regarding D.3 as the "eliminant" of round three). The important thing is that when one generates the entire set of triples, this set _will_ contain all of the System D solutions.

There are various ways of forming the eliminant. There are two older methods: one is the Euclidean Greatest Common Factor algorithm, the other is Sylvester's Dialytic Method of Elimination (a determinant based approach). There seem to be newer methods ("Grobner basis" is a term frequently seen) but I know nothing about these. I am most familiar with EGCF and it seems to me to be a good way to conceptualize what is going on under the hood. I used Maxima (the free CAS) to test and evaluate the System B problem; the package comes with its own ELIMINATE command. To date, I have not found any information as to how Maxima does elimination; but since it seems to work, this omission does not seem critical.

Elimination is far too difficult to do by hand except in the most trivial cases. Even for a CAS, if the coefficients of the input system are left undetermined, one gets eliminant equations that are usually enormous. Even quite small systems give expressions that are dozens of pages long. In the case of System D, running ELIMINATE tied up my computer for 20 minutes at which time it was canceled. However, when specific numbers were assigned to a, b, c, d, and e, ELIMINATE ran quite quickly.

As it turns out, the degree (and number of roots) for the first eliminant is typically 16, the degree for the second is typically 4, and the degree for the third is typically 2. Thus, we might expect the number of solutions of System D to be 16*4*2 = 128. Note that the number of solutions for System D is, according to Bezout's Theorem, bounded by 2*2*2 = 8. Since 128 is much greater than 8, this paradox requires resolution. Also, when we test the real solutions of the 128 outcomes, we find that the vast majority of them do not, in fact, satisfy System D. (However, some do.) My working theory is that the first round of elimination produces many x[1] solutions which, when substituted into two of the D equations, gives rise to two equations that either: one, are NOT logically independent, or two, are inconsistent. (Two equations are logically dependent when their corresponding functions are functionally dependent.) In such situations, elimination is not expected to give correct results. Another possibility is that having completed the first two rounds, the remaining equation in one variable may be a tautology (0 = 0). In such a case, there is no way to solve for the last variable. The inequality of 128 and 8 is an important question. I ultimately would like to do some testing and verify the explanations I have proposed. This will take some time and cannot be undertaken at this moment.

To get back to the original question, is there an analytic solution of System B?, my negative conclusion rests partly on the fact that the first eliminant, which is degree 16, will have coefficients that may be the result of hundreds or thousands of elementary arithmetic operations. Observing that there are special functions that give analytic solutions for quintics and sextics, it is conceivable that special functions could be developed for the solution of degree 16 univariate polynomials. Even if that is so, the arguments of such special functions would be the enormously long and complicated coefficients produced by the elimination process. My conclusion therefore is that if there is an analytic way to solve System D, it is totally impractical.

The "three round" method of solution described above leads to an interesting observation: to solve the system, all we need is some method of solving high degree univariate polynomials. Sturm sequences are valuable here since they definitely will locate all real roots. Carrying out the three rounds, we have a simple method of obtaining all of the System D solutions (as well as many other outcomes that are extraneous even for System D). This set will definitely contain the (potentially) 8 solutions of System B. Testing of each System D outcome is required to determine if it is, in fact, a solution of System B.

Solving a Polynomial System

We assume that System A was written down with a purpose in mind -- to solve it. There are two approaches: 1st, the numerical technique; and 2nd, "semi- analytic" solution of System D. A purely numerical solution must deal with the issue that we don't really know how many real solutions there are -- it might be anything from zero through eight. If we don't find a solution early on, how much time should we spend looking elsewhere? Similarly, there might be a need to find ALL of the solutions. So, even if we find one solution right away, the same difficulty arises when looking for a second. Is there a second? And so on. Based on the nature of the original problem, it may be possible to calculate the boundaries of a search cube that will contain all of the 8 possible real roots. If we subdivide this search cube into a fairly large number of fairly small sub-cubes, it may be possible to find all of the 8 possible solutions by iterative methods, each iteration starting in each sub-cube. The question is, how small do the sub-cubes have to be? At the moment, I have no idea how one would calculate that (or even if it is calculable in the first place). As best as I can tell, the only way to be confident of having located all (potentially) 8 solutions would be to transform System D into complex equations. With a sufficiently small sub-cube size, we must eventually find (potentially) 8 complex numbers that satisfy System D. The set of those that are purely real will contain the wanted real solutions of System B.

On the other hand, the polynomial reduction method described above (i.e, the three round approach) sidesteps the particular above-mentioned subdivision size problem. The use of Sturm sequences is a methodical approach to definitely locate each and every real root (and hence the number of real roots). Assuming there is a need to locate ALL real roots of System B, polynomial reduction may be a simpler approach. I have no information as to efficiency comparisons between the two methods.

Test Program

Using Maxima (the free CAS), a program was written to test the polynomial reduction method. To summarize: (1) the program works, (2) it produces various extraneous roots that do not satisfy either System D or B, (3) it produces extraneous roots that satisfy D but not B. Two test cases were tested, the more significant one being a situation where there were two solutions, satisfying both D and B. Another test case produced 6 solutions of D, none of which it happened, satisfied B. Constructing good a, b, c, d, and e test data can be difficult, so the testing was truncated as this point.

The Maxima coding can be found at the author's web site, access the page http://davidziskind.org/Three_Surface_Intersection_Problem.htm. The Maxima package comes with an ELIMINATE command and a REALROOTS command (which solves univariate polynomials using Sturm sequences). Reading Maxima code can be somewhat daunting; it takes quite a while to understand the psychology of the procedural mathematics being used. Also, there are a fair number of quirks that the package uses and learning them all can be time consuming. I will point out just two: first, ":" is the Maxima symbol for "bind" which is roughly equivalent to "="; and second, a statement such as "var3 : part(expression_a, 1)" may mean that expression_a is a list with just one element (which is than put into var3). For a full understanding of the program as well as translation into another CAS, some study of the Maxima manual is required.

David Ziskind
http://davidziskind.org
david.ziskind@att.net

Home

Rev. 11/11/11 g