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].
