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 |
This documentation describes version 1.0 of NumericalCertification.
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/.
The object NumericalCertification is a package.