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 x {\displaystyle x} , a region R {\displaystyle R} containing x {\displaystyle x} , and a proof that R {\displaystyle 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 introduced the quantity α {\displaystyle \alpha } , which quantifies the convergence of Newton's method. More precisely, let F {\displaystyle F} be a system of analytic functions in the variables x {\displaystyle x} , D {\displaystyle D} the derivative operator, and N {\displaystyle N} the Newton operator. The quantities
β ( f , x ) = ‖ x − N ( x ) ‖ = ‖ D f ( x ) − 1 f ( x ) ‖ {\displaystyle \beta (f,x)=\|x-N(x)\|=\|Df(x)^{-1}f(x)\|}
γ ( f , x ) = sup k ≥ 2 ‖ D f ( x ) − 1 D k f ( x ) k ! ‖ 1 k − 1 {\displaystyle \gamma (f,x)=\sup _{k\geq 2}\left\|{\frac {Df(x)^{-1}D^{k}f(x)}{k!}}\right\|^{\frac {1}{k-1}}}
and
α ( f , x ) = β ( f , x ) γ ( f , x ) {\displaystyle \alpha (f,x)=\beta (f,x)\gamma (f,x)}
are used to certify a candidate solution. In particular, if
α ( f , x ) < 13 − 3 17 4 , {\displaystyle \alpha (f,x)<{\frac {13-3{\sqrt {17}}}{4}},}
then x {\displaystyle x} is an approximate solution for f {\displaystyle 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 ∗ {\displaystyle x^{\ast }} of F {\displaystyle F} so that iterates of the Newton operator converge as
… excerpt ends here. Continue reading the full article.
