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 for a root is a computational proof of the correctness of a candidate solution. For instance, a certificate may consist of an approximate solution formula_1, a region formula_2 containing formula_1, and a proof that formula_2 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 introduced the quantity formula_5, which quantifies the convergence of Newton's method. More precisely, let formula_6 be a system of analytic functions in the variables formula_1, formula_8 the derivative operator, and formula_9 the Newton operator. The quantities 
formula_10
formula_11
and
formula_12
are used to certify a candidate solution. In particular, if 
formula_13
then formula_1 is an approximate solution for formula_15, 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 formula_16 of formula_6 so that iterates of the Newton operator converge as
formula_18
The software package alphaCertified provides an implementation of the alpha test for polynomials by estimating formula_19 and formula_20.
Interval Newton and Krawczyck methods.
Suppose formula_21 is a function whose fixed points correspond to the roots of formula_6. For example, the Newton operator has this property. Suppose that formula_23 is a region, then,
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.
In the univariate case, Newton's method can be directly generalized to certify a root over an interval. For an interval formula_34, let formula_35 be the midpoint of formula_34. Then, the interval Newton operator applied to formula_34 is
In practice, any interval containing formula_39 can be used in this computation. If formula_1 is a root of formula_6, then by the mean value theorem, there is some formula_42 such that formula_43. In other words, formula_44. Since formula_39 contains the inverse of formula_6 at all points of formula_34, it follows that formula_48. Therefore, formula_49.
Furthermore, if formula_50, then either formula_35 is a root of formula_6 and formula_53 or formula_54. Therefore, formula_55 is at most half the width of formula_34. Therefore, if there is some root of formula_6 in formula_34, the iterative procedure of replacing formula_34 by formula_60 will converge to this root. If, on the other hand, there is no root of formula_6 in formula_34, 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.
Let formula_63 be any formula_64 invertible matrix in formula_65. Typically, one takes formula_63 to be an approximation to formula_67. Then, define the function formula_68 We observe that formula_1 is a fixed of formula_24 if and only if formula_1 is a root of formula_6. Therefore the approach above can be used to identify roots of formula_6. This approach is similar to a multivariate version of Newton's method, replacing the derivative with the fixed matrix formula_63.
We observe that if formula_34 is a compact and convex region and formula_76, then, for any formula_77, there exist formula_78 such that
Let formula_80 be the Jacobian matrix of formula_24 evaluated on formula_34. In other words, the entry formula_83 consists of the image of formula_84 over formula_34. It then follows that formula_86
where the matrix-vector product is computed using interval arithmetic. Then, allowing formula_1 to vary in formula_34, it follows that the image of formula_24 on formula_34 satisfies the following containment: formula_91
where the calculations are, once again, computed using interval arithmetic. Combining this with the formula for formula_24, the result is the Krawczyck operator
where formula_23 is the identity matrix.
If formula_95, then formula_24 has a fixed point in formula_34, i.e., formula_6 has a root in formula_34. On the other hand, if the maximum matrix norm using the supremum norm for vectors of all matrices in formula_100 is less than formula_101, then formula_24 is contractive within formula_34, so formula_24 has a unique fixed point.
A simpler test, when formula_34 is an axis-aligned parallelepiped, uses formula_106, i.e., the midpoint of formula_34. In this case, there is a unique root of formula_6 if 
where formula_110 is the length of the longest side of formula_34.
"A priori" certification methods.
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.
Non-certified numerical path tracking relies on heuristic methods for controlling time step size and precision. 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.