System of quadratic equations -- incomplete solution

Dear Krishna,

Actually, you raise a very good point.

So the problem is not that solve() in this case may give false solutions;
but that instead of giving a complete set of four solutions (two of which
are false, but we don't know which two without knowing the values of r1 and
r2) it only gives two solutions but these aren't always the two "true"
solutions under the normal sign convention of sqrt. The other two solutions
can be obtained by flipping the sign of sqrt, but in other cases, e.g., when
solving a quadratic equation, Maxima does write out both solutions
explicitly. Furthermore, in the case of your two sets of equations, the
solve() function behaves inconsistently, choosing a different pair of
solutions for two slightly different formulations of the same set of
equations.

Yes, I buy that. I'm cc'ing the mailing list again, hopefully someone who
actually worked on the solve() function can take a peek. To recap, for their
benefit, the problem is illustrated by the following:

(%i1) display2d:false$
(%i2) e1a: x^2+y^2=r1^2$
(%i3) e2a: (x-1)^2+(y-1)^2=r2^2$
(%i4) sola: solve([e1a,e1a-e2a],[x,y])$
(%i5) e1b: x^2+y^2=(r1-err)^2$
(%i6) e2b: (x-1)^2+(y-1)^2=(r2-err)^2$
(%i7) solb: solve([e1b,e1b-e2b],[x,y])$
(%i8) sola;
(%o8) [[x = -(sqrt(-r2^4+(2*r1^2+4)*r2^2-r1^4+4*r1^2-4)+r2^2-r1^2-2)/4,
        y =
(sqrt(-r2^2+2*r1*r2-r1^2+2)*sqrt(r2^2+2*r1*r2+r1^2-2)-r2^2+r1^2+2)/4],
       [x = (sqrt(-r2^4+(2*r1^2+4)*r2^2-r1^4+4*r1^2-4)-r2^2+r1^2+2)/4,
        y = -(sqrt(-r2^2+2*r1*r2-r1^2+2)*sqrt(r2^2+2*r1*r2+r1^2-2)
+r2^2-r1^2-2) /4]]
(%i9) solb,err=0;
(%o9) [[x = -(sqrt(-r2^4+(2*r1^2+4)*r2^2-r1^4+4*r1^2-4)+r2^2-r1^2-2)/4,
        y =
(sqrt(-r2^2-2*r1*r2-r1^2+2)*sqrt(r2^2-2*r1*r2+r1^2-2)-r2^2+r1^2+2) /4],
       [x = (sqrt(-r2^4+(2*r1^2+4)*r2^2-r1^4+4*r1^2-4)-r2^2+r1^2+2)/4,
        y = -(sqrt(-r2^2-2*r1*r2-r1^2+2)*sqrt(r2^2-2*r1*r2+r1^2-2)
+r2^2-r1^2-2) /4]]

The two solution sets (%o8 and %o9) are both incomplete (the full solution
set includes four solutions, only two of which are valid but we don't know
which two without knowing the values of r1 and r2) and they do not evaluate
to the values using identical sign conventions.

By the way, I believe that when the values of r1 and r2 are known in
advance, solve does give the correct solutions; e.g.:

(%i1) e1a: x^2+y^2=r1^2$
(%i2) e2a: (x-1)^2+(y-1)^2=r2^2$
(%i3) solve(ev([e1a,e1a-e2a],r1^2=29,r2^2=17),[x,y]);
(%o3)                  [[x = 2, y = 5], [x = 5, y = 2]]
(%i4) solve(ev([e1a,e1a-e2a],r1^2=29,r2^2=37),[x,y]);
(%o4)                [[x = 2, y = - 5], [x = - 5, y = 2]]
(%i5) solve(ev([e1a,e1a-e2a],r1^2=29,r2^2=45),[x,y]);
(%o5)              [[x = - 2, y = - 5], [x = - 5, y = - 2]]
(%i6) solve(ev([e1a,e1a-e2a],r1^2=29,r2^2=25),[x,y]);
(%o6)                [[x = 5, y = - 2], [x = - 2, y = 5]]


Viktor



-----Original Message-----
From: Krishna Myneni [mailto:krishna.myneni at ccreweb.org] 
Sent: Wednesday, July 04, 2012 8:00 PM
To: Viktor T. Toth
Subject: Re: [Maxima] solution of quadratic equations -- incorrect solution

Dear Viktor,

Thank you for your detailed response. I think context is important here. 
We are considering the solution of equations. I would argue the 
counterpoint that a computer algebra system's solve() function can track 
multiple branches of a solution simultaneously, just as a human 
algebraist can, and would if the parameter bounds were unrestricted. In 
fact, your discussion below explicitly demonstrates the fact that a 
human algebraist can find all four *potentially valid* solutions!

First, note that our system of equations for the given problem nowhere 
specify the "sqrt()" function:

x^2 + y^2 = r1^2

(x-1)^2 + (y-1)^2 = r2^2

The issue of finding the four possible solutions to the above set of 
equations really does not have to do with what we mean by "sqrt(x)". 
That is an internal notation in the computer algebra system used to 
arrive at the solutions. The output of the solutions, of course, 
requires upon an agreed-upon notation. The notation for the above system 
does not have a sign ambiguity. Solve() can, in principle, return a list 
of all possible solutions for the different parameter regimes given by 
the space (r1, r2).

For example, when I type in Maxima,

solve(x^2-4,x);

I obtain both solutions, x=-2 and x=+2.

Similarly, for my two equations above, the second step of your solution 
below should be to write,

y = [+sqrt(r1^2-x^2), -sqrt(r1^2-x^2)]

and proceed from there. Below, you explicitly wrote both solutions for x 
(in terms of y) using both possible signs in front of the square root, 
but did not do so for y, as in my line above. Of course not all four 
solutions are going to be valid when the parameters are later specified. 
But that's a problem for the user to solve. The computer algebra system 
should not arbitrarily remove two potentially valid solutions. I would 
argue that the computer algebra system is not only capable of providing 
all four possible solutions in this case, but should do so as a matter 
of correctness and completeness.

Best,
Krishna


On 07/04/2012 04:47 PM, Viktor T. Toth wrote:
> Dear Krishna,
>
> The topic of our discussion has changed from Maxima proper to algebra in
> general (and the sign ambiguity of the square root function) which is why
I
> don't think we should burden the Maxima mailing list with it anymore.
>
> You are of course correct that the convention for the square root is to
use
> the positive value as the principal value. But the problem is that a
> computer algebra program (or a human algebraist, for that matter) does not
> know in advance what that value will be. Consider the expression,
sqrt(x^2).
> Is it x or -x? It depends on the sign of x of course. Or consider the
> expression sqrt(-x)*sqrt(-x). Is a computer algebra package allowed to
> simplify it to sqrt((-x)*(-x)) which is just sqrt(x^2)? Or perhaps
simplify
> it to x?
>
> So suppose that a computer algebra algorithm is allowed to replace
sqrt(x^2)
> with x. In this case, if x=-2, the result of sqrt(x^2) will be -2.
>
> Now suppose that another computer algebra algorithm is not allowed to make
> this replacement. So to evaluate sqrt(x^2), it first computes x^2=4, and
> takes the square root; the result is +2.
>
> Both algorithms are rigorous and follow the rules exactly. But one set of
> rules (entirely within "convention") yields the -2 result, another set
> yields +2.
>
> But you know what? Let's forget about computer algebra. Let us be human
> algebraists and solve your system of equations.
>
> First, from
>
> 	x^2 + y^2 = r1^2,
>
> we get
>
> 	y = sqrt(r1^2 - x^2).
>
> Second, we rearrange
>
> 	(x - 1)^2 + (y - 1)^2 = r2^2,
>
> to get
>
> 	(x - 1)^2 + (sqrt(r1^2 - x^2) - 1)^2 = r2^2,
>
> which is
>
> 	x^2 - 2*x + 1 + r1^2 - x^2 - 2*sqrt(r1^2 - x^2) + 1 = r2^2.
>
> Rearranging again,
>
> 	r1^2 - r2^2 + 2 - 2*x = 2*sqrt(r1^2 - x^2).
>
> Squaring this (*), we get
>
> 	(r1^2 - r2^2 + 2)^2 - 4*(r1^2 - r2^2 + 2)*x + 4*x^2 = 4*r1^2 -
> 4*x^2,
>
> or
>
> 	8*x^2 - 4*(r1^2 - r2^2 + 2)*x + r1^4 + r2^4 - 2*r1^2*r2^2 - 4*r2^2 +
> 4 = 0.
>
> Dividing by 8, we get
>
> 	x^2 - (1/2)*(r1^2 - r2^2 + 2)*x + r1^4/8 + r2^4/8 - r1^2*r2^2/4 -
> r2^2/2 + 1/2 = 0.
>
> This we can solve for x:
>
> 	x = (1/4)*((r1^2 - r2^2 + 2) +/- sqrt(-((r1 - r2)^2 - 2)*((r1 +
> r2)^2 - 2)).
>
> And, of course, we already have a solution for y, given by the second
> equation above.
>
> So let us try a specific set of values. Let's say that r1 = 17/3 and r2 =
> 13/3. So let us calculate x:
>
> 	x = (1/4)*(46/3 +/- sqrt(-(-2/9)*98)),
>
> which means
>
> 	x = 5  or  x = 8/3.
>
> We can now compute y:
>
> 	y = sqrt(r1^2 - x^2),
>
> which means
>
> 	y = 8/3  or  y = -8/3
>
> for x = 5, and
>
> 	y = 5  or y = -5
>
> for x = 8/3.
>
> So we have four solutions:
>
> 	x = 5, y = 8/3,
> 	x = 5, y = -8/3,
> 	x = 8/3, y = 5,
> 	x = 8/3, y = -5.
>
> So let us substitute these solutions back into your original equation. The
> first equation yields
>
> 	5^2 + (8/3)^2 = (17/3)^2,
> 	5^2 + (-8/3)^2 = (17/3)^2,
> 	(8/3)^2 + 5^2 = (17/3)^2,
> 	(8/3)^2 + (-5)^2 = (17/3)^2,
>
> whereas the second equation yields
>
> 	4^2 + (5/3)^2 = (13/3)^2,
> 	4^2 + (-11/3)^2 <> (13/3)^2,
> 	(5/3)^2 + 4^2 = (13/3)^2,
> 	(5/3)^2 + (-6)^2 <> (13/3)^2.
>
> So by substituting these explicit results into the original equations, we
> find that only two of the solutions are valid:
>
> 	x = 5, y = 8/3,
> 	x = 8/3, y = 5.
>
> The other two solutions are false solutions that arise as a result of the
> square root's sign ambiguity. (Specifically they arise because in order to
> obtain an algebraic solution, we needed to square an equation during the
> derivation, at the spot where I put a (*) in the text).
>
> If you express the solution algebraically, because of the sign ambiguity
in
> the two square roots, you always end up with a set of four solutions, only
> two of which are actually valid. We cannot remove this sign ambiguity
before
> assigning explicit values to r1 and r2. For the values I have chosen, we
> needed both signs of the square root in the solution for x, but only the
> positive sign in the solution for y. I could have picked different values
> for which we would have had to use the negative sign for the y-solution.
So
> if we cannot do it on paper, we surely cannot expect a computer algebra
> system to do it!
>
>
> Viktor
>   
>
>
>
> -----Original Message-----
> From: Krishna Myneni [mailto:krishna.myneni at ccreweb.org]
> Sent: Wednesday, July 04, 2012 3:41 PM
> To: Viktor T. Toth
> Subject: Re: [Maxima] solution of quadratic equations -- incorrect
solution
>
> On 07/04/2012 09:20 AM, Viktor T. Toth wrote:
>> Dear Krishna,
>>
>> Thanks for letting me know. I noticed that I was replying to the message
>> that you sent only to me, and there was a separate post to the mailing
> list,
>> but I figured it's probably a good idea to move this discussion away from
>> the mailing list anyway, since it is not necessarily of general interest
>> anymore.
>>
>> Please note that in my last message, where I said that "the y solutions
> are
>> the same up to sign", what I really meant was that they are the same up
to
>> the sign of the square roots.
>>
>> I also have a missing sign in one line (it should be kind of obvious, but
> I
>> don't want to mislead). Where the text reads
>>
>> y =
>>
>
(-%i*sqrt(-r2^2+2*r1*r2-r1^2+2)*%i*sqrt(r2^2+2*r1*r2+r1^2-2)-r2^2+r1^2+2)/4
>> it should actually read
>>
>> y =
>>
>
(-%i*sqrt(-r2^2+2*r1*r2-r1^2+2)*(-%i)*sqrt(r2^2+2*r1*r2+r1^2-2)-r2^2+r1^2+2)
>> /4
>>
>> Note that the second %i also has a minus sign (this is what was left out
> in
>> my message). Of course it's correct either way (again, because of the
sign
>> ambiguity of the square root!) but the second version better illustrates
> the
>> point I was trying to make.
>>
>>
>> Viktor
>>
>>
>>
>>
>>
>>
> Viktor,
>
> Thank you for the details. Yes, I see the equivalence to within a minus
> sign of the square root term. I believe this discussion would be of
> general interest to others with about the same skill level with Maxima
> as myself, which is "novice".
>
> I still consider Maxima's returned solutions as being not complete by
> virtue of a) end-user expectations, b) convention, and c) consistency:
>
> a) The sqrt() function, in the domain of computing, typically has the
> meaning of returning the principal value (positive root).
>
> b) The square-root radical sign has the mathematical convention of
> denoting the principal value, from what I gather, though I'm not a
> mathematician.
>
> c) Maxima itself treats the sqrt() function as returning the principal
> value, e.g.
>
>      c.1) "sqrt(16), numer;"  returns only the positive value.
>
>      c.2) "solve(a*x^2+b*x+c, x);"  returns two solutions, indicating
> that sqrt() has no ambiguity with respect to sign, i.e. the complete
> solution set assume that sqrt() is to be taken as positive, and both
> signs are explicitly provided.
>
> I believe that in order for Maxima's solve() to be useful, and for
> Maxima to remain consistent, it cannot assign an ambiguous sign
> interpretation for "sqrt()".
>
> Regards,
> Krishna
>
>