[Date Index]
[Thread Index]
[Author Index]
Re: Re: Solve / NSolve
*To*: mathgroup at smc.vnet.net
*Subject*: [mg95404] Re: [mg95348] Re: Solve / NSolve
*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>
*Date*: Sat, 17 Jan 2009 05:32:44 -0500 (EST)
*References*: <gkgouo$3sg$1@smc.vnet.net> <200901161109.GAA14111@smc.vnet.net> <DBB0C883-397F-4ED4-AEA9-EC8F2DD85382@mimuw.edu.pl>
On 16 Jan 2009, at 13:25, Andrzej Kozlowski wrote:
> In your second case there are no parameters and Solve and NSolve use
> different algorithms. Solve rationalizes the equations and uses
> exact GroebnerBasis, NSolve uses numerical Groebner basis. The first
> approach is faster in this case but the second approach shoudl be
> more reliable in cases involving numerical instability.
I wrote the above too carelessly, so besides being vague it can be
misleading. So I have decided to send a little more detailed
explanation with the hope that it can be of some use.
The standard method of solving systems of polynomial equations with
exact coefficient is based on an algebraic algorithm called the
Groebner basis algorithm. This is the algorithm used by Solve.
Unfortunately, like most exact algebraic algorithms it has rather high
complexity. One might hope that in cases when one only needs
approximate solutions (particularly when the coefficients of the
system are approximate anyway) there would be a faster numerical
method. Unfortunately the GroebnerBasis algorithm is numerically
unstable and in unfavorable cases a small perturbation in the
coefficients of the system will lead to a very different solution.
Thus the algorithm cannot be used reliably with fixed precision
arithmetic (and in particular with MachinePrecision).
The obvious approach, adopted by most computer algebra systems is
this: given a polynomial system with inexact coefficients, first
rationalize it, then use the exact Groebner basis algorithm to find
solutions and finally apply N with the requested precision. This is
exactly what Solve does. This method is effective except for a minor
problem that rationalizing is not a unique operation so in unstable
situation different rationalizations will give different results and a
more serious problem that this approach will be impossibly slow on
more complex systems.
Mathematica offers also another approach, based on its significance
arithmetic (a fast approximation to interval arithmetic) that in many
situations can overcome both problems. Essentially the precision of
computations is automatically increased until GroebnerBasis
computations produce a stable answer. On complex problems this is
usually faster than using exact Grobner basis on a rationalized
system, but it can be slower in the case of simple systems.
NSolve uses this approach, but I am not quite sure if it does it only
when WorkingPrecision other than MachinePrecision is used or always.
In any case, the general principle is: avoid if possible using
symbolic functions (and that includes Simplify etc) on input
containing inexact quantities as the results can be quite different
form what you might expect.
Andrzej Kozlowski
Prev by Date:
**Re: Which editor do you use for math articles**
Next by Date:
**Re: Solve / NSolve**
Previous by thread:
**Re: Re: Solve / NSolve**
Next by thread:
**Re: Solve / NSolve**
| |