RootFinding - Maple Programming Help

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 Isolate(f) Isolate(J, X) Isolate(J, X, digits=d, constraints=cons, output=outpt, method=mthd, maxroots=mxrts)

Parameters

 f - univariate polynomial with real coefficients J - set or list of polynomials, or a PolynomialIdeal X - (optional) list of variables d - (optional) number of significant digits cons - (optional) list of polynomials with integer coefficients outpt - (optional) type of output: numeric, midpoint, or interval mthd - (optional) name of algorithm to use: RS or RC. Default is RS. mxrts - (optional) number of roots to be returned.

Options

 • The digit=d option controls the precision. This option ensures that if the result is evaluated numerically, the first d digits of the mantissa are correct.
 • 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. 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, resulting in a list of floating point approximations.
 • The constraints option takes a list of polynomials with integer coefficients and evaluates them at the roots of the system. This option is preferable to direct evaluation using evalf because a smaller numerical error is introduced.
 • The method option specifies the algorithm to use.  It can be RS (the default) or RC.  method=RS returns the result by using the RealSolving (RS) C library by F. Rouillier.  method=RC returns the result by using the RegularChains package by M. Moreno Maza et al.
 The constraints option cannot be used simultaneously with method=RC.  When both method=RC and constraints are specified, Isolate carries out the computation using method=RS.
 When method=RS is specified, Isolate first computes a Groebner basis followed by a Rational Univariate Representation for multivariate polynomial systems. The second argument must be an ordered list of variables, and the roots are returned as corresponding lists of values.
 • 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.
 The maxroots option cannot be used in conjunction with method=RC. If both of these options are specified, maxroots is 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. All significant digits returned by the program are correct, and unlike purely numerical methods no roots are ever lost, although repeated roots are discarded. This command does not support symbolic or complex number coefficients.
 • The system must have a finite number of complex solutions or else 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](..).

Examples

 > $\mathrm{with}\left(\mathrm{RootFinding}\right):$
 > $f≔{x}^{4}-3{x}^{2}+2$
 ${f}{≔}{{x}}^{{4}}{-}{3}{}{{x}}^{{2}}{+}{2}$ (1)
 > $\mathrm{Isolate}\left(f\right)$
 $\left[{x}{=}{-}{1.414213562}{,}{x}{=}{-}{1.}{,}{x}{=}{1.}{,}{x}{=}{1.414213562}\right]$ (2)
 > $\mathrm{factor}\left(f\right)$
 $\left({x}{-}{1}\right){}\left({x}{+}{1}\right){}\left({{x}}^{{2}}{-}{2}\right)$ (3)
 > $\mathrm{Isolate}\left(f,\mathrm{digits}=30\right)$
 $\left[{x}{=}{-}{1.41421356237309504880168872421}{,}{x}{=}{-}{1.}{,}{x}{=}{1.}{,}{x}{=}{1.41421356237309504880168872421}\right]$ (4)

A multivariate system.

 > $F≔\left[{x}^{2}-2,y-1\right]$
 ${F}{≔}\left[{{x}}^{{2}}{-}{2}{,}{y}{-}{1}\right]$ (5)
 > $\mathrm{Isolate}\left(F,\left[x,y\right]\right)$
 $\left[\left[{x}{=}{-}{1.414213562}{,}{y}{=}{1.000000000}\right]{,}\left[{x}{=}{1.414213562}{,}{y}{=}{1.000000000}\right]\right]$ (6)
 > $R≔\mathrm{Isolate}\left(F,\left[x,y\right],\mathrm{output}='\mathrm{midpoint}'\right)$
 ${R}{≔}\left[\left[{x}{=}{-}\frac{{52175271301331166243}}{{36893488147419103232}}{,}{y}{=}\frac{{73786976294838206465}}{{73786976294838206464}}\right]{,}\left[{x}{=}\frac{{52175271301331166243}}{{36893488147419103232}}{,}{y}{=}\frac{{73786976294838206465}}{{73786976294838206464}}\right]\right]$ (7)
 > $\mathrm{evalf}\left(R\right)$
 $\left[\left[{x}{=}{-}{1.414213562}{,}{y}{=}{1.000000000}\right]{,}\left[{x}{=}{1.414213562}{,}{y}{=}{1.000000000}\right]\right]$ (8)
 > $R≔\mathrm{Isolate}\left(F,\left[x,y\right],\mathrm{output}='\mathrm{interval}',\mathrm{method}='\mathrm{RC}'\right)$
 ${R}{≔}\left[\left[{x}{=}\left[{-}\frac{{759250125}}{{536870912}}{,}{-}\frac{{24296003999}}{{17179869184}}\right]{,}{y}{=}\left[{1}{,}{1}\right]\right]{,}\left[{x}{=}\left[\frac{{24296003999}}{{17179869184}}{,}\frac{{759250125}}{{536870912}}\right]{,}{y}{=}\left[{1}{,}{1}\right]\right]\right]$ (9)
 > $\mathrm{evalf}\left(R\right)$
 $\left[\left[{x}{=}\left[{-}{1.414213562}{,}{-}{1.414213562}\right]{,}{y}{=}\left[{1.}{,}{1.}\right]\right]{,}\left[{x}{=}\left[{1.414213562}{,}{1.414213562}\right]{,}{y}{=}\left[{1.}{,}{1.}\right]\right]\right]$ (10)

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

 > $R≔\mathrm{Isolate}\left(\left({x}^{2}-2\right)\left({x}^{2}-7\right),x\right)$
 ${R}{≔}\left[{x}{=}{-}{2.645751311}{,}{x}{=}{-}{1.414213562}{,}{x}{=}{1.414213562}{,}{x}{=}{2.645751311}\right]$ (11)
 > $R≔\mathrm{Isolate}\left(\left({x}^{2}-2\right)\left({x}^{2}-7\right),x,\mathrm{maxroots}=1\right)$
 ${R}{≔}\left[{x}{=}{1.414213562}\right]$ (12)

An example with ill-conditioned constraints.

 > $w≔\mathrm{expand}\left(\mathrm{mul}\left(x-i,i=1..10\right)\right):$

Slightly shift a coefficient:

 > $f≔w+{x}^{7}:$
 > $R,C≔\mathrm{Isolate}\left(f,x,\mathrm{constraints}=\left[w\right],\mathrm{digits}=10\right):$
 > $C$
 $\left[\left[{{x}}^{{10}}{-}{55}{}{{x}}^{{9}}{+}{1320}{}{{x}}^{{8}}{-}{18150}{}{{x}}^{{7}}{+}{157773}{}{{x}}^{{6}}{-}{902055}{}{{x}}^{{5}}{+}{3416930}{}{{x}}^{{4}}{-}{8409500}{}{{x}}^{{3}}{+}{12753576}{}{{x}}^{{2}}{-}{10628640}{}{x}{+}{3628800}{=}{-}{1.000019291}\right]{,}\left[{{x}}^{{10}}{-}{55}{}{{x}}^{{9}}{+}{1320}{}{{x}}^{{8}}{-}{18150}{}{{x}}^{{7}}{+}{157773}{}{{x}}^{{6}}{-}{902055}{}{{x}}^{{5}}{+}{3416930}{}{{x}}^{{4}}{-}{8409500}{}{{x}}^{{3}}{+}{12753576}{}{{x}}^{{2}}{-}{10628640}{}{x}{+}{3628800}{=}{-}{126.6073008}\right]\right]$ (13)

This agrees with higher precision results:

 > $\mathrm{Isolate}\left(f,x,\mathrm{constraints}=\left[w\right],\mathrm{digits}=20\right)$
 $\left[{x}{=}{1.0000027558065671334}{,}{x}{=}{1.9968767019889278008}\right]{,}\left[\left[{{x}}^{{10}}{-}{55}{}{{x}}^{{9}}{+}{1320}{}{{x}}^{{8}}{-}{18150}{}{{x}}^{{7}}{+}{157773}{}{{x}}^{{6}}{-}{902055}{}{{x}}^{{5}}{+}{3416930}{}{{x}}^{{4}}{-}{8409500}{}{{x}}^{{3}}{+}{12753576}{}{{x}}^{{2}}{-}{10628640}{}{x}{+}{3628800}{=}{-}{1.0000192908054545330}\right]{,}\left[{{x}}^{{10}}{-}{55}{}{{x}}^{{9}}{+}{1320}{}{{x}}^{{8}}{-}{18150}{}{{x}}^{{7}}{+}{157773}{}{{x}}^{{6}}{-}{902055}{}{{x}}^{{5}}{+}{3416930}{}{{x}}^{{4}}{-}{8409500}{}{{x}}^{{3}}{+}{12753576}{}{{x}}^{{2}}{-}{10628640}{}{x}{+}{3628800}{=}{-}{126.60730080931688758}\right]\right]$ (14)

Compare this result to direct evaluation:

 > $\mathrm{map2}\left({\mathrm{evalf}}_{20}@\mathrm{eval},w,R\right)$
 $\left[{-}{1.000}{,}{-}{126.605}\right]$ (15)

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.

 > $\mathrm{with}\left(\mathrm{PolynomialIdeals}\right):$
 > $J≔⟨53yz-28y{x}^{2}+5{y}^{2}{x}^{2}z+13{y}^{4}z,83{y}^{2}z+9{x}^{2}{z}^{2}-60{y}^{2}{x}^{2}z-83{y}^{4}z,62xy+37{y}^{3}+5z{x}^{3}+96{y}^{4}z⟩:$
 > $\mathrm{Isolate}\left(J,\left[x,y,z\right]\right)$

The basis is remembered:

 > $\mathrm{IdealInfo}:-\mathrm{KnownGroebnerBases}\left(J\right)$
 $\left\{{\mathrm{tdeg}}{}\left({z}{,}{x}{,}{y}\right)\right\}$ (16)
 > $J≔⟨53yz-28y{x}^{2}+5{y}^{2}{x}^{2}z+13{y}^{4}z,83{y}^{2}z+9{x}^{2}{z}^{2}-60{y}^{2}{x}^{2}z-83{y}^{4}z,62xy+37{y}^{3}+5z{x}^{3}+96{y}^{4}z⟩:$
 > $\mathrm{Isolate}\left(J,\left[x,y,z\right],\mathrm{method}='\mathrm{RC}'\right)$

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.

Compatibility

 • The maxroots option was introduced in Maple 15.