Let be a set of distinct nodes on the unit circle and let be a set of positive weights. Introduce for complex-valued functions g and h defined at the nodes the discrete inner product on the unit circle
where the bar denotes complex conjugation. Polynomials that are orthogonal with respect to an inner product on the unit circle are known as Szego polynomials. Let denote the family of orthonormal Szego polynomials with respect to the inner product (1.1), where is of degree j and has a positive leading coefficient. The polynomials satisfy the Szego recurrence relations
where the recurrence coefficients and are determined by
See, for example, Grenander and Szego [7, Chapter 2,]. It can be shown by induction that the auxiliary polynomials in (1.2) satisfy
where denotes the polynomial obtained by conjugating the coefficients of in the power basis. Since the measure on the unit circle that defines (1.1) has precisely m points of increase, we have for and . The coefficients are known as Schur parameters, and we refer to the as the associated complementary parameters. Although the complementary parameters are mathematically redundant, we retain them during computations in order to avoid numerical instability. Note from (1.3) that is the total weight of the measure that defines (1.1), and that is the leading coefficient of for .
For later reference we also define the polynomial
In particular, for .
Example 1.1. Let and for , where . Then , and for , and . Thus, for , and .
Introduce the discrete norm
and let denote the set of all polynomials of degree at most n-1. Let f be a given complex-valued function defined at the nodes , and consider the problem of computing the polynomial , for some , that satisfies
The solution of the minimization problem (1.6) can be expressed conveniently in terms of the Szego polynomials as follows. Introduce the vector
and the matrix ,
where . Note that the matrix Q has orthonormal columns, i.e., , where . Let the vector be defined by
Then the polynomial can be written as
where the Fourier coefficients are independent of n.
It is the purpose of this paper to present an algorithm for downdating the recurrence coefficients and , as well as the Fourier coefficients , when an abscissa-weight pair is removed from the inner product (1.1). Our algorithm is based on the observation that the columns of the matrix Q are eigenvectors of a unitary Hessenberg matrix defined by the recurrence relations (1.2)--(1.3). This makes it possible to downdate the coefficients , and by applying the QR algorithm for unitary Hessenberg matrices, presented in , with the node to be removed as shift. Details are described in Section 2.
We remark that the problem of updating the coefficients , and when an abscissa-weight pair is added to the inner product (1.1) is discussed in . The updating problem can be solved by using an inverse QR algorithm for unitary Hessenberg matrices; see [10,1].
Assume that we wish to determine the polynomial , given by (1.9)--(1.10) with when the set of m nodes in the inner product (1.1) is a subset of the set of N equidistant nodes , with small. The weights are all assumed to be unity. Then it may be attractive to compute by first computing the polynomial interpolant on the set of N equidistant nodes by using the fast Fourier transform (FFT) algorithm, and determining from by applying our downdating scheme. The Fourier coefficients of the polynomial approximant are then equal to the first n Fourier coefficients of . This approach can similarly be applied to trigonometric polynomials. Details are described in Section 3. Computed examples are presented in Section 4.
Updating and downdating of polynomials approximants when all the nodes are real has received considerable attention in the literature; see Scott and Scott  and references there. A collection of algorithms for updating and downdating based on orthogonal polynomials is presented by Elhay et al. . Algorithms for updating are also considered in [6,8]. Analogous algorithms for the case when the inner product is allowed to be indefinite are considered in .