×

zbMATH — the first resource for mathematics

Floating-point arithmetic on the test bench. How are verified numerical solutions calculated? (Gleitkommaarithmetik auf dem Prüfstand. Wie werden verifiziert(e) numerische Lösungen berechnet?) (German) Zbl 1372.65140
Zusammenfassung: Um es vorweg zu nehmen, ungenaue numerische Resultate sind selten; zu selten, sich immer darum kümmern zu müssen, aber nicht selten genug, sie zu ignorieren.
Im folgenden sollen die Grenzen und Möglichkeiten von Gleitkommaarithmetik und von numerischen Verfahren untersucht und Eigenschaften und Fakten verdeutlicht werden, insbesondere anhand einiger Beispiele. Namentlich werden Algorithmen besprochen, die zwar nur Gleitkommaarithmetik nutzen, aber dennoch grundsätzlich nur korrekte Ergebnisse liefern.
Um auch das vorweg zu nehmen, korrekte Ergebnisse nicht-trivialer Probleme können mit Intervallarithmetik berechnet werden, auch wenn jene zuweilen immer noch in einem zweifelhaften Ruf steht. Hierauf wird öfter eingegangen, auch in einem eigenen Abschnitt 15.
Der Artikel wendet sich insbesondere an Mathematiker, die bisher eher peripher mit Numerik zu tun hatten. Ich hoffe auf Nachsicht, daß wenig mehr als mathematisches Abiturwissen durchaus genügt und verweise auf S. M. Rump [Acta Numerica 19, 287–449 (2010; Zbl 1323.65046)] für diejenigen, die mehr bzw. andere Mathematik hinzufügen möchten. Allein, ohne die hier explizierten Grundlagen wird man den tieferen Sinn der dort vorgestellten Verfahren kaum gründlich verstehen können.

MSC:
65G20 Algorithms with automatic result verification
65G30 Interval and finite arithmetic
65Y04 Numerical algorithms for computer arithmetic, etc.
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andrade, M.V.A., Comba, J.L.D., Stolfi, J.: Affine arithmetic. Presented at INTERVAL’94 (1994)
[2] Bertot, Y., Castéran, P.: Interactive Theorem Proving and Program Development Coq’Art: The Calculus of Inductive Constructions. Texts in Theoretical Computer Science, EATCS Series. Springer, Berlin (2004) · Zbl 1069.68095
[3] Bischof, C.H., Carle, A., Corliss, G., Griewank, A.: ADIFOR—Generating Derivative Codes from Fortran Programs. Technical report, Mathematics and Computer Science Devision, Argonne National Laboratory (1991) · Zbl 0031.31402
[4] Boldo, S., Pitfalls of a full floating-point proof: example on the formal proof of the veltkamp/dekker algorithms, IJCAR, Seattle · Zbl 1222.65156
[5] Bornemann, F.: Numerische lineare Algebra - Eine konzise Einführung mit MATLAB und Julia. Springer, Berlin (2016) · Zbl 1362.65030
[6] Bornemann, F.: The SIAM 100-digit challenge: a decade later. Jahresber. Dtsch. Mat.-Ver. (im Ersheinen) (2016). doi:10.1365/s13291-016-0137-2 · Zbl 1341.65001
[7] Bornemann, F., Laurie, D., Wagon, S., Waldvogel, J.: The SIAM 100-Digit Challenge—A Study in High-Accuracy Numerical Computing. SIAM, Philadelphia (2004) · Zbl 1060.65002
[8] Bouissou, O.; Goubault, E.; Goubault-Larrecq, J.; Putot, S., A generalization of p-boxes to affine arithmetic, Computing, 94, 180-201, (2012) · Zbl 1247.60006
[9] Breuer, B.; McKenna, P.J.; Plum, M., Multiple solutions for a semilinear boundary value problem: a computational multiplicity proof, J. Differ. Equ., 195, 243-269, (2003) · Zbl 1156.35359
[10] Chandrasekaran, S., Ipsen, I.: Perturbation theory for the solution of systems of linear equations. Technical report YALEU/DCS/RR-866, Yale University, Dept. of Computer Science (October 1991) · Zbl 0818.65033
[11] Cole, F.N., On the factoring of large numbers, Bull. Am. Math. Soc., 10, 134-137, (1903)
[12] Conn, A.R., Gould, N.I.M., Lescrenier, M., Toint, Ph.L.: Performance of a multifrontal scheme for partially separable optimization. Technical report 88/4, Dept. of Mathematics, FUNDP (Namur, B) (1988) · Zbl 0809.90117
[13] Cuyt, A.; Verdonk, B.; Becuwe, S.; Kuterna, P., A remarkable example of catastrophic cancellation unraveled, Computing, 66, 309-320, (2001) · Zbl 0999.65031
[14] Dekker, T.J., A floating-point technique for extending the available precision, Numer. Math., 18, 224-242, (1971) · Zbl 0226.65034
[15] Demmel, J.B.: On floating point errors in Cholesky. LAPACK working note 14 CS-89-87, Department of Computer Science, University of Tennessee, Knoxville, TN, USA (1989)
[16] Demmel, J.B., Henry, G., Kahan, W.: XBLAS: a draft proposal to the BLAS technical forum for extra precise BLAS (1997) · Zbl 0681.65012
[17] Durán, A.J.; Pérez, M.; Varona, J.L., Misfortunes of a mathematicians’ trio using computer algebra systems: can we trust?, Not. Am. Mat. Soc., 61, 1249-1252, (2014) · Zbl 1338.68299
[18] Figueiredo, L.H.; Stolfi, J., Affine arithmetic: concepts and applications, Numer. Algorithms, 37, 147-158, (2004) · Zbl 1074.65050
[19] Foster, L.V., Gaussian elimination with partial pivoting can fail in practice, SIAM J. Matrix Anal. Appl., 14, 1354-1362, (1994) · Zbl 0806.65022
[20] Fousse, L., Hanrot, G., Lefèvre, V., Pélissier, P., Zimmermann, P.: MPFR: a multiple-precision binary floating-point library with correct rounding. Research report RR-5753, INRIA (2005). Code and documentation available at http://hal.inria.fr/inria-00000818 · Zbl 1047.65012
[21] Gauß, C.F.: Theoria Motus Corporum Coelestium in Sectionibus Conicis Solem Ambientium (Theorie der Bewegung der Himmelskörper, die in Kegelschnitten die Sonne umlaufen). F. Perthes und I.H. Besser, Hamburg (1809) · Zbl 1234.01016
[22] Gidas, B.; Ni, W.; Nirenberg, L., Symmetry and related problems via the maximum principle, Commun. Math. Phys., 68, 209-243, (1979) · Zbl 0425.35020
[23] Golub, G.H., Van Loan, Ch.: Matrix Computations, 4. Aufl. Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037
[24] Griewank, A., A mathematical view of automatic differentiation, No. 12, 321-398, (2003), Cambridge · Zbl 1047.65012
[25] Griewank, A.; Juedes, D.; Mitev, H.; Utke, J.; Vogel, O.; Walther, A., ADOL-C: a package for the automatic differentiation of algorithms written in C/C++, ACM Trans. Math. Softw., 22, 131-167, (1995) · Zbl 0884.65015
[26] Hales, T.C.: The Kepler conjecture. Manuscript (1998). http://www.math.lsa.umich.edu/ hales/countdown/ · Zbl 1099.68725
[27] Hales, T.C., A proof of the Kepler conjecture, Ann. Math., 162, 1063-1183, (2000)
[28] Hales, T.C., Adams, M., Bauer, G., Dang, D.T., Harrison, J., Hoang, T.L., Kaliszyk, C., Magron, V., McLaughlin, S., Nguyen, T.T., Nguyen, T.Q., Nipkow, T., Obua, S., Pleso, J., Rute, J., Solovyev, A., Ta, A.H., Tran, T.N., Trieu, D.T., Urban, J., Vu, K.K., Zumkeller, R.: A formal proof of the Kepler conjecture. Manuscript (2015). http://arxiv.org/abs/1501.02155 · Zbl 1243.65047
[29] Harrison, J., Hol light: an overview, No. 5674, 60-66, (2009) · Zbl 1252.68255
[30] Higham, D.J.; Higham, N.J., Large growth factors in Gaussian elimination with pivoting, SIAM J. Matrix Anal. Appl., 10, 155-164, (1989) · Zbl 0681.65012
[31] Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2. Aufl. SIAM Publications, Philadelphia (2002) · Zbl 1011.65010
[32] Hotelling, H., Some new methods in matrix calculation, Ann. Math. Stat., 14, 1-34, (1943) · Zbl 0061.27007
[33] ANSI/IEEE 754-1985: IEEE standard for binary floating-point arithmetic. New York, 1985
[34] ANSI/IEEE 754-2008: IEEE standard for floating-point arithmetic. New York (2008)
[35] Jansson, C.; Chaykin, D.; Keil, C., Rigorous error bounds for the optimal value in semidefinite programming, SIAM J. Numer. Anal., 46, 180-200, (2007) · Zbl 1167.90009
[36] Jeannerod, C.-P.; Rump, S.M., Improved error bounds for inner products in floating-point arithmetic, SIAM J. Matrix Anal. Appl., 34, 338-344, (2013) · Zbl 1279.65052
[37] Kaplanski, I.: An Introduction to Differential Algebra, Illinois (1959) [Russian translation]
[38] Kashiwagi, M.: Private communication
[39] Kashiwagi, M., An algorithm to reduce the number of dummy variables in affine arithmetic, Novosibirsk
[40] Kernighan, B.W., Ritchie, D.M.: The C Programming Language. Prentice-Hall Software Series. Prentice Hall, New York (1988) · Zbl 0701.68014
[41] Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, Bd. 2, 3. Aufl. Addison Wesley, Reading (1998) · Zbl 0895.65001
[42] Loh, E.; Walster, W., Rump’s example revisited, Reliab. Comput., 8, 245-248, (2002) · Zbl 1001.65043
[43] Lohner, R.: Einschließung der Lösung gewöhnlicher Anfangs- und Randwertaufgaben und Anwendungen. PhD thesis, University of Karlsruhe (1988)
[44] Maple: release 2015, reference manual (2015)
[45] Markoff, J.: Flaw undermines accuracy of pentium chip. New York Times, November 23 (1994)
[46] Mathematica: release 10.4, reference manual (2016) · Zbl 0771.65049
[47] MATLAB: user’s guide, version 2016a, The MathWorks Inc. (2016)
[48] Moore, R.E.: Interval arithmetic and automatic error analysis in digital computing. Dissertation, Stanford University (1963) · Zbl 0999.65031
[49] Moore, R.E.: Interval Analysis. Prentice-Hall, Englewood Cliffs, N.J. (1966) · Zbl 0176.13301
[50] Muller, J.-M., Brisebarre, N., de Dinechin, F., Jeannerod, C.-P., Lefèvre, V., Melquiond, G., Revol, N., Stehlé, D., Torres, S.: Handbook of Floating-Point Arithmetic. Birkhäuser, Boston (2009) · Zbl 1197.65001
[51] Neumaier, A.: Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen. Z. Angew. Math. Mech. 54, 39-51 (1974) · Zbl 0273.65032
[52] Neumann, J.v.; Goldstine, H.H., Numerical inverting of matrices of high order, Bull. Am. Math. Soc., 53, 1021-1099, (1947) · Zbl 0031.31402
[53] GNU octave: release 4.0.1, user’s guide (2016). http://www.gnu.org/software/octave/ · Zbl 0703.65015
[54] Ogita, T.; Rump, S.M.; Oishi, S., Accurate sum and dot product, SIAM J. Sci. Comput., 26, 1955-1988, (2005) · Zbl 1084.65041
[55] Payne, M.; Hanek, R., Radian reduction for trigonometric functions, SIGNUM Newsl., 18, 19-24, (1983)
[56] Poljak, S., Rohn, J.: Radius of nonsingularity. No. 88-117, Universitas Carolina Pragensis (1988) · Zbl 1252.68255
[57] Risch, R.H., The problem of integration in finite terms, Trans. Am. Math. Soc., 139, 167-189, (1969) · Zbl 0184.06702
[58] Rump, S.M.: Kleine Fehlerschranken bei Matrixproblemen. PhD thesis, Universität Karlsruhe (1980) · Zbl 0437.65036
[59] Rump, S.M.; Csendes, T. (ed.), INTLAB—interval laboratory, 77-104, (1999), Dordrecht · Zbl 0949.65046
[60] Rump, S.M., Inversion of extremely ill-conditioned matrices in floating-point, Jpn. J. Ind. Appl. Math., 26, 249-277, (2009) · Zbl 1185.65050
[61] Rump, S.M., Verification methods: rigorous results using floating-point arithmetic, Acta Numer., 19, 287-449, (2010) · Zbl 1323.65046
[62] Rump, S.M., Error estimation of floating-point summation and dot product, BIT Numer. Math., 52, 201-220, (2012) · Zbl 1243.65047
[63] Rump, S.M., Accurate solution of dense linear systems. part I. algorithms in rounding to nearest, J. Comput. Appl. Math., 242, 157-184, (2013) · Zbl 1255.65084
[64] Rump, S.M.; Jeannerod, C.-P., Improved backward error bounds for Lu and Cholesky factorizations, SIAM J. Matrix Anal. Appl., 35, 684-698, (2014) · Zbl 1309.65031
[65] Sahinidis, N.V.; Tawaralani, M., A polyhedral branch-and-cut approach to global optimization, Math. Program., Ser. B, 103, 225-249, (2005) · Zbl 1099.90047
[66] Schloemilch, O.: Handbuch der Mathematik, Erster Band: Elementarmathematik. Trewendt, Breslau (1881) · JFM 35.0986.02
[67] Shewchuk, J.R., Adaptive precision floating-point arithmetic and fast robust geometric predicates, Discrete Comput. Geom., 18, 305-363, (1997) · Zbl 0892.68098
[68] Singh, S.: Homers formel. ZEIT Online 46, 14. November (2013) · Zbl 0033.28501
[69] Skeel, R., Iterative refinement implies numerical stability for Gaussian elimination, Math. Comput., 35, 817-832, (1980) · Zbl 0441.65027
[70] Stewart, G.W., Sun, J.: Matrix Perturbation Theory. Academic Press, San Diego (1990) · Zbl 0706.65013
[71] Stoer, J.: Einführung in die Numerische Mathematik, I. Springer, New York (1999)
[72] Stoer, J., Burlirsch, R.: Einführung in die Numerische Mathematik, II. Springer, New York (2005)
[73] Strubecker, K.: Einführung in die Höhere Mathematik. Oldenbourg Verlag, München (1967) · Zbl 0152.24203
[74] Sunaga, T.: Geometry of numerals. Master’s thesis, University of Tokyo (February 1956)
[75] Trefethen, L.N., The SIAM 100-dollar, 100-digit challenge, SIAM Soc. Newsl., 35, 2, (2002)
[76] Trefethen, L.N.; Schreiber, R., Average-case stability of Gaussian elimination, SIAM J. Matrix Anal. Appl., 11, 335-360, (1990) · Zbl 0703.65015
[77] Turing, A.M., Rounding-off errors in matrix processes, Q. J. Mech. Appl. Math., 1, 287-308, (1948) · Zbl 0033.28501
[78] Patriot missile defense: software problem led to system failure at Dhahran, Saudi Arabia. Report GAO/IMTEC-92-26. Information Management and Technology Division, United States General Accounting Office, Washington, D.C. (February 1992). 16 pp. · Zbl 1309.65031
[79] Wilkinson, J.H., Error analysis of floating-point computation, Numer. Math., 2, 319-340, (1960) · Zbl 0091.29605
[80] Wilkinson, J.H., Modern error analysis, SIAM Rev., 13, 548-568, (1971) · Zbl 0243.65018
[81] Wilkinson, J.H., Some comments from a numerical analyst [1970 Turing lecture anläßlich der verleihung des ACM Turing awards (ausarbeitung)], J. ACM, 18, 137-147, (1971) · Zbl 0223.01015
[82] Wright, S.J., A collection of problems for which Gaussian elimination with partial pivoting is unstable, SIAM J. Sci. Comput., 14, 231-238, (1993) · Zbl 0771.65049
[83] XBLAS: a reference implementation for extended and mixed precision BLAS. http://crd.lbl.gov/ xiaoye/XBLAS/
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.