Orthogonal Polynomials

Orthogonal polynomials are a sequence of polynomials that are orthogonal with respect to a specific inner product. They are widely used in numerical analysis, approximation theory, and other fields. Here we list some important orthogonal polynomials and their properties.

Orthogonal Polynomial	Definition on
Jacobi
Jacobi (shifted)
Gegenbauer or Ultraspherical
Legendre
Chebyshev (first kind)
Chebyshev (first kind, shifted)
Chebyshev (second kind)
Chebyshev (second kind, shifted)
Laguerre
Hermite ( or )

where is the Pochhammer symbol, satisfying

provided that is a nonnegative integer. The Pochhammer symbol is related to the gamma function by the formula

And is the hypergeometric function, defined as

The series terminates if or is a nonpositive integer, in which case the function reduces to a polynomial:

Jacobi Polynomials

Hypergeometric Definition
The Jacobi polynomials are defined via the hypergeometric function as follows:

In this case, the series for the hypergeometric function is finite, therefore one obtain the following equivalent expression:

Differential Definition
Legendre polynomials are a special case of Jacobi polynomials with , having the following differential definition:

In fact, the general Jacobi polynomials also have similar differential expression:

which is called the Rodrigues’ formula.

Properties

Orthogonality
The Jacobi polynomials are orthogonal with respect to the weight function on the interval , i.e.,

where

Hence the Jacobi polynomials are not orthonormal in general, but can be normalized by dividing by the square root of the corresponding , and an alternative normalization is sometimes preferred due to its simplicity:

Symmetry Relation
Jacobi polynomials satisfy the symmetry relation

thus the other terminal value is

Derivatives
The th derivative of the explict expression of Jacobi polynomials leads to

therefore the Jacobi-based th differential operator is

(first elements of first row are ), which satisfies

The differential operator, as well as multiplication and conversion operators are introduced in [6] for the ultraspherical spectral method.

Differential Equation
The Jacobi polynomial is a solution to the following 2nd-order linear homogeneous differential equation:

hence is a eigenfunction of the corresponding Sturm-Liouville operator.

Recurrence Relation
As an orthogonal polynomial, Jacobi polynomials satisfy the following three-term recurrence relation:

where

The multiplication operator , which satisfies

is given by

Generally, we need the operator for solving a variable coefficient differential equation by spectral methods in spectral space, which is assumed to satisfy

Since no closed-form expression is known, can only be constructed via the recurrence relation

where

Linearity of leads to

and the recurrence coefficients can be calculated by as follows:

Now we can construct the operator provided that is represented by a Jacobi series.

On the other hand, like the ultraspherical case, we need the conversion operator to improve the order of polynomials used to represent the solution. The conversion operator is defined as

To construct , differentiate both sides of results

recall the derivative of Jacobi polynomials satisfies

therefore we have

Notice can be represented by , and again:

we have

where

Therefore, the conversion operator is

Now the linear differential operator

can be approximated by Jacobi-based operator

which maps a series to a series.

Generating Function
The generating function of Jacobi polynomials is given by

where

and the branch of square root is chosen s.t. .

Orthogonal Polynomial Transforms

Orthogonal polynomial transforms involves computing expansion coefficients in one basis from

1. function samples (Synthesis and Analysis) or
2. coefficients in another basis (Connection problem).

In the former case, the (infinite-dimensional) synthesis operator is the map that takes expansion coefficients to the corresponding function by summing up the expansion, while the (infinite-dimensional) analysis operator takes function samples to expansion coefficients.

This section is mainly based on the review paper [7] and the Phd thesis [8] by Jens Keiner.

Synthesis and Analysis

Due to the speical importance of Chebyshev polynomial in orthogonal polynomials, let’s start from the synthesis and analysis corresponding to Chebyshev polynomials, which are closely connected with fast Fourier transform. Here we take the first kind Chebyshev polynomial for an example, else three kind Chebyshev polynomials share similar properties. The grid can be choosen as the zeros of all four kind Chebyshev polynomials.

Synthesis. Given coefficient so that

where , then the synthesis transform is of the kind

in which is one of four kind Chebyshev grids.

Since , above transformation can be related to discrete cosine transforms, which can be computed using an FFT.

Analysis. Transform from function values to Chebyshev expansion coefficients can be obtained by interpolation. The Chebyshev interpolation on given interval has four steps in general [10].

Step 1. Create the interpolation grid by the explicit formula. Usually, we use Chebyshev-Lobatto grid, which is given by

The benefit of such gird is all points on the -point Chebyshev-Lobatto grid are also points on the -point grid. Thus, if the number of grid points is increased, with , all samples of on coarser grids can be reused on the finer grid.

Step 2. Compute the samples of on the grid. Denote this function values as

Step 3. Construct the interpolation matrix , which is exactly the analysis transform operator, by setting

where

Step 4. The coefficients are evaluated by a vector-matrix multiply:

that is, .

Note that this vector-matrix multiply can be accelerated by the FFT, but since this multiply cost , while the eigensolving cost is , the FFT is scarcely worth the bother.

Connection problem

The connection problem concerns

1. how to change between different basis expansions;
2. how to do this efficiently and accurately.

To state this problem precisely, we first introduce the concept of connection coefficients.

Let be a family of orthogonal polynomials with respect to a measure (that is, some corresponding weight function), and let be another family of orthogonal polynomials with respect to a measure . Assuming that , then we have

where are referred to as the connection coefficients. Furthermore, if , then we call this problem measure-preserving, while if , then we say it’s measure-perturbing.

By using the notation of quasimatrix, that is, denote and , above equation can be written as

where is the connection matrix with elements :

If we are given a polynomial expansion in the basis , then the expansion in the basis is simply given by

where is the coefficient vector in the basis .

The key point now becomes how to construct the connection matrix efficiently and accurately. We first consider some special important kind orthogonal polynomials and their connection coefficients, which have different structures but are all sparse due to their orthogonality.

Chebyshev Polynomials. Based on the well-known connection formula of four kind Chebyshev polynomials, we have

Following the former notation, we denote the first matrix as , and the second as .

Ultraspherical Polynomials. For any , we have

which can also be written as

by left multiplying the inverse of the diagonal matrix of the previous equation on both sides.

Similarly, one can also efficiently convert between Jacobi bases and using a more general bidiagonal conversion matrix.

The Chebyshev-Legendre Transform. There are many different algorithms accelerate the Chebyshev-Legendre transform, that is, applying the conversions and , where

which includes

1. an adaptation of the fast multipole method by Alpert and Rokhlin in 1991;
2. methods based on semi-separable matrices by Keiner;
3. analysis of the Toeplitz-Hankel structure of the connection matrix by Townsend, Webb and Olver in 2018;
4. direct synthesis and analysis using the asymptotics of Legendre polynomials by Orszag, etc;
5. ideas related to non-oscillatory phase functions by Bremer and Yang in 2019;
6. …

The Chebyshev-Legendre transform has the beneficial feature that the conversion matrices are known explicitly, though they are not banded. According to Alpert and Rokhlin in 1991, the Chebyshev-Legendre connection operator are given by

and

where . More explicitly, for and even, we have and , where

Biref proof. Recall the differential equation satisfied by the Legendre quasimatrix is

where is a diagonal matrix satisfying . Substituting in , we find satisfies the following Sylvester equation:

in which we use the relationship

and , i.e.

Here is the differentiation matrix for Chebyshev polynomials, which is defined by

is the differentiation matrix for ultraspherical polynomials, which is defined by

Since and , we have . And is the weighted conversion between ultraspherical polynomials

where the entries of are determined by the recurrence

We have since . By the way, by composing weighted conversions. In the end, is the multiplication-by- operator for .

Direct inspection shows the proposed and satisfy the Sylvester equation, and it’s easy to verify the uniqueness of the solution.

Reference

1. Orthogonal Polynomials
2. Hypergeometric Function
3. Jacobi Polynomials
4. Yudell L. Luke, The Special Functions and Their Approximations, Volume 1, Academic Press, 1969.
5. Mason J. C., Handscomb D. C., Chebyshev Polynomials, Chapman and Hall/CRC, 2003.
6. Sheehan Olver, Alex Townsend. A Fast and Well-Conditioned Spectral Method, SIAM Rev. 55, 2013
7. Sheehan Olver, Richard Mikaël Slevinsky, Alex Townsend. Fast algorithms using orthogonal polynomials, Acta Numerica, 2020.
8. Jens Keiner, Fast Polynomial Transforms, Phd thesis, 2009.
9. Alex Townsend, Computing with Functions in Two Dimensions, Phd thesis, 2013.
10. Boyd J. P., Solving Transcendental Equations: The Chebyshev Polynomial Proxy and Other Numerical Rootfinders, Perturbation Series, and Oracles, SIAM, 2014.