On the orthogonality of residual polynomials of minimax polynomial preconditioning (Q1326379)

To solve the linear system \(Ax= b\) iteratively, one may replace it by a preconditioned system \(p(A)Ax= p(A)b\), where \(p\) is a polynomial. Setting \(r(\lambda)= 1- \lambda p(\lambda)\), an optimal choice for the preconditioner corresponds to finding the residual polynomial \(r\) such that \(\max| r(\lambda)|\) is minimal, where the maximum should be taken for \(\lambda\in \sigma(A)\), the spectrum of \(A\). Since finding \(\sigma(A)\) is very hard, \(\sigma(A)\) is replaced by \(E\), a continuous set containing it. Thus one is lead to the problem of finding a polynomial \(r_ m\) of degree \(m\) at most such that \(\max_ E | r_ m(\lambda)|= \min\) with \(r_ m(0)= 1\). When \(A\) is positive definite, \(E\) is a positive interval. In the indefinite case, \(E\) is the union of a positive and a negative interval. Such polynomials \(r_ m\) are called de Boor-Rice polynomials. An other, similar, preconditioning problem leads to a similar optimization problem, but now with the side conditions \(r_ m(0)= 1\) and \(r_ m'(0)= 0\). The polynomial solutions are called Grcar polynomials. It is shown in this paper that such minimax polynomials equioscillate over 4 (not necessarily disjoint) intervals and that they satisfy a second order linear differential equation, which is explicitly given. Such properties lead to the main result of this paper, which shows that \(r_ m\) is a polynomial of degree \(k_ m\in \{m,m-1\}\) which appears in a sequence of polynomials orthogonal over several intervals. It is important to note that the latter (and thus also \(r_ m\)) can be generated by a 3-term recurrence relation. The weight function for which orthogonality holds in explicitly given, but is difficult to compute because it depends through the positions of the extremes of \(r_ m\) on \(m\) as well as on the set \(E\). It resembles the integrand of an elliptic integral. The Grcar polynomials for a positive definite \(A\) (\(E\) is one interval) are studied in more detail. This leads to an a priori estimate of the number of iterations for the preconditioned conjugate gradient method.