Abstract
Recently Miyajima presented algorithms to compute componentwise verified error bounds for the solution of full-rank least squares problems and underdetermined linear systems. In this paper we derive simpler and improved componentwise error bounds which are based on equalities for the error of a given approximate solution. Equalities are not improvable, and the expressions are formulated in a way that direct evaluation yields componentwise and rigorous estimates of good quality. The computed bounds are correct in a mathematical sense covering all sources of errors, in particular rounding errors. Numerical results show a gain in accuracy compared to previous results.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arioli, M., Duff, I.S., de Rijk, P.P.M.: On the augmented system approach to sparse least-squares problems. Numer. Math. 55(6), 667–687 (1989)
Björck, Å.: Iterative refinement of linear least squares solutions I. BIT 7, 257–278 (1967)
Davis, T.A., Hu, Y.: The University of Florida Sparse Matrix Collection. ACM Trans. Math. Softw. 38(1), 1:1–1:25 (2011)
Demmel, J.B., Hida, Y., Kahan, W., Li, X.S., Mukherjee, S., Riedy, E.J.: Error, bounds from extra precise iterative refinement. ACM Trans. Math. Softw. (TOMS) 32(2), 325–351 (2006)
Frommer, A.: Proving conjectures by use of interval arithmetic. In: Kulisch, U., et al. (eds.) Perspectives on Enclosure Methods. SCAN 2000, GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic and Validated Numerics, Univ. Karlsruhe, Germany, September 19-22, 2000. Springer, Wien (2001)
Golub, G.H., Van Loan, C.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM Publications, Philadelphia (2002)
IEEE Standard for Floating-Point Arithmetic IEEE Std 754-2008. In: IEEE Std 754-2008, pp. 1–58, 29 Aug 2008
MATLAB: Users Guide, Version 7, the MathWorks Inc. (2004)
Miyajima, S.: Fast enclosure for solutions in underdetermined systems. J. Comput. Appl. Math. (JCAM) 234, 3436–3444 (2010)
Miyajima, S.: Componentwise enclosure for solutions in least squares problems and underdetermined linear systems. SCAN conference Novosibirsk (2012)
Rump, S.M.: Kleine Fehlerschranken bei Matrixproblemen. PhD thesis. Universität Karlsruhe (1980)
Rump, S.M.: INTLAB - INTerval LABoratory. In: Csendes, T. (ed.) Developments in Reliable Computing, pp 77–104. Kluwer Academic Publishers, Dordrecht (1999)
Rump, S.M.: Verified bounds for least squares problems and underdetermined linear systems. SIAM J. Matrix Anal. Appl. (SIMAX) 33(1), 130–148 (2012)
Sahinidis, N.V., Tawaralani, M.: A polyhedral branch-and-cut approach to global optimization. Math. Program. B103, 225–249 (2005)
Stetter, H.J.: Sequential defect correction in high-accuracy floating-point arithmetics. Num. Anal. 1066, 186-202 (1984). Proceedings, Dundee 1983
Tucker, W.: The Lorenz attractor exists. C. R. Acad. Sci., Paris, Sér. I, Math. 328(12), 1197–1202 (1999)
Wedin, P.Å.: Perturbation theory for pseudo-inverses. BIT 13, 217–232 (1973)
Wright, S.J.: A collection of problems for which Gaussian elimination with partial pivoting is unstable. SIAM J. Sci. Comput. (SISC) 14(1), 231–238 (1993)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rump, S.M. Improved componentwise verified error bounds for least squares problems and underdetermined linear systems. Numer Algor 66, 309–322 (2014). https://doi.org/10.1007/s11075-013-9735-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-013-9735-6
Keywords
- Least squares problems
- Underdetermined linear systems
- INTLAB
- Componentwise error estimates
- Normal equations
- Extra-precise residual evaluation