Orthogonal Polynomials and Least Squares Approximation

Section 6.3 Orthogonal Polynomials and Least Squares Approximation

Let’s say that we have a function $f(x)$ on an interval $[a,b]\text{.}$ We wish to find a polynomial $P_{n}(x)$ that approximates $f$ on the interval. A mathematical statement of this is that we wish to minimize

\begin{equation*} \int_{a}^{b} \left(f(x)-P_{n}(x)\right)^{2} \,dx = ||f-P_{n}||_{2}^2 \end{equation*}

🔗

If we let $P_{n}(x)$ be a general $n$th order polynomial, then

\begin{equation*} \begin{aligned}P_{n}(x)\amp = \sum_{k=0}^{n} a_{k} x^{k}\end{aligned} \end{equation*}

🔗

Then we wish to minimize

\begin{equation*} \begin{aligned}E(a_{0},a_{1},\ldots, a_{n})\amp = \int_{a}^{b} \biggl( f(x) - \sum_{k=0}^{n} a_{k} x^{k} \biggr)^{2} \, dx \\ \amp \qquad \text{which can be written as}\\ \amp = \int_{a}^{b} \bigl(f(x))^{2} \, dx - 2 \sum_{k=0}^{n} a_{k} \int_{a}^{b} x^{k} f(x) \, dx + \int_{a}^{b} \biggl( \sum_{k=0}^{n} a_{k} x^{k} \biggr)^{2} \, dx \\ \amp \qquad \text{and differentiating we obtain,}\\ \frac{\partial E}{\partial a_{j}}\amp = -2 \int_{a}^{b} x^{j} f(x) \, dx + 2 \sum_{k=0}^{n} a_{k} \int_{a}^{b} x^{j+k}\, dx.\end{aligned} \end{equation*}

and the minimum occurs when $\partial E/\partial a_{k}=0$ for all $k$ or

\begin{equation} \sum_{k=0}^{n} a_{k} \int_{a}^{b} x^{j+k}\, dx = \int_{a}^{b} x^{j} f(x) \, dx\tag{6.3.1} \end{equation}

🔗

These are called the normal equations. Since

\begin{equation} \int_{a}^{b} x^{j} \, dx = \frac{b^{j+1}-a^{j+1}}{j+1}\tag{6.3.2} \end{equation}

the normal equations in (6.3.1) form an $(n+1) \times (n+1)$ linear system in the unknown $a$’s. The elements of the matrix have the form in (6.3.2) and solving a system with such elements is numerically unstable due to rounding errors, thus finding the coefficients of the polynomial $P_{n}(x)$ is not usually a desired way to go.

🔗

Despite this, we will show an interpolation using this form for $f(x)=e^{x}$ on $[0,1]$ in the next example.

🔗

Example 6.3.1.

Use the normal equations in (6.3.1) to find $P_{2}(x)$ that interpolates $f(x)=e^{x}$ on $[0,1]\text{.}$

🔗

Solution.

The equations form the linear equations:

\begin{equation*} \begin{aligned}a_{0} + \frac{1}{2}a_{1} + \frac{1}{3}a_{2}\amp = \int_{0}^{1} e^{x} \,dx = e-1\\ \frac{1}{2}a_{0} + \frac{1}{3}a_{1} + \frac{1}{4}a_{2}\amp = \int_{0}^{1} x e^{x} \, dx = 1\\ \frac{1}{3}a_{0} + \frac{1}{4}a_{1} + \frac{1}{5}a_{2}\amp = \int_{0}^{1} x^{2} e^{x} \, dx = e-2\\\end{aligned} \end{equation*}

the solution to this (using exact precision is),

\begin{equation*} \begin{aligned} a_{0}\amp = -105+39e,\amp a_{1}\amp = 588-216e,\amp a_{2}\amp = -570+210e. \end{aligned} \end{equation*}

🔗

A plot of this polynomial,

\begin{equation*} P_{2}(x) = -105+39e + (588-216e) x +(-570+210e) x^{2} \end{equation*}

and $f(x)=e^{x}$ is

🔗

Figure 6.3.2.

🔗

Clearly, the approximation looks good by the "eye"-test.

🔗

The example above found the interpolating polynomial that minimizes $||f-P_{2}||_{2}\text{,}$ however due to the form of the matrix, numerically, this is a poor way find the polynomial.

🔗

Instead, we will use orthogonal polynomials to construct the interpolating polynomial. This has many advantages.

🔗

Subsection 6.3.1 Orthogonal Polynomials

Finding the coefficients of a set of orthogonal polynomials is relatively straightforward with this theorem.

🔗

Theorem 6.3.3.

If $\{\phi_{0},\phi_{1},\phi_{2}, \ldots, \phi_{n}\}$ is an orthogonal set of functions on $[a,b]$ with respect to the weight function $w\text{,}$ then $n$th degree polynomial

\begin{equation*} P_{n}(x) = \sum_{k=0}^{n} a_{k} \phi_{k}(x) \end{equation*}

minimizes $||f-P_{n}||_{w}^2$ where for each $k=0,1,2,\ldots, n\text{,}$

\begin{equation*} a_{k} = \frac{\langle f(x), \phi_k(x) \rangle_w}{ \langle \phi_k, \phi_k \rangle_w} = \frac{ \int_{a}^{b} f(x) w(x) \phi_{j} (x) \, dx}{\int_{a}^{b} w(x) \phi_{j}^{2} \, dx} \end{equation*}

🔗

Proof.

Since $\{\phi_{0},\phi_{1},\phi_{2}, \ldots, \phi_{n}\}$ is an orthogonal set of functions, then

\begin{equation*} \langle \phi_{i} , \phi_{j} \rangle = 0 \qquad \text{for all $i \neq j$.} \end{equation*}

🔗

Since

\begin{equation*} \begin{aligned}E\amp = ||f-P_{n}||_{w}^2 = \biggl\vert\biggl\vert f(x) - \sum_{k=0}^{n} a_{k} \phi_{k}(x) \biggr\vert\biggr\vert^2 \\ \amp = \langle f(x) - \sum_{k=0}^n a_k \phi_k, f(x) - \sum_{k=0}^n a_k \phi_k \rangle \end{aligned} \end{equation*}

The minimum occurs when $\partial E /\partial a_{j}=0\text{,}$ so

\begin{equation*} \begin{aligned} \frac{\partial E}{\partial a_{j}} \amp = \langle f(x) - \sum_{k=0}^n a_k \phi_k, - \phi_j \rangle_w + \langle - \phi_j, f(x) - \sum_{k=0}^n a_k \phi_k \rangle_w \\ \amp = -2 \langle f(x) - \sum_{k=0}^n a_k \phi_k, \phi_j \rangle_w = -2 \left( \langle f(x), \phi_j \rangle - \sum_{k=0}^n a_k \langle \phi_k, \phi_j \rangle\right) \\ \amp = -2 \left( \langle f(x), \phi_j \rangle - a_k \langle \phi_j, \phi_j \rangle \right) \end{aligned} \end{equation*}

where on the last step the fact of $\langle \phi_k, \phi_j \rangle = 0$ when $k \neq j\text{.}$

🔗

Solving for $a_j\text{,}$

\begin{equation*} a_j = \frac{ \int_{a}^{b} f(x) w(x) \phi_{j} (x) \, dx}{\int_{a}^{b} w(x) \phi_{j}^{2} \, dx} \end{equation*}

🔗

This shows that if we have a set of orthogonal functions, then this theorem provides a way to find the polynomial that minimizes $||f-P_{n}||_{w}\text{.}$ After the next section, we will show an example.

🔗

Subsection 6.3.2 The Gram-Schmidt process for Orthogonalizing Polynomials

As alluded to above, it is desirable to use orthogonal polynomials (with respect to some weight). The following is called the Gram-Schmidt process for doing this.

🔗

Theorem 6.3.4.

The set of polynomial functions $\{ \phi_{0}, \phi_{1}, \phi_{2}\, \ldots \phi_{n}\}$ defined in the following way is orthogonal on $[a,b]$ with respect to weight function $w(x)\text{.}$

🔗

Let $\phi_{0} \equiv 1$ and $\phi_1 = x-B_{1}$ where

\begin{equation} B_{1} = \frac{\int_{a}^{b} x w(x)\, dx}{\int_{a}^{b} w(x) \, dx}\tag{6.3.3} \end{equation}

and when $k\geq 2\text{,}$

\begin{equation} \phi_{k}(x) = (x-B_{k})\phi_{k-1}(x) - C_{k}\phi_{k-2}(x),\tag{6.3.4} \end{equation}

where

\begin{equation} B_{k} = \frac{\int_{a}^{b} x w(x) \phi_{k-1}^2\, dx}{\int_{a}^{b} w(x) \phi_{k-1}^2 \, dx}\tag{6.3.5} \end{equation}

and

\begin{equation} C_{k} = \frac{\int_{a}^{b} x w(x) \phi_{k-1} \phi_{k-2}\, dx}{\int_{a}^{b} w(x) \phi_{k-2}^2 \, dx}\tag{6.3.6} \end{equation}

🔗

Proof.

We will show that $\langle \phi_{k}, \phi_{j} \rangle = 0$ for all $j \lt k\text{.}$ We will do this by induction on $k\text{.}$ For the base case,

\begin{equation*} \begin{aligned} \langle \phi_{1}, \phi_{0} \rangle \amp = \int_a^b w(x) (1)(x-B_1) \, dx \\ \amp = \int_a^b x w(x) \, dx - B_1 \int_a^b w(x) \,dx \\ \amp = \int_a^b x w(x) \,dx - \left( \frac{\int_{a}^{b} x w(x)\, dx}{\int_{a}^{b} w(x) \, dx}\right) \int_a^b w(x) \,dx = 0 \end{aligned} \end{equation*}

🔗

Assume that $\langle \phi_{i}, \phi_{j} \rangle = 0$ for all $i \neq j\text{.}$ To show the induction there are two cases. For the first case,

\begin{equation*} \begin{aligned} \langle \phi_k, \phi_{k-1} \rangle \amp = \int_{a}^{b} w(x) \bigl((x-B_{k})\phi_{k-1}(x) - C_{k}\phi_{k-2}(x)\bigr) \phi_{k-1}(x) \, dx\\ \amp = \int_a^b w(x) x \phi_{k-1}^2 \,dx - B_k \int_a^bw(x) \phi_{k-1}^2 \,dx - C_k \int_a^b w(x) \phi_{k-1} \phi_{k-2} \end{aligned} \end{equation*}

where (6.3.4) is used in the first step. Also, the third term above is 0 since $\langle \phi_{k-1}, \phi_{k-2}\rangle = 0 \text{.}$ Then substituting $B_k$ from (6.3.5),

\begin{equation*} \begin{aligned} \langle \phi_k, \phi_{k-1} \rangle \amp = \int_a^b w(x) x \phi_{k-1}^2 \,dx - \left(\frac{\int_{a}^{b} x w(x) \phi_{k-1}^2\, dx}{\int_{a}^{b} w(x) \phi_{k-1}^2 \, dx}\right) \int_a^bw(x) \phi_{k-1}^2 \,dx \end{aligned} \end{equation*}

which is 0 after canceling terms. Then,

\begin{equation*} \begin{aligned} \langle \phi_k, \phi_{k-2} \rangle \amp = \int_{a}^{b} w(x) \bigl((x-B_{k})\phi_{k-1}(x) - C_{k}\phi_{k-2}(x)\bigr) \phi_{k-2}(x) \, dx\\ \amp =\int_a^b w(x) x \phi_{k-1}\phi_{k-2} \, dx - B_k \int_a^b w(x) \phi_{k-1}\phi_{k-2} \, dx - C_k \int_a^b w(x) \phi_{k-2}^2 \, dx \end{aligned} \end{equation*}

For this case, the 2nd terms is zero because $\langle \phi_{k-1}, \phi_{k-2}\rangle = 0$ and then using (6.3.6),

\begin{equation*} \begin{aligned} \langle \phi_k, \phi_{k-2} \rangle \amp = \int_a^b w(x) x \phi_{k-1}\phi_{k-2} \, dx - \left( \frac{\int_{a}^{b} x w(x) \phi_{k-1} \phi_{k-2}\, dx}{\int_{a}^{b} w(x) \phi_{k-2}^2 \, dx}\right) \int_a^b w(x) \phi_{k-2}^2 \, dx \end{aligned} \end{equation*}

which is 0 after canceling terms.

🔗

The last case is when $j \leq k-2$ or

\begin{equation*} \begin{aligned} \langle \phi_k, \phi_j \rangle \amp = \int_{a}^{b} w(x) \bigl((x-B_{k})\phi_{k-1}(x) - C_{k}\phi_{k-2}(x)\bigr) \phi_{j}(x) \, dx\\ \amp = \int_a^b x w(x) \phi_{k-1} \phi_{j} \, dx - B_k \int_a^b w(x) \phi_{k-1}\phi_j \, dx - C_k \int_a^b w(x) \phi_{k-2} \phi_j \end{aligned} \end{equation*}

At this point, the 2nd and 3rd integrals are zero from orthogonality. The first integral can be interpreted as the inner product between $\phi_{k-1}$ and a polynomial of degree $j+1$ and since $j \leq k-2\text{,}$ then this is a smaller degree and a consequence of orthogonality is that any polynomial is orthogonal to any lower degree polynomial so the first term is also 0.

🔗

We saw the Legendre polynomials in Section 5.4 on Gaussian Quadrature and we now revisit them in a different context. The following example will show that the Legendre polynomials form an orthogonal set of functions with respect to $w(x) \equiv 1\text{.}$

🔗

Example 6.3.5.

Find the first 4 polynomials that are orthogonal with respect to the weight function $w(x) \equiv 1$ on $[-1,1]$ using the Gram-Schmidt process.

🔗

Solution.

\begin{equation*} \begin{aligned}\phi_{0}\amp \equiv 1,\amp \phi_{1}\amp = x-B_{1}\end{aligned} \end{equation*}

where

\begin{equation*} B_{1} = \frac{\int_{-1}^{1} x(1)^{2} \, dx}{\int_{-1}^{1} (1)^{2} \, dx}= 0 \end{equation*}

so $\phi_{1}=x\text{.}$ Also,

\begin{equation*} \begin{aligned} B_{2}\amp = \frac{\int_{-1}^{1} x^{3} \, dx}{\int_{-1}^{1} x^{2} \, dx}= 0\amp C_{2}\amp = \frac{\int_{-1}^{1} x^{2} \, dx}{\int_{-1}^{1}1 \, dx}= \frac{1}{3}\end{aligned} \end{equation*}

\begin{equation*} \begin{aligned}\phi_{2}\amp = (x-B_{2}) \phi_{1} - C_{2} \phi_{0} = (x-0)x - \frac{1}{3}\cdot 1 = x^{2} - \frac{1}{3}\end{aligned} \end{equation*}

and then

\begin{equation*} \begin{aligned}B_{3}\amp = \frac{\int_{-1}^{1} x (x^{2}-1/3)^{2} \, dx}{\int_{-1}^{1} (x^{2}-1/3)^{2} \, dx}= 0\amp C_{3}\amp = \frac{\int_{-1}^{1} x (x^{2}-1/3)x \, dx}{\int_{-1}{1}x^{2} \, dx}= \frac{4}{15}\end{aligned} \end{equation*}

\begin{equation*} \begin{aligned}\phi_{3}(x)\amp = (x-B_{3})\phi_{2} - C_{3}\phi_{1} = (x-0)(x^{2}-1/3)- \frac{4}{15}x = x^{3}- \frac{3}{5}x\end{aligned} \end{equation*}

🔗

Recall from Section 5.4 that the interpolation points for the 2-pt Gaussian Quadrature formula are the roots of $\phi_{2}$ and that for the 3-pt formula was the roots of $\phi_{3}\text{.}$

🔗

And now that the Legendre Polynomials have been found, we will use them to do interpolation.

🔗

Example 6.3.6.

Use the set $\{\phi_{0},\phi_{1},\phi_{2},\phi_{3}\}$ found above to find the interpolating polynomial $P_{3}(x)$ that minimizes $||f-P_{3}||$ with weight function $w(x)\equiv 1$ where $f(x) = \cos (\pi x/2)\text{.}$

🔗

In this case, we will use Theorem 6.3.3 to find the coefficients of

\begin{equation*} P_{3}(x) = a_{0} \phi_{0} + a_{1} \phi_{1} + a_{2} \phi_{2} + a_{3} \phi_{3} \end{equation*}

where

\begin{equation*} \begin{aligned}a_{k}\amp = \frac{\int_{a}^{b} w(x) \phi_{k}(x) f(x) \, dx}{\int_{a}^{b} w(x) \bigl(\phi_{k}(x)\bigr)^{2} \, dx}\end{aligned} \end{equation*}

that is,

\begin{equation*} \begin{aligned}a_{0}\amp = \frac{\int_{-1}^{1} \cos (\pi x/2) \, dx }{\int_{-1}^{1} 1 \cdot (1)^{2} \, dx}= \frac{2}{\pi}\\ a_{1}\amp = \frac{\int_{-1}^{1} x \cos (\pi x/2) \, dx }{\int_{-1}^{1} 1 \cdot (x)^{2} \, dx}= 0 \\ a_{2}\amp = \frac{\int_{-1}^{1} (x^{2}-1/3) \cos (\pi x/2) \, dx }{\int_{-1}^{1} 1 \cdot (x^{2}-1/3)^{2} \, dx}= \frac{15(\pi^{2}-12)}{\pi^{3}}\\ a_{3}\amp = \frac{\int_{-1}^{1} (x^{3}-3x/5) \cos (\pi x/2) \, dx }{\int_{-1}^{1} 1 \cdot (x^{3}-3x/5)^{2} \, dx}= 0 \\\end{aligned} \end{equation*}

and the polynomial is

\begin{equation*} P_{3}(x) = \frac{2}{\pi}+ \frac{15(\pi^{2}-12)}{\pi^{3}}\biggl( x^{2}-\frac{1}{3}\biggr) \end{equation*}

🔗

A good way to determine if the above function is correct to plot $P_{3}(x)$ and $\cos x$ together as the following shows:

🔗

Figure 6.3.7.

🔗

where the dashed curve is the polynomial. As one can see these are nearly identical as a plot.

🔗

The main purpose of this section is to show that there is a way to produce a set of orthogonal polynomials and then use them to produce a polynomial that minimizes a weighted norm. In the next section, we examine which norm may be the best.

🔗

Prev Top Next