Validated numerics

Validated numerics (or rigorous computation, verified computation, reliable computation) is numerics including mathematically strict error(rounding error, truncation error, discretization error) evaluation, and it is one field of numerical analysis. For computation, interval arithmetic is used, and all results are represented by intervals. Validated numerics were used by Warwick Tucker in order to solve the 14th of Smale's problems^[1], and today it is recognized as a powerful tool for the study of dynamical systems^[2].

Importance

Computation without verification may cause unfortunate results. Below are some examples.

Rump's example

In the 1980s, Rump made an example^[3]. He made a complicated function and tried to obtain its value. Single precision, double precision, extended precision results seemed to be correct, but its plus-minus sign was different from the true value.

Phantom solution

Breuer-Plum-McKenna used the spectrum method to solve the boundary value problem of the Emden equation, and reported that an asymmetric solution was obtained^[4]. This result to the study conflicted to the theoretical study by Gidas-Ni-Nirenberg which claimed that there is no asymmetric solution^[5]. The solution obtained by Breuer-Plum-McKenna was a phantom solution caused by discretization error. This is a rare case, but it tells us that when we want to strictly discuss differential equations, numerical solutions must be verified.

Accidents caused by numerical errors

The following examples are known as accidents caused by numerical errors.

Failure of intercepting missiles in the Gulf War (1991)^[6]
Failure of the Ariane 5 rocket (1996)^[7]

Main Topics

The study of validated numerics is divided into the following fields.

Verification in numerical linear algebra
Verification of special functions (such as the gamma function and the Bessel function)
Verification of numerical integration
Verification of nonlinear equations (The Kantorovich theorem, Krawczyk method, interval Newton method, and the Durand-Kerner-Aberth method are studied)
Verification for solutions of ODEs, PDEs (for PDEs, knowledge of functional analysis are used)
Verification of linear programming
Verification of computational geometry
Verification at high-performance computing environment

Tools

INTLAB Library made by MATLAB/Octave
kv Library made by C++.
Arb Library made by C. It is capable to rigorously compute various special functions.
CAPD A collection of flexible C++ modules which are mainly designed to computation of homology of sets and maps and nonrigorous and validated numerics for dynamical systems.

External links

Validated Numerics for Pedestrians

References

^ Tucker, W. (1999). The Lorenz attractor exists. Comptes Rendus de l'Académie des Sciences-Series I-Mathematics, 328(12), 1197-1202.
^ ZIN ARAI, HIROSHI KOKUBU, AND PAWEÃL PILARCZYK . RECENT DEVELOPMENT IN RIGOROUS COMPUTATIONAL METHODS IN DYNAMICAL SYSTEMS.
^ Rump, S. M. (1988). Algorithms for verified inclusions: Theory and practice. In Reliability in computing (pp. 109-126). Academic Press.
^ Breuer, B., Plum, M., & McKenna, P. J. (2001). Inclusions and existence proofs for solutions of a nonlinear boundary value problem by spectral numerical methods. In Topics in Numerical Analysis (pp. 61-77). Springer, Vienna.
^ Gidas, B., Ni, W. M., & Nirenberg, L. (1979). Symmetry and related properties via the maximum principle. Communications in Mathematical Physics, 68(3), 209-243.
^ http://www-users.math.umn.edu/~arnold//disasters/patriot.html
^ ARIANE 5 Flight 501 Failure, http://sunnyday.mit.edu/nasa-class/Ariane5-report.html

Category:Numerical analysis Category:Computational science

[1] Tucker, W. (1999). The Lorenz attractor exists. Comptes Rendus de l'Académie des Sciences-Series I-Mathematics, 328(12), 1197-1202.

[2] ZIN ARAI, HIROSHI KOKUBU, AND PAWEÃL PILARCZYK . RECENT DEVELOPMENT IN RIGOROUS COMPUTATIONAL METHODS IN DYNAMICAL SYSTEMS.

[3] Rump, S. M. (1988). Algorithms for verified inclusions: Theory and practice. In Reliability in computing (pp. 109-126). Academic Press.

[4] Breuer, B., Plum, M., & McKenna, P. J. (2001). Inclusions and existence proofs for solutions of a nonlinear boundary value problem by spectral numerical methods. In Topics in Numerical Analysis (pp. 61-77). Springer, Vienna.

[5] Gidas, B., Ni, W. M., & Nirenberg, L. (1979). Symmetry and related properties via the maximum principle. Communications in Mathematical Physics, 68(3), 209-243.

[6] ttp://www-users.math.umn.edu/~arnold//disasters/patriot.html

[7] ARIANE 5 Flight 501 Failure, http://sunnyday.mit.edu/nasa-class/Ariane5-report.html

[1]

[2]

[3]

[4]

[5]

[6]

[7]