Abstract
The condition number is a quantity that is well-known in “classical” numerical analysis, that is, where numerical computations are performed using floating-point numbers. This quantity appears much less frequently in interval numerical analysis, that is, where the computations are performed on intervals. The goal of this paper is twofold. On the one hand, it is stressed that the notion of condition number already appears in the literature on interval analysis, even if it does not bear that name. On the other hand, three small examples are used to illustrate experimentally the impact of the condition number on interval computations. As expected, problems with a larger condition number are more difficult to solve: this means either that the solution is not very accurate (for moderate condition numbers) or that the method fails to solve the problem, even inaccurately (for larger condition numbers). Different strategies to counteract the impact of the condition number are discussed and experimented: use of a higher precision, iterative refinement, bisection of the input. More strategies are discussed as a conclusion.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
E. Carson, N.J. Higham, A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems. Technical Report MIMS Eprint 2017.12, Manchester Institute for Mathematical Sciences, (The University of Manchester, UK, 2017). SIAM J. Sci. Comput.,39(6), A2834–A2856, (2017)
E. Carson, N.J. Higham, Accelerating the solution of linear systems by iterative refinement in three precisions. Technical Report MIMS Eprint 2017.24, Manchester Institute for Mathematical Sciences, (The University of Manchester, UK, 2017). SIAM J. Sci. Comput.,40(2), A817–A847, (2018)
J. Demmel, Y. Hida, W. Kahan, X.S. Li, S. Mukherjee, E.J. Riedy, Error bounds from extra-precise iterative refinement. ACM Trans. Math. Softw. 32(2), 325–351 (2006)
O. Heimlich, Interval arithmetic in GNU Octave, In SWIM 2016: Summer Workshop on Interval Methods (2016)
N. Higham, Accuracy and Stability of Numerical Algorithms, 2nd edn. (SIAM Press, 2002)
V. Kreinovich, S. Rump, Towards optimal use of multi-precision arithmetic: a remark. Reliab. Comput. 12(5), 365–369 (2006)
J.-M. Muller, N. Brunie, de Dinechin, F. Jeannerod, C.-P. Joldes, M. Lefèvre, V. Melquiond, G. Revol, S. Torres, Handbook of Floating-Point Arithmetic (2nd edition, 2018)
A. Neumaier, Interval Methods for Systems of Equations (Cambridge University Press, 1990)
A. Neumaier, A simple derivation of the Hansen-Bliek-Rohn-Ning-Kearfott enclosure for linear interval equations. Reliab. Comput. 5, 131–136 (1999) (+ Erratum: Reliable Computing 6, p. 227, 2000)
H.D. Nguyen, Efficient algorithms for verified scientific computing: numerical linear algebra using interval arithmetic. Ph.D. Thesis, École Normale Supérieure de Lyon - ENS LYON, (2011). https://tel.archives-ouvertes.fr/tel-00680352/en
N. Revol, Y. Denneulin, J.-F. Méhaut, B. Planquelle, A methodology of parallelization for continuous verified global optimization. LNCS 2328, 803–810 (2002)
S. Rump, Developments in Reliable Computing, T. Csendes ed., chapter INTLAB - Interval Laboratory (Kluwer, 1999), pp. 77–104
J.H. Wilkinson, Rounding Errors in Algebraic Processes (Prentice-Hall, Englewood Cliffs, NJ, 1963)
Acknowledgements
This work has been partially supported by the ANR project MetaLibm ANR-13-INSE-0007-04.
The author thanks H. D. Nguyen for his kind permission to reproduce the material of Sect. 4. She also thanks Olga Kosheleva for her kind invitation. Last but not least, she wishes to thank Vladik Kreinovich for his kindness and friendship during many years, and for his vitality that is contagious and beneficial to the community.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Revol, N. (2020). Influence of the Condition Number on Interval Computations: Illustration on Some Examples. In: Kosheleva, O., Shary, S., Xiang, G., Zapatrin, R. (eds) Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications. Studies in Computational Intelligence, vol 835. Springer, Cham. https://doi.org/10.1007/978-3-030-31041-7_20
Download citation
DOI: https://doi.org/10.1007/978-3-030-31041-7_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-31040-0
Online ISBN: 978-3-030-31041-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)