MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Strange empty set of solutions

  • To: mathgroup at smc.vnet.net
  • Subject: [mg71853] Re: [mg71814] Re: Strange empty set of solutions
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Fri, 1 Dec 2006 06:22:03 -0500 (EST)
  • References: <ekh7pg$sgs$1@smc.vnet.net> <ekjfrf$d7h$1@smc.vnet.net> <200611301105.GAA08424@smc.vnet.net>

José Carlos Santos wrote:
> On 29-11-2006 8:19, Jens-Peer Kuska wrote:
> 
> 
>>and we can't read you mind and the memory of your computer
>>so we must imagine a matrix M and write down
> 
> 
> Do you want an example? Here it is:
> 
> M = {{4/5(c - 1), -2/Sqrt[5]s, 2/5(1 - c)},
>       {2/5(1 - c), -1 + s/Sqrt[5], 4/5 + c/5},
>       {-2s/Sqrt[5], -c, -1 + s/Sqrt[5]}} // N
> 
> with c = Cos[Sqrt[5]] and s = Sin[Sqrt[5]].
> 
> If I type
> 
> Solve[{M.{x, y, z} == {0, 0, 0}}, {x, y, z}]
> 
> I get
> 
> {{x -> 0. - 0.0438861 z, y -> 0. + 1. z}}
> 
> but if I type
> 
> Solve[{M.{x, y, z} == {0, 0, 0}, x^2 + y^2 + z^2 == 1}, {x, y, z}]
> 
> then I get the empty set. Why is that?
> 
> Best regards,
> 
> Jose Carlos Santos


In the first example you have three equations in three variables. They 
are linear and have rank of 2. The numerical row reduction code 
correctly deduces this and returns a one dimensional solution set.

When you augment by the norm=1 you now have four equations in three 
variables. They are overdetermined but no longer linear. Now ou are in 
the realm of polynomial algebra where dependencies are more difficult to 
assess, and indeed this one is missed. Solve believes it has an 
overdetermined system and returns an empty solution set.

Ways to avoid this pitfall are to work with the exact system, or with a 
higher precision numericization. Also I would recommend NSolve in the 
case where you expect to have finitely many solutions.

c = Cos[Sqrt[5]];
s = Sin[Sqrt[5]];
exactM = {{4/5(c - 1), -2/Sqrt[5]s, 2/5(1 - c)},
       {2/5(1 - c), -1 + s/Sqrt[5], 4/5 + c/5},
       {-2s/Sqrt[5], -c, -1 + s/Sqrt[5]}};
M100 = N[exactM, 100];
allpolys100 = Flatten[{M100.{x,y,z}, x^2+y^2+z^2-1}];

Now you get your two solutions.

solns = NSolve[allpolys100, {x,y,z}]

I should mention that this is a tenuous area. You are working with 
finite precision on a problem for which perturbations give no solution. 
So you really need to use the benefits afforded by significance 
arithmetic, or else code a method that can handle "fuzzy zeros".

An alternative, for problems like this where you have a linear solution 
set and wish to select certain members, is to use a linear algebra 
method first and then post-process. This is advantageous because linear 
algebra is both faster and, if you use appropriate methods e.g. singular 
value decomposition, better studied and more robust in terms of 
assessing and handling rank deficiencies.


Daniel Lichtblau
Wolfram Research



  • Prev by Date: NETLink: LoadNETAssembly["C:\\lego\\Debug\\C4F.LegoRcx.dll"] failed
  • Next by Date: Re: Re: Strange empty set of solutions
  • Previous by thread: Re: Strange empty set of solutions
  • Next by thread: Re: Re: Strange empty set of solutions