Numerical certification

Numerical certification is the process of verifying the correctness of a candidate solution to a system of equations, often a result of algorithmic calculation. In numerical computational mathematics, such as numerical algebraic geometry, candidate solutions are computed, but there is the possibility that errors have been introduced. Beyond the inexactness of candidates, they may also simply be grossly incorrect as the result of any of a number of modes of failure. The goal of numerical certification is to provide a certificate which proves which of these candidates 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

A certificate is a computational proof of the correctness of a candidate solution.

A certificate in this context for a candidate solution is similar to a certificate for correctness in computer science. Whereas a computer science certificate proves that a function produces the correct result, numerical certification operates on solutions. Between the two flavors, a priori numerical certification bears the greatest similarity to certification of an algorithm, in that the results are mathematically guaranteed to be correct -- much like total correctness. On the other hand, a posteriori numerical certification operates on solution candidates, regardless of how they are computed, and hence is rather different from algorithmic correctness -- for an extreme example, one could randomly generate candidates and attempt to certify them a posteriori.

A posteriori certification methods

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

Alpha theory (Smale)
Krawczyk's method/Interval Newton (Moore)
Miranda Test (Yap, Vegter, Sharma)

Alpha theory

The cornerstone of Smale's alpha theory is error bounding for Newton's method. Smale's 1986 work^[1] introduced the quantity $\alpha$ , a measurement on the distance to a true solution.

More precisely, let $f$ be a system of polynomials with variables $x$ , with $D$ the derivative operator, $N$ a Newton step. The quantities $\beta (f,x)=||x-N(x)||=||Df(x)^{-1}f(x)||$ $\gamma (f,x)=\sup _{k\geq 2}||{\frac {Df(x)^{-1}D^{k}f(x)}{k!}}||^{\frac {1}{k-1}}$ and $\alpha (f,x)=\beta (f,x)\gamma (f,x)$ can be computed and used to certify a candidate solution, since if $\alpha <{\frac {13-3{\sqrt {17}}}{4}}$ then $x$ is an approximate solution for $f$ , meaning that the candidate is in the domain of quadratic convergence for Newton's method.^[2]

Interval Newton

The fixed points of the Newton operator Newton's method for a square system of functions $F:\mathbb {C} ^{n}\rightarrow \mathbb {C} ^{n}$ correspond to the roots of $f$ . In more generality, suppose that $G:\mathbb {C} ^{n}\rightarrow \mathbb {C} ^{n}$ is a function whose fixed points correspond to the roots of $F$ . Interval Newton ^{[citation needed]}, Krawczyk ^{[citation needed]}, and related methods use such functions to establish the existence and uniqueness of roots within a region $I$ using topological methods:

1 If $G$ maps a region $I$ into itself, then by Brouwer fixed-point theorem, $G$ has at least one fixed point in $I$ , and, hence $F$ has at least one root in $I$ .

2 If $F$ is a contraction mapping in a region $I$ , then there is at most one root of $F$ in $I$ .

The basic form of Newton's method replaces the input in the iterator with an interval approximation. In other words

$N_{f}(I)=m(I)+J_{F}(I)^{-1}F(m(I))$

is contained within $I$ , where $m(I)$ is the midpoint of $I$ and $J_{f}(I)$ is an over-approximation to the set-image of the JacobianJacobian matrix and determinant of $F$ on $I$ .

Miranda test

A priori certification methods

Interval arithmetic (Moore, Arb, Mezzarobba)
Condition numbers (Beltran-Leykin)

Interval arithmetic

Interval arithmetic can be used to provide an a priori numerical certificate by computing intervals containing unique solutions.

Condition numbers

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.