Summary
Given a nonsingular linear systemA x=b, a splittingA=M−N leads to the one-step iteration (1)x m =T X m−1 +c withT:=M −1N andc:=M −1 b. We investigate semiiterative methods (SIM's) with respect to (1), under the assumption that the eigenvalues ofT are contained in some compact set Ω of ℂ, with 1≠Ω. There exist SIM's which are optimal with respect to Ω, but, except for some special sets Ω, such optimal methods are not explicitly known in general. Using results about “maximal convergence” of polynomials and “uniformly distributed” nodes from approximation and function theory, we describe here SIM's which are asymptotically optimal with respect to Ω. It is shown that Euler methods, extensively studied by Niethammer-Varga [NV], are special SIM's. Various algorithms for SIM's are also derived here. A 1-1 correspondence between Euler methods and SIM's, generated by generalized Faber polynomials, is further established here. This correspondence gives that asymptotically optimal Euler methods are quite near the optimal SIM's.
Similar content being viewed by others
References
[E] Eiermann, M.: Numerische analytische Fortsetzung durch Interpolationsverfahren. Dissertation, U. Karlsruhe 1982
[EN] Eiermann, M., Niethammer, W.: On the construction of semiiterative methods. SIAM J. Numer. Anal.30, 1153–1160 (1983)
[F1] Faber, G.: Über polynomische Entwicklungen. Math. Ann.57, 398–408 (1903)
[F2] Faber, G.: Über Tschebyscheffsche Polynome. J. Reine Angew. Math.150, 79–106 (1920)
[Ga] Gaier, D.: Vorlesungen über Approximation im Komplexen. Basel-Boston-Stuttgart: Birkhäuser 1980
[G] Gantmacher, F.R.: Matrizenrechnung, I Berlin: Deutscher Verlag der Wissenschaften 1965
[H] Householder, A.S.: The Theory of Matrices in Numerical Analysis. New York-Toronto-London: Blaisdell 1964
[M] Manteuffel, T.A.: The Tschebychev iteration for nonsymmetric linear systems. Numer. Math.28, 307–327 (1977)
[NV] Niethammer, W., Varga, R.S.: The analysis ofk-step iterative methods for linear systems from summability theory. Numer. Math.41, 177–206 (1983)
[OS] Opfer, G., Schober, G.: Richardson's iteration for nonsymmetric matrices. Linear Algebra Appl.58, 343–367 (1984)
[OR] Ortega, J.M., Reinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. New York-London: Academic Press 1970
[SL] Smirnov, V.L., Lebedev, N.A.: Functions of a Complex Variable: Constructive Theory. Cambridge, MA: MIT Press 1968
[S1] Suetin, P.K.: Fundamental properties of Faber polynomials. Russ. Math. Surv.19, 121–149 (1964)
[S2] Suetin, P.K.: Series in Faber polynomials and several generalizations. J. Sov. Math.5, 502–551 (1976)
[T] Todd, J.: Special polynomials in numerical analysis. In: On Numerical Approximation (R.E. Langer, ed.), pp. 423–446. Madison: University of Wisconsin Press 1959
[V1] Varga, R.S.: A comparison of the successive overrelaxation method and semi-iterative methods using Chebyschev polynomials. J. Soc. Indust. Appl. Math.5, 39–46 (1957)
[V2] Varga, R.S.: Matrix Iterative Analysis. Englewood Cliffs, NJ: Prentice Hall 1962
[W] Walsh, J.L.: Interpolation and Approximation by Rational Functions in the Complex Domain. Providence, RI: AMS Colloquium Publications 1956
[Wi] Wimp, J.: Sequence Transformations and their Applications. New York-London: Academic Press 1981
[ZB] Zeller, K., Beekmann, W.: Theorie der Limitierungsverfahren. Berlin-Heidelberg-New York: Springer 1978
Author information
Authors and Affiliations
Additional information
Dedicated to Professor Karl Zeller (Universität Tübingen) on the occasion of his sixtieth birthday (December 28, 1984)
Rights and permissions
About this article
Cite this article
Eiermann, M., Niethammer, W. & Varga, R.S. A study of semiiterative methods for nonsymmetric systems of linear equations. Numer. Math. 47, 505–533 (1985). https://doi.org/10.1007/BF01389454
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01389454