Iterative Solution of Indefinite Symmetric Linear Systems by Methods Using Orthogonal Polynomials over Two Disjoint Intervals

Abstract

In the classical Chebyshev algorithm for solving symmetric positive definite linear systems $Ax = b$, the approximate solution is of the form $x_k = x_0 + s_k (A)r_0 $, where $r_0 = b - Ax_0 $ is the initial residual and $s_k $ is a polynomial of degree $k - 1$ which minimizes $||1 - \lambda s_k (\lambda )||_\infty $, where $|| \cdot ||_\infty $ is the uniform norm on some interval S containing the spectrum of A but not the origin. If A is not positive definite, the set S can be taken to be the union of two disjoint intervals $[a,b]$ and $[c,d]$ with $b < 0 < c$ and a generalization of the Chebyshev algorithm based on the minimax polynomial has been considered by several authors. In this paper we propose a new technique based upon the least squares polynomial in the set S, i.e. the polynomial $t_k $ which minimizes $||1 - \lambda t_k (\lambda )||_w $, where $|| \cdot ||_w $ is an $L_2 $ norm with respect to a weight function $w(\lambda )$ defined on S. With a suitable weight function $w(\lambda )$, the polynomials $s_k $ can be computed without numerical integration. The convergence of the algorithm is established.