Summary
Ann×n complex matrixB is calledparacontracting if ‖B‖2≦1 and 0≠x∈[N(I-B)]⊥⇒‖Bx‖2<‖x‖2. We show that a productB=B k B k−1 ...B 1 ofk paracontracting matrices is semiconvergent and give upper bounds on the subdominant eigenvalue ofB in terms of the subdominant singular values of theB i 's and in terms of the angles between certain subspaces. Our results here extend earlier results due to Halperin and due to Smith, Solomon and Wagner. We also determine necessary and sufficient conditions forn numbers in the interval [0, 1] to form the spectrum of a product of two orthogonal projections and hence characterize the subdominant eigenvalue of such a product. In the final part of the paper we apply the upper bounds mentioned earlier to provide an estimate on the subdominant eigenvalue of the SOR iteration matrix ℒω associated with ann×n hermitian positive semidefinite matrixA none of whose diagonal entries vanish.
Similar content being viewed by others
References
Ballantine, C.S.: Products of positive definite matrices III. Pac. J. Math.24, 7–17 (1969)
Berman, A., Plemmons, R.J.: Non-negative Matrices in the Mathematical Sciences. New York: Academic Press 1979
Bjork, A., Golub, G.H.: Numerical methods for computing angles between subspaces. Math. Comput.27, 579–594 (1973)
Deutsch, E., Wielandt, H.: Nested bounds for the Perron root of a nonnegative matrix. Linear Algebra Appl.52/53, 235–251 (1984)
Deutsch, F.: Rate of convergence of the method of alternating projections. In: Parametric Optimization and Approximations (Brosowsfi, Deutsch, eds.) Birkhäuser Basel: ISNM72, 96–107 (1985)
Franchetti, C., Light, W.: On the von Neumann alternating algorithm in Hilbert space. Cent Approx Theor. Rpt. No. 28 (1982)
Golub, G.H., Van Loan, C.: Matrix Computation. The John Hopkins University Press, Baltimore, Maryland 1983
Halperin, I.: The product of projection operators. Acta Sci. Math. (Szeged)23, 96–99 (1962)
Keller, H.B.: On the solution of singular and semidefinite linear systems by iteration. SIAM J. Numer. Anal.2, 281–290 (1965)
Mott, J.L., Schneider, H.: Matrix algebras and groups relatively bounded in norm. Arch. Math.10, 1–6 (1959)
von Neumann, J.: Functional Operator-Vol II. The Geometry of Orthogonal Spaces. Ann. Math. Studies. No. 22. Princeton, New Jersey: University Press 1959
Neumann, M., Plemmons, R.J.: Convergent nonnegative matrices and iterative methods for consistent linear systems. Numer. Math.31, 265–279 (1978)
Nicolaides, R.A.: On a geometrical aspect of SOR and the theory of consistent ordering for positive definite matrices. Numer. Math.23, 99–104 (1974)
Oldenburger, R.: Infinite powers of matrices and characteristic roots. Duke Math. J.6, 357–361 (1940)
Rothblum, U.G., Tan, C.P.: Upper bounds on the maximum modulus of subdominant eigenvalues of nonnegative matrices. SIAM J. Algebraic Discrete Methods. Linear Algebra Appl66, 45–86 (1985)
Seneta, E.: Non-negative Matrices and Markov Chains. Heidelberg, Berlin, New York: Springer 1981
Smith, K.T., Solomon, D.C., Wagner, S.L.: Practical and Mathematical aspects of the problem of reconstructing objects from radiographs. Bull. Am. Math. Soc.83, 1227–1270 (1977)
Taussky, O.: Positive-definite matrices and their role in the study of the characteristic roots of general matrices. Adv. Math.2, 175–186 (1986)
Varga, R.S.: Matrix Iterative Analysis. Englewood Cliffs, New Jersey: Prentice Hall 1962
Wigner, U.P.: On weakly positive matrices. Can. J. Math.15, 313–317 (1963)
Young, D.M.: Iterative Solution of Large Linear Systems. New York: Academic Press 1971
Author information
Authors and Affiliations
Additional information
The work of this author was supported in part by NSF Research Grant No. MCS-8400879
Rights and permissions
About this article
Cite this article
Nelson, S., Neumann, M. Generalizations of the projection method with applications to SOR theory for hermitian positive semidefinite linear systems. Numer. Math. 51, 123–141 (1987). https://doi.org/10.1007/BF01396746
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01396746