The Interpolation Problem - Study Guide

The Interpolation Problem 1 Intro 1. Definition: The function interpolation problem is, given data points {(x1 , y1 ), (x2 , y2 ), . . . , (xn , yn )} find a function f so that yi = f (xi ) for i = 1..n. 2. There are an infinite number of possible functions- This is an ill-defined problem. Perhaps the simplest functions to consider would be the set of polynomials. 3. Polynomial Interpolation Theorem: Given a set of n + 1 points with distinct x values, there is a unique interpolating polynomial of degree n or less that interpolates the points. You may have seen this in linear algebra. Given n + 1 points, we construct n + 1 equations in n + 1 unknowns. In the following equation, let ak be the coefficient for xk in the unknown polynomial, and let (xk , yk ) be the k th data point (given in the problem). The j th equation is given by: an (xj )n + an−1 (xj )n−1 + . . . a1 (xj ) + a0 = yj In matrix-vector form (the matrix is n + 1 × n + 1), the equation looks like:        xn1 xn2 .. . xn−1 1 xn−1 2 xnn+1 xn−1 n+1 ... ... x1 x2 .. . 1 1 .. . . . . xn+1 1           an an−1 .. . a2 a1 a0            =        y1 y2 .. . yn yn+1          If the points xi are distinct, then the matrix is invertible, and that gives you the coefficients of your polynomial. 2 The Lagrange Polynomial First, consider a line through the points (x0 , f (x0 )) and (x1 , f (x1 )). If we define L0 (x) = x − x1 x0 − x1 L1 (x) = x − x0 x1 − x0 then L0 (x0 ) = 1, L0 (x1 ) = 0. Similarly, L1 (x0 ) = 0 and L1 (x1 ) = 1. With these, we can write the equation of the interpolating line as: P (x) = L0 (x)f (x0 ) + L1 (x)f (x1 ) 1 (Verify that P (x0 ) = f (x0 ) and P (x1 ) = f (x1 )) Similarly, for a quadratic going through three points, L0 (x) = (x − x1 )(x − x2 ) , (x0 − x1 )(x0 − x2 ) L2 (x) = L1 (x) = (x − x0 )(x − x2 ) , (x1 − x0 )(x1 − x2 ) (x − x0 )(x − x1 ) (x2 − x0 )(x2 − x1 ) then P (x) = L0 (x)f (x0 ) + L1 (x)f (x1 ) + L2 (x)f (x2 ) These are the Lagrange Polynomials. To generalize to n+1 points with index k = 0, 1, 2, . . . , n we form Lk (x) = (x − x0 )(x − x1 ) · · · (x − xk−1 )(x − xk+1 ) · · · (x − xn ) (xk − x0 )(xk − x1 ) · · · (xk − xk−1 )(xk − xk+1 ) · · · (xk − xn ) with n + 1 points, Lk is a degree n polynomial, and we see that Lk (xj ) = 0 if j 6= k and Lk (xk ) = 1. Note the relationship between the index k and the construction of the polynomial Lk (x). The Lagrange polynomial is then constructed as a linear combination of the Lk : P (x) = L0 (x)f (x0 ) + . . . + Ln (x)f (xn ) (1) Note: We said before that the interpolating polynomial is unique. The polynomial that comes from the matrix equation we wrote in the previous section is the same as the Lagrange polynomial- The Lagrange polynomial is easier to write down, and we get an immediate function to work with. 2.1 Exercises: 1. Write the Lagrange polynomial for the data: x −1 0 1 y 1 −1 2 2. Use the Matlab function lagrange.m (download from our class website) to plot the functions L0 , L1 , L2 for the data whose x−coordinates are given by: 1, 2, 3, 4. EXAMPLE: To plot L1 , type: x=linspace(1,4); %These are x where P(x) is eval’d y=lagrange(x,[1,2,3,4],[0,1,0,0]); plot(x,y); grid on; %Makes it easier to see the axes values 2 Before continuing with our analysis, we need some theory from Calculus. 1. Generalized Rolle’s Theorem (I) If f is continuous on [a, b] and differentiable on (a, b), and f (a) = f (b) = 0, then there exists c in (a, b) such that f 0 (c) = 0. (II) If f 0 is continuous on [a, b] and differentiable on (a, b) and there are points a0 , a1 , a2 in [a, b] where f (a0 ) = f (a1 ) = f (a2 ) = 0, then there exists c in (a, b) such that f 00 (c) = 0. Exercise: How does (II) follow from (I)? To generalize our result, let f, f 0 , . . . , f (n) all be continuous on [a, b], and suppose we have n + 1 roots of f in [a, b]. Then there exists c ∈ (a, b) so that f (n) (c) = 0. 2. Let x0 , x1 , . . . , xn be n + 1 real numbers, and let x be fixed (so its also constant). Consider the function of t: Ψ(t) = (t − x0 )(t − x1 ) · · · (t − xn ) (x − x0 )(x − x1 ) · · · (x − xn ) (a) Ψ(t) is a polynomial of what degree? (b) What is Ψ(xj ), j = 0, 1, 2, . . . , n? What is Ψ(x)? (c) What is the n + 1st derivative of Ψ, with respect to t? (HINT below) It is possible to write Ψ(t) as: ! Ψ(t) = 1 tn+1 + terms with lower powers of t (x − x0 )(x − x1 ) · · · (x − xn ) 3. Now suppose that we have n + 1 points, (x0 , f (x0 )), (x1 , f (x1 )), . . . , (xn , f (xn )) and suppose that P (x) is the (nth degree) Lagrange polynomial interpolating those points (see Equation 1). The question: Is there a way to estimate how far f (x) is away from P (x)? Consider the following function of t: g(t) = f (t) − P (t) − (f (x) − P (x))Ψ(t) (2) From the previous exercises, the roots of g are when t = x, x0 , x1 , x2 , . . . , xn so that g(t) = 0 has n + 2 solutions. Now, from the generalized Rolle’s Theorem, we know there exists c in the interval from the smallest to the largest of the numbers x, x0 , x1 , . . . , xn so that g (n+1) (c) = 0 3 Now, differentiate both sides of Equation 2 (n+1)−times with respect to t, and evaluate at c: 0 = f (n+1) (c) − 0 − (f (x) − P (x))Ψ(n+1) (c) 0 = f (n+1) (c) − (f (x) − P (x)) so that: f (x) = P (x) + (n + 1)! (x − x0 ) · · · (x − xn ) f (n+1) (c) (x − x0 ) · · · (x − xn ) (n + 1)! We have proven the following theorem, which gives the error between a function f (x) and the interpolating polynomial, P (x): Interpolation Error Theorem: Let x0 , x1 , . . . , xn be (n + 1) distinct numbers in [a, b], and let f be n + 1 times continuously differentiable on [a, b]. Then, for each x in [a, b], there exists a number c in (a, b) such that: f (x) = P (x) + f (n+1) (c) (x − x0 ) · · · (x − xn ) (n + 1)! Notes about the theorem: • Compare this error term to the error term in the Taylor Series. • The error we have here depends on x. If we know that the derivatives are all bounded, then we can make an estimate on the error- That is, if |f (n+1) (x)| ≤ M for all x in [a, b], then: f (n+1) (c) M |f (x) − P (x)| = (x − x0 ) · · · (x − xn ) ≤ |(x − x0 ) · · · (x − xn )| (n + 1)! (n + 1)! • EXAMPLE 1: Let f (x) = sin(x), x = 0, π/6, π/3, π/2. Assess the accuracy of the interpolating polynomial P (x) on [0, π/2]. In particular, consider the error at the π π 5π midpoint of each subinterval (x = 12 , 4 , 12 ) SOLUTION: From the error formula, sin(c) π sin(x) − P (x) = ·x x− 4! 6  1 π | sin(x) − P (x)| ≤ · x x− 24 6 At π/12, we get:    π x− 3 π x− 3   π x− 2 π x− 2 1 π π 3π 5π 5 π | sin(π/12) − P (π/12)| ≤ · · · · = 24 12 12 12 12 8 12  The actual error I computed in Matlab as: 4 4   ≈ 0.002936 %% Individual Error: x=[pi/12,pi/4,5*pi/12]; xp=[0,pi/6,pi/3,pi/2]; y=lagrange(x,xp,sin(xp)); Error=abs(y-sin(x)) %Download this from our website %Leave off the semicolon to output %% To plot all, actual, error: xx=linspace(0,pi/2); yy=lagrange(xx,xp,sin(xp)); ActualError=abs(yy-sin(xx)); plot(xx,ActualError); %% To plot the actual error vs. error bound: ErrorBd=(1/24).*xx.*(xx-pi/6).*(xx-pi/3).*(xx-pi/2); plot(xx,ActualError,xx,abs(ErrorBd)) In this case, the actual error was 0.001798, about half of the upper bound. We could repeat this for the other points (we leave this as an exercise (see below)). One thing to note about the error plot given in Matlab: Notice that the error goes down in the interior of [0, π/2], and we get more error on the two extremes, close to 0 and π/2. This is generally the case. 3 Exercises 1. Type the previous Matlab commands in a script file and name it, for example, Error1.m. Some things to note: • The double percentage signs splits the work into three pieces (in Matlab, they call this “Cell Mode”). • To run the script, go back to the command window and type Error1 (or whatever the filename is). The second plot function overwrites the first, so you’ll only see one figure. • To output the results into a nice format, go back to the editor, go to File, then Publish to HTML. Matlab will create a webpage that has all the output nicely arranged, and even creates a table of contents based on the cell titles! This is a great way to turn in Matlab-based homework problems! 2. Let f (x) = ex , let P (x) be its interpolating polynomial at x = −1, −1/2, 1/2, 1. • By hand, construct the Lagrange polynomial, P (x). • By hand, find the upper bound for the error, |f (x) − P (x)| at the point x = 14 . HINT: For f 0 (c), consider f 0 (x) on the interval [0, 1]. 5 3. We want to find the solution to ex +sin(x)−4 = 0 using Inverse Quadratic Interpolation. Start the algorithm with x0 = 1, x1 = 2 and x2 = 0 and update by retaining the three most recent iterates. Continue until |f (x)| < 10−10 . Here’s a “skeleton” script file to fill in: f=inline(’exp(x)+sin(x)-4’); x=[1, 2, 0]; %Our three points y=f(x); Tol=1e-10; while abs(y(3))>Tol % Compute the new estimate, x3: % Use the function from the website, lagrange %Update x and y: end 4 Newton’s Divided Differences Newton’s divided differences give another way to construct the interpolating polynomialOne that is computationally more attractive, since it is in a form that is ready for Horner’s method of evaluating polynomials. First, some notation needs to be defined. View the data as coming from some function f , and list the points in a table: x1 f (x1 ) x2 f (x2 ) .. .. . . xn f (xn ) Now define the divided differences, which are defined recursively: f [xk ] = f (xk ) f [xk+1 ] − f [xk ] xk+1 − xk f [xk+1 , xk+2 ] − f [xk , xk+1 ] f [xk , xk+1 , xk+2 ] = xk+2 − xk f [xk+1 , xk+2 , xk+3 ] − f [xk , xk+1 , xk+2 ] f [xk , xk+1 , xk+2 , xk+3 ] = xk+3 − xk These numbers are the coefficients for the interpolating polynomial for the data, where: f [xk , xk+1 ] = P (x) = f [x1 ] + f [x1 , x2 ](x − x1 ) + f [x1 , x2 , x3 ](x − x1 )(x − x2 )+ 6 f [x1 , x2 , x3 , x4 ](x−x1 )(x−x2 )(x−x3 )+. . .+f [x1 , . . . , xn ](x−x1 )(x−x2 ) · · · (x−xn−1 ) We’ll wait for the proof. For now, we want to notice that the formula gives an efficient way for evaluating the polynomial- It’s already nested (we’ll see this more in depth shortly). For now, consider the interpolating polynomial on three points, (x1 , y1 ), (x2 , y2 ), (x3 , y3 ). To compute the coefficients, build a table: x1 y1 = f [x1 ] f [x1 x2 ] = y2 −y1 x2 −x1 x2 y2 = f [x2 ] f [x1 x2 x3 ] = f [x2 x3 ] = y3 −y2 x3 −x2 f [x2 x3 ]−f [x1 x2 ] x3 −x1 x3 y3 = f [x3 ] The polynomial coefficients are along the top edge of the triangle. For example, build the interpolating polynomial through (0, 1), (2, 2), (3, 4): 0 1 2−1 2−0 = 1 2 2−(1/2) 3−0 2 2 4−2 3−2 = 1 2 =2 3 4 Therefore, the interpolating polynomial is: 1 1 1 1 P (x) = 1 + (x − 0) + (x − 0)(x − 2) = 1 + x + x(x − 2) 2 2 2 2 Which can be written in nested form directly, in anticipation of using Horner’s Method for evaluation:   1 1 P (x) = 1 + (x − 0) + (x − 2) · 2 2 The table also makes it easy to add a point. Example: Add the point (1, 0) to the previous list. We simply put the necessary values in at the bottom of the triangle- Note that the x−values did not need to be in order: 0 1 1 2 1 2 2 2 2 2−2 1−2 3 4 0−4 1−3 0−1/2 1−0 = − 12 =0 =2 1 0 Now the new polynomial is (first in normal, then in nested form): 1 1 1 1 1 P (x) = 1 + (x − 0) + (x − 0)(x − 2) = 1 + x + x(x − 2) − x(x − 2)(x − 3) 2 2 2 2 2    1 1 −1 P (x) = 1 + x + (x − 2) + (x − 3) · 2 2 2 7 Newton’s Divided Differences, continued from “The Interpolation Problem” Example: Find the interpolating polynomial passing through the following points: x 0 1 2 3 y 2 1 0 −1 Construct the divided difference triangle: 0 2 1 1 2 0 −1 0 −1 0 0 −1 3 −1 Reading off the coefficients, P (x) = 2 + (−1)(x − 0) = 2 − x. Did you notice that the y−values were decreasing linearly? 4.1 Code for Newton’s Interpolation Here is a short piece of Matlab code that computes the polynomial coefficients using Newton’s Divided Differences. Here we also see something slightly different about the function call- Here we have three inputs and two outputs. The output variable v contains all of the divided differences, and the vector c contains only the top part of the triangle (those are the polynomial coefficients). function [v,c]=newtdd(x,y,n) for j=1:n v(j,1)=y(j); % Fill in y column of Newton triangle end for i=2:n % For column i, for j=1:n+1-i % fill in column from top to bottom v(j,i)=(v(j+1,i-1)-v(j,i-1))/(x(j+i-1)-x(j)); end end for i=1:n c(i)=v(1,i); % Read along top of triangle end % for output coefficients Example: How many polynomials of degree less than 5 pass through the following points? x −1 0 2 3 y −5 −1 1 11 Here is the Matlab version of the divided difference table: 8 xp=[-1 0 2 3]; yp=[-5 -1 1 11]; [v,c]=newtdd(xp,yp,4); c = -5 4 -1 1 v = -5 4 -1 1 -1 1 3 0 1 10 0 0 11 0 0 0 %Plot the polynomial over more points: xx=linspace(-1,3); yy=nest(3,c,xx,xp); plot(xx,yy,xp,yp,’r*’) %Plot curve and data points Here we see how our “triangle” was stored, and we can read off the necessary information. Because the polynomial coefficients were not all zero as in our previous example, we know that there are no lines or quadratics that pass through our data points, and only one cubic: P3 (x) = −5 + 4(x + 1) − (x + 1)x + (x + 1)x(x − 2) There are infinitely many degree 4 polynomials. Here is one way to get an infinite number of them: P4 (x) = P3 (x) + k(x + 1)x(x − 2)(x − 3) Similarly, there are infinitely many degree 5 polynomials, constructed in a similar way. Here are some examples: P5 (x) = P3 (x) + k(x + 1)2 x(x − 2)(x − 3) or P5 (x) = P3 (x) + k(x + 1)x2 (x − 2)(x − 3) 4.2 Exercises: 1. Use Lagrange interpolation to find a polynomial that goes through the following points. Use Newton’s Divided Differences to also find that polynomial, and verify that they are the same. x −1 2 3 5 y 0 1 1 2 2. How many degree d polynomials go through the four points (−1, 3), (1, 1), (2, 3), (3, 7)? Write down one, if possible: (a) d = 2, (b) d = 3, (c) d = 6 3. Give an example, or explain why it doesn’t exist: (a) A polynomial of degree 6 that is zero at x = 1, 2, 3, 4, 5, 6 and is 10 at x = 7. 9 (b) A polynomial of degree 6 that is zero at x = 1, 2, 3, 4, 5, 6 and is 10 at x = 7, and is 70 at x = 8. 4. Use newtdd.m and nest.m to see how well an interpolating polynomial approximates the function f (x) on the interval [−1, 1], and using evenly spaced points. f (x) = 1 1 + 12x2 First, use 7 points and plot the points, f (x) and the interpolating polynomial. Next, generate a new graph using 15 points, plot the points, f (x) and the interpolating polynomial. Repeat with 25 points. What do you see in terms of the error? HINT: Below is the beginning of a script file. To turn in the solution to this problem, have Matlab export this as an HTML page, and print that. f=inline(’1./(1+12*x.^2)’); %% Example 1: Seven points %First define the points for the polynomial: xp=linspace(-1,1,7); yp=f(xp); %Find the coefficients: [v,c]=newtdd(xp,yp); xx=linspace(-1,1,200); %Pts for f, P yy1=f(xx); yy2=nest(c,xx,xp); plot(xp,yp,’r*’,xx,yy1,xx,yy2); legend(’Data’,’f(x)’,’Polynomial’) %% Example 2: 15 Points %% Example 3: 25 Points 10