a logo for the course

Numerical Analysis

David Gleich

Purdue University

Spring 2016

Course number CS-51400, MATH-51400

Tuesday and Thursday, noon-1:15pm

Location Lawson B155


Homework 3

Please answer the following questions in complete sentences in a typed manuscript and submit the solution on blackboard by on February 29th at noon.

Problem 0: Homework checklist

Problem 1: Gautschi Exercise 2.26

Just a little bit of algebra. Show that the elementary Lagrange interpolation polynomials are invariant with respect to any linear transformation of the independent variable. (What this is asking you to do is to show that if , and we write the the interpolating polynomials in terms of , then we get the same polynomials in terms of .)

Problem 2: Gautschi Exercise 2.35

The error in linear interpolation of at is known to be if . Determine explicitly in the case of and . Find the maximum and minimum of on .

Problem 3: Gautschi Machine Exercise 2.7

  1. Modify the computation of the divided differences for Newton interpolation given in class compute_newton_coeffs https://www.cs.purdue.edu/homes/dgleich/cs514-2016/julia/Lecture-11-Hermite-interpolation.html in order to avoid storing the -by- matrix of coefficients and only store coefficients. Modify the Newton interpolation program to use the single coefficients instead of the table (very easy).

  2. Use your routine to interpolate the Runge function from using and equally spaced points on including the endpoints. (i.e. for two points, use .) Plot the interpolants vs. the true function.

Problem 4: Gatuschi Machine Exercise 2.8b

The book outlines most of the solution. 1. Write a program for computing the natural spline interpolant on an arbitrary partition of .

  1. Test your program on using 11 uniformly spaced points from to including the endpoints (linspace(0.,1.,11)) and use uniformly spaced points to find the maximum error at any point (uniform approximation).

  2. Test your program on using 11 uniformly spaced points from to including the endpoints (linspace(0.,1.,11)) and use uniformly spaced points to find the maximum error at any point (uniform approximation).

  3. Test your program on using the 11 points for and use uniformly spaced points to find the maximum error at any point (uniform approximation).

  4. Test your program on using 25 uniformly spaced points from to and use uniformly spaced points to find the maximum error at any point (uniform approximation).

Problem 5: Derivatives via interpolants, two ways

In this problem, we are going to compare two strategies for approximating the derivative of a function when given access to a computer program to evaluate . That is, we want to write a computer program that returns an approximate value of .

Strategy 1 We use a central difference formula to approximate the derivative:

Strategy 2 We first compute a polynomial interpolant to at data points, then evaluate the derivative of the polynomial interpolant. where is the derivative of the elementary Lagrange polynomial.

Both strategies have a parameter: for the central difference and for the interpolation. For strategy 2, we'll have to work out the derivative of the elemenary Lagrange polynomial .

The goal of this problem is to compare the strategies to see how they differ on the functions:

We'll evaluate the error by taking 10000 uniformly spaced points within these intervals and comparing the true derivatives to the approximations by looking at the point of maximum difference (this is called uniform approximation).

  1. Write down the derivaties of these three functions and plot their exact derivatives.

  2. Implement a computer code for strategy 1. Evaluate the error for . Show a plot of how the error changes for these values of . Show three or four plots that illustrate different error regimes (think high,middle,low error and maybe an extra point).

  3. Write down an expression for the derivative of the Lagrange polynomials. (Hint: see the paper by Berrut and Trefethen from the readings!)

  4. Implement a computer code for strategy 2. Evaluate the error for . Show a plot of how the error changes for these values of . Show three or four plots that illustrate different error regimes (think high,middle,low error and maybe an extra point).

  5. Discuss advantanges and disadvantages of these approaches.

Optional extra problems (not graded)