  Often, polynomials or rational functions, orthogonal for a particular inner
product are desired. In practical numerical algorithms these polynomials are
not constructed, but instead the associated recurrence relations are computed.
Moreover, also typically the inner product is changed to a discrete inner
product, which is the finite sum of weighted functions evaluated in specific
nodes. For particular applications it is beneficial to have an efficient
procedure to update the recurrence relations when adding or removing nodes from
the inner product. The construction of the recurrence relations is equivalent
to computing a structured matrix (polynomial) or pencil (rational) having
prescribed spectral properties. Hence the solution of this problem is often
referred to as solving an Inverse Eigenvalue Problem. In Van Buggenhout et al.
(2022) we proposed updating techniques to add nodes to the inner product while
efficiently updating the recurrences. To complete this study we present in this
article manners to efficiently downdate the recurrences when removing nodes
from the inner product. The link between removing nodes and the QR algorithm to
deflate eigenvalues is exploited to develop efficient algorithms. We will base
ourselves on the perfect shift strategy and develop algorithms, both for the
polynomial case and the rational function setting. Numerical experiments
validate our approach.
