×

Componentwise perturbation theory for linear systems with multiple right- hand sides. (English) Zbl 0801.65043

From the abstract: “Existing definitions of componentwise backward error and componentwise condition number for linear systems are extended to a general class of componentwise measure of perturbations involving Hölder \(p\)-norms. It is shown that for a system of order \(n\) with \(r\) right-hand sides, the componentwise backward error can be computed by finding the minimum \(p\)-norm solutions to \(n\) underdetermined linear systems, and an explicit expression is obtained in the case \(r = 1\). A perturbation bound is derived, and from this the componentwise condition number is obtained to within a multiplicative constant.
Applications of the results are discussed to invariant subspace computations, quasi-Newton methods based on multiple secant equations, and an inverse problem in ordinary differential equations”.

MSC:

65F35 Numerical computation of matrix norms, conditioning, scaling
15A12 Conditioning of matrices
65G50 Roundoff error
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, R. C.; Pruess, S. A., An analysis of an inverse problem in ordinary differential equations, SIAM J. Sci. Statist. Comput., 2, 176-185 (1981) · Zbl 0471.65064
[2] Arioli, M.; Demmel, J. W.; Duff, I. S., Solving sparse linear systems with sparse backward error, SIAM J. Matrix Anal. Appl., 10, 165-190 (1989) · Zbl 0684.65022
[3] Barlow, J. L.; Demmel, J. W., Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM J. Numer. Anal., 27, 762-791 (1990) · Zbl 0725.65043
[4] Barnes, J. G.P., An algorithm for solving non-linear equations based on the secant method, Comput. J., 8, 66-72 (1965) · Zbl 0254.65036
[5] Bischof, C. H.; Demmel, J. W.; Dongarra, J. J.; Du Croz, J. J.; Greenbaum, A.; Hammarling, S. J.; Sorensen, D. C., Provisional Contents, Lapack Working Note 5, (Report ANL-88-38 (1988), Mathematics and Computer Science Div., Argonne National Lab: Mathematics and Computer Science Div., Argonne National Lab Argonne, Ill)
[6] Bunch, J. R.; Demmel, J. W.; Van Loan, C. F., The strong stability of algorithms for solving symmetric linear systems, SIAM J. Matrix Anal. Appl., 10, 494-499 (1989) · Zbl 0687.65021
[7] Cadzow, J. A., A finite algorithm for the minimum \(l_∞\) solution to a system of consistent linear equations, SIAM J. Numer. Anal., 10, 607-617 (1973) · Zbl 0261.65033
[8] Cadzow, J. A., An efficient algorithmic procedure for obtaining a minimum \(l_∞\)-norm solution to a system of consistent linear equations, SIAM J. Numer. Anal., 11, 1151-1165 (1974) · Zbl 0292.65015
[9] Coleman, T. F.; Li, Y., A Global and Quadratically-Convergent Method for Linear \(L_∞\) Problems, (Technical Report 90-1121 (1990), Dept. of Computer Science, Cornell Univ: Dept. of Computer Science, Cornell Univ Ithaca, N.Y), SIAM J. Optimization, to appear · Zbl 0704.65023
[10] Deift, P.; Demmel, J. W.; Li, L. C.; Tomei, C., The Bidiago al Singular Value Decomposition and Hamiltonian Mechanics, (Lapack Working Note 11 (1989), Mathematics and Computer Science Div., Argonne National Lab: Mathematics and Computer Science Div., Argonne National Lab Argonne, Ill), SIAM J. Numer. Anal., to appear
[11] Demmel, J. W.; Veselić, K., Jacobi’s Method Is More Accurate than QR, (Lapack Working Note 15 (1989), Dept. of Computer Science, Univ. of Tennessee: Dept. of Computer Science, Univ. of Tennessee Knoxville), SIAM J. Matrix Anal. Appl., to appear · Zbl 0759.65011
[12] Dennis, J. E.; Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0579.65058
[13] Gastinel, N., Linear Numerical Analysis (1970), Academic: Academic London · Zbl 0318.65006
[14] Gohberg, I.; Koltracht, I., On the inversion of Cauchy matrices, (Kaashoek, M. A.; van Schuppen, J. H.; Ran, A. C.M., Signal Processing, Scattering and Operator Theory, and Numerical Methods. Signal Processing, Scattering and Operator Theory, and Numerical Methods, Proceedings of the International Symposium MTNS-89, Vol. III (1990)), 381-392 · Zbl 0719.65018
[15] Hager, W. W., Condition estimates, SIAM J. Sci. Statist. Comput., 5, 311-316 (1984) · Zbl 0542.65023
[16] Higham, D. J.; Higham, N. J., Backward Error and Condition of Structured Linear Systems, (Numerical Analysis Report 192 (1990), Univ. of Manchester), SIAM J. Matrix Anal. Appl., to appear · Zbl 0681.65029
[17] Higham, N. J., Fortran codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation (Algorithm 674), ACM Trans. Math. Software, 14, 381-396 (1988) · Zbl 0665.65043
[18] Higham, N. J., Experience with a matrix norm estimator, SIAM J. Sci. Statist. Comput., 11, 804-809 (1990) · Zbl 0752.65036
[19] Higham, N. J., How accurate is Gaussian elimination?, (Griffiths, D. F.; Watson, G. A., Numerical Analysis 1989, Proceedings of the 13th Dundee Conference. Numerical Analysis 1989, Proceedings of the 13th Dundee Conference, Pitman Research Notes in Mathematics 228 (1990), Longman Scientific and Technical), 137-154 · Zbl 0696.65020
[20] Horn, R. A.; Johnson, C. R., Topics in Matrix Analysis (1991), Cambridge U.P · Zbl 0729.15001
[21] Kovarik, Z. V., Compatibility of approximate solutions of inaccurate linear equations, Linear Algebra Appl., 15, 217-225 (1976) · Zbl 0412.65031
[22] 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
[23] Rigal, J. L.; Gaches, J., On the compatibility of a given solution with the data of a linear system, J. Assoc. Comput. Mach., 14, 543-548 (1967) · Zbl 0183.17704
[24] Rohn, J., New condition numbers for matrices and linear systems, Computing, 41, 167-169 (1989) · Zbl 0665.65042
[25] Schnabel, R. B., Quasi-Newton Methods Using Multiple Secant Updates, (Report CU-CS-247-83 (1983), Dept. of Computer Science, Univ. of Colorado: Dept. of Computer Science, Univ. of Colorado Boulder)
[26] Skeel, R. D., Scaling for numerical stability in Gaussian elimination, J. Assoc. Comput. Mach., 26, 494-526 (1979) · Zbl 0435.65035
[27] Stewart, G. W.; Sun, J.-G., Matrix Perturbation Theory (1990), Academic: Academic London
[28] Watson, G. A., Approximation Theory and Numerical Methods (1980), Wiley: Wiley Chichester · Zbl 0442.65005
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.