Numerical certification: Difference between revisions

Revision as of 19:38, 12 October 2018

Revision as of 19:17, 2 November 2018

Line 1:

{{Draft article}}

'''Numerical certification''' is the process of provingverifying thatthe correctness of a numericalcandidate computationsolution producedto a correctsystem of equations, often a result of algorithmic calculation. In numerical computational mathematics, specificallysuch as [[numerical algebraic geometry]], approximations tocandidate solutions ofare systemscomputed, ofbut equationsthere areis computed.the possibility Thethat coordinateserrors ofhave thesebeen solutionsintroduced. are notBeyond exact.the inexactness Henceof candidates, doubtthey ismay castalso onsimply thebe correctnessgrossly ofincorrect as the solutions.result of Certificationany isof a methodplethora of provingmodes theof correctnessfailure. The goal of numerical certification is to provide a solutioncertificate which proves which of these candidates 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 [[Stephen_Smale|Smale]]'s alpha theory, while a typical example of ''a priori'' certification is [[interval arithmetic]].

== ''A posteriori'' certification methods ==

The foundation of numerical certification is [[Stephen_Smale|Smale]]'s alpha theory, a body of mathematical theory and techniques for proving that a solution is in the ___domain of quadratic convergence for [[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>

* Alpha theory (Smale)

* Krawczyk's method/Interval Newton (Moore)

* Miranda Test (Yap, Vegter, Sharma)

The foundation of numerical certification is [[Stephen_Smale|Smale]]'s alpha theory, a body of mathematical theory and techniques for proving that a solution is in the ___domain of quadratic convergence for [[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>

== ''A priori'' certification methods ==

* Interval Arithmetic (Moore, Arb, Mezzarobba)

* Condition numbers (Beltran-Leykin)

[[:Category:Algebraic geometry]]