RootFinding - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

RootFinding

  

BivariatePolynomial

  

find the solutions of two or more bivariate polynomials

 

Calling Sequence

Parameters

Description

Options

Examples

References

Calling Sequence

BivariatePolynomial(fg, varlist, options)

Parameters

fg

-

set or list of two or more polynomials in two variables

varlist

-

list or set of two names; a list defines the order in the solutions pairs returned, a set requests output in the form {x=..,y=..}

options

-

(optional) equations of the form option=value where option is one of exact, verify, or verifyTol.

Description

• 

The BivariatePolynomial(fg, varlist, options) command solves the bivariate polynomials fg, in the case when there is only a finite number of solutions.  If there are an infinite number of solutions, this routine may fail.

• 

The routine performs a random orthogonal change of coordinates, takes a random linear combination of the two or more input polynomials to produce exactly two polynomials fx,y and gx,y.  It then constructs the Bezout matrix By of fx,y and gx,y with respect to x, and then the Companion matrix pencil of the matrix polynomial By.  It then solves the generalized eigenproblem for eigenvalues and eigenvectors of the pencil; the eigenvalues give the values of y, and the corresponding values of x are deduced from the eigenvectors.

  

If the option verify=true is given (the default), or if there are more than two input polynomials, each putative root is tested on the original polynomials to see if the residual is acceptably small. A residual is judged to be small enough if it is smaller than ilog[10](n+1)*verifyTol times the maxnorm of the polynomial, where n is the number of roots.  By default, verifyTol=Float(1,1-Digits). This default tolerance may be overridden by setting the option verifyTol=... in the call.

• 

The routine assumes that fx,y=gx,y=0 has only isolated simple roots. Multiple roots are, numerically, perturbed into clusters of simple roots by rounding errors in the process. In practice, if the multiplicity of the root is not too high (say not more than three) then the results may be acceptable. If, however, there are an infinite number of roots (i.e. the dimensionality of the variety is higher than zero), then this routine will fail.  Through rounding errors, a higher-dimensional system MAY be perturbed to a zero-dimensional system, and in this case pseudozeros are calculated and some information may be deduced about the true solutions by repeated solving; the differing random combinations will produce different pseudozeros that can be put together to get a partial picture of the higher- dimensional zero set.

• 

Exact solutions are sometimes possible, and may be attempted by specifying the option exact=true. In this case, the random combinations are done over the integers to avoid introducing rounding errors. In the case where the input coefficients are exact and the polynomials are not of too high a degree, this may give exact (though not necessarily useful) answers.

• 

Solutions obtained by BivariatePolynomial may be refined by use of fsolve.  See the examples.

Options

• 

The options argument can contain the following equation.

  

 

  

exact = true or false

  

If exact=true, the command performs the computation exactly (depending on Eigenvectors succeeding with an exact computation).

  

 

  

verify = true or false

  

If verify=true (the default), the command tests that the values of each input polynomial at each computed root is smaller than 10 ulps, where an ulp is a Unit in the Last Place, measured relative to the user's setting of Digits and a vector norm of the polynomial coefficients. If verify=false, this residual test is not performed and infinite and spurious roots are returned along with any genuine roots.

  

 

  

 

  

verifyTol = positive floating-point number for residual tolerance

  

If verifyTol is overridden, the residual test is passed if the residual is less than or equal to ilog[10](n+1)*verifyTol times a vector norm of the polynomial coefficients.

  

 

  

Note: The resultType = data_type option has been superseded by the exact option.

Examples

withRootFinding

Analytic,AnalyticZerosFound,BivariatePolynomial,EnclosingBox,HasRealRoots,Homotopy,Isolate,NextZero,Parametric,WitnessPoints

(1)

Exact answers (not usually useful)

BivariatePolynomial25uv12,u2+v21,u,v,exact=true

45,35,45,35,35,45,35,45

(2)

frandpolyx,y,degree=2,dense

f:=7x2+22xy94y255x+87y56

(3)

grandpolyx,y,degree=2,dense

g:=62xy73y2+97x4y83

(4)

Set output, and a large residual tolerance

BivariatePolynomialf,g,y,x,verifyTol=0.000010

x=3.950351689443595.66623769360475I,y=1.583147105039780.669082838293886I,x=3.95035168944359+5.66623769360474I,y=1.58314710503978+0.669082838293885I,x=0.217656104641047+0.580098578671159I,y=0.283760691054644+0.781752717215509I,x=0.2176561046410570.580098578671162I,y=0.2837606910546440.781752717215509I

(5)

A higher-degree example

frandpolyx,y,degree=3,dense

f:=10x3+62x2y+80xy217y382x244xy75y2+71x10y7

(6)

grandpolyx,y,degree=3,dense

g:=40x3+42x2y+23xy2+6y350x2+75xy+74y292x+72y+37

(7)

solsBivariatePolynomialf,g,x,y,verify=false:

finiteSolsselecttype,mapconvert,sols,set,setcomplexnumeric

finiteSols:=8.725464918237642.8555844946147010-17I,0.8044221907783854.4597933471056010-18I,1.61657845360197+1.7632360317023910-13I,0.422070508744692+1.2040340059549910-13I,0.7865884116822691.14300482684492I,0.6041015492968660.622769842152089I,0.786588411681988+1.14300482684388I,0.604101549296844+0.622769842152230I,0.4535547554991611.18516902864061I,0.278993622119871+1.39562033543789I,0.453554755498940+1.18516902864132I,0.2789936221204891.39562033543821I,0.373755472345006+7.8036702259738610-15I,0.1569922728184476.6162524552082910-14I,0.237394982252645+1.1271793607123610-14I,0.5466288530062389.5566611566323610-14I,1.197761543057695.0449221065633010-14I,1.96030291260013+5.1086351900201710-13I

(8)

Refining the solutions by passing them as initial approximations to fsolve.

finiteSolsBivariatePolynomialf,g,x,y

finiteSols:=0.804422190776779+1.4642279310103810-13I,8.725464918243241.6399606411001210-12I,0.4535547555024041.18516902863964I,0.278993622115287+1.39562033544011I,0.453554755497188+1.18516902864016I,0.2789936221202921.39562033543835I,0.422070508744006+8.3433422035365810-14I,1.61657845360167+1.4249492550503810-14I,0.786588411674601+1.14300482683916I,0.604101549297742+0.622769842150683I,0.7865884116757191.14300482684891I,0.6041015492975450.622769842152378I,1.96030291261376+1.1874429472180210-11I,1.19776154306172+2.0674912083222210-12I,0.546628853006180+9.5742122022545410-13I,0.237394982252101+1.6669937365115610-13I,0.1569922728184051.9131115843323610-13I,0.3737554723450443.3309738294486110-14I

(9)

Digits30

Digits:=30

(10)

betterfsolvef,g,x=finiteSols51,y=finiteSols52

better:=x=0.804422190778384243337546951432,y=8.72546491823766479368773875110

(11)

subsbetter,f,g

0.,3.10-26

(12)

A one-dimensional variety, which causes BivariatePolynomial to fail: Note that many roots are found of the form x=1, y=anything (but not an infinite number), and the isolated roots are lost.

DigitstruncevalhfDigits

Digits:=15

(13)

fx2+y21x1

f:=x2+y21x1

(14)

g25xy12x1

g:=25xy12x1

(15)

BivariatePolynomialf,g,x,y,verifyTol=0.000010

1.00000000000001+0.I,48.28547646009460.I,0.999999999999999+0.I,8.857749224112280.I,0.999999999999998+4.1633363423443410-17I,0.548256881731674+1.00539649995290I,0.9999999999999982.5673907444456710-16I,0.5482568817316741.00539649995290I,1.00000000000001+4.7836992089485910-17I,0.464774473406571+2.7593176124460910-18I

(16)

Another example, worse in that the multiplicity is higher.

fx32xy6

f:=x32xy6

(17)

gx32y+1

g:=x32y+1

(18)

BivariatePolynomialf,g,x,y,verifyTol=0.010

x=2.635541850676310.I,y=1.38085325883703+0.I,x=2.12995540337232+0.622583869330654I,y=1.46559457336100+1.74733758077540I,x=2.129957387554650.622594396170797I,y=1.465596131746461.74732931294925I

(19)

Correct solutions are not always returned. Doing it again may produce different output (because of the randomness)

BivariatePolynomialf,g,x,y,verifyTol=0.010

BivariatePolynomialf,g,x,y,verifyTol=0.010

x=2.14250546275868+0.898469218387198I,y=1.58617065883303+4.48452871192331I,x=2.061858275476510.982449876693879I,y=1.591122022361914.48837346265817I,x=2.03981276155472+0.375561551280485I,y=0.521592707409674+0.0223477076242725I

(20)

BivariatePolynomialf,g,x,y,verifyTol=0.010

x=2.831184803938750.I,y=5.34480781287653+0.I,x=3.32629745669730+0.802410003300878I,y=3.71257592387898+2.66170988201845I,x=3.326539046520190.802409357995646I,y=3.712796999506762.66171047252867I,x=4.35044870040840+0.539684548379420I,y=0.329198756425294+1.71611171106350I,x=4.350660232022920.539711124060112I,y=0.3293923261871281.71608739201221I

(21)

BivariatePolynomialf,g,x,y,verifyTol=0.010

x=1.192013437884810.422393658380706I,y=0.908817949661711+1.59914528712520I,x=1.21905466301025+0.241127987145236I,y=0.7389590714291961.46047917324046I,x=1.860763458912070.646800016344119I,y=1.57054555844117+0.0469456788076298I

(22)

Digits30

Digits:=30

(23)

BivariatePolynomialf,g,x,y,verifyTol=0.010

x=1.965395826458190990861401853970.I,y=1.34173486482746415826261682659+0.I,x=2.20909291710640018583589456389+0.145549312451602328964743749684I,y=4.042782818845184817437544331332.85972344437370543674374161486I,x=2.208958052425865425246132106270.145067015797578085699523849376I,y=4.04278922333647673689316298150+2.85970054093665600096145064424I,x=2.013305195715065316319858613930.0000371927463827307011660112568869I,y=0.121133485823375131383156239594+0.00000176621943852358571166213138333I

(24)

References

  

Barnett, Stephen. Polynomials and Linear Control Systems. Deffer, 1983.

  

Manocha, Dinesh. "Numerical methods for solving polynomial equations, in Applications of Computational Geometry." AMS proceedings of applied mathematics, Vol. 53. 1998.

See Also

fsolve

LinearAlgebra[BezoutMatrix]

LinearAlgebra[CompanionMatrix]

LinearAlgebra[Eigenvectors]

RootFinding

select

solve

type

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam