On the orthogonality of residual polynomials of minimax polynomial preconditioning
type: Item
instance of: scholarly article
title: On the orthogonality of residual polynomials of minimax polynomial preconditioning
zbMATH Open document ID: 0802.65043
author: Hong Jiang
published in: Numerische Mathematik
publication date: 1994-12-11T00:00:00Z
review text: 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 …
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65F35
Mathematics Subject Classification ID: 42C05
Mathematics Subject Classification ID: 33E05
zbMATH DE Number: 569104
zbMATH Keywords: orthogonal polynomials
zbMATH Keywords: iterative methods
zbMATH Keywords: orthogonality over several intervals
zbMATH Keywords: Chebyshev approximation
zbMATH Keywords: preconditioner
zbMATH Keywords: de Boor-Rice polynomials
zbMATH Keywords: Grcar polynomials
zbMATH Keywords: minimax polynomials
zbMATH Keywords: recurrence relation
zbMATH Keywords: elliptic integral
zbMATH Keywords: preconditioned conjugate gradient method
MaRDI profile type: Publication
full work available at URL: s002110050032
OpenAlex ID: W1992139425
DOI: 10.1007/S002110050032
description: scientific article; zbMATH DE number 569104