Content deleted Content added
MichaelBurr (talk | contribs) Worked on introduction and listed topics for two sections. |
added descriptions of what a cert is, and of alpha theory |
||
Line 4:
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 [[Stephen_Smale|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.
A certificate in this context for a candidate solution is similar to a certificate for [[Correctness (computer science)|correctness in computer science]]. Whereas a computer science certificate proves that a function produces the correct result, numerical certification operates on solutions. Between the two flavors, ''a priori'' numerical certification bears the greatest similarity to that of an algorithm, in that the results are mathematically guaranteed to be correct, much like '''total correctness'''. On the other hand, ''a posteriori'' certification operates on candidates, regardless of how they are computed, and hence is rather different from algorithmic correctness -- for an extreme example, one could randomly generate candidates and attempt to certify them ''a posteriori''.
== ''A posteriori'' certification methods ==
There are a variety of methods for ''a posteriori'' certification, including
* Alpha theory (Smale)
* Krawczyk's method/Interval Newton (Moore)
* Miranda Test (Yap, Vegter, Sharma)
=== Alpha theory ===
[[Newton's method]].<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 (TOMS) |date=2012 |volume=38 |issue=4 |page=28 |doi=10.1145/2331130.2331136}}</ref>▼
The cornerstone of '''Smale's alpha theory''' is [[Newton's method]]. In 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=185-196}}</ref> named for the quantity <math>\alpha</math>, a measurement on the distance to a true solution.
More precisely, let <math>f</math> be a system of polynomials with variables <math>x</math>, with <math>D</math> the derivative operator, <math>N</math> a Newton step. The quantities
<math display="block">\beta(f,x) = ||x - N_f(x)|| = ||Df(x)^{-1} f(x)||</math>
<math display="block">\gamma(f,x) = \sup_{k\geq 2}|| \frac{Df(x)^{-1}D^kf(x)}{k!} ||^\frac{1}{k-1}</math>
and
<math display="block">\alpha(f,x) = \beta(f,x) \gamma(f,x) </math>
can be computed and used to certify a candidate solution, since if
<math display="block">\alpha < \frac{13 - 3\sqrt{17}}{4}</math>
▲
=== Interval Newton ===
=== Miranda test ===
== ''A priori'' certification methods ==
Line 17 ⟶ 42:
* Interval Arithmetic (Moore, Arb, Mezzarobba)
* Condition numbers (Beltran-Leykin)
== See also ==
[[:Category:Algebraic geometry]]
| |||