Numerical certification
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. \beta(f,x) = \|x - N(x)\| = \|Df(x)^{-1} f(x)\| \gamma(f,x) = \sup_{k\geq 2}\left\| \frac{Df(x)^{-1}D^kf(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) 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 .
Interval Newton method
In the univariate case, Newton's method can be directly generalized to certify a root over an interval. For an interval J , let m(J) be the midpoint of J . Then, the interval Newton operator applied to J is IN(J)=m(J)-F(m(J))/F'(J). In practice, any interval containing F'(J) can be used in this computation. If x is a root of F , then by the mean value theorem, there is some c\in J such that F(m(J))-F'(c)(m(J)-x)=F(x)=0 . In other words, F(m(J))=F'(c)(m(J)-x) . Since F'(J) contains the inverse of F at all points of J , it follows that m(J)-x\in F(m(J))/F'(J) . Therefore, x=m(J)-(m(J)-x)\in IN(J) . Furthermore, if 0\not\in F'(J) , then either m(J) is a root of F and IN(J)=\{m(J)\} or m(J)\not\in IN(J) . Therefore, J\cap N(J) is at most half the width of J . Therefore, if there is some root of F in J , the iterative procedure of replacing J by J\cap IN(J) will converge to this root. If, on the other hand, there is no root of F in J , 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 Y be any n\times n invertible matrix in GL(n,\mathbb{R}) . Typically, one takes Y to be an approximation to F'(y)^{-1} . Then, define the function G(x)=x-YF(x). We observe that x is a fixed of G if and only if x is a root of F . Therefore the approach above can be used to identify roots of F . This approach is similar to a multivariate version of Newton's method, replacing the derivative with the fixed matrix Y . We observe that if J is a compact and convex region and y\in J , then, for any x\in J , there exist c_1,\dots,c_n\in J such that G(y)-G(x)=\begin{bmatrix}\nabla g_1(c_1)^T\\\vdots\\\nabla g_n(c_n)^T\end{bmatrix}(y-x). Let G'(J) be the Jacobian matrix of G evaluated on J . In other words, the entry (G'(J))_{ij} consists of the image of \frac{\partial g_i}{\partial x_j} over J . It then follows that G(x)\in G(y)+\nabla G(J)(x-y), where the matrix-vector product is computed using interval arithmetic. Then, allowing x to vary in J , it follows that the image of G on J satisfies the following containment: G(J)\subset G(y)+G'(J)(J-y), where the calculations are, once again, computed using interval arithmetic. Combining this with the formula for G , the result is the Krawczyck operator K_{y,Y}(J)=y-YF(y)+(I-F'(J))(J-y), where I is the identity matrix. If K_{y,Y}(J)\subset J , then G has a fixed point in J , i.e., F has a root in J . On the other hand, if the maximum matrix norm using the supremum norm for vectors of all matrices in I-F'(J) is less than 1 , then G is contractive within J , so G has a unique fixed point. A simpler test, when J is an axis-aligned parallelepiped, uses y=m(J) , i.e., the midpoint of J . In this case, there is a unique root of F if \|K(X)-m(X)\| where w(X) is the length of the longest side of J .
References
Text derived from https://en.wikipedia.org/w/index.php?oldid=1276533209 under CC BY-SA 4.0; modifications have been made.