The weak and strong stability of algorithms in numerical linear algebra. (English) Zbl 0652.65032

The stability of algorithm in numeical linear algebra is discussed. The concept of stability is extended to notions of weak stability and strong stability. Justifications are given for these extensions, and the implications of error analysis in terms of these definitions are discussed. The concept of weak stability helps to clarify some of the controversy which has arisen concerning the stability of algorithms for Toeplitz systems.


65F35 Numerical computation of matrix norms, conditioning, scaling
15A12 Conditioning of matrices
65G50 Roundoff error


Full Text: DOI


[1] Bitmead, R. R.; Anderson, B. D.O., Asymptotically fast solution of Toeplitz and related systems of equations, Linear Algebra Appl., 34, 103-116 (1980) · Zbl 0458.65018
[2] Brent, R. P.; Gustavson, F. G.; Yun, D. Y.Y., Fast solution of Toeplitz systems of equations and computation of Padé approximants, J. Algorithms, 1, 259-295 (1980) · Zbl 0475.65018
[3] Bunch, J. R., Analysis of the diagonal pivoting method, SIAM J. Numer. Anal., 8, 656-680 (1971)
[5] Bunch, J. R.; Parlett, B. N., Direct methods for solving symmetric indefinite systems of linear equations, SIAM J. Numer. Anal., 8, 639-655 (1971) · Zbl 0199.49802
[6] Cybenko, G., The numerical stability of the Levinson-Durbin algorithm for Toeplitz systems of equations, SIAM J. Sci. Statist. Comput., 1, 303-319 (1980) · Zbl 0474.65026
[7] de Hoog, F., A new algorithm for solving Toeplitz systems of equations, Linear Algebra Appl., 88, 123-138 (1987) · Zbl 0621.65014
[8] Dongarra, J. J.; Bunch, J. R.; Moler, C. B.; Stewart, G. W., LINPACK User’s Guide (1979), SIAM Publ: SIAM Publ Philadelphia
[9] Durbin, J., The fitting of time-series models, Rev. Internat. Statist. Inst., 28, 229-249 (1959)
[10] Forsythe, G. E.; Moler, C. B., Computer Solution of Linear Algebraic Systems (1967), Prentice-Hall · Zbl 0154.40401
[11] Gohberg, I.; Sementsul, A., On the inversion of finite Toeplitz matrices and their continuous analogs, Mat. Issled., 2, 201-233 (1972), (in Russian)
[12] Goldstine, H. H.; von Neumann, J., Numerical inverting of matrices of high order II, Proc. Amer. Math. Soc., 2, 188-202 (1951) · Zbl 0043.12301
[13] Golub, G. H.; Van Loan, C. F., Matrix Computations (1983), Johns Hopkins U.P · Zbl 0559.65011
[14] Levinson, N., The Wiener rms (root-mean-square) error criterion in filter design and prediction, J. Math. Phys., 25, 261-278 (1947)
[15] Stewart, G. W., Introduction to Matrix Computations (1973), Academic · Zbl 0302.65021
[16] Trench, W., An algorithm for the inversion of finite Toeplitz matrices, SIAM J. Appl. Math., 12, 515-522 (1964) · Zbl 0131.36002
[17] Wilkinson, J. H., Error analysis of direct methods of matrix inversion, J. Assoc. Comput. Mach., 8, 281-330 (1961) · Zbl 0109.09005
[18] Wilkinson, J. H., Rounding Errors in Algebraic Processes (1963), Prentice-Hall · Zbl 0868.65027
[19] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Oxford U.P: Oxford U.P London · Zbl 0258.65037
[20] Zohar, S., The solution of a Toeplitz set of linear equations, J. Assoc. Comput. Mach., 21, 272-276 (1974) · Zbl 0276.65014
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.