Interval analysis: Theory and applications. (English) Zbl 0995.65056

Alefeld, Götz; Mayer, Günter

J. Comput. Appl. Math. 121, No. 1-2, 421-464 (2000).

Summary: We give an overview on applications of interval arithmetic. Among others we discuss verification methods for systems of linear equations, nonlinear systems, the algebraic eigenvalue problem, initial value problems for ordinary differential equations and boundary value problems for elliptic partial differential equations of second-order. We also consider the item software in this field and give some historical remarks.

MSC:

65G30	Interval and finite arithmetic
65-02	Research exposition (monographs, survey articles) pertaining to numerical analysis
76F10	Shear flows and turbulence
65F15	Numerical computation of eigenvalues and eigenvectors of matrices
65G40	General methods in interval analysis
65G20	Algorithms with automatic result verification
65H10	Numerical computation of solutions to systems of equations
65L05	Numerical methods for initial value problems involving ordinary differential equations
65N06	Finite difference methods for boundary value problems involving PDEs
65Y15	Packaged methods for numerical algorithms

Keywords:

survey paper; systems of nonlinear equations; systems of linear equations; algebraic eigenvalue problem; ordinary differential equations; partial differential equations; software; interval arithmetic; verification methods

Software:

FORTRAN-XSC; C-XSC 2.0; C-XSC; PASCAL-XSC

References:

[1]	Adams, E.; Kulisch (Eds.), U., Scientific Computing with Automatic Result Verification (1993), Academic Press: Academic Press Boston · Zbl 0773.00004
[2]	Albrecht, R.; Alefeld, G.; Stetter (Eds.), H. J., Validation Numerics, Theory and Applications (1993), Springer: Springer Wien · Zbl 0784.00013
[4]	Alefeld, G., Über die Durchführbarkeit des Gaußschen Algorithmus bei Gleichungen mit Intervallen als Koeffizienten, Comput. Suppl., 1, 15-19 (1977) · Zbl 0361.65017
[5]	Alefeld, G., Bounding the slope of polynomials and some applications, Computing, 26, 227-237 (1981) · Zbl 0444.65027
[6]	Alefeld, G., Berechenbare Fehlerschranken für ein Eigenpaar unter Einschluß von Rundungsfehlern bei Verwendung des genauen Skalarprodukts, Z. Angew. Math. Mech., 67, 145-152 (1987) · Zbl 0622.65028
[7]	Alefeld, G., Rigorous error bounds for singular values of a matrix using the precise scalar product, (Kaucher, E.; Kulisch, U.; Ullrich, C., Computerarithmetic (1987), B.G. Teubner: B.G. Teubner Stuttgart), 9-30
[8]	Alefeld, G., Über das Divergenzverhalten des Intervall-Newton-Verfahrens, Computing, 46, 289-294 (1991) · Zbl 0753.65044
[9]	Alefeld, G., Inclusion methods for systems of nonlinear equations – the interval Newton method and modifications, (Herzberger, J., Topics in Validated Computations (1994), Elsevier: Elsevier Amsterdam), 7-26 · Zbl 0822.65029
[10]	Alefeld, G.; Gienger, A.; Mayer, G., Numerical validation for an inverse matrix eigenvalue problem, Computing, 53, 311-322 (1994) · Zbl 0813.65076
[11]	Alefeld, G.; Gienger, A.; Potra, F., Efficient numerical validation of solutions of nonlinear systems, SIAM J. Numer. Anal., 31, 252-260 (1994) · Zbl 0796.65068
[12]	Alefeld, G.; Herzberger, J., Einführung in die Intervallrechnung (1974), Bibliographisches Institut: Bibliographisches Institut Mannheim
[13]	Alefeld, G.; Herzberger, J., Introduction to Interval Computations (1983), Academic Press: Academic Press New York
[14]	Alefeld, G.; Hoffmann, R.; Mayer, G., Verification algorithms for generalized singular values, Math. Nachr., 208, 5-29 (1999) · Zbl 0939.65065
[15]	Alefeld, G.; Kreinovich, V.; Mayer, G., On the shape of the symmetric, persymmetric, and skew-symmetric solution set, SIAM J. Matrix Anal. Appl., 18, 693-705 (1997) · Zbl 0873.15003
[16]	Alefeld, G.; Kreinovich, V.; Mayer, G., The shape of the solution set of linear interval equations with dependent coefficients, Math. Nachr., 192, 23-36 (1998) · Zbl 0907.15003
[18]	Alefeld, G.; Lohner, R., On higher order centered forms, Computing, 35, 177-184 (1985) · Zbl 0564.65031
[19]	Alefeld, G.; Mayer, G., The Cholesky method for interval data, Linear Algebra Appl., 194, 161-182 (1993) · Zbl 0796.65032
[20]	Alefeld, G.; Mayer, G., A computer-aided existence and uniqueness proof for an inverse matrix eigenvalue problem, Int. J. Interval Comput., 1994, 1, 4-27 (1994) · Zbl 0834.65027
[21]	Alefeld, G.; Mayer, G., On the symmetric and unsymmetric solution set of interval systems, SIAM J. Matrix Anal. Appl., 16, 1223-1240 (1995) · Zbl 0834.65012
[22]	Beeck, H., Über Struktur und Abschätzungen der Lösungsmenge von linearen Gleichungssystemen mit Intervallkoeffizienten, Computing, 10, 231-244 (1972) · Zbl 0255.65014
[23]	Behnke, H.; Goerisch, F., Inclusions for eigenvalues of selfadjoint problems, (Herzberger, J., Topics in Validated Computations (1994), Elsevier: Elsevier Amsterdam), 277-322 · Zbl 0838.65060
[24]	Chen, X., A verification method for solutions of nonsmooth equations, Computing, 58, 281-294 (1997) · Zbl 0882.65038
[27]	Cornelius, H.; Lohner, R., Computing the range of values of real functions with accuracy higher than second order, Computing, 33, 331-347 (1984) · Zbl 0556.65037
[29]	Dwyer, P. S., Linear Computations (1951), Wiley: Wiley New York · Zbl 0044.12804
[33]	Golub, G. H.; van Loan, C. F., Matrix Computations (1995), John Hopkins: John Hopkins Baltimore
[34]	Griewank, A.; Corliss (Eds.), G. F., Automatic Differentiation of Algorithms (1992), SIAM: SIAM Philadelphia, PA
[36]	Hammer, R.; Hocks, M.; Kulisch, U.; Ratz, D., Numerical Toolbox for Verified Computing I (1993), Springer: Springer Berlin · Zbl 0796.65001
[37]	Hansen, E., An overview of global optimization using interval analysis, (Moore, R. E., Reliability in Computing. Reliability in Computing, The Role of Interval Methods in Scientific Computing, Perspectives in Computing, Vol. 19 (1988), Academic Press: Academic Press Boston), 289-307
[38]	Hansen, E., Global Optimization Using Interval Analysis (1992), Dekker: Dekker New York · Zbl 0762.90069
[42]	Jansson, C., On self-validating methods for optimization problems, (Herzberger, J., Topics in Validated Computations (1994), Elsevier: Elsevier Amsterdam), 381-438 · Zbl 0817.65044
[43]	Kaucher, E. W.; Miranker, W. L., Self-Validating Numerics for Function Space Problems. Self-Validating Numerics for Function Space Problems, Computations with Guarantees for Differential and Integral Equations (1984), Academic Press: Academic Press Orlando · Zbl 0548.65028
[44]	Kearfott, R. B., A review of techniques in the verified solution of constrained global optimization problems, (Kearfott, R. B.; Kreinovich, V., Applications of Interval Computations (1996), Kluwer: Kluwer Dordrecht), 23-59 · Zbl 0841.65049
[45]	Klatte, R.; Kulisch, U.; Lawo, C.; Rauch, M.; Wiethoff, A., C-XSC. A \(C^{++}\) Class Library for Extended Scientific Computing (1993), Springer: Springer Berlin
[46]	Klatte, R.; Kulisch, U.; Neaga, M.; Ratz, D.; Ullrich, C., PASCAL-XSC, Language Reference with Examples (1992), Springer: Springer Berlin · Zbl 0757.68023
[48]	Krawczyk, R., Newton-Algorithmen zur Bestimmung von Nullstellen mit Fehlerschranken, Computing, 4, 187-201 (1969) · Zbl 0187.10001
[54]	Lohner, R., Enclosing all eigenvalues of symmetric matrices, (Ullrich, C.; Wolff von Gudenberg, J., Accurate Numerical Algorithms. A Collection of Research Papers, Research Reports, ESPRIT, Project 1072, Diamond, Vol. 1 (1989), Springer: Springer Berlin), 87-103
[55]	Mayer, G., Old and new aspects for the interval Gaussian algorithm, (Kaucher, E.; Markov, S. M.; Mayer, G., Computer Arithmetic, Scientific Computation and Mathematical Modelling. Computer Arithmetic, Scientific Computation and Mathematical Modelling, IMACS Annals on Computing and Applied Mathematics, Vol. 12 (1991), J.C. Baltzer AG, Scientific Publishing: J.C. Baltzer AG, Scientific Publishing Basel), 329-349
[56]	Mayer, G., Enclosures for eigenvalues and eigenvectors, (Atanassova, L.; Herzberger, J., Computer Arithmetic and Enclosure Methods (1992), Elsevier: Elsevier Amsterdam), 49-67 · Zbl 0838.65036
[57]	Mayer, G., Result verification for eigenvectors and eigenvalues, (Herzberger, J., Topics in Validated Computations (1994), Elsevier: Elsevier Amsterdam), 209-276 · Zbl 0813.65077
[58]	Mayer, G., Epsilon-inflation in verification algorithms, J. Comput. Appl. Math., 60, 147-169 (1995) · Zbl 0839.65059
[59]	Mayer, G., Epsilon-inflation with contractive interval functions, Appl. Math., 43, 241-254 (1998) · Zbl 0938.65058
[60]	Mayer, G.; Rohn, J., On the applicability of the interval Gaussian algorithm, Reliable Comput., 4, 205-222 (1998) · Zbl 0933.65027
[62]	Miranda, C., Un’ osservazione su un teorema di Brouwer, Bol. Un. Mat. Ital. Ser. II, 3, 5-7 (1941) · JFM 66.0217.01
[64]	Moore, R. E., Interval Analysis (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[65]	Nakao, M. T., State of the art for numerical computations with guaranteed accuracy, Math. Japanese, 48, 323-338 (1998) · Zbl 0916.65044
[67]	Neher, M., An enclosure method for the solution of linear ODEs with polynomial coefficients, Numer. Funct. Anal. Optim., 20, 779-803 (1999) · Zbl 0936.65084
[68]	Neumaier, A., The enclosure of solutions of parameter-dependent systems of equations, (Moore, R. E., Reliability in Computing.. Reliability in Computing., The Role of Interval Methods in Scientific Computing, Perspectives in Computing, Vol. 19 (1988), Academic Press: Academic Press Boston), 269-286 · Zbl 0651.65044
[69]	Neumaier, A., Interval Methods for Systems of Equations (1990), University Press: University Press Cambridge · Zbl 0706.15009
[70]	Nguyen, H. T.; Kreinovich, V.; Nesterov, V.; Nakumura, M., On hardware support for interval computations and for soft computing: theorems, IEEE Trans. Fuzzy Systems, 5, 1, 108-127 (1997)
[71]	Ortega, J. M.; Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables (1970), Academic Press: Academic Press New York · Zbl 0241.65046
[72]	Oettli, W.; Prager, W., Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. Math., 6, 405-409 (1964) · Zbl 0133.08603
[73]	Petković, M.; Petković, L. D., Complex Interval Arithmetic and Its Applications (1998), Wiley: Wiley New York · Zbl 0911.65038
[74]	Plum, M., Inclusion methods for elliptic boundary value problems, (Herzberger, J., Topics in Validated Computations (1994), Elsevier: Elsevier Amsterdam), 323-379 · Zbl 0814.65105
[75]	Rall, L. B., Computational Solution of Nonlinear Operator Equations (1969), Wiley: Wiley New York · Zbl 0175.15804
[76]	Rall, L. B., Automatic Differentiation: Techniques and Applications. Automatic Differentiation: Techniques and Applications, Lecture Notes in Computer Science, Vol. 120 (1981), Springer: Springer Berlin · Zbl 0473.68025
[77]	Ratschek, H., Centered forms, SIAM J. Numer. Anal., 17, 656-662 (1980) · Zbl 0456.65019
[78]	Ratschek, H.; Rokne, J., Computer Methods for the Range of Functions (1984), Ellis Horwood: Ellis Horwood Chichester · Zbl 0584.65019
[79]	Ratschek, H.; Rokne, J., New Computer Methods for Global Optimization (1988), Ellis Horwood: Ellis Horwood Chichester, UK · Zbl 0648.65049
[80]	Rihm, R., Interval methods for initial value problems in ODE’s, (Herzberger, J., Topics in Validated Computations (1994), Elsevier: Elsevier Amsterdam), 173-207 · Zbl 0815.65095
[81]	Rump, S. M., Solving algebraic problems with high accuracy, (Kulisch, U. W.; Miranker, W. L., A New Approach to Scientific Computation (1983), Academic Press: Academic Press New York), 53-120
[82]	Rump, S. M., Rigorous sensitivity analysis for systems of linear and nonlinear equations, Math. Comp., 54, 721-736 (1990) · Zbl 0701.65039
[83]	Rump, S. M., On the solution of interval linear systems, Computing, 47, 337-353 (1992) · Zbl 0753.65030
[84]	Rump, S. M., Verification methods for dense and sparse systems of equations, (Herzberger, J., Topics in Validated Computations (1994), Elsevier: Elsevier Amsterdam), 63-135 · Zbl 0813.65072
[85]	Schrijver, A., Theory of Linear and Integer Programming (1986), Wiley: Wiley New York · Zbl 0665.90063
[87]	Shary, P. S., Solving the linear interval tolerance problem, Math. Comput. Simulation, 39, 53-85 (1995)
[88]	Sunaga, T., Theory of an interval algebra and its application to numerical analysis, RAAG Memoirs, 2, 29-46 (1958) · Zbl 0176.13201
[89]	Walter, W. V., FORTRAN-XSC: a portable FORTRAN 90 module library for accurate and reliable scientific computing, (Albrecht, R.; Alefeld, G.; Stetter, H. J., Validation Numerics, Theory and Applications (1993), Springer: Springer Wien), 265-285 · Zbl 0802.68022