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:
guassquadexample

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

Create a free website or blog at WordPress.com.