next | previous | forward | backward | up | top | index | toc | Macaulay2 website
NumericalCertification :: NumericalCertification

NumericalCertification -- certify the solution for the square system using alpha theory or interval arithmetic

Description

This package provides two different types of root certification for the square polynomial system. The first is Smale's alpha theory and the second is Krawczyk method via interval arithmetic. Both methods are based on Newton's method and they all describe the specific region containing a unique root of the system.

In the case of alpha theory, this package follows the algorithms of alpha theory introduced in "alphaCertified: certifying solutions to polynomial systems" (2012).

In the case of Krawczyk method, this package follows the theory suggested in "Introduction to Interval Analysis" (2009).

Ceritification Methods:

$\bullet$ certifySolution

$\bullet$ krawczykMethod

Examples

The following example shows how to certify the roots of solutions for the square polynomial system. This example is suggested in "Certifying solutions to square systems of polynomial-exponential equations" (2017)

$\bullet$ alpha theory

A set of points for certification should be given in advance using other system solvers.

i1 : R = QQ[x1,x2,y1,y2];
 
i2 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -7/2, x1^2 + y1^2 -1, x2^2 + y2^2 -1};
 
i3 : p1 = point{{.95, .32, -.30, .95}};
 
i4 : p2 = point{{.9, .3, -.3, 1}}; -- poorly approximated solution
 
i5 : P = {p1,p2};

It shows the result of certification.

i6 : certifySolution(f,P)

o6 = ({p1}, {(.0505356, .00526407, 9.60011)})

o6 : Sequence

Also, if we have other solutions of the system, alpha theory suggests an algorithm for distinguishing these solutions.

i7 : p1 = point{{.95,.32,-.30,.95}};
 
i8 : p2 = point{{.65,.77,.76,-.64}};
 
i9 : certifyDistinctSoln(f,p1,p2)

o9 = true

In the case of real polynomial system, we can certify that a given solution is real or not.

i10 : p = point{{.954379, .318431, -.298633, .947949}};
 
i11 : certifyRealSoln(f,p)

o11 = true

$\bullet$ Krawczyk method

Intervals for certification should be given in advance using other system solvers.

i12 : R = QQ[x1,x2,y1,y2];
 
i13 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -7/2, x1^2 + y1^2 -1, x2^2 + y2^2 -1};
 
i14 : (I1, I2, I3, I4) = (interval(.94,.96), interval(.31,.33), interval(-.31,-.29), interval(.94,.96));

We set the relationships between variables and intervals using the function intervalOptionList.

i15 : o = intervalOptionList {("x1" => "I1"), ("x2" => "I2"), ("y1" => "I3"), ("y2" => "I4")};
 
i16 : krawczykOper(f,o)

o16 = {{[.954149, .954609]}, {[.318086, .318777]}, {[-.298824, -.298442]},
      -----------------------------------------------------------------------
      {[.947663, .948236]}}

o16 : IntervalMatrix

The function krawczykMethod automatically checks whether the Krawczyk operator is contained in the input interval box.

i17 : krawczykMethod(f,o)
given interval contains a unique solution

o17 = true

Author

Version

This documentation describes version 1.0 of NumericalCertification.

Source code

The source code from which this documentation is derived is in the file NumericalCertification.m2. The auxiliary files accompanying it are in the directory NumericalCertification/.

Exports

  • Types
  • Functions and commands
    • certifyCount -- executes alpha-certification on a given system and list of points
    • certifyDistinctSoln -- determine whether given points are distinct approximate solutions to the system
    • certifyRealSoln -- determine whether a given point is an real approximate solution to the system
    • certifySolution -- certify whether a given point is an approximate solution to the system
    • computeConstants -- compute the auxilary quantities related to alpha theory
    • identityIntMat -- compute the identity diagonal interval matrix.
    • interval -- construct an interval
    • intervalMatrix -- construct an interval matrix from the given list
    • intervalMatrixNorm -- compute the infinity norm for interval matrix.
    • intervalOptionList -- convert a list type object to list of options for intervals
    • krawczykMethod -- certify the interval box for square polynomial system
    • krawczykOper -- compute the Krawczyk operator
    • newtonOper -- apply Newton's method on a given point.
    • pointNorm -- compute the "projectivized" norm of the given point
    • polyNorm -- compute the "Bombieri-Weyl" norm of the given polynomial
    • polySysNorm -- compute the norm of the given polynomial system
  • Methods
    • "certifyCount(PolySystem,List)" -- see certifyCount -- executes alpha-certification on a given system and list of points
    • "certifyDistinctSoln(PolySystem,Point,Point)" -- see certifyDistinctSoln -- determine whether given points are distinct approximate solutions to the system
    • "certifyRealSoln(PolySystem,Point)" -- see certifyRealSoln -- determine whether a given point is an real approximate solution to the system
    • "certifySolution(PolySystem,List)" -- see certifySolution -- certify whether a given point is an approximate solution to the system
    • "computeConstants(PolySystem,Point)" -- see computeConstants -- compute the auxilary quantities related to alpha theory
    • "identityIntMat(ZZ)" -- see identityIntMat -- compute the identity diagonal interval matrix.
    • "interval(Interval)" -- see interval -- construct an interval
    • "interval(Number)" -- see interval -- construct an interval
    • "interval(Number,Number)" -- see interval -- construct an interval
    • "interval(Number,RingElement)" -- see interval -- construct an interval
    • "interval(RingElement,Interval)" -- see interval -- construct an interval
    • "interval(RingElement,Number)" -- see interval -- construct an interval
    • "interval(RingElement,RingElement)" -- see interval -- construct an interval
    • "intervalMatrix(List)" -- see intervalMatrix -- construct an interval matrix from the given list
    • "intervalMatrixNorm(IntervalMatrix)" -- see intervalMatrixNorm -- compute the infinity norm for interval matrix.
    • intervalNorm(Interval) -- compute a norm of an interval
    • "intervalOptionList(List)" -- see intervalOptionList -- convert a list type object to list of options for intervals
    • "krawczykMethod(PolySystem,IntervalOptionList)" -- see krawczykMethod -- certify the interval box for square polynomial system
    • "krawczykOper(PolySystem,IntervalOptionList)" -- see krawczykOper -- compute the Krawczyk operator
    • mInterval(Interval) -- compute a midpoint of an interval
    • "newtonOper(PolySystem,Point)" -- see newtonOper -- apply Newton's method on a given point.
    • "pointNorm(Point)" -- see pointNorm -- compute the "projectivized" norm of the given point
    • "polyNorm(RingElement)" -- see polyNorm -- compute the "Bombieri-Weyl" norm of the given polynomial
    • "polySysNorm(PolySystem)" -- see polySysNorm -- compute the norm of the given polynomial system
    • wInterval(Interval) -- compute a width of an interval.
  • Symbols
    • "InvertibleMatrix" -- see krawczykMethodOptions -- invertible matrix for computing Krawczyk operator (option for "krawczykOper" and "krawczykMethod")
    • krawczykMethodOptions -- invertible matrix for computing Krawczyk operator (option for "krawczykOper" and "krawczykMethod")

For the programmer

The object NumericalCertification is a package.