An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: Gaussian Quadrature

Since integration of functions is difficult, approximation techniques for definite integrals are very important. In calculus we are introduced to various methods, e.g., the midpoint, trapezoid, and Simpson's rule, for approximating definite integrals. These methods divide the interval of integration into subintervals and then use values of the integrand at the endpoints to approximate the integral. These are useful methods when approximating integrals from tabulated data, but there are better methods for other types of integrands. If we make judicious choices in the points we use to evaluate the integrand, we can obtain more accurate results with less work. One such method is Gaussian quadrature (which, for example, is widely used in solving problems of radiation heat transfer in direct integration of the equation of transfer of radiation over space), which we explore later in this section. This method utilizes the Gram-Schmidt process to produce orthogonal polynomials.

Subsection Introduction

We have seen that orthogonal bases make computations very convenient, and the Gram-Schmidt process allowed us to create orthogonal bases in \(\R^n\) using the dot product as inner product. In this section we will see how the Gram-Schmidt process works in any inner product space.

Subsection The Gram-Schmidt Process using Inner Products

Our goal is to understand how the Gram-Schmidt process works in any inner product space.

Preview Activity 36.1 shows the first steps of the Gram-Schmidt process to construct an orthogonal basis from any basis of an inner product space. To understand how the process works in general, let \(\{\vv_1, \vv_2, \ldots, \vv_m\}\) be a basis for a subspace \(W\) of an inner product space \(V\text{.}\) Let \(\vw_1 = \vv_1\) and let \(W_1 = \Span\{\vw_1\}\text{.}\) Since \(\vw_1 = \vv_1\) we have that \(W_1 = \Span\{\vw_1\} = \Span\{\vv_1\}\text{.}\) Now consider the subspace

of \(W\text{.}\) The vectors \(\vv_1 = \vw_1\) and \(\vv_2\) are possibly not orthogonal, but we know the orthogonal projection of \(\vv_2\) onto \(W_1^{\perp}\) is orthogonal to \(\vw_1\text{.}\) Let

Then \(\{\vw_1, \vw_2\}\) is an orthogonal set. Note that \(\vw_1 = \vv_1 \neq \vzero\text{,}\) and the fact that \(\vv_2 \notin W_1\) implies that \(\vw_2 \neq \vzero\text{.}\) So the set \(\{\vw_1, \vw_2\}\) is linearly independent, being a set of non-zero orthogonal vectors. Now the question is whether \(\Span\{\vw_1,\vw_2\} = \Span\{\vv_1,\vv_2\}\text{.}\) Note that \(\vw_2\) is a linear combination of \(\vv_1\) and \(\vv_2\text{,}\) so \(\vw_2\) is in \(\Span\{\vv_1,\vv_2\}\text{.}\) Since \(\Span\{\vw_1,\vw_2\}\) is a 2-dimensional subspace of the 2-dimensional space \(W_2\text{,}\) it must be true that \(\Span\{\vw_1,\vw_2\} = W_2 = \Span\{\vv_1,\vv_2\}\text{.}\)

Now we take the next step, adding \(\vv_3\) into the mix. Let

The vector

is orthogonal to both \(\vw_1\) and \(\vw_2\) and, by construction, \(\vw_3\) is a linear combination of \(\vv_1\text{,}\) \(\vv_2\text{,}\) and \(\vv_3\text{.}\) So \(\vw_3\) is in \(W_3\text{.}\) The fact that \(\vv_3 \notin W_2\) implies that \(\vw_3 \neq \vzero\) and \(\{\vw_1, \vw_2, \vw_3\}\) is a linearly independent set. Since \(\Span\{\vw_1, \vw_2, \vw_3\}\) is a 3-dimensional subspace of the 3-dimensional space \(W_3\text{,}\) we conclude that \(\Span\{\vw_1, \vw_2, \vw_3\}\) equals \(\Span\{\vv_1,\vv_2,\vv_3\}\text{.}\)

We continue inductively in this same manner. If we have constructed a set \(\{\vw_1\text{,}\) \(\vw_2\text{,}\) \(\vw_3\text{,}\) \(\ldots\text{,}\) \(\vw_{k-1}\}\) of \(k-1\) orthogonal vectors such that

then we let

where

We know that \(\vw_k\) is orthogonal to \(\vw_1\text{,}\) \(\vw_2\text{,}\) \(\ldots\text{,}\) \(\vw_{k-1}\text{.}\) Since \(\vw_1\text{,}\) \(\vw_2\text{,}\) \(\ldots\text{,}\) \(\vw_{k-1}\text{,}\) and \(\vv_k\) are all in \(W_k = \Span\{\vv_1, \vv_2, \ldots, \vv_k\}\) we see that \(\vw_k\) is also in \(W_k\text{.}\) Since \(\vv_k \notin W_{k-1}\) implies that \(\vw_k \neq \vzero\) and \(\{\vw_1, \vw_2, \ldots, \vw_k\}\) is a linearly independent set. Then \(\Span\{\vw_1, \vw_2, \vw_3, \ldots, \vw_{k}\}\) is a \(k\)-dimensional subspace of the \(k\)-dimensional space \(W_k\text{,}\) so it follows that

This process will end when we have an orthogonal set \(\{\vw_1\text{,}\) \(\vw_2\text{,}\) \(\vw_3\text{,}\) \(\ldots\text{,}\) \(\vw_{m}\}\) with \(\Span\{\vw_1\text{,}\) \(\vw_2\text{,}\) \(\vw_3\text{,}\) \(\ldots\text{,}\) \(\vw_{m}\}\) = \(W\text{.}\)

We summarize the process in the following theorem.

The Gram-Schmidt process builds an orthogonal basis \(\{\vw_1, \vw_2, \vw_3, \ldots, \vw_{m}\}\) for us from a given basis. To make an orthonormal basis \(\{\vu_1, \vu_2, \vu_3, \ldots, \vu_{m}\}\text{,}\) all we need do is normalize each basis vector: that is, for each \(i\text{,}\) we let

Subsection Examples

What follows are worked examples that use the concepts from this section.

Example 36.3.

Consider the space \(V = C[0,1]\) with inner product \(\langle f,g \rangle = \int_0^1 f(x)g(x) \ dx\text{.}\)

(a)

Find the polynomial in \(\pol_2\) (considered as a subspace of \(V\)) that is closest to \(h(x) = \sqrt{x}\text{.}\) Use technology to calculate any required integrals. Draw a graph of your approximation against the graph of \(h\text{.}\)

Solution.

Our job is to find \(\proj_{\pol_2} h(x)\text{.}\) To do this, we need an orthogonal basis of \(\pol_2\text{.}\) We apply the Gram-Schmidt process to the standard basis \(\{1, t, t^2\}\) of \(\pol_2\) to obtain an orthogonal basis \(\{p_1(t), p_2(t), p_3(t)\}\) of \(\pol_2\text{.}\) We start with \(p_1(t) = 1\text{,}\) then

\begin{align*} p_2(t) \amp = t - \frac{\left\langle t,1 \right\rangle}{\langle 1,1 \rangle} (1)\\ \amp = t - \frac{1}{2} \end{align*}

and

\begin{align*} p_3(t) \amp = t^2 - \frac{\left\langle t^2,1 \right\rangle}{\langle 1,1 \rangle} (1) - \frac{\left\langle t^2,t-\frac{1}{2} \right\rangle}{\left\langle t-\frac{1}{2},t-\frac{1}{2} \right\rangle} \left(t-\frac{1}{2}\right)\\ \amp = t^2 - \frac{1}{3} - \frac{\frac{1}{12}}{\frac{1}{12}}\left(t-\frac{1}{2}\right)\\ \amp = t^2-t + \frac{1}{6}\text{.} \end{align*}

Then

\begin{align*} \proj_{\pol_2} \sqrt{x} \amp = \frac{\left\langle \sqrt{x},1 \right\rangle}{\langle 1,1 \rangle} (1) + \frac{\left\langle \sqrt{x},x-\frac{1}{2} \right\rangle}{\left\langle x-\frac{1}{2},x-\frac{1}{2} \right\rangle} \left(x-\frac{1}{2}\right)\\ \amp \qquad + \frac{\left\langle \sqrt{x}, x^2-x + \frac{1}{12} \right\rangle}{\left\langle x^2-x + \frac{1}{6}, x^2-x + \frac{1}{6} \right\rangle} \left( x^2-x + \frac{1}{6}\right)\\ \amp = \frac{\frac{2}{3}}{1}(1) + \frac{\frac{1}{15}}{\frac{1}{12}} \left(x-\frac{1}{2}\right) - \frac{\frac{1}{315}}{\frac{1}{180}} \left(x^2-x + \frac{1}{6}\right)\\ \amp = \frac{2}{3} + \left(\frac{4}{5}\right)\left(x-\frac{1}{2}\right) - \frac{4}{7}\left(x^2-x + \frac{1}{6}\right)\\ \amp = -\frac{4}{7}x^2 + \frac{48}{35}x + \frac{6}{35}\text{.} \end{align*}

A graph of the approximation and \(h\) are shown in Figure 36.4

(b)

Provide a numeric measure of the error in approximating \(\sqrt{x}\) by the polynomial you found in part (a).

Solution.

The norm of \(\proj_{\pol_2^{\perp}} \sqrt{x} = \sqrt{x} - \left(-\frac{4}{7}x^2 + \frac{48}{35}x + \frac{6}{35}\right)\) tells us how well our projection \(-\frac{4}{7}x^2 + \frac{48}{35}x + \frac{6}{35}\) approximates \(\sqrt{x}\text{.}\) Technology shows that

\begin{equation*} ||\proj_{\pol_2^{\perp}} \sqrt{x}|| = \sqrt{ \langle \proj_{\pol_2^{\perp}} \sqrt{x}, \proj_{\pol_2^{\perp}} \sqrt{x}\rangle } = \frac{\sqrt{2}}{70} \approx 0.02\text{.} \end{equation*}

Subsection Summary

• The Gram-Schmidt process produces an orthogonal basis from any basis. It works as follows. Let \(\{\vv_1, \vv_2, \ldots, \vv_m\}\) be a basis for a subspace \(W\) of \(\R^n\text{.}\) The set \(\{\vw_1\text{,}\) \(\vw_2\text{,}\) \(\vw_3\text{,}\) \(\ldots\text{,}\) \(\vw_{m}\}\) defined by

  • \(\vw_1 = \vv_1\text{,}\)

  • \(\vw_2 = \vv_2 - \ds \frac{\vv_2 \cdot \vw_1}{\vw_1 \cdot \vw_1} \vw_1\text{,}\)

  • \(\vw_3 = \vv_3 - \ds \frac{ \vv_3 \cdot \vw_1 }{ \vw_1 \cdot \vw_1 } \vw_1 - \frac{ \vv_3 \cdot \vw_2 }{ \vw_2 \cdot \vw_2 } \vw_2\text{,}\) \(\vdots\)

  • \(\vw_m = \vv_m - \ds \frac{ \vv_m \cdot \vw_1 }{ \vw_1 \cdot \vw_1 } \vw_1 - \frac{ \vv_m \cdot \vw_2 }{ \vw_2 \cdot \vw_2 } \vw_2 - \cdots - \frac{ \vv_m \cdot \vw_{m-1} }{ \vw_{m-1} \cdot \vw_{m-1} } \vw_{m-1}\text{.}\)

  is an orthogonal basis for \(W\text{.}\) Moreover,

  \begin{equation*} \Span\{\vw_1, \vw_2, \vw_3, \ldots, \vw_{k}\} = \Span\{\vv_1,\vv_2,\vv_3, \ldots, \vv_{k}\} \end{equation*}

  for each \(k\) between 1 and \(m\text{.}\)

Subsection Project: Gaussian Quadrature and Legendre Polynomials

Simpson's rule is a reasonably accurate method for approximating definite integrals since it models the integrand on subintervals with quadratics. For that reason, Simpson's rule provides exact values for integrals of all polynomials of degree less than or equal to 2. In Gaussian quadrature, we will use a family of polynomials to determine points at which to evaluate an integral of the form \(\int_{-1}^1 f(t) \ dt\text{.}\) By allowing ourselves to select evaluation points that are not uniformly distributed across the interval of integration, we will be able to approximate our integrals much more efficiently. The method is constructed so as to obtain exact values for as large of degree polynomial integrands as possible. As a result, if we can approximate our integrand well with polynomials, we can obtain very good approximations with Gaussian quadrature with minimal effort.

The Gaussian quadrature approximation has the form

where the \(w_i\) (weights) and the \(t_i\) (nodes) are points in the interval \([-1,1]\)⁶². Gaussian quadrature describes how to find the weights and the points in (36.4) to obtain suitable approximations. We begin to explore Gaussian quadrature with the simplest cases.

We do one more specific case before considering the general case.

Other than solving a system of linear equations as in Project Activity 36.4, it might be reasonable to ask what the connection is between Gaussian quadrature and linear algebra. We explore that connection now.

In the general case, we want to find the weights and nodes to make the approximation exact for as large degree polynomials as possible. We have \(2n\) unknowns \(w_1\text{,}\) \(w_2\text{,}\) \(\ldots\text{,}\) \(w_n\) and \(t_1\text{,}\) \(t_2\text{,}\) \(\ldots\text{,}\) \(t_n\text{,}\) so we need to impose \(2n\) conditions to determine the unknowns. We will require equality for the \(2n\) functions \(t^i\) for \(i\) from 0 to \(2n-1\text{.}\) This yields the equations

In the \(i\)th equation the right hand side is

Although it would take us beyond the scope of this project to verify this fact, the nodes in the \(n\)th Gaussian quadrature approximation (36.4) are in fact the roots of the \(n\)th order Legendre polynomial. In other words, if \(p_n(t)\) is the \(n\)th order Legendre polynomial, then \(t_1\text{,}\) \(t_2\text{,}\) \(\ldots\text{,}\) \(t_n\) are the roots of \(p_n(t)\) in \([-1,1]\text{.}\) Gaussian quadrature as described in (36.4) using the polynomial \(p_n(t)\) is exact if the integrand \(f(t)\) is a polynomial of degree less than \(2n\text{.}\)

We can find the corresponding weights, \(w_i\text{,}\) using the formula⁶³

where \(q_i(t)\) is the \(i\)th order Legendre polynomial scaled so that \(q_i(1)=1\text{.}\)

Our Gaussian quadrature formula was derived for integrals on the interval \([-1,1]\text{.}\) We conclude by seeing how a definite integral on an interval can be converted to one on the interval \([-1,1]\text{.}\)