Validated numerics
Validated numerics, or rigorous computation, verified computation, reliable computation, numerical verification (German: Zuverlässiges Rechnen) 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
[edit]Computation without verification may cause unfortunate results. Below are some examples.
Rump's example
[edit]In the 1980s, Rump made an example.[3][4] 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
[edit]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.[5] This result to the study conflicted to the theoretical study by Gidas–Ni–Nirenberg which claimed that there is no asymmetric solution.[6] 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
[edit]The following examples are known as accidents caused by numerical errors:
- Failure of intercepting missiles in the Gulf War (1991)[7]
- Failure of the Ariane 5 rocket (1996)[8]
- Mistakes in election result totalization[9]
Main topics
[edit]The study of validated numerics is divided into the following fields:
- Verification in numerical linear algebra
- Verification of special functions:
- Verification of numerical quadrature[31][32][33]
- Verification of nonlinear equations (The Kantorovich theorem,[34] Krawczyk method, interval Newton method, and the Durand–Kerner–Aberth method are studied.)
- Verification for solutions of ODEs, PDEs[35] (For PDEs, knowledge of functional analysis are used.[34])
- Verification of linear programming[36]
- Verification of computational geometry
- Verification at high-performance computing environment
Tools
[edit]- INTLAB Library made by MATLAB/GNU Octave
- kv Library made by C++. This library can obtain multiple precision outputs by using GNU MPFR.
- 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, maps and validated numerics for dynamical systems.
- JuliaIntervals on GitHub (Library made by Julia)
- Boost Safe Numerics - C++ header only library of validated replacements for all builtin integer types.
See also
[edit]References
[edit]- ^ Tucker, Warwick. (1999). "The Lorenz attractor exists." Comptes Rendus de l'Académie des Sciences-Series I-Mathematics, 328(12), 1197–1202.
- ^ Zin Arai, Hiroshi Kokubu, Paweãl Pilarczyk. Recent Development In Rigorous Computational Methods In Dynamical Systems.
- ^ Rump, Siegfried M. (1988). "Algorithms for verified inclusions: Theory and practice." In Reliability in computing (pp. 109–126). Academic Press.
- ^ Loh, Eugene; Walster, G. William (2002). Rump's example revisited. Reliable Computing, 8(3), 245-248.
- ^ Breuer, B.; Plum, Michael; McKenna, Patrick 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, Wei-Ming; Nirenberg, Louis (1979). "Symmetry and related properties via the maximum principle." Communications in Mathematical Physics, 68(3), 209–243.
- ^ "The Patriot Missile Failure".
- ^ ARIANE 5 Flight 501 Failure, http://sunnyday.mit.edu/nasa-class/Ariane5-report.html
- ^ Rounding error changes Parliament makeup
- ^ Yamamoto, T. (1984). Error bounds for approximate solutions of systems of equations. Japan Journal of Applied Mathematics, 1(1), 157.
- ^ Oishi, S., & Rump, S. M. (2002). Fast verification of solutions of matrix equations. Numerische Mathematik, 90(4), 755-773.
- ^ Yamamoto, T. (1980). Error bounds for computed eigenvalues and eigenvectors. Numerische Mathematik, 34(2), 189-199.
- ^ Yamamoto, T. (1982). Error bounds for computed eigenvalues and eigenvectors. II. Numerische Mathematik, 40(2), 201-206.
- ^ Mayer, G. (1994). Result verification for eigenvectors and eigenvalues. Topics in Validated Computations, Elsevier, Amsterdam, 209-276.
- ^ Ogita, T. (2008). Verified Numerical Computation of Matrix Determinant. SCAN’2008 El Paso, Texas September 29–October 3, 2008, 86.
- ^ Shinya Miyajima, Verified computation for the Hermitian positive definite solution of the conjugate discrete-time algebraic Riccati equation, Journal of Computational and Applied Mathematics, Volume 350, Pages 80-86, April 2019.
- ^ Shinya Miyajima, Fast verified computation for the minimal nonnegative solution of the nonsymmetric algebraic Riccati equation, Computational and Applied Mathematics, Volume 37, Issue 4, Pages 4599-4610, September 2018.
- ^ Shinya Miyajima, Fast verified computation for the solution of the T-congruence Sylvester equation, Japan Journal of Industrial and Applied Mathematics, Volume 35, Issue 2, Pages 541-551, July 2018.
- ^ Shinya Miyajima, Fast verified computation for the solvent of the quadratic matrix equation, The Electronic Journal of Linear Algebra, Volume 34, Pages 137-151, March 2018
- ^ Shinya Miyajima, Fast verified computation for solutions of algebraic Riccati equations arising in transport theory, Numerical Linear Algebra with Applications, Volume 24, Issue 5, Pages 1-12, October 2017.
- ^ Shinya Miyajima, Fast verified computation for stabilizing solutions of discrete-time algebraic Riccati equations, Journal of Computational and Applied Mathematics, Volume 319, Pages 352-364, August 2017.
- ^ Shinya Miyajima, Fast verified computation for solutions of continuous-time algebraic Riccati equations, Japan Journal of Industrial and Applied Mathematics, Volume 32, Issue 2, Pages 529-544, July 2015.
- ^ Rump, Siegfried M. (2014). Verified sharp bounds for the real gamma function over the entire floating-point range. Nonlinear Theory and Its Applications, IEICE, 5(3), 339-348.
- ^ Yamanaka, Naoya; Okayama, Tomoaki; Oishi, Shin’ichi (2015, November). Verified Error Bounds for the Real Gamma Function Using Double Exponential Formula over Semi-infinite Interval. In International Conference on Mathematical Aspects of Computer and Information Sciences (pp. 224-228). Springer.
- ^ Johansson, Fredrik (2019). Numerical Evaluation of Elliptic Functions, Elliptic Integrals and Modular Forms. In Elliptic Integrals, Elliptic Functions and Modular Forms in Quantum Field Theory (pp. 269-293). Springer, Cham.
- ^ Johansson, Fredrik (2019). Computing Hypergeometric Functions Rigorously. ACM Transactions on Mathematical Software (TOMS), 45(3), 30.
- ^ Johansson, Fredrik (2015). Rigorous high-precision computation of the Hurwitz zeta function and its derivatives. Numerical Algorithms, 69(2), 253-270.
- ^ Miyajima, S. (2018). Fast verified computation for the matrix principal pth root. en:Journal of Computational and Applied Mathematics, 330, 276-288.
- ^ Miyajima, S. (2019). Verified computation for the matrix principal logarithm. Linear Algebra and its Applications, 569, 38-61.
- ^ Miyajima, S. (2019). Verified computation of the matrix exponential. Advances in Computational Mathematics, 45(1), 137-152.
- ^ Johansson, Fredrik (2017). Arb: efficient arbitrary-precision midpoint-radius interval arithmetic. IEEE Transactions on Computers, 66(8), 1281-1292.
- ^ Johansson, Fredrik (2018, July). Numerical integration in arbitrary-precision ball arithmetic. In International Congress on Mathematical Software (pp. 255-263). Springer, Cham.
- ^ Johansson, Fredrik; Mezzarobba, Marc (2018). Fast and Rigorous Arbitrary-Precision Computation of Gauss--Legendre Quadrature Nodes and Weights. SIAM Journal on Scientific Computing, 40(6), C726-C747.
- ^ a b Eberhard Zeidler, Nonlinear Functional Analysis and Its Applications I-V. Springer Science & Business Media.
- ^ Mitsuhiro T. Nakao, Michael Plum, Yoshitaka Watanabe (2019) Numerical Verification Methods and Computer-Assisted Proofs for Partial Differential Equations (Springer Series in Computational Mathematics).
- ^ Oishi, Shin’ichi; Tanabe, Kunio (2009). Numerical Inclusion of Optimum Point for Linear Programming. JSIAM Letters, 1, 5-8.
Further reading
[edit]- Tucker, Warwick (2011). Validated Numerics: A Short Introduction to Rigorous Computations. Princeton University Press.
- Moore, Ramon Edgar, Kearfott, R. Baker., Cloud, Michael J. (2009). Introduction to Interval Analysis. Society for Industrial and Applied Mathematics.
- Rump, Siegfried M. (2010). Verification methods: Rigorous results using floating-point arithmetic. Acta Numerica, 19, 287–449.
External links
[edit]- Validated Numerics for Pedestrians
- Reliable Computing, An open electronic journal devoted to numerical computations with guaranteed accuracy, bounding of ranges, mathematical proofs based on floating-point arithmetic, and other theory and applications of interval arithmetic and directed rounding.