RefineRoot - Maple Help

RootFinding

 RefineRoot
 refine a real root for a polynomial system

 Calling Sequence RefineRoot( interval, p, digits = d, partialresults = partial, strategy = s ) RefineRoot( interval, p, x, digits = d, partialresults = partial, strategy = s ) RefineRoot( box, sys, vars, digits = d, partialresults = partial, strategy = s ) RefineRoot( vbox, sys, digits = d, partialresults = partial, strategy = s ) RefineRoot( R, digits = d, partialresults = partial, strategy = s )

Parameters

 interval - single interval; isolating interval for a real root of the univariate polynomial p p - univariate polynomial with rational coefficients x - (optional) name; variable for the univariate polynomial p box - non-empty list of intervals; isolating box for a real root of the system sys or polynomial p sys - nonemptylist( polynom ); polynomials with rational coefficients defining a polynomial system vars - nonemptylist( name ); variables for the polynomials in sys, ordered with respect to the intervals of box vbox - non-empty list containing elements with type name = interval; simultaneously describes the isolating box for a real root of the system sys and the accompanying variables, where the name preceding each interval describes the associated variable for the interval of the isolating box R - A real algebraic number represented by a (potentially nested) RootOf where all RootOfs represent a real algebraic number via indexing by rational intervals d - (optional) posint; target precision to refine the root to (default $2\mathrm{Digits}$) partial - (optional) truefalse; defines whether a partially refined root is satisfactory to return in the case of lack of integrity in the input (default false) s - (optional) The symbol oracle or geometric; defines strategy for a second attempt at refinement in the case of missing integrity in the input (default oracle)

Description

 • RefineRoot is a function to refine a real root for a polynomial system to target precision defined by d.
 • Throughout, any interval can be represented by either a list or range of two rational numbers, i.e. [ rational, rational ] or rational .. rational. In other words, RefineRoot accepts and returns intervals under both such representations. A list or range of rationals represents an open real interval with rational endpoints with respect to one variable in this way. When the intervals are supplied as part of the parameter R, only ranges are applicable.
 • The return value of RefineRoot is in the same format as the parameter for input containing the isolating box, i.e. vbox, box, or R.
 • In the univariate case, the parameter interval is a single interval, and the polynomial p must be univariate. It is not necessary to supply a variable, which can be deduced from the single variable in p.
 • In the multivariate case, lists of intervals are supplied via box or vbox, but the intervals do not need to be represented in the same way for each element (ranges or lists of rational numbers are interchangable). In this case we assume n polynomials in sys, n elements of box, and n variables in vars, or n elements of vbox. The ordering of vars must correspond with the intervals contained within box to confirm which interval corresponds to which variable for the root. For the parameter vbox, the correspondence is clear.
 • For the parameter R, isolating intervals are supplied directly with each polynomial in the real algebraic number supplied.
 • RefineRoot attempts to refine to the target precision represented by d. This is always achievable when the input has integrity. The input has integrity if every polynomial in the system is radical, the solutions of the system are all zero dimensional, and the given box is isolating for the root, i.e. it contains exactly one real root. In the case of missing integrity, the attempt at refinement at a working precision matching the target may fail, and a second attempt at refinement is made using a working precision defined by the strategy determined by the value of the keyword option strategy. In this case the parameter partial defines whether it is acceptable to return a partially refined root which may not meet the target precision defined by d.
 • Working precision strategy for a second attempt at refinement in the case of lack of input integrity is defined by the keyword option strategy, i.e. the parameter s. When s = geometric, the procedure tries a higher working precision of twice the last working precision in the case of first failure to refine the root. When s = oracle, the situation is similar, but the next working precision to use also takes into account the current precision of the box, as well as the degree of the polynomials in the system for the root.
 • When a second attempt at refinement fails in the case of lack of input integrity, an error is thrown. This error represents an identification of lack of integrity that is one of two possibilities:
 – that there is a problem with the polynomial system,
 – or that the passed box is not isolating for the root.
 • In the univariate case where the passed interval contains roots but is not isolating, the procedure will converge to exactly one of the roots contained within the interval. There is no guarantee as to which.
 • In the case where the argument R is passed (a real algebraic number via RootOf), the same discussion on integrity of input is relevant, however construction and evaluation of the associated RootOf will do some checking that the associated box for the implied triangular system for the RootOf contains a root. It is still possible that the implied system lacks integrity, or the box is not isolating.
 • An error is thrown if the passed box does not contain any root for the system.

Examples

 > $\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(1..2,{x}^{2}-2\right)$
 $\frac{{417402170410649030795}}{{295147905179352825856}}{..}\frac{{834804340821298061591}}{{590295810358705651712}}$ (1)
 > $\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(\left[1,2\right],{x}^{2}-2\right)$
 $\left[\frac{{417402170410649030795}}{{295147905179352825856}}{,}\frac{{834804340821298061591}}{{590295810358705651712}}\right]$ (2)
 > $\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2,1..2\right)\right)$
 ${\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{,}\frac{{417402170410649030795}}{{295147905179352825856}}{..}\frac{{834804340821298061591}}{{590295810358705651712}}\right)$ (3)
 > $p≔{x}^{3}-x-2$
 ${p}{≔}{{x}}^{{3}}{-}{x}{-}{2}$ (4)
 > $\mathrm{iso}≔\mathrm{RootFinding}:-\mathrm{Isolate}\left(p,'\mathrm{digits}'=20,'\mathrm{output}=\mathrm{interval}'\right)$
 ${\mathrm{iso}}{≔}\left[{x}{=}\left[\frac{{33132716007484265070125064459573906572651}}{{21778071482940061661655974875633165533184}}{,}\frac{{8283179001871066267531266114893476643183}}{{5444517870735015415413993718908291383296}}\right]\right]$ (5)
 > $\mathrm{intvl}≔\mathrm{op}\left(\left[1,2\right],\mathrm{iso}\right)$
 ${\mathrm{intvl}}{≔}\left[\frac{{33132716007484265070125064459573906572651}}{{21778071482940061661655974875633165533184}}{,}\frac{{8283179001871066267531266114893476643183}}{{5444517870735015415413993718908291383296}}\right]$ (6)
 > $\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(\mathrm{intvl},p,x,'\mathrm{digits}'=40\right)$
 $\left[\frac{{4240987648957985928976008250825460041302649}}{{2787593149816327892691964784081045188247552}}{,}\frac{{8481975297915971857952016501650920082605379}}{{5575186299632655785383929568162090376495104}}\right]$ (7)
 > $\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(\mathrm{RootOf}\left({\mathrm{_Z}}^{2}-2\mathrm{RootOf}\left({\mathrm{_Z}}^{3}-9,2..3\right),1..2\right)\right)$
 ${\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{2}}{-}{2}{}{\mathrm{RootOf}}{}\left({{\mathrm{_Z}}}^{{3}}{-}{9}{,}\frac{{4911459063769832938769}}{{2361183241434822606848}}{..}\frac{{19645836255079331755077}}{{9444732965739290427392}}\right){,}\frac{{9631969614722211425099}}{{4722366482869645213696}}{..}\frac{{19263939229444422850199}}{{9444732965739290427392}}\right)$ (8)
 > $\mathrm{sys}≔\left[{x}^{2}+y+z-1,{y}^{2}+x+z-1,{z}^{2}+x+y-1\right];$$\mathrm{vars}≔\left[x,y,z\right]$
 ${\mathrm{sys}}{≔}\left[{{x}}^{{2}}{+}{y}{+}{z}{-}{1}{,}{{y}}^{{2}}{+}{x}{+}{z}{-}{1}{,}{{z}}^{{2}}{+}{x}{+}{y}{-}{1}\right]$
 ${\mathrm{vars}}{≔}\left[{x}{,}{y}{,}{z}\right]$ (9)
 > $\mathrm{iso}≔\mathrm{RootFinding}:-\mathrm{Isolate}\left(\mathrm{sys},\mathrm{vars},'\mathrm{digits}'=40,'\mathrm{output}=\mathrm{interval}'\right)$
 ${\mathrm{iso}}{≔}\left[\left[{x}{=}\left[{-}\frac{{53838761509319310478766384898835632967531233}}{{22300745198530623141535718272648361505980416}}{,}{-}\frac{{215355046037277241915065539595342531870124917}}{{89202980794122492566142873090593446023921664}}\right]{,}{y}{=}\left[{-}\frac{{107677523018638620957532769797671265935062463}}{{44601490397061246283071436545296723011960832}}{,}{-}\frac{{107677523018638620957532769797671265935062459}}{{44601490397061246283071436545296723011960832}}\right]{,}{z}{=}\left[{-}\frac{{215355046037277241915065539595342531870124925}}{{89202980794122492566142873090593446023921664}}{,}{-}\frac{{215355046037277241915065539595342531870124921}}{{89202980794122492566142873090593446023921664}}\right]\right]{,}\left[{x}{=}\left[{0}{,}{0}\right]{,}{y}{=}\left[{0}{,}{0}\right]{,}{z}{=}\left[{1}{,}{1}\right]\right]{,}\left[{x}{=}\left[{0}{,}{0}\right]{,}{y}{=}\left[{1}{,}{1}\right]{,}{z}{=}\left[{0}{,}{0}\right]\right]{,}\left[{x}{=}\left[\frac{{18474542224516128391389896707077819911140797}}{{44601490397061246283071436545296723011960832}}{,}\frac{{147796337796129027131119173656622559289126385}}{{356811923176489970264571492362373784095686656}}\right]{,}{y}{=}\left[\frac{{147796337796129027131119173656622559289126377}}{{356811923176489970264571492362373784095686656}}{,}\frac{{9237271112258064195694948353538909955570399}}{{22300745198530623141535718272648361505980416}}\right]{,}{z}{=}\left[\frac{{147796337796129027131119173656622559289126379}}{{356811923176489970264571492362373784095686656}}{,}\frac{{73898168898064513565559586828311279644563191}}{{178405961588244985132285746181186892047843328}}\right]\right]{,}\left[{x}{=}\left[{1}{,}{1}\right]{,}{y}{=}\left[{0}{,}{0}\right]{,}{z}{=}\left[{0}{,}{0}\right]\right]\right]$ (10)
 > $\mathrm{box}≔\mathrm{map2}\left(\mathrm{op},2,\mathrm{iso}\left[1\right]\right)$
 ${\mathrm{box}}{≔}\left[\left[{-}\frac{{53838761509319310478766384898835632967531233}}{{22300745198530623141535718272648361505980416}}{,}{-}\frac{{215355046037277241915065539595342531870124917}}{{89202980794122492566142873090593446023921664}}\right]{,}\left[{-}\frac{{107677523018638620957532769797671265935062463}}{{44601490397061246283071436545296723011960832}}{,}{-}\frac{{107677523018638620957532769797671265935062459}}{{44601490397061246283071436545296723011960832}}\right]{,}\left[{-}\frac{{215355046037277241915065539595342531870124925}}{{89202980794122492566142873090593446023921664}}{,}{-}\frac{{215355046037277241915065539595342531870124921}}{{89202980794122492566142873090593446023921664}}\right]\right]$ (11)
 > $\mathrm{box}≔\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(\mathrm{box},\mathrm{sys},\mathrm{vars},'\mathrm{digits}'=50\right)$
 ${\mathrm{box}}{≔}\left[\left[{-}\frac{{115617859969835018863785862782323656037503032977164605}}{{47890485652059026823698344598447161988085597568237568}}{,}{-}\frac{{115617859969835018863785862782323656037503032977164603}}{{47890485652059026823698344598447161988085597568237568}}\right]{,}\left[{-}\frac{{115617859969835018863785862782323656037503032977164605}}{{47890485652059026823698344598447161988085597568237568}}{,}{-}\frac{{115617859969835018863785862782323656037503032977164603}}{{47890485652059026823698344598447161988085597568237568}}\right]{,}\left[{-}\frac{{115617859969835018863785862782323656037503032977164605}}{{47890485652059026823698344598447161988085597568237568}}{,}{-}\frac{{115617859969835018863785862782323656037503032977164603}}{{47890485652059026823698344598447161988085597568237568}}\right]\right]$ (12)
 > $\mathrm{box}≔\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(\mathrm{box},\mathrm{sys},\mathrm{vars},'\mathrm{digits}'=60\right)$
 ${\mathrm{box}}{≔}\left[\left[{-}\frac{{62071865925493619066937919924652958696028559517216435939679651}}{{25711008708143844408671393477458601640355247900524685364822016}}{,}{-}\frac{{496574927403948952535503359397223669568228476137731487517437207}}{{205688069665150755269371147819668813122841983204197482918576128}}\right]{,}\left[{-}\frac{{62071865925493619066937919924652958696028559517216435939679651}}{{25711008708143844408671393477458601640355247900524685364822016}}{,}{-}\frac{{496574927403948952535503359397223669568228476137731487517437207}}{{205688069665150755269371147819668813122841983204197482918576128}}\right]{,}\left[{-}\frac{{62071865925493619066937919924652958696028559517216435939679651}}{{25711008708143844408671393477458601640355247900524685364822016}}{,}{-}\frac{{496574927403948952535503359397223669568228476137731487517437207}}{{205688069665150755269371147819668813122841983204197482918576128}}\right]\right]$ (13)
 > $\mathrm{intvls}≔\mathrm{map}\left(r↦\mathrm{..}\left(\mathrm{op}\left(r\right)\right),\mathrm{box}\right)$
 ${\mathrm{intvls}}{≔}\left[{-}\frac{{62071865925493619066937919924652958696028559517216435939679651}}{{25711008708143844408671393477458601640355247900524685364822016}}{..}{-}\frac{{496574927403948952535503359397223669568228476137731487517437207}}{{205688069665150755269371147819668813122841983204197482918576128}}{,}{-}\frac{{62071865925493619066937919924652958696028559517216435939679651}}{{25711008708143844408671393477458601640355247900524685364822016}}{..}{-}\frac{{496574927403948952535503359397223669568228476137731487517437207}}{{205688069665150755269371147819668813122841983204197482918576128}}{,}{-}\frac{{62071865925493619066937919924652958696028559517216435939679651}}{{25711008708143844408671393477458601640355247900524685364822016}}{..}{-}\frac{{496574927403948952535503359397223669568228476137731487517437207}}{{205688069665150755269371147819668813122841983204197482918576128}}\right]$ (14)
 > $\mathrm{intvls}≔\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(\mathrm{intvls},\mathrm{sys},\mathrm{vars},'\mathrm{digits}'=75\right)$
 ${\mathrm{intvls}}{≔}\left[{-}\frac{{1118187329008977802634693552378588657873139398432508152652405164837706556819627}}{{463168356949264781694283940034751631413079938662562256157830336031652518559744}}{..}{-}\frac{{1118187329008977802634693552378588657873139398432508152652405164837706556819625}}{{463168356949264781694283940034751631413079938662562256157830336031652518559744}}{,}{-}\frac{{1118187329008977802634693552378588657873139398432508152652405164837706556819627}}{{463168356949264781694283940034751631413079938662562256157830336031652518559744}}{..}{-}\frac{{1118187329008977802634693552378588657873139398432508152652405164837706556819625}}{{463168356949264781694283940034751631413079938662562256157830336031652518559744}}{,}{-}\frac{{1118187329008977802634693552378588657873139398432508152652405164837706556819627}}{{463168356949264781694283940034751631413079938662562256157830336031652518559744}}{..}{-}\frac{{1118187329008977802634693552378588657873139398432508152652405164837706556819625}}{{463168356949264781694283940034751631413079938662562256157830336031652518559744}}\right]$ (15)
 > $\mathrm{vbox}≔\mathrm{iso}\left[1\right]$
 ${\mathrm{vbox}}{≔}\left[{x}{=}\left[{-}\frac{{53838761509319310478766384898835632967531233}}{{22300745198530623141535718272648361505980416}}{,}{-}\frac{{215355046037277241915065539595342531870124917}}{{89202980794122492566142873090593446023921664}}\right]{,}{y}{=}\left[{-}\frac{{107677523018638620957532769797671265935062463}}{{44601490397061246283071436545296723011960832}}{,}{-}\frac{{107677523018638620957532769797671265935062459}}{{44601490397061246283071436545296723011960832}}\right]{,}{z}{=}\left[{-}\frac{{215355046037277241915065539595342531870124925}}{{89202980794122492566142873090593446023921664}}{,}{-}\frac{{215355046037277241915065539595342531870124921}}{{89202980794122492566142873090593446023921664}}\right]\right]$ (16)
 > $\mathrm{iso}≔\mathrm{RootFinding}:-\mathrm{RefineRoot}\left(\mathrm{vbox},\mathrm{sys},'\mathrm{digits}'=50\right)$
 ${\mathrm{iso}}{≔}\left[{x}{=}\left[{-}\frac{{115617859969835018863785862782323656037503032977164605}}{{47890485652059026823698344598447161988085597568237568}}{,}{-}\frac{{115617859969835018863785862782323656037503032977164603}}{{47890485652059026823698344598447161988085597568237568}}\right]{,}{y}{=}\left[{-}\frac{{115617859969835018863785862782323656037503032977164605}}{{47890485652059026823698344598447161988085597568237568}}{,}{-}\frac{{115617859969835018863785862782323656037503032977164603}}{{47890485652059026823698344598447161988085597568237568}}\right]{,}{z}{=}\left[{-}\frac{{115617859969835018863785862782323656037503032977164605}}{{47890485652059026823698344598447161988085597568237568}}{,}{-}\frac{{115617859969835018863785862782323656037503032977164603}}{{47890485652059026823698344598447161988085597568237568}}\right]\right]$ (17)

Compatibility

 • The RootFinding[RefineRoot] command was introduced in Maple 2022.