On the application of orthogonal polynomials to the iterative solution of linear systems of equations with indefinite or non-Hermitian matrices

AbstractLet Ax=b be a large linear system of equations, and let the eigenvalues of the matrix A lie in one or several known simply connected regions Sj,j=1(1)l, in the complex plane. We consider the iterative solution of such linear systems by methods that make use of polynomials {pn(z)}∞n=0 orthogonal on the boundary of ∪lj=1Sj. We show that for boundary curves such that the pn(z) satisfy a three-term recurrence relation, iterative methods based on this recurrence relation yield an optimal asymptotic rate of convergence. For boundary curves for which the pn(z) do not satisfy a three-term recurrence relation, we show that n-cyclic Richardson iteration methods with relaxation parameters chosen as the reciprocal roots of pn(z) give nearly asymptotic optimal convergence for n sufficiently large. Our analysis suggests that in many cases the iterative methods should be based on residual polynomials pn(z)pn(0), instead of on the corresponding kernel polynomials qz=∑nk=0pk(0)pk(z)∑nk=0|pk(0)|2. Numerical examples are presented