2 19 2012 Computational Methods CMSC AMSC MAPL 460 Polynomial Interpolation Ramani Duraiswami Dept of Computer Science Interpolation Given a function at N points find its value at other point s within the points Interpolation outside the points Extrapolation How do we extend the value from known points to unknown points Have to have prior knowledge about the function Can do what is convenient Occam s razor Parsimony One should not increase beyond what is necessary the number of entities required to explain anything Key in all scientific modeling 1 2 19 2012 Function representation in a function space In interpolation sampled values of a function are available We need to extend these values to points where they are not available Can assume that the function is expanded over a basis of functions which span the functional space Polynomials are a basis Fourier series are another Many others Knowing coefficients specifies the function Most common basis are power series polynomials Here x is a point about which we expand in series am are coefficients Polynomial interpolation is often natural Part of theory of Taylor series solution of differential equations via power series in computing integrals A theorem guaranteeing that a polynomial can represent a function is available Interpolation Weierstrass theorem Provides a guarantee that polynomials can interpolate any function On the other hand does not tell us how to choose the polynomial Also does not guarantee that the polynomial will actually interpolate the function only that it will be within Does not tell what the degree of the polynomial is 2 2 19 2012 Taylor Series Let f y be a real function f y C n x x r nth derivative fn exists for x y x r Residual determines accuracy Two evaluations of remainder Cauchy evaluation Lagrange evaluation Polynomial Facts A polynomial of degree k has at most k distinct zeroes unless it is identically zero Sum of two polynomials of degree k is another polynomial of degree at most k Polynomials can be expressed in many ways Degree of basis functions is 2 1 and 0 Basis 3 is the power basis or monomial basis Any basis can be used often orthogonal polynomials are used 3 2 19 2012 Uniqueness of interpolant We know that the polynomial exists Suppose that there are two different polynomials that can interpolate the data Let them be pn 1 and qn 1 So we have pn 1 xi yi i 1 n qn 1 xi yi i 1 n So pn 1 xi qn 1 xi 0 i 1 n pn 1 qn 1 is the difference of two polynomials of degree n 1 It has n zeroes Recall polynomial of degree k has at most k zeroes or is the zero polynomial Here we have more zeroes than degree so it is the zero polynomial So interpolant is unique Interpolating polynomials in power form Given n values of the function yi at points xi Fit a polynomial P x that interpolates data at these points If we have n points to interpolate then a polynomial of degree n 1is We can write the condition that it interpolate as a linear system 4 2 19 2012 Vandermonde matrices Matlab code In matlab Vandermonde matrix is defined in flipped order using the function vander Example Also there is a function to fit polynomials to data polyfit Vandermonde matrices are nonsingular if the points are distinct However they can be very poorly conditioned Computing interpolants by hand Suppose we have data at n points and we have fit a polynomial How can we do this fit efficiently Fit for one point is y y1 Fit for two points can be written as y a x x1 b x x2 Fit for three points can be written as y a x x1 x x2 b x x1 x x3 c x x2 x x3 And so on Advantage each coefficient can be calculated independent of others Why What is the form of the coefficient computed 5 2 19 2012 Lagrange and Newton forms for interpolations Lagrange and Newton modified these forms further to conveniently compute polynomials Lagrange Polynomials Summation of terms such that Equal to f at a data point Equal to zero at all other data points Each term is a nthdegree polynomial n pn x Li x f xi i 0 n Li x k 0 k i x xi 1 L i x j ij 0 xk xk i j i j 6