On Hybrid Semi-Iterative Methods
Authors:
- M. EiermannMEM. Eiermann
- X. LiXLX. Li
- R. S. VargaRVR. S. Varga
- 1 February 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Numerical Analysis
- Vol. 26 (1) , 152-168
Abstract
Given a large sparse system of linear algebraic equations in fixed point form ${\bf x} = T{\bf x} + {\bf c}$, one way to solve this system is to apply a semi-iterative method (SIM) to the basic iteration method ${\bf x}_m = T{\bf x}_{m - 1} + {\bf c}$. It is known that if the spectrum, $\sigma (T)$, of T is contained in some compact subset $\Omega $ of the complex plane (where $1 \notin \Omega $) then there are asymptotically optimal SIMs, associated with the basic iteration and $\Omega $ whose asymptotic rates of convergence are best possible for the class of all matrices T with $\sigma (T) \subseteq \Omega $, However, for a given compact set $\Omega $, an asymptotically optimal SIM for $\Omega $ is usually not well suited for efficient numerical computation unless this SIM can be generated from a k-step recurrence formula. In this paper, hybrid semi-iterative methods are investigated which consist of two independent steps: First, ${\bf x} = T{\bf x} + {\bf c}$ is transformed into a consistent linear system, namely ${\bf x} = \tilde T{\bf x} + \tilde {\bf c}$, where $\tilde T: = t_n (T)$ and where $t_n (z)$ is a complex polynomial in z, and then asymptotically optimal SIMs are considered with respect to ${\bf x} = \tilde T{\bf x} + \tilde {\bf c}$ and $\tilde \Omega : = t_n (\Omega )$. In Theorem 6, a geometrical characterization is given of those $t_n (z)$ for which the asymptotically optimal hybrid SIMs for $\tilde \Omega $ give the same effective asymptotic convergence rate as do asymptotically optimal SIMs applied to the original matrix problem ${\bf x} = T{\bf x} + {\bf c}$ and $\Omega $. Finally, three examples are given (one arising from neutron-transport theory) to show how specific hybrid SIMs can give asymptotically optimal rates of convergence, and also, that these associated hybrid SIMs, generated by k-step recurrence formulas, are numerically effective.
Keywords
This publication has 14 references indexed in Scilit:
- On the application of orthogonal polynomials to the iterative solution of linear systems of equations with indefinite or non-Hermitian matricesLinear Algebra and its Applications, 1987
- A study of semiiterative methods for nonsymmetric systems of linear equationsNumerische Mathematik, 1985
- On the Construction of Semi-Iterative MethodsSIAM Journal on Numerical Analysis, 1983
- The analysis ofk-step iterative methods for linear systems from summability theoryNumerische Mathematik, 1983
- Polynomial Preconditioners for Conjugate Gradient CalculationsSIAM Journal on Numerical Analysis, 1983
- Extremal Polynomials with Application to Richardson Iteration for Indefinite Linear SystemsSIAM Journal on Scientific and Statistical Computing, 1982
- Approximating the inverse of a matrix for use in iterative algorithms on vector processorsComputing, 1979
- The Tchebychev iteration for nonsymmetric linear systemsNumerische Mathematik, 1977
- An Iterative Method for Solving the Neutron Transport Equation inx-yGeometrySIAM Journal on Applied Mathematics, 1969
- Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methodsNumerische Mathematik, 1961