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

Then

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 [5], 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 [10]. 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 [11] and references there.
A collection of algorithms for updating and downdating based on orthogonal
polynomials is presented by Elhay et al. [3]. 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 [9].

Tue Feb 14 12:51:53 CST 1995