This package provides symbolic-numeric approaches to certify roots for a square polynomial system.
For regular roots, the package has two different approaches. 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 established in "alphaCertified: certifying solutions to polynomial systems" (2012). In the case of Krawczyk method, this package follows the theory introduced in "Introduction to Interval Analysis" (2009). These two methods also support not only floating-point arithmetic over the real and complex numbers, but also the exact computation with inputs of rational numbers.
Moreover, the package has a function certifying regular roots via a software "alphaCertified".
For singular roots, the concept of the iterated deflation established in "Newton's method with deflation for isolated singularities of polynomial systems" (2006) is implemented. For a given system and a point, the package provides a function constructing a system having a given point as a regular solution and certifies it via alpha theory or interval arithmetic.
Certifying a list of solutions :
$\bullet$ certifySolutions
For a direct use of the package, a given polynomial system and a list of numerical solutions can be given.
|
|
|
|
|
For possible options for certification, see CertificationOptions.
Regular Root Certification Methods:
$\bullet$ certifyRegularSolution
$\bullet$ krawczykTest
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.
|
|
|
|
It shows the results of the certification.
|
|
Also, if we have other solutions of the system, alpha theory suggests an algorithm for distinguishing these solutions.
|
|
|
In the case of real polynomial system, we can certify that a given solution is real or not.
|
|
Even more, when the polynomial and a point are given exact numbers over the rational number, the package computes auxiliary quantities exactly and performs an exact certification.
|
|
|
|
|
$\bullet$ Krawczyk method
Intervals for certification should be given in advance using other system solvers.
|
|
|
We set the relationships between variables and intervals using the matrix aligning entries in the order of variables of the polynomial ring.
|
The function krawczykTest automatically checks whether the Krawczyk operator is contained in the input interval box.
|
For a given point, the function pointToInterval provides a proper complex interval box for the input. For constructing a complex interval and a matrix with complex interval entries, see CCi and CCiMatrix.
|
|
|
|
|
Multiple Root Certification Method:
$\bullet$ certifySingularSolution
It is known that an isolated singular solution is regularized within finitely many steps by the iterated first order deflation (e.g. see "Newton's method with deflation for isolated singularities of polynomial systems" (2006)). The function certifySingularSolution determines if a given point is associated to a singular solution of a given system using the deflation method.
|
|
|
|
This documentation describes version 1.6 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.