find numerical approximations to roots of systems of polynomial equations - Maple Help

Online Help

All Products    Maple    MapleSim


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

RootFinding[Homotopy] - find numerical approximations to roots of systems of polynomial equations

Calling Sequence

Homotopy(eqns, options)

Parameters

eqns

-

set or list of polynomial equations or polynomials

options

-

(optional) equations of the form option=value where option is one of MaxPredictorSteps, MinimumStepSize, or Tolerance; control solution method

Description

• 

The Homotopy(eqns, options) function finds isolated non-repeated roots of square systems of polynomial equations, returning them as a list.

  

Homotopy attempts to find all isolated multiplicity one roots for the system of equations eqns that are not part of a solution manifold.

• 

The basic concepts used by the algorithm are straightforward.

  

Computation of the roots is by a homotopy, which is a continuous map from a set of known solutions to the solutions of the input system. The known solutions are generated  by Homotopy from a simple random start system.

  

For an input system {p1x1,x2,...,xn,...,pnx1,x2,...,xn} and automatically generated random start system {q1x1,...,qnxn }, this map is of the form Hx,t=11t2p1x1,x2,,xn1t2q1x1,,11t2pnx1,x2,,xn1t2qnxn , which is called the homotopy system. When t=0, solutions of Hx,0 are solutions of the generated system, and when t=1, solutions of Hx,1 are solutions of the input system.

  

Once this map is created, then follow each path from a known solution to a possible solution of the input system by varying t from 0 to 1.

  

Homotopy then differentiates the homotopy system, turning the problem into the integration of an ODE system over t=0..1. The path is then followed by discrete steps, using an ODE solution method as a predictor for each step, and an application of Newton's method as a corrector for each step, thus ensuring the computed solution stays on the path.

• 

Potential difficulties include paths that are close at some time, or isolated roots that are close. The default for Homotopy is to compute the roots that it can obtain easily, and stop for more expensive roots indicating that the computation becomes too difficult for the current settings. These settings can be controlled through a number of options.

• 

MaxPredictorSteps = M controls the maximum number of steps taken from t=0..1, and by default has a value of M=400. As an option, M must be in the range 10..infinity.

• 

MinimumStepSize = m controls the smallest step that can be taken on any path before abandoning it. The default value is 1.10-7, but can be set in the range 1.10-9..0.001. The smaller the value, the harder Homotopy works.

• 

Tolerance = tol is used as a partial criterion throughout the computation of a path for when the correction steps have sufficiently converged. It also has a second purpose, which is to provide a strict limit for the accuracy of the output isolated roots, in that these should satisfy the normalized input polynomials (that is, each polynomial is divided by the modulus of its largest coefficient) to within a maximum error of tol. The default value is 1.10-8, but it can be set in the range 1.10-14..0.0001. There is an additional constraint that the tolerance value tol must be smaller than 1/10 the minimum step size m.

• 

In summary, the default settings are sufficient for many problems, but for difficult problems a combination of increasing the maximum number of predictor steps and decreasing the minimum step size and tolerance may produce the desired solutions when the default values are insufficient.

• 

In addition, for cases in which only a few solutions are needed, these can be obtained more efficiently by increasing the minimum step size and tolerance.

Examples

withRootFinding

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

(1)

Intersection points of a line and circle:

Homotopy25xy11,x2+y21

x=0.51236037930.I,y=0.8587705408+0.I,x=0.85877054150.I,y=0.5123603786+0.I,x=0.8587705415+0.I,y=0.51236037860.I,x=0.5123603793+0.I,y=0.85877054080.I

(2)

Random system:

sys:=randpolyu,v,degree=2,randpolyu,v,degree=3

sys:=62u2+97uv73v256u+87,71u317uv2+80u244v2+62u82v

(3)

sols1:=Homotopysys

sols1:=u=0.21400653400.7500992223I,v=1.4061796760.6741681736I,u=0.84684753650.I,v=1.0622431470.I,u=0.2140065344+0.7500992219I,v=1.406179676+0.6741681732I,u=1.069439412+0.I,v=1.953758199+0.I,u=1.0645446290.8455148939I,v=0.64874410500.5933444492I,u=1.064544629+0.8455148939I,v=0.6487441050+0.5933444492I

(4)

foriinsols1doevalf20evalsys,iend do

6.46526613110-82.035700968210-8I,3.644822504410-8+1.884167184310-8I

4.966434660310-8+0.I,3.2057709670210-7+0.I

4.7565708610-9+1.061655620110-8I,8.147850457610-81.526686777310-8I

1.77093987310-8+0.I,1.35842971610-8+0.I

1.2163966410-9+1.3121021585810-7I,6.66419876210-8+2.392421908610-8I

1.2163966410-91.3121021585810-7I,6.66419876210-82.392421908610-8I

(5)

Tighter tolerance:

sols2:=Homotopysys,Tolerance=1.10-12

sols2:=u=0.2140065347+0.7500992219I,v=1.406179677+0.6741681731I,u=1.064544629+0.8455148939I,v=0.6487441050+0.5933444492I,u=1.069439412+0.I,v=1.953758199+0.I,u=0.84684753560.I,v=1.062243147+0.I,u=0.21400653470.7500992219I,v=1.4061796770.6741681731I,u=1.0645446290.8455148939I,v=0.64874410500.5933444492I

(6)

foriinsols2doevalf20evalsys,iend do

5.587320171010-8+2.3309830110-10I,1.33395270810-88.5407613110-10I

1.2163966410-91.3121021585810-7I,6.66419876210-82.392421908610-8I

1.77093987310-8+0.I,1.35842971610-8+0.I

2.51001168710-9+0.I,2.261716856910-80.I

5.587320171010-82.3309830110-10I,1.33395270810-8+8.5407613110-10I

1.2163966410-9+1.3121021585810-7I,6.66419876210-8+2.392421908610-8I

(7)

See Also

dsolve, evalf, fsolve, Groebner[Solve], LinearAlgebra[LinearSolve], randpoly, RootFinding[BivariatePolynomial], solve

References

  

Allgower, E.L., and Georg, K.  "Numerical path following." Handbook of Numerical Analysis, Vol. 5. North-Holland, 1997.

  

Verschelde, J. "Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation." Transactions on Mathematical Software, Vol. 25, No. 2 (1999): 251-276.


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