RootFinding - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Factorization and Solving Equations : Roots : RootFinding : RootFinding/Isolate

RootFinding

  

Isolate

  

isolate the real roots of a univariate polynomial or polynomial system

 

Calling Sequence

Parameters

Options

Description

Univariate polynomials with irrational coefficients

Examples

References

Compatibility

Calling Sequence

Isolate(f)

Isolate(f, X, digits=d, constraints=icons, output=outpt, maxroots=mxrts, method=mthd)

Isolate(g, X, digits=d, constraints=rcons, output=outpt, maxroots=mxrts, method=ABND, maxprec=mxprc, partialresults=partial)

Isolate(J, X)

Isolate(J, X, digits=d, constraints=icons, output=outpt, maxroots=mxrts, method=mthd)

Parameters

f

-

univariate polynomial with real-valued numeric coefficients

g

-

univariate polynomial with real-valued coefficients

J

-

set or list of polynomials, or a PolynomialIdeal

X

-

(optional) list of variables

d

-

(optional) positive integer; number of significant digits (default: Digits)

icons

-

(optional) list of polynomials with integer coefficients

rcons

-

(optional) list of polynomials with real coefficients

outpt

-

(optional) type of output: numeric (default), midpoint, or interval

mxrts

-

(optional) maximum number of roots to be returned. Default is .

mthd

-

(optional) name of algorithm to use: ABND, RS or RC. Default is ABND for univariate and RS for multivariate inputs.

mxprc

-

(optional) maximum internal working precision. Default is  for numeric coefficients, otherwise see the description of the option below.

partial

-

(optional) return regions that could not be completely decided: true or false (default).

Options

• 

The digits=d option controls the output precision.

  

In the case of numeric coefficients, the isolating intervals have a relative diameter of at most 10d. That is, if the result is evaluated numerically, the resulting floating point mantissae have d digits and an error of at most 0.6 units in the last place. Note that this does not necessarily mean that the preceding digits are correct; e.g., an exact value of 57512500 could be represented with the interval 2.299,2.301 at digits=4. In particular, isolating intervals corresponding to a root of magnitude larger than 10d may have a width larger than 1; even if the exact root is an integer, the midpoint does not necessarily round to this value.

  

For non-numeric coefficients, it might not be possible to decide if the trailing coefficient vanishes or, equivalently, whether 0 is an exact root. In this situation, the isolating interval for the near-0 root will be of absolute diameter of at most 10d and contain 0, and neither of the output formats midpoint or numeric (see below) will help to determine the sign of the root; for closer inspection, use the output format interval.

• 

The output option specifies the format of the output, and can be one of interval, midpoint, or numeric (the default). output=interval returns a list of intervals with rational endpoints, each containing a root. The intervals are open, unless an exact root is found; in this situation, both endpoints are identical. output=midpoint computes the midpoint of each interval exactly, so that a list of rational approximations is returned. output=numeric evaluates the midpoints numerically at the desired precision d, resulting in a list of floating point approximations.

• 

The constraints option takes a list of polynomials with real-valued coefficients and evaluates them at the roots of the system. This option is more reliable than direct evaluation using evalf because of two reasons: (1) A smaller numerical error is introduced, and (2) the results are certified in the sense that the exact value of the constraint at the exact root will always be contained in the interval returned by this option. In contrast, evaluation via evalf can be subject to round-off errors and cancellation.

• 

The maxroots option specifies the maximum number of roots to be returned. If the polynomials have fewer roots than maxroots, this setting is ignored.  Note that this option does not guarantee any particular roots to be returned.

  

This option cannot be used in conjunction with method=RC. If both method=RC and maxroots are given, method is silently ignored.

• 

The method option specifies the algorithm to use. It can be ABND (default for the univariate case), RS (default for the multivariate case) or RC. method=RS uses the RealSolving (RS) C library by F. Rouillier et al. method=RC computes the result by using the RegularChains package by M. Moreno Maza et al.

  

method=ABND uses the Approximate Bitstream Newton-Descartes method by A. Kobel et al., which is based on the univariate components of RS. The ABND variant gives improved complexity guarantees and significantly improved performance for high accuracy requests, whereas RS' performance tends to be better for well-conditioned instances of small input size and accuracy demand.

  

The constraints and maxroots options cannot be used simultaneously with method=RC.  If both method=RC and constraints or maxroots are specified, Isolate carries out the computation using method=ABND (univariate case) or method=RS (multivariate case).

  

The maxprec and partialresults options can only be used with method=ABND (and univariate inputs).  If maxprec or partialresults is given, the choice of method is ignored.

• 

For multivariate polynomial systems, when method=RS is specified, Isolate first computes a Groebner basis followed by a Rational Univariate Representation. The second argument must be an ordered list of variables, and the roots are returned as corresponding lists of values.

• 

The maxprec option specifies the maximum internal working precision of the root solver. The numerical solver works in stages of gradually increasing precision; when a new stage begins, the computation is interrupted if the new precision would exceed the given value.

  

The unprocessed intermediate results can be inspected with the partialresults option (see below).

  

If an interval can be proven to be isolating within the maxprec constraints, but cannot be refined to the accuracy requested through the digits option, it will nevertheless be reported in the default output even if partialresults is not given.

  

This option can only be used in conjunction with method=ABND (and, thus, univariate polynomials). If maxprec is specified, the choice of method is silently ignored.

• 

If partialresults=true, a list of intervals that have not been fully processed within the limits of maxroots or maxprec is returned as a second (or third) return value. Each item of the list is a record with two fields, named interval and multiplicity. The interval entry contains an interval with dyadic endpoints, and the multiplicity entry contains a certified estimate of the possible number of distinct roots of g in the corresponding interval, given as a range.

  

This option can only be used in conjunction with method=ABND (and, thus, univariate polynomials). If partialresults is specified, the choice of method is silently ignored.

Description

• 

The RootFinding[Isolate] command isolates the real roots of univariate polynomials and polynomial systems with a finite number of solutions. By default it computes isolating intervals for each of the roots and numerically evaluates the midpoints of those intervals at the current setting of Digits. If possible, the intervals are refined such that the numerical evaluation is accurate up to 0.6 units in the last place; see the digits option for details.

  

Unlike purely numerical methods no roots are ever lost, although repeated roots are discarded. This command does not support parametric or complex number coefficients.

  

For a polynomial with numeric coefficients (that is, all coefficients are of type integer, fraction or float), all real roots will be given in the output (unless specifically requested otherwise, see the maxroots and maxprec options).

  

Polynomials with irrational coefficients are only supported in the univariate case, and only with method=ABND (see below). For such inputs, complete and certified root isolation is infeasible for sufficiently general instances, and Isolate returns a best-effort output according to the specification in the corresponding section.

• 

The system must have a finite number of complex solutions; otherwise, Isolate will return an error.

• 

This function is part of the RootFinding package, and can be used in the form Isolate(..) only after executing the command with(RootFinding).  However, it can always be accessed through the long form of the command using RootFinding[Isolate](..).

Univariate polynomials with irrational coefficients

• 

Irrational coefficient support for univariate polynomials is provided with method=ABND. If non-numeric coefficients are given, the choice of method is silently ignored and the ABND algorithm is used. If irrational polynomials are passed to RootFinding[Isolate], the user is required to take proper precautions for dealing with possibly incomplete output; see the description of the maxprec and partialresults options above.

• 

In full generality, root isolation for arbitrary polynomials is infeasible: a purely numerical routine can eventually isolate simple roots, but cannot detect multiple roots. A square-free decomposition is required, but this cannot be performed in all situations. A notable exception are polynomials with numeric coefficients, where such a decomposition is done implicitly if required.

  

Instead, the ANBD root solver tries a best-effort isolation up to a certain maximum internal working precision maxprec. If the instance could not be conclusively handled within that precision constraint, a partial output is given. It contains (1) a list of proven isolating intervals, (2) a list of the constraint polynomials (if applicable, i.e., if constraints is not empty) evaluated at those isolating intervals, and (3) a list of unresolved intervals (if partialresults=true; see the description of the option above).

• 

There is no general way to determine the "right" value of maxprec a priori. For numeric instances, the default maximum precision is virtually infinity; such instances can always be dealt with in a complete manner. For non-numeric instances, the default is chosen purely heuristically, as a function of the value of the Digits environment variable, the digits option, and the degree n of the polynomial g: maxprec defaults to maxDigits,4d,8nlog2n. Under typical circumstances, the default value allows to isolate and refine well-separated roots of g up to the requested accuracy of d digits, but there is no guarantee.

• 

A special situation arises in the case g is a numeric polynomial, but some or all constraints are non-numeric. Under such circumstances, a user-given value maxprec is enforced throughout the entire computation, but a heuristic default of maxprec is applied only to non-numeric constraint evaluation. In particular, an important use case for constraints is to check whether any constraint polynomial might be zero at a root of g.

  

If g is a numeric polynomial, the default is to fully isolate the roots of g up to an accuracy of d digits, and to enforce the evaluation of numeric constraints up to d significant digits. In particular, the interval evaluation of a numeric constraint will be 0,0 if and only if the constraint vanishes at the corresponding root of g; otherwise, all interval evaluations of numeric constraints will not contain 0.

  

Similar guarantees cannot be made if the constraint is non-numeric. In this situation, the numeric sub-instances will be solved according to the above rules, and the remaining non-numeric sub-instances will be subject to the maxprec heuristic.

Examples

withRootFinding:

fx43x2+2

fx43x2+2

(1)

Isolatef

x=−1.414213562,x=−1.,x=1.,x=1.414213562

(2)

factorf

x1x+1x22

(3)

Isolatef,digits=30

x=−1.41421356237309504880168872421,x=−1.,x=1.,x=1.41421356237309504880168872421

(4)

A multivariate system.

Fx22,y1

Fx22,y1

(5)

IsolateF,x,y

x=−1.414213562,y=1.000000000,x=1.414213562,y=1.000000000

(6)

RIsolateF,x,y,output='midpoint'

Rx=5217527130133116624336893488147419103232,y=7378697629483820646573786976294838206464,x=5217527130133116624336893488147419103232,y=7378697629483820646573786976294838206464

(7)

evalfR

x=−1.414213562,y=1.000000000,x=1.414213562,y=1.000000000

(8)

RIsolateF,x,y,output='interval',method='RC'

Rx=759250125536870912,2429600399917179869184,y=1,1,x=2429600399917179869184,759250125536870912,y=1,1

(9)

evalfR

x=−1.414213562,−1.414213562,y=1.,1.,x=1.414213562,1.414213562,y=1.,1.

(10)

Specify the maximum number of roots returned by using the maxroots option.

RIsolatex22x27,x

Rx=−2.645751311,x=−1.414213562,x=1.414213562,x=2.645751311

(11)

RIsolatex22x27,x,maxroots=1

Rx=2.645751311

(12)

An example with ill-conditioned constraints.

wexpandmulxi,i=1..10:

Slightly shift a coefficient:

fw+x7:

R,CIsolatef,x,constraints=w,digits=10:

C

x1055x9+1320x818150x7+157773x6902055x5+3416930x48409500x3+12753576x210628640x+3628800=−1.000019291,x1055x9+1320x818150x7+157773x6902055x5+3416930x48409500x3+12753576x210628640x+3628800=−126.6073008

(13)

This agrees with higher precision results:

Isolatef,x,constraints=w,digits=20

x=1.0000027558065671334,x=1.9968767019889278008,x1055x9+1320x818150x7+157773x6902055x5+3416930x48409500x3+12753576x210628640x+3628800=−1.0000192908054545330,x1055x9+1320x818150x7+157773x6902055x5+3416930x48409500x3+12753576x210628640x+3628800=−126.60730080931688758

(14)

Compare this result to direct evaluation:

map2evalf20@eval,w,R

−1.000,−126.605

(15)

Isolate can find roots of polynomials with irrational coefficients as well.

RIsolatePix2ⅇ2x+2

Rx=0.2101740008,x=2.141835605

(16)

In case of multiple or near-multiple roots, this is infeasible in general; in the following example, without symbolic simplification, a purely numerical routine cannot infer the fact that there is a double root at 2:

RIsolatex22x2

Rx=−1.414213562

(17)

Inspecting the partial results will reveal such instances:

R,partialIsolatex22x2,partialresults=true

R,partialx=−1.414213562,Recordinterval=16696086816425961207651180591620717411303424,417402170410649030981295147905179352825856,multiplicity=0..2

(18)

If it is a priori known that the input is indeed square-free, increasing the maximum precision allows to resolve such situations:

aevalf1002:

Not that a is very close to 2, but not identical.

isolating,unfinishedIsolatex2xa,partialresults=true:

nopsisolating,nopsunfinished

0,1

(19)

isolating,unfinishedIsolatex2xa,maxprec=1000,partialresults=true:

nopsisolating,nopsunfinished

2,0

(20)

Note that the polynomial x22xa has no irrational coefficients, but only such of type numeric (which comprises floats); thus, the following call defaults to complete isolation:

isolating,unfinishedIsolatex22xa,partialresults=true:

nopsisolating,nopsunfinished

3,0

(21)

The maxprec mechanism can also be used to limit the computational resources if an incomplete or approximate answer is acceptable. The following polynomial has two well-separated simple roots of absolute value close to 110, but also two simple roots extremely close to 10−100. For the latter two, approximately 50000 digits of accuracy are required to distinguish them:

isolating,unfinishedIsolatex10010100x12,maxprec=100,partialresults=true:

isolating

x=−109.8541142,x=109.8541142

(22)

evalf30unfinished1'interval'

9.9999999999999999999999929766510−101,1.0000000000000000000000014249410−100

(23)

Despite the fact that it is feasible to fully isolate the roots in this example, such partial results might be sufficient for numerical applications.

Finally, we consider a harder multivariate system with infinitely many complex solutions. The input is given as a PolynomialIdeal so that the Groebner basis computed by Isolate is remembered.

withPolynomialIdeals:

J53yz28yx2+5y2x2z+13y4z,83y2z+9x2z260y2x2z83y4z,62xy+37y3+5zx3+96y4z:

IsolateJ,x,y,z

Error, (in RootFinding:-Isolate) the system has an infinite number of solutions

The basis is remembered:

IdealInfo:-KnownGroebnerBasesJ

tdegz,x,y

(24)

J53yz28yx2+5y2x2z+13y4z,83y2z+9x2z260y2x2z83y4z,62xy+37y3+5zx3+96y4z:

IsolateJ,x,y,z,method='RC'

Error, (in RootFinding:-Isolate) the system has an infinite number of solutions

References

  

Rouillier, F. "Solving zero-dimensional systems through the rational univariate representation." Journal of Applicable Algebra in Engineering, Communication, and Computing, Vol. 9, No. 5 (1999): 433-461.

  

Rouillier, F. and Zimmermann, P. "Efficient isolation of polynomial real roots." Journal of Computational and Applied Mathematics, Vol. 162 No. 1 (2003):33-50.

  

Aubry, P., Lazard, D., and Moreno Maza, M. "On the theories of triangular sets." J. of Symb. Comput., Vol. 28, No. 1-2 (1999): 105-124.

  

Xia, B. and Yang, L. "An Algorithm for Isolating the Real Solutions of Semi-algebraic Systems." J. of Symb. Comput. , Vol. 34, No. 5 (2002): 461-477.

  

Kobel, A. and Sagraloff, M. and Rouillier, F. "Computing Real Roots of Real Polynomials ... And now For Real!" Proceedings of the 41st International Symposium on Symbolic and Algebraic Computation (ISSAC) (2016):303-310.

Compatibility

• 

The maxroots option was introduced in Maple 15.

• 

For more information on Maple 15 changes, see Updates in Maple 15.

• 

The method=ABND, maxprec and partialresults options were introduced in Maple 2019.

• 

For more information on Maple 2019 changes, see Updates in Maple 2019.

See Also

evalf

fsolve

PolynomialIdeals

RegularChains

root

RootFinding