Orthogonal polynomials

Interpolation is not the only way to use polynomials for global approximation of functions. In Fitting functions to data we saw how to find least-squares polynomial fits to data by solving linear least-squares matrix problems. This idea can be extended to fitting functions.

We can extend least-squares fitting from data to functions by extending several familiar finite-dimensional definitions. The continuous extension of a sum is an integral, which leads to the following.

9.4.1Quasimatrices¶

If we are extending our notion of vectors to include continuous functions, what should serve as an extension of a matrix? One of our most important interpretations of a matrix is the connection to linear combinations. For instance, the Vandermonde-like system $\mathbf{V} \mathbf{c} \approx \mathbf{y}$ from (3.1.2) is the statement

in which the $i$th row of $\mathbf{v}_j$ is $t_i^j$. This was derived as a discrete approximation for $j=0,\ldots,n$.

which we want to abbreviate in “matrix”-vector form.

We consider any other expressions involving a quasimatrix to be undefined. It might help to think of $\mathbf{F}$ as an $\infty\times n$ matrix, which is consistent with the definitions that $\mathbf{F}\mathbf{z}$ is a function ($\infty\times 1$), $\mathbf{F}^T g$ is a vector ($n\times 1$), and $\mathbf{F}^T\mathbf{F}$ is a matrix ($n \times n$). When infinite dimensions combine in a product, we use integrals rather than sums.

9.4.2Normal equations¶

The discrete linear least-squares problem of minimizing $\| \mathbf{y} - \mathbf{V} \mathbf{c} \|_2$ over all possible $\mathbf{c}$, given matrix $\mathbf{V}$ and data vector $\mathbf{y}$, has a solution via the normal equations (3.2.3),

We can now reinterpret (9.4.11) in terms of quasimatrices.

There is no need to supply a proof of Theorem 9.4.1 because it will read exactly the same as for the discrete normal equations. All the effort has gone into making definitions that set up a perfect analogy. In retrospect, all we needed in the original discrete case were linear combinations and inner products.

9.4.3Legendre polynomials¶

Equation (9.4.13) becomes much simpler if $\mathbf{V}^T\mathbf{V}$ is diagonal. By our definitions, this would imply that the columns of $\mathbf{V}$ are mutually orthogonal in the sense of the function inner product. This is not the case for the monomial functions $x^j$. But there are orthogonal polynomials which do satisfy this property.

For what follows, let $\mathcal{P}_n \subset S$ be the set of polynomials of degree $n$ or less.

Here are some key facts that are straightforward to prove.

Now let us define the quasimatrix

Then $\mathbf{L}_n^T\mathbf{L}_n=\mathbf{I}$. The normal equations (9.4.13) thus simplify accordingly. Unraveling the definitions, we find the least-squares solution

9.4.4Chebyshev polynomials¶

Equation (9.4.1) is not the only useful way to define an inner product on a function space. It can be generalized to

for a positive function $w(x)$ called the weight function of the inner product. An important special case is

Chebyshev polynomials also have a startling alternative form,

The results from Theorem 9.4.2 apply to Chebyshev polynomials as well, with orthogonality being in the sense of (9.4.23). Their Gram matrix is given by

The least-squares solution is not the same in the Legendre and Chebyshev cases: both find the nearest approximation to a given $f(x)$, but the norm used to measure distances is not the same.

9.4.5Roots of orthogonal polynomials¶

Interesting properties can be deduced entirely from the orthogonality conditions. The following result will be relevant in Spectrally accurate integration. The same result holds for orthogonal polynomial families with different weight functions, such as the Chebyshev polynomials.

The result of Theorem 9.4.3 holds for orthogonal families of polynomials for other weight functions. The Chebyshev case is unusual in that thanks to (9.4.25), the roots of $T_n$ are known explicitly:

These are known as the Chebyshev points of the first kind. The chief difference between first-kind and second-kind points is that the latter type include the endpoints $\pm 1$. Both work well for polynomial interpolation and give spectral convergence.

9.4.6Least squares versus interpolation¶

Both interpolation and the solution of a linear least-squares problem produce a projection of a function into the space of polynomials $\mathcal{P}_n$. In the least-squares case, the close connection with inner products and orthogonality makes the 2-norm, perhaps with a weight function, a natural setting for analysis. Because a constant weight function is the simplest choice, Legendre polynomials are commonly used for least squares.

Interpolation has no easy connection to inner products or the 2-norm. With interpolants a different kind of approximation analysis is more fruitful, often involving the complex plane, in which the max-norm is the natural choice. For reasons beyond the scope of this text, Chebyshev polynomials are typically the most convenient to work with in this context.

9.4.7Exercises¶

1. ✍ Let $\mathbf{F}$ be the quasimatrix $\bigl[\, \underline{1} \quad\! \underline{\cos(\pi x)}\quad\! \underline{\sin(\pi x)}\,\bigr]$ for $x\in[-1,1]$.

   (a) Find $\mathbf{F}^T e^x$.

   (b) Find $\mathbf{F}^T \mathbf{F}$.

2. ✍ (a) Find the best linear approximation in the least-squares sense to the function $\sin(x)$ on $[-1,1]$.

   (b) Using Theorem 9.4.1, explain why the best fitting quadratic polynomial will be the linear function you found in part (a). (Note: You do not need to carry out the complete calculation.)

3. (a) ✍ ⌨ Use (9.4.18) to write out $P_2(x)$ and $P_3(x)$. Plot $P_0,P_1,P_2,P_3$ on one graph for $-1\le x \le 1$. (You may find it interesting to compare to the graph in Exercise 3.3.3.)

   (b) ✍ ⌨ Use (9.4.24) to write out $T_2(x)$ and $T_3(x)$. Plot $T_0,T_1,T_2,T_3$ on one graph for $-1\le x \le 1$.

4. ✍ Use (9.4.18) to show that $P_n(x)$ is an odd function if $n$ is odd and an even function if $n$ is even.

5. ⌨ Using (9.4.18), write a function legpoly(x,n) that returns a matrix whose columns are the Legendre polynomials $P_0,P_1,\ldots,P_n$ evaluated at all the points in the vector $x$. Then use your function to plot $P_0,P_1,P_2,P_3$ on one graph.

6. ⌨ (Continuation of previous problem.) Choose 1600 evenly spaced points in $[-1,1]$. For $n=1,2,\ldots,16$, use this vector of points and the function legpoly to construct a $1600\times (n+1)$ matrix that discretizes the quasimatrix

   $$\mathbf{A}_n = \begin{bmatrix} \underline{P_0} & \underline{P_1} & \cdots & \underline{P_{n}} \end{bmatrix}.$$

   (9.4.30)

   Make a table of the matrix condition number $\kappa(\mathbf{A}_n)$ as a function of $n$. (These will not be much larger than 1, showing that the Legendre polynomials are a good basis set.)

7. ⌨ Using (9.4.25), write a function chebpoly that returns a matrix whose columns are the Chebyshev polynomials $T_0,T_1,\ldots,T_n$ evaluated at all the points in the vector $x$. Then use your function to plot $T_0,T_1,T_2,T_3$ on one graph.

8. (a) ✍ Use (9.4.25) to show that the first-kind points (9.4.29) are roots of $T_n$.

   (b) ✍ Use (9.4.25) to show that the second-kind points (9.3.2) are local extreme points of $T_n$.

9. ✍ Show that the definition (9.4.25) satisfies the recursion relation in (9.4.24).

10. ✍ Use (9.4.25) to show that $\langle T_0,T_0 \rangle=\pi$ and $\langle T_k,T_k \rangle=\pi/2$ for $k>0$ in the Chebyshev-weighted inner product. (Hint: Change to the variable θ.)