Numerical certification

Numerical certification is the process of verifying the correctness of a candidate solution to a system of equations. In (numerical) computational mathematics, such as numerical algebraic geometry, candidate solutions are computed algorithmically, but there is the possibility that errors have corrupted the candidates. For instance, in addition to the inexactness of input data and candidate solutions, numerical errors or errors in the discretization of the problem may result in corrupted candidate solutions. The goal of numerical certification is to provide a certificate which proves which of these candidates are, indeed, approximate solutions.

Methods for certification can be divided into two flavors: a priori certification and a posteriori certification. A posteriori certification confirms the correctness of the final answers (regardless of how they are generated), while a priori certification confirms the correctness of each step of a specific computation. A typical example of a posteriori certification is Smale's alpha theory, while a typical example of a priori certification is interval arithmetic.

Certificates

edit

A certificate for a root is a computational proof of the correctness of a candidate solution. For instance, a certificate may consist of an approximate solution  , a region   containing  , and a proof that   contains exactly one solution to the system of equations.

In this context, an a priori numerical certificate is a certificate in the sense of correctness in computer science. On the other hand, an a posteriori numerical certificate operates only on solutions, regardless of how they are computed. Hence, a posteriori certification is different from algorithmic correctness – for an extreme example, an algorithm could randomly generate candidates and attempt to certify them as approximate roots using a posteriori certification.

A posteriori certification methods

edit

There are a variety of methods for a posteriori certification, including

Alpha theory

edit

The cornerstone of Smale's alpha theory is bounding the error for Newton's method. Smale's 1986 work[1] introduced the quantity  , which quantifies the convergence of Newton's method. More precisely, let   be a system of analytic functions in the variables  ,   the derivative operator, and   the Newton operator. The quantities     and   are used to certify a candidate solution. In particular, if   then   is an approximate solution for  , i.e., the candidate is in the domain of quadratic convergence for Newton's method. In other words, if this inequality holds, then there is a root   of   so that iterates of the Newton operator converge as  

The software package alphaCertified provides an implementation of the alpha test for polynomials by estimating   and  .[2]

Interval Newton and Krawczyck methods

edit

Suppose   is a function whose fixed points correspond to the roots of  . For example, the Newton operator has this property. Suppose that   is a region, then,

  1. If   maps   into itself, i.e.,  , then by Brouwer fixed-point theorem,   has at least one fixed point in  , and, hence   has at least one root in  .
  2. If   is contractive in a region containing  , then there is at most one root in  .

There are versions of the following methods over the complex numbers, but both the interval arithmetic and conditions must be adjusted to reflect this case.

Interval Newton method

edit

In the univariate case, Newton's method can be directly generalized to certify a root over an interval. For an interval  , let   be the midpoint of  . Then, the interval Newton operator applied to   is

 

In practice, any interval containing   can be used in this computation. If   is a root of  , then by the mean value theorem, there is some   such that  . In other words,  . Since   contains the inverse of   at all points of  , it follows that  . Therefore,  .

Furthermore, if  , then either   is a root of   and   or  . Therefore,   is at most half the width of  . Therefore, if there is some root of   in  , the iterative procedure of replacing   by   will converge to this root. If, on the other hand, there is no root of   in  , this iterative procedure will eventually produce an empty interval, a witness to the nonexistence of roots.

See interval Newton method for higher dimensional analogues of this approach.

Krawczyck method

edit

Let   be any   invertible matrix in  . Typically, one takes   to be an approximation to  . Then, define the function   We observe that   is a fixed of   if and only if   is a root of  . Therefore the approach above can be used to identify roots of  . This approach is similar to a multivariate version of Newton's method, replacing the derivative with the fixed matrix  .

We observe that if   is a compact and convex region and  , then, for any  , there exist   such that

 

Let   be the Jacobian matrix of   evaluated on  . In other words, the entry   consists of the image of   over  . It then follows that   where the matrix-vector product is computed using interval arithmetic. Then, allowing   to vary in  , it follows that the image of   on   satisfies the following containment:   where the calculations are, once again, computed using interval arithmetic. Combining this with the formula for  , the result is the Krawczyck operator

 

where   is the identity matrix.

If  , then   has a fixed point in  , i.e.,   has a root in  . On the other hand, if the maximum matrix norm using the supremum norm for vectors of all matrices in   is less than  , then   is contractive within  , so   has a unique fixed point.

A simpler test, when   is an axis-aligned parallelepiped, uses  , i.e., the midpoint of  . In this case, there is a unique root of   if

 

where   is the length of the longest side of  .

Miranda test

edit
  • Miranda test (Yap, Vegter, Sharma)

A priori certification methods

edit
  • Interval arithmetic (Moore, Arb, Mezzarobba)
  • Condition numbers (Beltran–Leykin)

Interval arithmetic

edit

Interval arithmetic can be used to provide an a priori numerical certificate by computing intervals containing unique solutions. By using intervals instead of plain numeric types during path tracking, resulting candidates are represented by intervals. The candidate solution-interval is itself the certificate, in the sense that the solution is guaranteed to be inside the interval.

Condition numbers

edit

Numerical algebraic geometry solves polynomial systems using homotopy continuation and path tracking methods. By monitoring the condition number for a tracked homotopy at every step, and ensuring that no two solution paths ever intersect, one can compute a numerical certificate along with a solution. This scheme is called a priori path tracking.[3]

Non-certified numerical path tracking relies on heuristic methods for controlling time step size and precision.[4] In contrast, a priori certified path tracking goes beyond heuristics to provide step size control that guarantees that for every step along the path, the current point is within the domain of quadratic convergence for the current path.

References

edit
  1. ^ Smale, Steve (1986). "Newton's method estimates from data at one point". The merging of disciplines: new directions in pure, applied, and computational mathematics: 185–196.
  2. ^ Hauenstein, Jonathan; Sottile, Frank (2012). "Algorithm 921: alphaCertified: certifying solutions to polynomial systems". ACM Transactions on Mathematical Software. 38 (4): 28. doi:10.1145/2331130.2331136.
  3. ^ Beltran, Carlos; Leykin, Anton (2012). "Certified numerical homotopy tracking". Experimental Mathematics. 21 (1): 69–83.
  4. ^ Bates, Daniel; Hauenstein, Jonathan; Sommese, Andrew; Wampler, Charles (2009). "Stepsize control for path tracking". Contemporary Mathematics. 496 (21).