AMSC/CMSC 460 Computational Methods, Fall 2007UNIT 2: Polynomial ApproximationsDianne P. O’Learyc°2001, 2002, 2007Polynomial InterpolationRead: Chapter 2. Skip: 2.4.2, 2.4.4.Caution: The numbering of coefficients is inconsistent in the chapter. See thedifference between the top of p. 76 and the bottom. I’ll use the Matlab notation(top of p. 76) rather than Van Loan’s.The Plan:• Why polynomial interpolation is useful.• Some facts about polynomials.• Computing interpolating polynomials.• Evaluating polynomials.• Existence and uniqueness: Lagrange and Newton form of the polynomial.• The error formula.• 2-d interpolation.Why polynomial interpolation is usefulMotivationProblem 1: Given some experimental data (e.g., 1000 measurements of mortalityrate as a function of fat consumption, or 20 yearly measurements of amount ofpollution in a river), see how well the data fits a model such as a polynomial or asum of exponentials.Problem 2: Fit a model to data in order to reduce the effects of noise in themeasurements.We’ll study this in Chapter 7.11990 1991 1992 1993 1994 1995 1996 1997 1998 19993456789Figure 1: Pollution levels (ppm) vs. year. Does a polynomial fit this data?20 1 2 3 4 5 6 7 8 9 10 11−0.200.20.40.60.81Figure 2: Is a straight line a good model to this data?3Problem 3: Fit a simple model, such as a polynomial, to a piece of a functionthat is expensive to calculate, so that we can use the simple model as asubstitute.Problem 4: Estimate the integral or the derivative of some function.Polynomial InterpolationWhy polynomials?• often a reasonable model.• cheap to calculate and evaluate.• important in solving ordinary differential equations (ode’s) and nonlinearequations and in computing integrals.How well can polynomials approximate functions?To find out, we need to drop the requirement of interpolation.Theorem: (Weierstrass) For all f ∈ C[a, b], for all ² > 0, there exists a degree nand a polynomial pnsuch that ||f − p||∞< ².Problems with Weierstrass way of constructing the polynomial:• The degree can be quite high.• The polynomial is not guaranteed to interpolate at any given set of points.The standard polynomial interpolation problem:Given: (xi, fi), i = 1, . . . , n, xi6= xjfor i 6= jFind: a polynomial pn−1(x) of degree at most n − 1 such that pn−1(xi) = fi,i = 1, . . . , n.Some facts about polynomialsSome facts about polynomials41990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000012345678910Figure 3: Polynomial fit to pollution data5• A polynomial of degree k has at most k distinct zeroes, unless it is the zeropolynomial z(x) = 0 for all x.• The sum of two polynomials of degree at most k is a polynomial of degreeat most k.• There are many ways to write a given polynomial.For example (x − 2)(x − 5) = x2− 2x − 5(x − 2) = x2− 7x + 10.We have used three different sets ofbasis functions in this example:1. (x − 2)(x − 5), x − 1, and 1.2. x2, x, and x − 2.3. x2, x, and 1.The third basis set is the most familiar one, called the power basis.How we write a polynomial – what set of basis functions we use – can bechosen for our convenience!We can use any basis functions, as long as they are independent.Computing interpolating polynomialsComputing interpolating polynomialsSuppose we want to compute the polynomial of degree 3 that interpolates thedata (1, 3), (2, 5), (−1, 4), (0, 6). Let’s use the power basis: x3, x2, x, 1, and letthe polynomial be denoted asp(x) = a1x3+ a2x2+ a3x + a4.Then the four conditions that our polynomial needs to satisfy arep(1) = 3 : 13a1+ 12a2+ 1a3+ a4= 3,p(2) = 5 : 23a1+ 22a2+ 2a3+ a4= 5,p(−1) = 4 : (−1)3a1+ (−1)2a2+ (−1)a3+ a4= 4,p(0) = 6 : 03a1+ 02a2+ 0a3+ a4= 6,If we write this in matrix form, we have1 1 1 18 4 2 1−1 1 −1 10 0 0 1a1a2a3a4=3546.6For conciseness, we can sayV a = ywhere V is the matrix, a is the vector of coefficients of the polynomial, and y isthe set of y coordinates for the data. The x coordinates determine the matrix V :V =x31x21x11x32x22x21x33x23x31x34x24x41.We need to solve this linear system for the 4 values in the vector a.This is such a commonly occurring problem that Matlab has a special function todo it:x = [1 2 -1 0];y=[3 5 4 6];a = polyfit(x,y,3)The third argument to polyfit gives the degree of the polynomial.The matrix for the interpolation problemThe matrix in our polynomial interpolation problem has a very special form:V =xn−11xn−21. . . x111xn−12xn−22. . . x121. . . . . . . . . . . . . . .. . . . . . . . . . . . . . .xn−1nxn−2n. . . x1n1and a special name, aVandermonde matrix.(To be precise, a Vandermonde matrix looks like this but with the order of thecolumns reversed.)Evaluating polynomialsEvaluating polynomials7Now suppose someone asks what is the value of the polynomial at x = 7?We can determine this by computinga1∗ 7 ∗ 7 ∗ 7 + a2∗ 7 ∗ 7 + a3∗ 7 + a4.Unquiz:• Write an algorithm to implement this for a polynomial of degree n − 1.• Count the number of multiplications that the program does.• Think about how we might make the algorithm faster.Evaluating polynomials using Horner’s ruleGiven x, we can evaluate p(x) by the following recursion:p = a1For j = 2, . . . , n,p = p ∗ x + aj.end forUnquiz: Count the number of multiplications and compare with the previousalgorithm.Existence and uniqueness: Lagrange and Newton form of the polynomialExistence of interpolation polynomialCan we guarantee that we can always find a unique polynomial of degree n − 1that interpolates any given set of n data points?In order to guarantee this, we would have to know that the linear system ofequations V a = y always has one and only one solution. In other words, wewould need to know that V is a nonsingular matrix.Although it is true that V is always nonsingular, as long as the values x1, . . . xnare distinct, this is not so easy to prove. So we use the fact that we can write the80 1 2 3 4 5 6−1−0.500.511.5Figure 4: L5,1and L5,3for interpolation points 1, 2, 3, 4, 5.polynomial in any basis, and choose one more convenient for the proof, in orderto show existence. Then we will show uniqueness using properties of polynomials.The most convenient set of basis functions for this proof: Lagrange basis: fork = 1, 2, . . . , nLn,k(x) =Qni=1,i6=k(x − xi)Qni=1,i6=k(xk− xi)Ln,kis an