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

A certificate is a computational proof of the correctness of a candidate solution. For instance, a certificate may consist of an approximate solution $x$ , a region $R$ containing $x$ , and a proof that $R$ 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

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

Alpha theory

The cornerstone of Smale's alpha theory is bounding the error for Newton's method. Smale's 1986 work^[1] introduced the quantity $\alpha$ , which quantifies the convergence of Newton's method. More precisely, let $F$ be a system of analytic functions in the variables $x$ , $D$ the derivative operator, and $N$ the Newton operator. The quantities $\beta (f,x)=\|x-N(x)\|=\|Df(x)^{-1}f(x)\|$ $\gamma (f,x)=\sup _{k\geq 2}\left\|{\frac {Df(x)^{-1}D^{k}f(x)}{k!}}\right\|^{\frac {1}{k-1}}$ and $\alpha (f,x)=\beta (f,x)\gamma (f,x)$ are used to certify a candidate solution. In particular, if $\alpha (f,x)<{\frac {13-3{\sqrt {17}}}{4}},$ then $x$ is an approximate solution for $f$ , 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 $x^{\ast }$ of $F$ so that iterates of the Newton operator converge as $\left\|N^{k}(x)-x^{\ast }\right\|\leq {\frac {1}{2^{2^{k}-1}}}\|x-x^{\ast }\|.$

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

The Interval Newton and Krawczyck Methods

Suppose $G:\mathbb {C} ^{n}\rightarrow \mathbb {C} ^{n}$ is a function whose fixed points correspond to the roots of $F$ . For example, the Newton operator has this property. Suppose that $I$ is a region, then,

If $G$ maps $I$ into itself, i.e., $G(I)\subseteq I$ , 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$ .
If $G$ is contractive in a region containing $I$ , then there is at most one root in $I$ .

For instance, we observe that if $I$ is a compact and convex region and $y\in I$ , then, for any $x\in I$ , there exist $c_{1},\dots ,c_{n}$ such that $F(y)-F(x)={\begin{bmatrix}\nabla f_{1}(c_{1})^{T}\\\vdots \\\nabla f_{n}(c_{n})^{T}\end{bmatrix}}(y-x).$

These properties can often be established using interval arithmetic. For example, the interval Newton operator replaces

$x$ with the region $I$ containing $x$ . For example, the interval Newton operator is $N(I)=m(I)+D(I)^{-1}\cdot (I-m(I)),$ where $m(I)$ is a point (often the center of mass) of $I$ and $D(I)^{-1}$ is an interval over-approximation to the set inverses of derivatives for $x\in I$ . Then, one can show that if $x$ is a fixed point of

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:

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 Jacobian of $F$ on $I$ .

Miranda test

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

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. 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

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.