Content deleted Content added
MichaelBurr (talk | contribs) |
Link suggestions feature: 3 links added. |
||
| (11 intermediate revisions by 5 users not shown) | |||
Line 1:
'''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.▼
▲'''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 [[
== 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 <math>x</math>, a region <math>R</math> containing <math>x</math>, and a proof that <math>R</math> 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 (computer science)|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
== ''A posteriori'' certification methods ==
Line 17 ⟶ 15:
=== Alpha theory ===
The cornerstone of '''Smale's alpha theory''' is bounding the error for [[Newton's method]]. Smale's 1986 work<ref>{{cite journal |last1=Smale |first1=Steve |title=Newton’s method estimates from data at one point |journal=The merging of disciplines: new directions in pure, applied, and computational mathematics |date=1986 |pages=
<math display="block">\beta(f,x) = \|x - N(x)\| = \|Df(x)^{-1} f(x)\|</math>
<math display="block">\gamma(f,x) = \sup_{k\geq 2}\left\| \frac{Df(x)^{-1}D^kf(x)}{k!} \right\|^\frac{1}{k-1}</math>
Line 27 ⟶ 25:
<math display="block">\left\|N^k(x)-x^\ast\right\|\leq\frac{1}{2^{2^k-1}}\|x-x^\ast\|.</math>
The software package [http://www.math.tamu.edu/~sottile/research/stories/alphaCertified/ alphaCertified] provides an implementation of the alpha test for polynomials by estimating <math>\beta</math> and <math>\gamma</math>.<ref name="alphacertified">{{cite journal |last1=Hauenstein |first1=Jonathan |last2=Sottile |first2=Frank |title=Algorithm 921: alphaCertified: certifying solutions to polynomial systems |journal=ACM Transactions on Mathematical Software
=== Interval Newton and Krawczyck
Suppose <math>G:\mathbb{R}^n\rightarrow\mathbb{R}^n</math> is a function whose fixed points correspond to the roots of <math>F</math>. For example, the Newton operator has this property. Suppose that <math>I</math> is a region, then,
Line 36 ⟶ 34:
# If <math>G</math> is [[contractive]] in a region containing <math>I</math>, then there is at most one root in <math>I</math>.
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.
====
:<math>IN(J)=m(J)-F(m(J))/F'(J).</math>
In practice, any interval containing <math>F'(J)</math> can be used in this computation. If <math>x</math> is a root of <math>F</math>, then by the [[mean value theorem]], there is some <math>c\in J</math> such that <math>F(m(J))-F'(c)(m(J)-x)=F(x)=0</math>. In other words, <math>F(m(J))=F'(c)(m(J)-x)</math>. Since <math>F'(J)</math> contains the inverse of <math>F</math> at all points of <math>J</math>, it follows that <math>m(J)-x\in F(m(J))/F'(J)</math>. Therefore, <math>x=m(J)-(m(J)-x)\in IN(J)</math>.
Furthermore, if <math>0\not\in F'(J)</math>, then either <math>m(J)</math> is a root of <math>F</math> and <math>IN(J)=\{m(J)\}</math> or <math>m(J)\not\in IN(J)</math>. Therefore, <math>J\cap N(J)</math> is at most half the width of <math>J</math>. Therefore, if there is some root of <math>F</math> in <math>J</math>, the iterative procedure of replacing <math>J</math> by <math>J\cap IN(J)</math> will converge to this root. If, on the other hand, there is no root of <math>F</math> in <math>J</math>, this iterative procedure will eventually produce an empty interval, a witness to the nonexistence of roots.
See [[Interval arithmetic#Interval Newton method|interval Newton method]] for higher dimensional analogues of this approach.
====Krawczyck method====
Let <math>Y</math> be any <math>n\times n</math> [[invertible matrix]] in <math>GL(n,\mathbb{R})</math>. Typically, one takes <math>Y</math> to be an approximation to <math>F'(y)^{-1}</math>. Then, define the function <math>G(x)=x-YF(x).</math> We observe that <math>x</math> is a fixed of <math>G</math> if and only if <math>x</math> is a root of <math>F</math>. Therefore the approach above can be used to identify roots of <math>F</math>. This approach is similar to a multivariate version of Newton's method, replacing the derivative with the fixed matrix <math>Y</math>.
We observe that if <math>J</math> is a compact and convex region and <math>y\in J</math>, then, for any <math>x\in J</math>, there exist <math>c_1,\dots,c_n\in J</math> such that
Line 48 ⟶ 56:
where the calculations are, once again, computed using interval arithmetic. Combining this with the formula for <math>G</math>, the result is the Krawczyck operator
:<math>K_{y,Y}(J)=y-YF(y)+(I-F'(J))(J-y),</math>
where <math>I</math> is the [[identity matrix]].
If <math>K_{y,Y}(J)\subset J</math>, then <math>G</math> has a fixed point in <math>J</math>, i.e., <math>F</math> has a root in <math>J</math>. On the other hand, if the maximum [[matrix norm]] using the [[Uniform norm|supremum norm for vectors]] of all matrices in <math>I-F'(J)</math> is less than <math>1</math>, then <math>G</math> is contractive within <math>J</math>, so <math>G</math> has a unique fixed point.
Line 58 ⟶ 66:
=== Miranda test ===
* Miranda
== ''A priori'' certification methods ==
* Interval arithmetic (Moore, Arb, Mezzarobba)
* Condition numbers (
=== Interval arithmetic ===
Line 73 ⟶ 81:
{{Main|Condition number}}
[[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.<ref>{{cite journal |last1=Beltran |first1=Carlos |last2=Leykin |first2=Anton |title=Certified numerical homotopy tracking |journal=Experimental Mathematics |date=2012 |volume=21 |issue=1 |pages=
Non-certified numerical path tracking relies on heuristic methods for controlling time step size and precision.<ref>{{cite journal |last1=Bates |first1=Daniel |last2=Hauenstein |first2=Jonathan |last3=Sommese |first3=Andrew |last4=Wampler |first4=Charles |title=Stepsize control for path tracking |journal=Contemporary Mathematics |date=2009 |volume=496 |issue=21}}</ref> 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.
==
{{Reflist}}
[[
[[
| |||