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*} \begin{aligned}\int_{a}^{b} \bigl(f(x)-P_{n}(x))^{2} \,dx = ||f-P_{n}||_{2}\end{aligned} \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.

🔗

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

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}$ where for each $k=0,1,2,\ldots, n\text{,}$

\begin{equation*} a_{k} = \frac{1}{\alpha_{k}}\int_{a}^{b} w(x) \phi_{k}(x) f(x) \, dx \end{equation*}

where

\begin{equation*} \alpha_{k} = \int_{a}^{b} w(x) \bigl(\phi_{k}(x)\bigr)^{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} = \biggl\vert\biggl\vert f(x) - \sum_{k=0}^{n} a_{k} \phi_{k}(x) \biggr\vert\biggr\vert \\\amp = \int_{a}^{b} w(x) \biggl( f(x) - \sum_{k=0}^{n} a_{k} \phi_{k}(x) \biggr)^{2} \, dx\end{aligned} \end{equation*}

setting $\partial E /\partial a_{j}=0$ we get, the normal equations,

\begin{equation*} \frac{\partial E}{\partial a_{j}} = -2 \int_{a}^{b} w(x) f(x) \phi_{j} (x) \, dx + 2 \sum_{k=0}^{n} a_{k} \int_{a}^{b} w(x) \phi_{i}(x) \phi_{j}(x) \, dx \\ \end{equation*}

and since $\int_{a}^{b} w(x) \phi_{j}\phi_{k} \, dx = 0$ if $j \neq k\text{,}$ then solving for $a_{j}$ results in

\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_{2} = x-B_{1}$ where

\begin{equation*} B_{1} = \frac{\int_{a}^{b} x w(x) \bigl(\phi_{0}(x)\bigr)^{2}\, dx}{\int_{a}^{b} w(x) \bigl(\phi_{0}(x)\bigr)^{2} \, dx} \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), \end{equation*}

where

\begin{equation*} \begin{aligned}B_{k}\amp = \frac{\int_{a}^{b} x w(x) \bigl(\phi_{k-1}(x)\bigr)^{2}\, dx}{\int_{a}^{b} w(x) \bigl(\phi_{k-1}(x)\bigr)^{2} \, dx}\\ \amp \qquad \text{and}\\ C_{k}\amp = \frac{\int_{a}^{b} x w(x) \phi_{k-1}(x) \phi_{k-2}\, dx}{\int_{a}^{b} w(x) \bigl(\phi_{k-2}(x)\bigr)^{2} \, dx}\end{aligned} \end{equation*}

🔗

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