# College Math Teaching

## October 3, 2016

### Lagrange Polynomials and Linear Algebra

Filed under: algebra, linear albegra — Tags: — collegemathteaching @ 9:24 pm

We are discussing abstract vector spaces in linear algebra class. So, I decided to do an application.

Let $P_n$ denote the polynomials of degree $n$ or less; the coefficients will be real numbers. Clearly $P_n$ is $n+1$ dimensional and $\{1, x, x^2, ...x^n \}$ constitutes a basis.

Now there are many reasons why we might want to find a degree $n$ polynomial that takes on certain values for certain values of $x$. So, choose $x_0, x_1, x_2, ..., x_{n-1}$. So, let’s construct an alternate basis as follows: $L_0 = \frac{(x-x_1)(x-x_2)(x-x_3)..(x-x_{n})}{(x_0 - x_1)(x_0-x-x_2)..(x_0 - x_{n})}, L_1 = \frac{(x-x_0)(x-x_2)(x-x_3)..(x-x_{n})}{(x_1 - x_0)(x_1-x-x_2)..(x_1 - x_{n})}, ...L_k = \frac{(x-x_0)(x-x_1)(x-x_2)..(x-x_{k-1})(x-x_{k+1})...(x-x_{n})}{(x_k - x_1)(x_k-x-x_2)..(x_k - x_{k-1})(x_k - x_{k+1})...(x_k - x_{n})}.$ $....L_{n} = \frac{(x-x_0)(x-x_1)(x-x_2)..(x-x_{n-1})}{(x_{n}- x_1)(x_{n}-x-x_2)..(x_{n} - x_{n})}$

This is a blizzard of subscripts but the idea is pretty simple. Note that $L_k(x_k) = 1$ and $L_k(x_j) = 0$ if $j \neq k$.

But let’s look at a simple example: suppose we want to form a new basis for $P_2$ and we are interested in fixing $x$ values of $-1, 0, 1$.

So $L_0 = \frac{(x)(x-1)}{(-1-0)(-1-1)} = \frac{(x)(x-1)}{2}, L_1 = \frac{(x+1)(x-1)}{(0+1)(0-1)} = -(x+1)(x-1),$
$L_2 = \frac{(x+1)x}{(1+1)(1-0)} = \frac{(x+1)(x)}{2}$. Then we note that

$L_0(-1) = 1, L_0(0) =0, L_0(1) =0, L_1(-1)=0, L_1(0) = 1, L_1(1) = 0, L_2(-1)=0, L_2(0) =0, L_2(1)=1$

Now, we claim that the $L_k$ are linearly independent. This is why:

Suppose $a_0 L_0 + a_1 L_1 + ....a_n L_n =0$ as a vector. We can now solve for the $a_i$ Substitute $x_i$ into the right hand side of the equation to get $a_iL_i(x_i) = 0$ (note: $L_k(x_i) = 0$ for $i \neq k$). So $L_0, L_1, ...L_n$ are $n+1$ linearly independent vectors in $P_n$ and therefore constitute a basis.

Example: suppose we want to have a degree two polynomial $p(x)$ where $p(-1) =5, p(0) =3, p(1) = 17.$. We use our new basis to obtain:

$p(x) = 5L_0(x) + 3 L_1(x) + 17L_2(x) = \frac{5}{2}(x)(x-1) -3(x+1)(x-1) + \frac{17}{2}x(x+1)$. It is easy to check that $p(-1) = 5, p(0) =3, p(1) = 17$

## April 4, 2014

### Gaussian Quadrature and Legendre polynomials

In a previous post, I discussed the Legendre polynomials. We now know that if $P_n$ is the n’th Legendre polynomial then:

1. If $k < n, \int^{1}_{-1}P_k(x)P_n(x)dx = 0$.
2. If $Q(x)$ has degree $k < n$ then $\int^{1}_{-1}Q(x)P_n(x)dx = 0$.
3. $P_n(x)$ has n simple roots in $(-1,1)$ which are symmetric about 0.
4. $P_n(x)$ is an odd function if $n$ is odd and an even function if $n$ is even.
5. $P_0, P_1, P_2,....P_n$ form an orthogonal basis for the vector pace of polynomials of degree $n$ or less.

To make these notes complete, I’d like to review the Lagrange Interpolating polynomial:

Given a set of points $(x_0, y_0), (x_1, y_1), .....(x_n, y_n)$ where the $x_0, x_1, ...x_n$ are all distinct, the Lagrange polynomial through these points (called “nodes”) is defined to be:
$L_n(x) = y_0 \frac{(x-x_1)(x-x_2)....(x-x_n)}{(x_0 -x_1)(x_0-x_2)...(x_0-x_n)} +y_1 \frac{(x-x_0)(x-x_2)...(x-x_n)}{(x_1-x_0)(x_1-x_2)....(x_1-x_n)} + ....y_n\frac{(x-x_0)(x-x_2)...(x-x_{n-1})}{(x_n-x_0)(x_n-x_2)....(x_n-x_{n-1})}$

It is easy to see that $L_n(x_i) = y_i$ because the associated coefficient for the $y_i$ term is 1 and the other coefficients are zero. We call the coefficient polynomials $L_{n,i} = \Pi^n_{j=0, j \ne i}\frac{(x-x_j)}{x_j-x_i}$

It can be shown by differentiation that if $f$ is a function that has $n+1$ continuous derivatives on some open interval containing $(a,b)$ and if $L_n(x)$ is the Lagrange polynomial running through the nodes $(x_i, f(x_i))$ where all of the $x_i \in [a,b]$ then the maximum of $|f(x) - L_n(x)|$ is bounded by $|K f^{n+1}(\omega) |$ where $\omega \in [a,b]$. So if the n+1’st derivative of $f$ is zero, then the interpolation is exact.

So, we introduce some notation: let $P_m(x)$ be the $m'th$ Legendre polynomial, let $r_1, r_2,...r_m$ be the roots, and $c_i = L_(m,i) = \Pi^n_{j=0, j \ne i}\frac{(x-x_j)}{x_j-x_i}$, the j’th coefficient polynomial for the Lagrange polynomial through the nodes $(r_i, 1)$.

Now let $P(x)$ be any polynomial of degree less than $m$. First: the Lagrange polynomial $L_m$ through the nodes $(r_1, P(r_1)), (r_2, P(r_2)), ...(r_m, P(r_m))$ represents $P(x)$ exactly as the error term is a multiple of the $m+1'st$ derivative of $P(x)$ which is zero.

Therefore $\int^{1}_{-1} P(x) dx = \int^{1}_{-1} L_m (x)dx$ $= \int^{1}_{-1} P(r_1 )L_{m,1} +P(r_2 )L_{m,2} + ....P(r_m )L_{m,m} dx$ $= \sum^{m}_{i=1} P(r_i )\int^1_{-1} L_{m,i}(x) dx$

Now here is the key: $\int^1_{-1} L_{m,i}(x) dx$ only depends on the Legendre polynomial being used and NOT on $P(x)$.

Hence we have a quadrature formula that is exact for all polynomials of degree less than $m$.

But, thanks to the division algorithm, we can do even better. We show that this quadrature scheme is exact for all polynomials $P$ whose degree are less than $2m$. This is where the orthogonality of the Legendre polynomials will be used.

Let $P$ be a polynomial of degree less than $2m$. Then by the division algorithm, $P(x) = Q(x)P_m(x) + R(x)$ where BOTH $Q(x)$ and $R(x)$ have degree less than $m$.

Now note the following: $P(r_i) = Q(r_i)P_m(r_i) + R(r_i) = R(r_i)$; that is where the fact that the $r_i$ are the roots of the Legendre polynomials matters.
Then if we integrate: $\int^1_{-1} P(x) dx = \int^{1}_{-1} Q(x)P_m(x) dx + \int^{1}_{-1} R(x)dx$. Now because of property 2 above, $\int^{1}_{-1} Q(x)P_m(x)dx =0$.

Now because the degree of $R$ is less than $m$, $\int^1_{-1}R(x) dx = \sum^{m}_{i=1} R(r_i )\int^1_{-1} L_{m,i}(x) dx =\sum^{m}_{i=1} P(r_i )\int^1_{-1} L_{m,i}(x) dx$

This means: this quadrature scheme using the Legendre polynomials of degree m is EXACT for all polynomials of degree less than 2m.

Of course, one must know the roots $r_i$ and the corresponding $\int^1_{-1} L_{m,i}(x) dx$ but these have been tabulated.

Why this is exciting:

Let’s try this technique on: $\int^1_{-1} e^x dx$ with, say, n = 5. We know that the exact answer is $e-e^{-1}$. But using the quadrature method with a spreadsheet:

The roots $r_i$ are in column A, rows 5-9. The weights (coefficients; the $\int^1_{-1} L_{m,i}(x) dx$) are in column B, rows 5-9. In column F we apply the function $e^x$ to the roots in column A; the products of the weights with $e^{r_i}$ are in column G, and then we do a simple sum to get a very accurate approximation to the integral.

The accuracy: this is due to the quadrature method being EXACT on the first 9 terms of the series for $e^{x} = \sum^{\infty}_{j=0} \frac{x^j}{j!}$. The inexactness comes from the higher order Taylor terms.

Note: to convert $\int^{b}_{a} f(x) dx$, one uses the change of variable: $u = \frac{2}{b-a} x - \frac{a+b}{b-a}$ to convert this to $\frac{(b-a)}{2}\int^{1}_{-1} f(u \frac{(b-a)}{2}+\frac{a+b}{2})dx$