Summary
For a square matrixT∈ℂn,n, where (I−T) is possibly singular, we investigate the solution of the linear fixed point problemx=T x+c by applying semiiterative methods (SIM's) to the basic iterationx 0∈ℂn,x k ≔T c k−1+c(k≧1). Such problems arise if one splits the coefficient matrix of a linear systemA x=b of algebraic equations according toA=M−N (M nonsingular) which leads tox=M −1 N x+M −1 b≕T x+c. Even ifx=T x+c is consistent there are cases where the basic iteration fails to converge, namely ifT possesses eigenvalues λ≠1 with |λ|≧1, or if λ=1 is an eigenvalue ofT with nonlinear elementary divisors. In these cases — and also ifx=T x+c is incompatible — we derive necessary and sufficient conditions implying that a SIM tends to a vector\(\hat x\) which can be described in terms of the Drazin inverse of (I−T). We further give conditions under which\(\hat x\) is a solution or a least squares solution of (I−T)x=c.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ben Israel, A., Greville, T.N.E.: Generalized Inverses: Theory and Applications. New York London Sydney Toronto: Wiley 1974
Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. New York London: Academic Press 1979
Campbell, S.L., Meyer, C.D. Jr.: Generalized Inverses of Linear Transformations. London San Francisco Melbourne: Pitman 1979
Eiermann, M., Niethammer, W.: On the construction of semiiterative methods. SIAM J. Numer. Anal.20, 1153–1160 (1983)
Eiermann, M., Niethammer, W., Varga, R.S.: A study of semiiterative methods for nonsymmetric systems of linear equations. Numer. Math.47, 505–533 (1985)
Gantmacher, F.R.: Matrizenrechnung I. Berlin: Deutscher Verlag der Wissenschaften 1965
Hensel, K.: Über Potenzreihen von Matrizen. J. Reine Angew. Math.155, 107–110 (1926)
Kuznetsov, Y.A., Lebedev, V.I.: Chebyshev iteration methods for solving incompatible systems. Soviet Math. (Iz. VUZ)27, 72–83 (1983)
Marek, I., Zitny, K.: Matrix Analysis for Applied Sciences. Vol. 1 and 2. Teubner Texte zur Mathematik 60, 84. Leipzig: Teubner 1983, 1986
Meyer, C.D., Plemmons, R.J.: Convergent powers of a matrix with applications to iterative methods for singular linear systems. SIAM J. Numer. Anal.14, 699–705 (1977)
Molchanov, I.N., Yakovlev, M.F.: Iterative processes for solving a class of incompatible systems of linear algebraic equations. U.S.S.R. Comput. Math. Phys.15, 1–12 (1975)
Niethammer, W., de Pillis, J., Varga, R.S.: Convergence of block iterative methods applied to sparse least-squares problems. Linear Algebra Appl.58, 327–341 (1984)
Niethammer, W., Varga, R.S.: The analysis ofk-step iterative methods for linear systems from summability theory. Numer. Math.41, 177–206 (1983)
Oldenburger, R.: Infinite powers of matrices and characteristic roots. Duke Math. J.6, 357–361 (1940)
Rothblum, U.G.: Convergence properties of powers of matrices with applications to iterative methods for solving linear systems. In: A.V. Fiacco and K.O. Kortanek (ed.) Extremal Methods and Systems Analysis. (Internat. Symp., Univ. Texas, Austin, Tex., 1977), pp. 231–247. Lect. Notes Econom. Math. Syst. vol. 174. Berlin Heidelberg New York: Springer 1980
Tanabe, K.: Characterization of linear stationary iterative processes for solving a singular system of linear equations. Numer. Math.22, 349–359 (1974)
Varga, R.S.: A comparison of the successive overrelaxation method and semi-iterative methods using Chebyshev polynomials. J. Soc. Indust. Appl. Math.5, 39–46 (1957)
Varga, R.S.: Matrix Iterative Analysis. Englewood Cliffs, N.J.: Prentice-Hall 1962
Author information
Authors and Affiliations
Additional information
Research supported in part by the Alexander von Humboldt-Stiftung
Rights and permissions
About this article
Cite this article
Eiermann, M., Marek, I. & Niethammer, W. On the solution of singular linear systems of algebraic equations by semiiterative methods. Numer. Math. 53, 265–283 (1988). https://doi.org/10.1007/BF01404464
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01404464