General k -Part Stationary Iterative Solutions to Linear Systems
Bradley N. Parsons · SIAM Journal on Numerical Analysis · 1987
The solution of $(I - B)x = b$ is sought, where B is a $n \times n$ matrix, I is the identity matrix, b is an n vector of known constants and x is the unknown vector. When n is large, a direct solution of the equation is not feasible; one instead seeks an approximation to x. This paper discusses stationary k-part methods for finding sequences of approximations to x. After presenting a generalization of the companion matrix criteria for the convergence of k-part stationary operator coefficient algorithms, two theorems are proved which relate the spectrum of a particular form of the companion matrix to the roots of a meromorphic function evaluated at the eigenvalues of B. A corollary which results from these theorems gives the convergence criteria for the most general k-part stationary constant coefficient algorithm in terms of the image of the unit disc under a rational function which is easily related to the stationary algorithm. It is then shown that the asymptotic rate of convergence for this most general k-part algorithm is the log of the radius of the largest disc centered at the origin which has no pre-image points of the spectrum of B under the associated rational function. An example of this algorithm is given where the spectral radius of B is greater than one.