Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

In about two dozen papers, Walter Gautschi developed the so-called constructive theory of orthogonal polynomials on ℝ, including effective algorithms for numerically generating orthogonal polynomials, a detailed stability analysis of such algorithms as well as several new applications of orthogonal polynomials. Furthermore, he provided software necessary for implementing these algorithms (see Section 23, Vol. 3) and applications.

Let P be the space of real polynomials and P n  ⊂ P the space of polynomials of degree at most n. Suppose dμ(t) is a positive measure on ℝ with finite or unbounded support, for which all moments μ k  = ∫ ℝ t kdμ(t) exist and are finite, andμ 0 > 0. Then the inner product

$$\displaystyle{(p,q) =\int _{\mathbb{R}}p(t)q(t)\mathrm{d}\mu (t)}$$

is well defined for any polynomials p, q ∈ P and gives rise to a unique system of monic orthogonal polynomials π k (  ⋅ ) = π k (  ⋅ ; dμ); that is,

$$\displaystyle{\pi _{k}(t) \equiv \pi _{k}(t;\mathrm{d}\mu ) = {t}^{k} + \mbox{ terms of lower degree},\quad k = 0,1,\ldots\,,}$$

and

$$\displaystyle{(\pi _{k},\pi _{n}) = \vert \vert \pi _{n}\vert {\vert }^{2}\delta _{ kn} = \left\{\begin{array}{cc} 0, & n\neq k, \\ \vert \vert \pi _{n}\vert {\vert }^{2},&n = k. \end{array} \right.}$$

1 Three-term recurrence relation

Because of the property (tp, q) = (p, tq), these polynomials satisfy a three–term recurrence relation

$$\displaystyle{ \pi _{k+1}(t) = (t -\alpha _{k})\pi _{k}(t) -\beta _{k}\pi _{k-1}(t),\quad k = 0,1,2\ldots\,, }$$
(11.1)

with π 0(t) = 1 and π  − 1(t) = 0, where (α k ) = (α k (dμ)) and (β k ) = (β k (dμ)) are sequences of recursion coefficients which depend on the measure dμ. The coefficient β 0 may be arbitrary, but is conveniently defined by β 0 = μ 0 = ∫ ℝdμ(t). In the case of a discrete measure dμ = dμ N , i.e., when μ(t) has only N points of increase, the system of polynomials {π k } consists of only N polynomials π 0, π 1, …, π N − 1 (discrete orthogonal polynomials).

There are many reasons why the coefficients α k and β k in the three-term recurrence relation (11.1) are fundamental quantities in the constructive theory of orthogonal polynomials (for details see [GA81]). For example, α k and β k provide a compact way of representing and easily calculating orthogonal polynomials, their derivatives, and their linear combinations, requiring only a linear array of parameters.

The same recursion coefficients α k and β k appear also in the Jacobi continued fraction associated with the measure dμ,

$$\displaystyle{F(z) =\int _{\mathbb{R}} \frac{\mbox{ d}\mu (t)} {z - t} \sim\frac{\beta _{0}} {z -\alpha _{0}-}\, \frac{\beta _{1}} {z -\alpha _{1}-}\,\cdots \,,}$$

which is the Stieltjes transform of the measure dμ (for details see [GAB3, p. 15], [17, p. 114]). The nth convergent of this continued fraction is easly seen to be

$$\displaystyle{ \frac{\beta _{0}} {z -\alpha _{0}-}\, \frac{\beta _{1}} {z -\alpha _{1}-}\,\cdots\frac{\beta _{n-1}} {z -\alpha _{n-1}} = \frac{\sigma _{n}(z)} {\pi _{n}(z)}\,, }$$
(11.2)

where σ n are the so-called associated polynomials defined by

$$\displaystyle{\sigma _{k}(z) =\int _{\mathbb{R}} \frac{\pi _{k}(z) -\pi _{k}(t)} {z - t} \,\mbox{ d}\mu (t),\quad k \geq0.}$$

They satisfy the same fundamental relation (11.1), i.e.,

$$\displaystyle{\sigma _{k+1}(z) = (z -\alpha _{k})\sigma _{k}(z) -\beta _{k}\sigma _{k-1}(z),\quad k \geq0,}$$

with starting values σ 0(z) = 0, σ  − 1(z) =  − 1.

The functions of the second kind,

$$\displaystyle{ \varrho _{k}(z) =\int _{\mathbb{R}} \frac{\pi _{k}(t)} {z - t}\,\mbox{ d}\mu (t),\quad k \geq0, }$$
(11.3)

where z is outside the spectrum of dμ (the Stieltjes transforms of π k ), also satisfy the same three-term recurrence relation (11.1) and, under some mild conditions, represent its minimal solution (cf. Section 21, Vol. 3) normalized by ϱ  − 1(z) = 1. This has been observed by Gautschi in [GA75] and is a remarkable result, very important for computation in the areas of orthogonal polynomials, special functions, and numerical analysis. Gautschi [GA75] showed that this minimal solution can be computed accurately by means of his continued fraction algorithm presented in [GA29]. Namely, if one wishes to compute ϱ k (z) for k = 0, 1, …, n, then for some ν > n one generates quantities r k (ν) and ϱ k (ν) by

$$\displaystyle\begin{array}{rcl} & & r_{\nu }^{(\nu )} = 0,\quad r_{ k-1}^{(\nu )} = \frac{\beta _{k}} {z -\alpha _{k} - r_{k}^{(\nu )}},\quad k =\nu,\nu -1,\ldots\,,1,0, {}\\ & & \varrho _{-1}^{(\nu )} = 1,\quad \varrho _{ k}^{(\nu )} = r_{ k-1}^{(\nu )}\varrho _{ k-1}^{(\nu )},\quad k = 0,1,\ldots\,,n. {}\\ \end{array}$$

The quantities ϱ k (ν)(z) then tend to ϱ k (z) when ν → ∞, for every k = 0, 1, …, n. For some standard measures dμ, Gautschi also provides good estimates for the starting index ν, given n and the desired accuracy.

Notice that the rational function (11.2) has simple poles at the zeros z = x n, k , k = 1, …, n, of the polynomial π n (t). By λ n, k we denote the corresponding residues, i.e.,

$$\displaystyle{\lambda _{n,k} =\lim _{z\rightarrow x_{n,k}}(z - x_{n,k})\frac{\sigma _{n}(z)} {\pi _{n}(z)} = \frac{1} {\pi ^{\prime}_{n}(x_{n,k})}\int _{\mathbb{R}} \frac{\pi _{n}(t)} {t - x_{n,k}}\,\mbox{ d}\mu (t),}$$

so that the continued fraction representation (11.2) assumes the form

$$\displaystyle{ \frac{\sigma _{n}(x)} {\pi _{n}(x)} =\sum _{ k=1}^{n} \frac{\lambda _{n,k}} {x - x_{n,k}}\,. }$$
(11.4)

The coefficients λ n, k play an important role in Gauss–Christoffel quadrature formulae, being the Christoffel numbers associated with dμ. Using procedures of numerical linear algebra, notably the QR or QL algorithm, one easily computes the zeros of the orthogonal polynomials π n rapidly and efficiently as eigenvalues of the leading nth-order principal minor matrix of the Jacobi matrix associated with dμ,

$$\displaystyle{J(\mbox{ d}\mu ) = \left[\begin{array}{ccccc} \alpha _{0} & \sqrt{\beta _{1}} & & & \mathbf{0} \\ \sqrt{\beta _{1}}\ & \alpha _{1}\ & \sqrt{\beta _{2}}\ & \ & \ \\ & \sqrt{\beta _{2}} & \alpha _{2} & \ddots\ & \\ & & \ddots & \ddots & \\ \mathbf{0} & & && \end{array} \right].}$$

The first components of the corresponding normalized eigenvectors give also immediately the Christoffel numbers λ n, k (cf. [12, GA65]).

Unfortunately, the recursion coefficients are known explicitly only for some narrow classes of orthogonal polynomials. One of the most important classes for which these coefficients are known explicitly are surely the so-called very classical orthogonal polynomials (Jacobi, the generalized Laguerre, and Hermite polynomials), which appear frequently in applied analysis and computational science. Orthogonal polynomials for which the recursion coefficients are not known we call strongly nonclassical polynomials. In this case, if we know how to compute the first n recursion coefficients α k and β k , k = 0, 1, …, n − 1, we can compute all orthogonal polynomials of degree ≤ n by a straightforward application of the three-term recurrence relation (11.1).

In [GA81] Walter Gautschi starts with an arbitrary positive measure dμ(t), which is given explicitly, or implicitly via moment information, and considers the actual (numerical) construction of orthogonal polynomials to be a basic computational problem: For a given measure d μ and for given n ∈ ℕ, generate the first n coefficients α k (dμ) and β k (dμ), k = 0,1,…,n − 1.

At that time, and even more so in the “pre-computer” era, the problem was given surprisingly little attention in the literature, probably because it has a straightforward theoretical solution. Indeed, if one knows the moments μ k , k ≥ 0, the polynomial π k (t; dμ) can be expressed in the form

$$\displaystyle{\pi _{k}(t;\,\mathrm{d}\mu ) = \frac{1} {\Delta _{k}}\,\left\vert \begin{array}{ccccc} \mu _{0} & \mu _{1} & \cdots & \mu _{k-1} & 1 \\ \mu _{1} & \mu _{2} & \cdots & \mu _{k} & t\\ \vdots & \vdots & & \vdots & \vdots \\ \mu _{k}&\mu _{k+1} & \cdots &\mu _{2k-1} & {t}^{k} \end{array} \right\vert,}$$

where the Hankel determinant

$$\displaystyle{\Delta _{k} = \left\vert \begin{array}{cccc} \mu _{0} & \mu _{1} & \cdots & \mu _{k-1} \\ \mu _{1} & \mu _{2} & \cdots & \mu _{k}\\ \vdots & \vdots & & \vdots \\ \mu _{k-1} & \mu _{k}&\cdots &\mu _{2k-2} \end{array} \right\vert }$$

is nonvanishing. The coefficients in the three-term recurrence relation can also be expressed in terms of Hankel determinats (or by Darboux’s formulae),

$$\displaystyle{ \alpha _{k} = \frac{\Delta ^{\prime}_{k+1}} {\Delta _{k+1}} -\frac{\Delta ^{\prime}_{k}} {\Delta _{k}}\left(= \frac{(t\pi _{k},\pi _{k})} {(\pi _{k},\pi _{k})} \right),\quad \beta _{k} = \frac{\Delta _{k-1}\Delta _{k+1}} {\Delta _{k}^{2}} \left(= \frac{(\pi _{k},\pi _{k})} {(\pi _{k-1},\pi _{k-1})}\right), }$$
(11.5)

where Δ k ′ denotes the determinant obtained from Δ k by replacing the last column [μ k − 1 μ k … μ 2k − 2]T by [μ k  μ k + 1 … μ 2k − 1]T.

Thus, the recursion coefficients α k and β k in (11.1) can be computed from (11.5) in terms of Hankel-type determinants, but this involves excessive complexity and is subject to extreme numerical instability. In the numerical construction of recursion coefficients an important aspect is the sensitivity of the problem with respect to small perturbations in the data (for example, perturbations in the first 2n moments μ k , k = 0, 1, …, 2n − 1, when calculating the coefficients for k ≤ n − 1). There is a simple algorithm, due to Chebyshev, which transforms the moments to the desired recursion coefficients, \( {[\mu_{k}]}^{2n-1}_{k=0} \mapsto {[\alpha_{k},\beta_{k}]}^{n-1}_{k=0},\) but its viability is strictly dependent on the conditioning of this mapping. The latter is usually severely ill conditioned so that these calculations via moments, in finite precision on a computer, are quite ineffective. The only salvation, in this case, is to either use symbolic computation, which however requires special resources and often is not possible, or else to use the explicit form of the measure. In the latter case, an appropriate discretization of the measure and subsequent approximation of the recursion coefficients is a viable alternative.

2 Basic procedures for generating the recursion coefficients

There are three well-known approaches for generating recursion coefficients: the method of (modified) moments, the Stieltjes procedure, and the Lanczos algorithm.

2.1 Method of (modified) moments

In an attempt to avoid ill-conditioning, one can use the so-called modified moments m k  = ∫ ℝ p k (t)dμ(t), k = 0, 1, 2, … , where p k are monic polynomials of degree k “close” in some sense to the desired polynomials π k . Usually, the polynomials p k satisfy a three-term recurrence relation of the form (11.1), with coefficients a k  ( ∈ ℝ) and b k  ( ≥ 0) (instead of α k and β k ). Then there is a unique map K n : ℝ2n → ℝ2n that takes the first 2n modified moments into the desired n recurrence coefficients α k and β k , i.e., \( {[m_{k}]}^{2n-1}_{k=0} \mapsto {[\alpha_{k},\beta_{k}]}^{n-1}_{k=0}\). An algorithm for realizing this map (modified Chebyshev algorithm) is formulated and summarized schematically in Gautschi [GA81]. In a somewhat different form, the algorithm has been first proposed by Sack and Donovan [29], and modified by Wheeler [33]. A derivation can also be found in [GA64]. For a k  = b k  = 0 we have p k (t) = t k and the modified moments m k reduce to the standard moments μ k .

A rigorous and detailed analysis of the map K n was given by Gautschi in [GA81] (see also [GA94] and especially his excellent survey [GA146] on applications and computational aspects of orthogonal polynomials). The novelty of his treatment consists in representing K n : ℝ2n → ℝ2n as a composition of two maps, K n  = H n  ∘ G n , where G n : \( {[m_{k}]}^{2n-1}_{k=0} \rightarrow {[x_{n,k},\lambda_{n,k}]}^{n}_{k=1}\) is the map from the modified moments to the Gauss–Christoffel nodes and weights, and H n : \( {[x_{n,k},\lambda_{n,k}]}^{n}_{k=1} \rightarrow {[\alpha_{k},\beta_{k}]}^{n-1}_{k=0}\), the map from the Gauss–Christoffel quadrature rule

$$\displaystyle{\int _{\mathbb{R}}f(t)\,\mathrm{d}\mu (t) =\sum _{ k=1}^{n}\lambda _{ n,k}f(x_{n,k}) + R_{n}(f),\quad R_{n}(\mathcal{P}_{2n-1}) = {0},}$$

to the desired recursion coefficients. Notice that x n, k , k = 1, …, n, are the zeros of the orthogonal polynomial π n associated with the measure dμ. The parameters x n, k and λ n, k , k = 1, …, n, also appear in (11.4).

The components H n and G n of the map K n can be analyzed individually with regard to their numerical condition, which in turn yields a bound on the condition of the composite map. The map H n is usually fairly well conditioned, but G n is the more sensitive one. The map K n for standard moments, \( [\mu_{k}]^{2n-1}_{k=0}\mapsto [\alpha_{k},\beta_{k}]^{n-1}_{k=0} \), is severely ill conditioned when n is large. By using modified moments, the map may become better conditioned, very much so when the measure has finite support.

2.2 Discretization methods

The basic idea for these methods is an approximation of the given measure dμ by a discrete N-point measure, usually through an appropriate quadrature rule,

$$\displaystyle{\mathrm{d}\mu (t) \approx \mathrm{d}\mu _{N}(t) =\sum _{ k=1}^{N}w_{ k}\delta (t - x_{k}),\quad w_{k} > 0,}$$

where δ is the Dirac delta function. Thereafter, the first n recursion coefficients are approximated by those of the discrete measure,

$$\displaystyle{\alpha _{k}(\mathrm{d}\mu ) \approx \alpha _{k}(\mathrm{d}\mu _{N}),\quad \beta _{k}(\mathrm{d}\mu ) \approx \beta _{k}(\mathrm{d}\mu _{N}),\quad k = 1,2,\ldots\,,n.}$$

The approximate coefficients are computed by a discretized Stieltjes procedure. It takes N ≫ n and uses Darboux’s formulae in (11.5) for k ≤ n − 1, computing the inner products as finite sums by

$$\displaystyle{(p,q)_{N} =\int _{\mathbb{R}}p(t)q(t)\,\mathrm{d}\mu _{N}(t) =\sum _{ k=1}^{N}w_{ k}p(x_{k})q(x_{k}).}$$

All aspects of discretization methods, theoretical and practical, are carefully analyzed by Gautschi in [GA81] (questions of convergence, problems of computing recursion coefficients of discrete measures, appropriate choices of discretizations, numerical stability of the procedure, etc.). The idea of discretizing inner products appeared already in the 1968 paper [GA31], where the discretization is effected by the Fejér quadrature rule. Because of Gautschi’s important contributions, the method is now known as the discretized Stieltjes–Gautschi procedure.

2.3 Lanczos algorithm

An alternative approach for obtaining the recursion coefficients of a discrete measure is the Lanczos algorithm, which is based on ideas of Lanczos and Rutishauser (for details see [GA146] and Gautschi’s book from 2004 [GAB3, pp. 97–98]).

3 Examples of interesting classes of orthogonal polynomials

Walter’s work and his contributions in the constructive theory of orthogonal polynomials allow the construction of many new classes of polynomials and their application in diverse areas of applied and numerical analysis (numerical integration, interpolation processes, integral equations, probability, moment-preserving spline approximation, summation of slowly convergent series, approximation theory, etc.), as well as in many other areas of applied and computational science.

In this subsection we mention some interesting nonclassical measures dμ(t) = w(t) dt for which the recursion coefficients α k ( dμ), β k ( dμ), k = 0, 1, …, n − 1, have been obtained in the literature and used in the construction of Gaussian quadratures and other applications of orthogonal polynomials. Many interesting examples, including discrete and continuous measures, were considered by Gautschi [GA81] in order to illustrate the strengths and weaknesses of the various constructive methods and to test the underlying theory.

1) Christoffel’s example dμ(t) = [(1 − k 2 t 2)(1 − t 2)] − 1 ∕ 2 dt on [ − 1, 1], 0 < k < 1, was treated in [GA81, GA94] by the method of moments, using modified moments relative to Chebyshev polynomials of the first kind.

2) The logarithmic weight w(t) = t αlog(1 ∕ t), α  >  − 1, on (0, 1) was first considered by Piessens and Branders [28] for some particular values of α. Gautschi [GA81, GA117] gave a complete stability analysis and used the modified moments relative to shifted Jacobi polynomials [GA67] in his construction, even for the more general measure dμ(t) = t α(1 − t)βlog(1 ∕ t) dt, where α, β >  − 1.

3) The half-range Hermite measure dμ(t) = exp( − t 2) dt on [0, ∞) was dealt with in [GA81] by using the discretized Stieltjes–Gautschi procedure. Orthogonal polynomials with respect to the same measure, but on a finite interval [0, c] (Maxwell velocity distribution), were considered for c = 1 and n = 10 by Steen, Byrne, and Gelbard [30]. A stable construction is given by Gautschi in [GA122].

4) Polynomials orthogonal with respect to multiple-component distributions, e.g., dμ(t) = [(1 − t 2) − 1 ∕ 2 + a] dt on [ − 1, 1], a > 0 (adding a multiple of the Legendre weight function to the Chebyshev weight function), was considered in [GA81].

5) In [GA90] Gautschi developed constructive methods for a class of polynomials orthogonal on two symmetric intervals with respect to the measure dμ(t) = w(t) dt on [ − 1, 1], where

$$\displaystyle{w(t) = \left\{\begin{array}{ll} \vert t{\vert }^{\gamma }{({t}^{2} {-\zeta }^{2})}^{p}{(1 - {t}^{2})}^{q},\quad &t \in[-1,-\zeta ] \cup[\zeta,1], \\ 0\ \mbox{ elsewhere}, &0 <\zeta < 1,\ p >\,-1,\ q >\,-1,\ \gamma \in\mathbb{R}. \end{array} \right.}$$

An analysis is given of certain phenomena of instability in connection with nonlinear recursions. The special case γ = 1, p = q =  − 1 ∕ 2, ζ = (1 − r) ∕ (1 + r) (0 < r < 1) arises in the study of the diatomic linear chain (cf. J. C. Wheeler [34]). Gautschi showed how to use the recurrence relations for related polynomials orthogonal on [ζ, 1] to generate the coefficients β k in the desired three-term recurrence relation. For certain special values of the parameters p, q and γ, he obtained β k explicitly in closed form. For general parameters, the theory of this class of polynomials has previously been studied by Barkov [2]. In 1989 Locher [14] obtained an explicit representation of these polynomials in the case γ = 0 (and in some other cases where γ is an even integer), from which the recurrence relation can be derived.

6) The Airy weight w(t) = exp( − t 3 ∕ 3) on (0, + ∞) was considered in the chemistry literature [13], but the numerical results obtained were accurate to only 1 − 2 decimal digits (cf. also Section 15.1). The inhomogeneous Airy functions Hi(t) and Gi(t) arise in theoretical chemistry (e.g. in harmonic oscillator models for large quantum numbers); their integral representations [13] are given by

$$\displaystyle\begin{array}{rcl} \mbox{ Hi}(t)& =& \frac{1} {\pi } \int _{0}^{+\infty }w(x){e}^{xt}\,dx, {}\\ \mbox{ Gi}(t)& =& -\frac{1} {\pi } \int _{0}^{+\infty }w(x){e}^{-xt/2}\cos {\Bigl (\frac{\sqrt{3}} {2} \,xt + \frac{2\pi } {3}\Bigr )}\,dx. {}\\ \end{array}$$

These functions can effectively be evaluated by Gaussian quadrature relative to the Airy weight w(t) once the orthogonal polynomials with respect to this weight are known. Gautschi [GA84] computed their recursion coefficients for n = 15 to 16 decimal digits after the decimal point, using standard double-precision arithmetic.

7) The reciprocal gamma function w(t) = 1 ∕ Γ(t) as a weight function on (0, + ∞) was considered by Gautschi in [GA80]. It could be useful as a probability density function in reliability theory (see Fransén [10]).

8) Einstein’s and Fermi’s weight functions on (0, + ∞),

$$\displaystyle{w_{1}(t) =\varepsilon (t) = \frac{t} {{e}^{t} - 1}\qquad \mbox{ and}\qquad w_{2}(t) =\varphi (t) = \frac{1} {{e}^{t} + 1},}$$

arise in solid state physics. (For this example, see also Section 15.5.) For w 1(x), w 2(x), w 3(x) = ɛ(x)2 and w 4(x) = φ(x)2, in a joint paper with Walter Gautschi [GA93], we determined the recursion coefficients α k and β k for n = 40 to 25 decimal digits, and gave an application of the respective Gauss–Christoffel quadratures to the summation of slowly convergent series whose general term is expressible in terms of a Laplace transform or its derivative. (For this, see also Section 25.2, Vol. 3) It was our first joint paper. The story of our collaboration has recently been told by Walter Gautschi [GA201] on the occasion of my 60th anniversary. Our collaboration has started in the mid eighties of the last century, just at the time when Walter developed his constructive theory of orthogonal polynomials. I was then in my thirties, so his influence on my scientific work and my further development was of crucial importance; for this I am very grateful to him.

9) For the hyperbolic weights on (0, + ∞),

$$\displaystyle{w_{1}(t) ={ \frac{1} {\cosh^{2}t}}\qquad \mbox{ and}\qquad w_{2}(t) ={ \frac{\sinh t} {\cosh^{2}t}},}$$

I constructed the recursion coefficients α k , β k for n = 40 to 30 decimal digits [19] using the discretized Stieltjes–Gautschi procedure with a discretization based on the Gauss–Laguerre quadrature rule. The Gaussian quadratures relative to these weights were used in the summation of slowly convergent series (for details see [19–21]); see also Dahlquist [7–9] and [25] for related work

10) The weight distribution dμ(t) = t α K 0(t) dt on [0, ∞), α >  − 1, where K 0 is the modified Bessel function, arose in work of R. Wong [35]. In [GA81] Gautschi showed how to decompose and discretize the inner product (p, q) = ∫ 0 ∞ p(t)q(t) dμ(t) in order to apply an appropriate Stieltjes–Gautschi procedure. Recently, Gautschi [GA169] described procedures for the high-precision calculation of the modified Bessel function K ν (t), 0 < ν < 1, and the Airy function Ai(t), for positive arguments t, as prerequisites for generating Gaussian quadrature rules having these functions as a weight function.

Recent progress in symbolic computation and variable-precision arithmetic now makes it possible to generate the coefficients α k and β k in the three-term recurrence relation (11.1) directly by using the original Chebyshev method in sufficiently high precision. Respective symbolic/variable-precision software for orthogonal polynomials is available (Gautschi’s package SOPQ in Matlab — see Section 23, Vol. 3 — and the Mathematica package OrthogonalPolynomials [5, 26]). Thus, all that is required is a procedure for the (symbolic) calculation of the moments in variable-precision arithmetic. Gautschi [GA176] illustrates this approach in the case of orthogonal polynomials having such unorthodox weight functions as 1 + sin(1 ∕ t) on [0, 1], or exp( − t − 1 ∕ t) on [0, ∞], which are respectively densely oscillating at one endpoint, or exponentially decaying at both. In each case the moments of the weight function are expressible in terms of special functions which can be evaluated to arbitrary precision. Similarly, in [GA195] Gautschi considered Freud and half-range Hermite polynomials, Bose–Einstein polynomials, and Fermi–Dirac polynomials.

Very recently, Gautschi [GA205] considered orthogonal polynomials relative to the Jacobi weight function w(x) = (1 − x)α(1 + x)β, α, β >  − 1, but orthogonal on a strict subinterval [ − c, c] or [ − 1, c], 0 < c < 1, especially with regard to their numerical computation. Such sub-range Jacobi polynomials π k (x) can be expressed in terms of polynomials orthogonal on [ − 1, 1] relative to the weight function w(ct) resp. \({w}( \frac{1} {2}(1+c)t- \frac{1} {2}(1-c))\) and constructed using a discretized Stieltjes–Gautschi procedure. Gautschi also considered corresponding Gaussian quadrature rules.

4 Christoffel modifications of the measure – modification algorithms

Let dμ(t) be a positive measure with finite support supp( dμ) = [a, b],

$$\displaystyle{u(t) = \pm \prod _{k=1}^{\ell}(t - u_{ k}),\quad v(t) =\prod _{ k=1}^{m}(t - v_{ k})}$$

be two real polynomials, relatively prime and not vanishing on [a, b], the sign + or − in u(t) being chosen so that u(t) ∕ v(t) > 0 on [a, b]. Define a new measure

$$\displaystyle{ \,\mathrm{d}\widehat{\mu }(t) = \frac{u(t)} {v(t)}\,\mathrm{d}\mu (t),\quad t \in[a,b]. }$$
(11.6)

The main problem is to generate the three-term recurrence coefficients of the modified measure (11.6), \(\widehat{\alpha }_{k} =\widehat{\alpha } _{k}(\mathrm{d}\widehat{\mu })\) and \(\widehat{\beta }_{k} =\widehat{\beta } _{k}(\mathrm{d}\widehat{\mu })\), from those of the original measure, α k  = α k (dμ) and β k  = β k (dμ). Methods for implementing this transformation are known as modification algorithms. The first result in this area is due to Christoffel [4], who in 1858 expressed \(u(t)\pi _{n}(t;\,\mathrm{d}\widehat{\mu })\), when v ≡ 1 and dμ(t) = dt, in determinantal form as a linear combination of orthogonal polynomials π n + ν (t; dμ), ν = 0, 1, …, ℓ. The case with v(t) ≢ 1 was solved hundred years later by Uvarov [31].

Modifications by linear and quadratic factors and divisors play an important role in the computational use of orthogonal polynomials. Subsequent to a paper of Galant [11], who considered modification by a linear factor, Gautschi [GA77] in 1982 developed general modification algorithms for linear and quadratic factors u(t) = t − x and u(t) = (t − x)2 + y 2 and analogous divisors. Based on work by Verlinden [32], these methods can be simplified considerably and in this simplified form are included in Gautschi’s book [GAB3, §2.4] along with Matlab software. An interesting quadratic factor is u(t) = (t − x)2. It can be treated by techniques of numerical linear algebra (cf. [GA170]). Namely, in order to obtain \(J_{n}(\,\mathrm{d}\widehat{\mu })\) one applies a single step of the QR algorithm with shift x to the Jacobi matrix J n + 2( dμ) of order n + 2 and then discards the last two rows and columns of the resulting matrix.

In [GA134] Gautschi (with Shikang Li) considered \(\,\mathrm{d}\widehat{\mu }(t) = {[\pi _{n}(t;\,\mathrm{d}\mu )]}^{2}\,\mathrm{d}\mu (t)\) and constructed the orthogonal polynomials \(\widehat{\pi }_{n}(t;\,\mathrm{d}\widehat{\mu })\) and their recursion coefficients from the coefficients α k (dμ) and β k (dμ) of the polynomials π n (t; dμ). They proposed a stable computational algorithm, which uses a sequence of QR steps with shifts, but for all four Chebyshev measures they obtained the desired coefficients analytically in closed form. These ideas have been used in [6] to develop a rational algorithm for quadratic Christoffel modification and to apply it to constrained L 2-approximation.

Recently, Gautschi [GA206] has developed algorithms for computing the recursion coefficients in the three-term recurrence relation of repeatedly modified orthogonal polynomials, the modifications involving division of the orthogonality measure by linear functions with real or complex coefficients. Several interesting examples are given, including Bose–Einstein distributions and the Szegő–Bernstein measure.

5 Sobolev-type orthogonal polynomials

In the last two decades, interest arose, and grew, in the development of orthogonal polynomials with respect to an inner product of Sobolev type, i.e., involving derivatives up to a given order with corresponding positive measures. There is a growing literature on this kind of orthogonal polynomials, largely concerned with analytic and algebraic properties (cf. [15]). Computational aspects were first discussed systematically by Gautschi and his student M. Zhang [GA145], where the inner product considered is a bilinear functional involving derivatives up to some order s ( ≥ 1) with arbitrary positive measures dμ ν , ν = 0, 1, …, s,

$$\displaystyle{ (p,q)_{H_{s}} =\sum _{ \nu =0}^{s}\int _{ \mathbb{R}}{p}^{(\nu )}(t){q}^{(\nu )}(t)\,\mathrm{d}\mu _{\nu }(t). }$$
(11.7)

Here H s denotes the Sobolev space \( {H}_{s}(\mathbb{R}) = \{f :\sum\nolimits^{s}_{\nu=0}\int_{\mathbb{R}}[f^{(\nu)}(t)]^{2}\text{d}\mu_\nu(t)<{\infty}\}\). They developed two numerical methods for determining the coefficients in the (long) recurrence relation for orthogonal polynomials of Sobolev type,

$$\displaystyle{\pi _{k+1}(t) = t\pi _{k}(t) -\sum _{\nu =0}^{k}\beta _{ \nu }^{k}\pi _{ k-\nu }(t),\quad k = 0,1,\ldots\,.}$$

The first is based on modified moments of the constitutive measures and generalizes what for ordinary orthogonal polynomials is known as “modified Chebyshev algorithm”. The second is a generalized Stieltjes–Gautschi procedure. The numerical features of these methods are illustrated in the case of old, as well as new, Sobolev orthogonal polynomials. The coefficients in the recurrence relation can be used to compute the zeros of π n (t) as eigenvalues of an upper Hessenberg n ×n matrix. Based on numerical experimentation, a number of conjectures are formulated with regard to the location and interlacing properties of the respective zeros.

In [GA151] Gautschi develops two recursive schemes for computing a special class of Sobolev-type orthogonal polynomials, considered previously by F. Marcellán and A. Ronveaux [16]. The inner product involves functions with an arbitrary positive measure dμ(t) on ℝ, and a derivative of fixed order r with a one-point atomic measure, i.e., [f, g] = (f, g) + f (r)(c)g (r)(c), r ≥ 1, c ∈ ℝ, and (f, g) = ∫ ℝ f(t)g(t) dμ(t). Gautschi combines in an elegant way known algebraic properties of such Sobolev orthogonal polynomials with algorithmic ideas of his own to arrive at effective methods for computing these polynomials numerically. He illustrates them in the case of Hermite, Laguerre and Legendre measures, and uses them to explore numerically the zeros of the respective Sobolev-type orthogonal polynomials.

In the very interesting paper [GA153] Gautschi and Kuijlaars, using potential-theoretic methods, study the asymptotic distribution of zeros and critical points of Sobolev polynomials π n orthogonal with respect to the inner product (11.7) with s = 1, assuming that dμ 0 and dμ 1 are compactly supported positive measures on the real line with finite total mass and infinite Σ = supp(μ 0) ∪supp(μ 1). Under appropriate assumptions they show that the critical points (zeros of \(\pi^{\prime}_{n}\)) have a canonical asymptotic limit distribution supported on the real line. In certain cases the zeros themselves have the same asymptotic limit distribution. They also give a new result on zero distributions of asymptotically extremal polynomials.

6 Further extensions and applications

Gautschi’s work on the constructive theory of orthogonal polynomials has had a great impact on the general development of the theory of orthogonal polynomials and led to many new applications of orthogonal polynomials in numerical integration, interpolation processes, approximation and optimization theory, spline theory, integral and differential equations, linear algebra, and in many other fields of applied and computational science. In particular, the development of appropriate software has encouraged a number of new applications. His article [GA81] alone is cited over 150 times (according to the Web of Science) in papers from the previously mentioned areas of mathematics, mechanics, computer science, physics, chemistry, engineering, etc.

In conclusion, I would like to mention a few generalizations and applications of Gautschi’s ideas in my own work.

(a) Construction of s-orthogonal polynomials. These polynomials \(\{\pi_{n,s}(t)\}^{\infty}_{n=0}\) (with a fixed s ∈ ℕ) are characterized by the nonlinear orthogonality relation

$$\displaystyle{\int _{\mathbb{R}}{t}^{\nu }{[\pi _{n,s}(t)]}^{2s+1}\,\mathrm{d}\mu (t) = 0,\quad \nu = 0,1,\ldots\,,n - 1,}$$

and play an important role in the construction of so-called Turán quadratures with multiple nodes (cf. [23]). In [18] we first reinterpret these relations as ordinary orthogonality conditions relative to the positive measure (implicitly defined) dμ n, s (t) = [π n, s (t)]2s dμ(t),

$$\displaystyle{\int _{\mathbb{R}}{t}^{\nu }\pi _{n,s}(t)\,\mathrm{d}\mu _{n,s}(t) = 0,\quad \nu = 0,1,\ldots\,,n - 1,}$$

and then apply Gautschi’s idea of the discretized Stieltjes procedure to the corresponding system of nonlinear equations. In a joint paper with Walter Gautschi [GA154] the method was applied to construct Gauss–Turán quadrature formulae. (For this, see also Section 15.5.) These methods have led to further progress in the theory of quadratures with multiple nodes.

(b) Orthogonal polynomials on radial rays. In 1997 I introduced a class of polynomials orthogonal on radial rays in the complex plane [22]. For the numerical construction of the corresponding recurrence coefficients I used a generalized Stieltjes–Gautschi procedure [24].

(c) Multiple orthogonal polynomials. A nice survey of these polynomials, known also as Hermite–Padé polynomials, was given by Aptekarev [1]. In 2003, with my student Stanić, I gave an application of the generalized Stieltjes–Gautschi procedure to the numerical construction of a special class of multiple orthogonal polynomials (see [27]). Using these polynomials, we also described a method for the stable construction of Borges quadrature rules [3].