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 2

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

Problem 0: Homework checklist

Problem 1: Gautschi Exercise 2.2

Consider the data

  1. Determine the discrete approximant to by means of a constant .

  2. Do the same for discrete (equally weighted) least squares approximation.

  3. Compare what happens as .

Problem 2: Gautschi Exercise 2.5

Taylor expansion yields the simple approximation on . Suppose you want to improve this by seeking an approximation of the form for and some suitable .

  1. How must be chosen if the approximation is to be optimal in the continuous, equally weighted least-squares sense?

  2. Plot the error curves and using determined in part 1. Find the maximum magnitude of each error curve on .

  3. Repeat steps 1 and 2 for polynomial approximations .

Problem 3: Gautschi Exercise 2.11

Suppose you want to approximate the step function on the positive real line using a linear combination of exponentials in a least-squares sense.

  1. Derive the normal equations. How is the matrix related to the Hilbert matrix?

  2. Plot the condition number of the matrix for .

Problem 4: Gautschi Machine Exercise 2.2

  1. Determine the matrix of the normal equations relative to the Berstein basis and weight function on .

  2. Solve the normal equations for on a computer when . What should the exact answer be? For each , print the infinity norm of the error vector and an estimate of the condition number of .

Problem 5: Chebyshev approximation

There are two types of Chebyshev points commonly used. Your book discusses both, although doesn't call them by their names "Chebyshev points of the first kind" and "Chebyshev points of the second kind". The Chebyshev points of the first kind are the roots, or zeros, of the th Chebyshev polynomial (equation 2.85). Chebyshev points of the second kind are the extrema of the th Chebyshev polynomial. Note that an degree polynomial will have extrema.

  1. Develop a program to compute the Chebyshev points of the first and second kind. Prepare a plot of each set of points for . Discuss any features of your plot.

  2. Generate a program to compute a polynomial interpolant through Chebyshev points of the second kind and uniformly spaced points on an arbitrary interval and evaluate the resulting interpolant at another set of points.

    Your program should take as input a "function handle", a function handle, the number of points to use to build the interpolant, and the set of points.

    """
    Compute an interpolant for function f in n uniformly spaced
    points over the region [r(1),r(2)] and return the values
    of the polynomial at points pts.
    
    Example:
      f(x) = e^(-x) # declare a function in julia to evaluate e^-x
      pts = linspace(1,5,10000) # generate points to evaluate the polynomial
      y = interpolate_unif(f, [1,5], 101, pts) # build the interpolant and evaluate
      plot(pts, y)
    """
    
    function interpolate_unif(f, r, n, pts)
        # you have to fill this in
    end
    
  3. Apply your program to the function on the region with . Prepare plots of your results and discuss them.

  4. Apply your program to the function on the region with . Prepare plots of your results and discuss them.

  5. Discuss the course logo on the course homepage in the context of your results.

Problem 6: Multivariate approximation

The book has largely focused on univariate approximation where we have a univariate function and we wish to generate a computer approximation of that function. In many scientific studies, we have multivariate data where may depend on multiple inputs say, and . The same idea of having a linear function space works, but we need to enrich it with multivariate functions!

The degree of a multivariate polynomial is the sum of powers of expressions. Suppose we work with the space of bi-variate (two variable) polynomials of degree at most 1. These are: If we increase it degree 2, we get

We extend the idea of a function norm in the same way:

Thus, the best approximation problem easily translates into the multivariate case, and these generalize in a straightforward way at this point.

  1. (Warmup) Consider approximating the bivariate step function with a constant in the L_2 sense. Show that the best approximation is the constant .

  2. How many points uniquely determine the interpolating polynomial of degree at most if there are two variables?

  3. How many points uniquely determine the interpolating polynomial of degree at most if there are variables? (no need for a closed form expression, but your answer should be recogonizably correct and well explained)

  4. Derive the Lagrange form of the interpolating polynomial in the bivariate case, e.g.

  5. One way to sample a function in multiple dimensions is to use a tensor-product construction. We'll illustrate a simple case. Suppose we have the univariate points , then the tensor-product point (sometimes called Cartesian product) is the set Use a tensor product of 5 Chebyshev points on the region to sample the Multivariate Runge function : and display your interpolant. (Hint, see here http://nbviewer.jupyter.org/github/gizmaa/Julia_Examples/blob/master/pyplot_surfaceplot.ipynb for info on plotting.)