×

Perturbation and error analyses for block downdating of a Cholesky decomposition. (English) Zbl 0848.65015

From the authors’ abstract: A new perturbation result is presented for the problem of block downdating a Cholesky decomposition \(X^T X = R^T R\). Then, a condition number for block downdating is proposed and compared to other downdating condition numbers presented in literature recently. This new condition number is shown to give a tighter bound in many cases. Using the perturbation theory, an error analysis is presented for the block downdating algorithms based on the LINPACK downdating algorithm and stabilized hyperbolic transformations.
An error analysis is also given for block downdating using corrected seminormal equations (CSNE), and it is shown that for ill-conditioned downdates this method gives more accurate results than the algorithms based on the LINPACK downdating algorithm or hyperbolic transformations.
Reviewer: Th.Sonar (Hamburg)

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F35 Numerical computation of matrix norms, conditioning, scaling

Software:

LINPACK; mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. T. Alexander, C.-T. Pan, and R. J. Plemmons,Analysis of a recursive least squares hyperbolic rotation algorithm for signal processing, Linear Algebra Appl., 98 (1988), pp. 3–40. · Zbl 0639.94004 · doi:10.1016/0024-3795(88)90158-9
[2] Å. Björck,Stability analysis of the method of semi-normal equations for least squares problems, Linear Algebra Appl., 88/89 (1987), pp. 31–48. · Zbl 0616.65043 · doi:10.1016/0024-3795(87)90101-7
[3] Å. Björck,Error analysis of least squares algorithms, in Numerical Linear Algebra, Digital Signal Processing and Parallel Algorithms, G. H. Golub and P. V. Dooren, eds., NATO ASI Series, Berlin, 1991, Springer-Verlag, pp. 41–73. · Zbl 0757.65047
[4] Å. Björck, H. Park, and L. Elden,Accurate downdating of least squares solutions, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 549–568. · Zbl 0811.65034 · doi:10.1137/S089547989222895X
[5] A. W. Bojanczyk, R. P. Brent, P. van Dooren, and F. R. de Hoog,A note on downdating the Cholesky factorization, SIAM J. Sci. Stat. Comput., 8 (1987), pp. 210–221. · Zbl 0617.65013 · doi:10.1137/0908031
[6] A. W. Bojanczyk and A. O. Steinhardt,Stabilized hyperbolic Householder transformations, IEEE Trans. Acoust., Speech, Signal Processing, ASSP-37 (1989), pp. 1286–1288. · Zbl 0697.93064 · doi:10.1109/29.31277
[7] J. Chambers,Regression updating, J. Amer. Stat. Assoc., 66 (1971), pp. 744–748. · doi:10.2307/2284221
[8] L. Eldén and H. Park,Block downdating of least squares solutions, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 1018–1034. · Zbl 0808.65041 · doi:10.1137/S089547989223691X
[9] L. Eldén and H. Park,Perturbation analysis for block downdating of a Cholesky decomposition, Numer. Math., 68 (1994), pp. 457–467. · Zbl 0808.65042 · doi:10.1007/s002110050072
[10] P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders,Methods for modifying matrix factorizations, Math. Comp., 28 (1974), pp. 505–535. · Zbl 0289.65021 · doi:10.1090/S0025-5718-1974-0343558-6
[11] G. H. Golub and G. P. Styan,Numerical computations for univariate linear models, J. Stat. Comp. Simul., 2 (1973), pp. 253–272. · Zbl 0283.62062 · doi:10.1080/00949657308810051
[12] G. H. Golub and C. F. Van Loan,Matrix Computations.2nd ed., Johns Hopkins Press, Baltimore, MD, 1989.
[13] N. Higham,The accuracy of solutions to triangular systems, SIAM J. Numer. Anal., 26 (1989), pp. 1252–1265. · Zbl 0683.65029 · doi:10.1137/0726070
[14] N. Higham,Accuracy and Stability of Numerical Algorithms, SIAM, Philadelphia, 1996. · Zbl 0847.65010
[15] C. L. Lawson and R. J. Hanson,Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, NJ, 1974. · Zbl 0860.65028
[16] S. J. Olszanskyj, J. L. Lebak, and A. W. Bojanczyk,Rank-k modification methods for recursive least squares problems, Numerical Algorithms, 7 (1994), pp. 325–354. · Zbl 0813.65079 · doi:10.1007/BF02140689
[17] C. C. Paige,Error analysis of some techniques for updating orthogonal decompositions, Math. Comp., 34 (1980), pp. 465–471. · Zbl 0422.65027 · doi:10.1090/S0025-5718-1980-0559196-9
[18] C.-T. Pan,A perturbation analysis of the problem of downdating a Cholesky factorization, Linear Algebra Appl., 183 (1993), pp. 103–116. · Zbl 0771.65015 · doi:10.1016/0024-3795(93)90426-O
[19] C.-T. Pan and R. J. Plemmons,Least squares modifications with inverse factorizations: parallel implications, J. Comp. Appl. Math., 27 (1989), pp. 109–127. · Zbl 0677.65037 · doi:10.1016/0377-0427(89)90363-4
[20] H. Park and L. Eldén,Downdating the rank-revealing URV decomposition, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 138–155. · Zbl 0821.65025 · doi:10.1137/S0895479892241913
[21] C. Rader and A. Steinhardt,Hyperbolic Householder transformations, IEEE Trans. Acoust., Speech, Signal Processing, ASSP-34 (1986), pp. 1589–1602. · Zbl 0629.93063 · doi:10.1109/TASSP.1986.1164998
[22] M. A. Saunders,Large-scale linear programming using the Cholesky factorization, Technical Report CS252, Computer Science Department, Stanford University, 1972.
[23] G. Stewart,On the stability of sequential updates and downdates, Report TR-3238, Department of Computer Science, University of Maryland, College Park, MD 20742, March 1994.
[24] G. W. Stewart,The effects of rounding error on an algorithm for downdating a Cholesky factorization, Journal of the Institute for Mathematics and Applications, 23 (1979), pp. 203–213. · Zbl 0405.65019 · doi:10.1093/imamat/23.2.203
[25] J. Sun,Perturbation analysis of the Cholesky downdating and QR updating problems, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 760–775. · Zbl 0828.65027 · doi:10.1137/S0895479893249939
[26] J.-G. Sun,Perturbation bounds for the Cholesky and QR factorizations, BIT, 31 (1991), pp. 341–352. · Zbl 0728.65032 · doi:10.1007/BF01931293
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.