Abstract
We prove duality results for adjoint operators and product norms in the framework of Euclidean spaces. We show how these results can be used to derive condition numbers especially when perturbations on data are measured componentwise relatively to the original data. We apply this technique to obtain formulas for componentwise and mixed condition numbers for a linear function of a linear least squares solution. These expressions are closed when perturbations of the solution are measured using a componentwise norm or the infinity norm and we get an upper bound for the Euclidean norm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3 edn. SIAM, Philadelphia (1999)
Arioli, M., Baboulin, M., Gratton, S.: A partial condition number for linear least-squares problems. SIAM J. Matrix Anal. Appl. 29(2), 413–433 (2007)
Arioli, M., Demmel, J.W., Duff, I.S.: Solving sparse linear systems with sparse backward error. SIAM J. Matrix Anal. Appl. 10(2), 165–190 (1989)
Arioli, M., Duff, I.S., M de Rijk, P.P.: On the augmented system approach to sparse least squares problems. Numer. Math. 55, 667–684 (1989)
Bauer, F.L.: Genauigkeitsfragen bei der Lösung linearer Gleichungssysteme. Z. Angew. Math. Mech. 46(7), 409–421 (1966)
Björck, Å: Component-wise perturbation analysis and error bounds for linear least squares solutions. BIT Numer. Math. 31, 238–244 (1991)
Björck, Å: Numerical Methods for Least Squares Problems. SIAM, Philadelphia (1996)
Chandrasekaran, S., Ipsen, I.C.F.: On the sensitivity of solution components in linear systems of equations. SIAM J. Matrix Anal. Appl. 16(1), 93–112 (1995)
Cucker, F., Diao, H., Wei, Y.: On mixed and componentwise condition numbers for Moore-Penrose inverse and linear least squares problems. Math. Comput. 76(258), 947–963 (2007)
Demmel, J., Hida, Y., Li, X.S., Riedy, E.J.: Extra-precise iterative refinement for overdetermined least squares problems. Technical Report EECS-2007-77, UC Berkeley (2007). Also LAPACK Working Note 188
Dongarra, J., Du Croz, J., Duff, I., Hammarling, S.: A set of level 3 basic linear algebra subprograms. ACM Trans. Math. Softw. 16, 1–17 (1990)
Geurts, A.J.: A contribution to the theory of condition. Numer. Math. 39, 85–96 (1982)
Gohberg, I., Koltracht, I.: Mixed, componentwise, and structured condition numbers. SIAM J. Matrix Anal. Appl. 14(3), 688–704 (1993)
Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)
Graham, A.: Kronecker Products and Matrix Calculus with Application. Wiley, New York (1981)
Gratton, S.: On the condition number of linear least squares problems in a weighted Frobenius norm. BIT Numer. Math. 36(3), 523–530 (1996)
Grcar, J.F.: Adjoint formulas for condition numbers applied to linear and indefinite least squares. Technical Report LBNL-55221, Lawrence Berkeley National Laboratory (2004)
Higham, D.J., Higham, N.J.: Componentwise perturbation theory for linear systems with multiple right-hand sides. Linear Algebra Appl. 174, 111–129 (1992)
Higham, N.J.: Computing error bounds for regression problems. In: Brown, P.J., Fuller, W.A. (eds.) Statistical Analysis of Measurement Error Models and Applications. Contemporary Mathematics, vol. 112, pp. 195–208. American Mathematical Society, Providence (1990)
Higham, N.J.: A survey of componentwise perturbation theory in numerical linear algebra. In: Gautschi, W. (ed.) Mathematics of Computation 1943–1993: A Half Century of Computational Mathematics. Proceedings of Symposia in Applied Mathematics, vol. 48, pp. 49–77. American Mathematical Society, Providence (1994)
Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2 edn. SIAM, Philadelphia (2002)
Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)
Kenney, C.S., Laub, A.J., Reese, M.S.: Statistical condition estimation for linear least squares. SIAM J. Matrix Anal. Appl. 19(4), 906–923 (1998)
Lancaster, P., Tismenetsky, M.: The Theory of Matrices, 2nd edn. Academic Press, San Diego (1985). Second edition with applications
Läuchli, P.: Jordan-elimination und Ausgleichung nach kleinsten Quadraten. Numer. Math. 3, 226–240 (1961)
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)
Rice, J.: A theory of condition. SIAM J. Numer. Anal. 3, 287–310 (1966)
Rohn, J.: New condition numbers for matrices and linear systems. Computing 41(1–2), 167–169 (1989)
Rump, S.M.: Structured perturbations Part II: componentwise distances. SIAM J. Matrix Anal. Appl. 25(1), 31–56 (2003)
Skeel, R.D.: Scaling for numerical stability in Gaussian elimination. J. Assoc. Comput. Mach. 26(3), 494–526 (1979)
Stewart, G.W., Sun, J.: Matrix Perturbation Theory. Academic Press, San Diego (1991)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Lars Eldén.
Rights and permissions
About this article
Cite this article
Baboulin, M., Gratton, S. Using dual techniques to derive componentwise and mixed condition numbers for a linear function of a linear least squares solution. Bit Numer Math 49, 3–19 (2009). https://doi.org/10.1007/s10543-009-0213-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10543-009-0213-4