09 28 10 cs412 introduction to numerical analysis Lecture 6 Polynomial Interpolation II Instructor Professor Amos Ron 1 Scribes Yunpeng Li Mark Cowlishaw Nathanael Fillmore Polynomial Interpolation as a Linear Problem Last time we introduced the polynomial interpolation problem which we now state in a different but equivalent fashion Definition 1 1 Polynomial Interpolation Given points X x0 x1 xn which are pairwise disjoint that is no two points are equal and a function f defined at these points Find a polynomial p n such that p xi f xi 0 i n Note that the polynomial p may not fit the function f very well outside the given points but for now we will not concern ourselves with this If we choose to represent p as a linear combination of monomials then the problem of finding p is equivalent to solving a linear problem with n 1 variables the coefficients of the monomials and n 1 constraints p t a 1 tn a 2 tn 1 a n t a n 1 We can rewrite this system of equations as V a F where a a 1 a 2 a n 1 T F xn0 xn 1 V xn n 1 xnn 1 f x0 f xn T and xn 1 x10 x00 0 xn 1 x11 x01 1 1 0 xn 1 x x n 1 n 1 n 1 n 1 1 0 xn xn xn Transforming the problem of finding a polynomial p into an equivalent linear problem has helped us to understand polynomial interpolation However it has some significant drawbacks as a method for solving polynomial interpolation problems 1 Solving a linear system of equations takes a significant amount of time 2 This system of linear equations is often ill conditioned and prone to round off errors In other words although the Vandermonde matrix V is nonsingular it may be close to singular which makes it hard to solve accurately on a computer 1 3 It is not well suited to a common kind of exploratory analysis Suppose we are given x0 y0 xn yn We solve V a y and we get a solution a Suppose that we don t like the solution for some reason so we add a new point xn 1 yn 1 Now we make a new system V a y and solve for a We have to do this from scratch we can t reuse all the computation we already invested to solve V a y If n 1000 say this could be very bad This equivalence between solving a linear problem and finding a polynomial p rests on our representation of p as a linear combination of monomials To find a better method we should consider alternate representations Two methods of polynomial interpolation we shall talk about involve different polynomial representations These are Lagrange1 polynomials and Newton polynomials 2 Interpolation by Lagrange Polynomials Given the n 1 interpolation points x0 x1 xn suppose we can find n 1 polynomials 0 t 1 t n t of degree n These polynomials are fixed and independent of the function values f x0 f x1 f xn and satisfy the following condition 1 if i j i xj 2 0 if i 6 j For example given x0 and x1 two such polynomials are shown in Figure 1 Figure 1 Lagrange Polynomials 0 1 for two points x0 x1 How can we find such polynomials and more importantly how can we use them for interpolation 2 1 Using Lagrange Polynomials for Interpolation Fact 2 1 Any polynomial p n can be represented as a linear combination of n 1 Lagrange polynomials of degree n To illustrate the use of Lagrange polynomials consider the following example 1 Joseph Louis Comte de Lagrange 1736 1813 French mathematician published works on celestial mechanics differential and variable calculus theory of numbers etc 2 l 1 l 2 1 l 0 0 x 6 x0 2 1 x2 7 Figure 2 Quadratic Lagrange Polynomials 0 1 2 for x 2 6 7 T Example 2 1 Given the points x 2 6 7 T and the corresponding function values F 1 8 3 T find an interpolating polynomial p 2 Consider that if we had three quadratic Lagrange polynomials 0 t 1 t 2 t as shown in Figure 2 with 0 x 1 1 x 0 2 x 0 0 0 1 0 0 1 T T T If we multiply each polynomial li by the corresponding function value f xi then add them together the resulting polynomial will match f at each of the input points So we can define p as p t 1 0 t 8 1 t 3 2 t Evaluating p at the input point x0 2 we see p 2 1 0 2 8 1 2 3 2 2 1 1 8 0 3 0 1 In general given a set of input points x0 x1 xn the corresponding points on the graph of the function f f x0 f x1 f xn and the Lagrange polynomials for our input points 0 t 1 t n t we can define the following polynomial p n that interpolates f p t n X f xi i t 3 i 0 What have we done Initially when we first formulated the problem of polynomial interpolation we did not specify any particular representation of polynomials When we started to do 3 computation we needed a computationally accessible definition so we choose the most natural basis that we all are familiar with monomials For example we used the monomials t0 t1 t2 as a basis for 2 But this is only one basis The Lagrange polynomials also form a basis for the space of polynomials The difference is that the Lagrange basis is chosen so as to make our problem easier 2 2 Finding Lagrange Polynomials So how can we find a polynomial i given its roots and a point xi with i xi 1 Consider that if a polynomial has roots r1 r2 then it must have factors t r1 and t r2 We can get our polynomial by first multiplying the factors together obtaining a polynomial with the correct roots We can then multiply by a constant scaling factor so that i xi 1 To illustrate consider Example 2 1 Since 0 is 0 at 6 and 7 it must have factors t 6 and t 7 If we consider t 6 t 7 evaluated at x0 2 we see that its value will be 2 6 2 7 so if we divide by this value we will have the correct polynomial 0 t t 6 t 7 2 6 2 7 We can define 1 and 2 similarly t 2 t 7 6 2 6 7 t 2 t 6 2 t 7 2 7 6 1 t In general we can calculate each Lagrange polynomial i for a set of input points x0 x1 xn as n Y t xj i t xi xj j 0 4 j6 i 2 3 Analysis of Interpolation by Lagrange Polynomials So we have seen that we can solve a polynomial interpolation problem …