Numerical Analysis

David Gleich

Purdue University

Spring 2021

Course number CS-51400, MATH-51400

Online due to COVID-19 Pandemic

Social distance, wear a mask.

Zoom, Tuesday and Thursday, 10:30-11:45

Homework 3

Please answer the following questions in complete sentences in a typed manuscript and submit the solution on Gradescope by March 22nd around 5am like our usual deadline.

Problem 0: Homework checklist

• Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale.

• Make sure you have included your source-code and prepared your solution according to the most recent Piazza note on homework submissions.

Problem 1: Gautschi Exercise 2.35

The error in linear interpolation of $f$ at $x_0, x_1$ is known to be $$f(x) - p_1(f; x) = (x - x_0)(x-x_1) f''(\xi(x)) / 2 \qquad x_0 < x < x_1,$$ if $f \in C^2[x_0, x_1]$. Determine $\xi(x)$ explicitly in the case of $f(x) = \frac{1}{x}$ and $x_0 = 1, x_1 = 2$. Find the maximum and minimum of $\xi(x)$ on $1 \le x \le 2$.

Problem 2: 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 $a = x_1 < x_2 < \ldots < x_{n-1} < x_n = b$ of $[a,b]$.

2. Test your program on $f(x) = e^{-x}$ using 11 uniformly spaced points from $0$ to $1$ including the endpoints (linspace(0.,1.,11)) and use $1000$ uniformly spaced points to find the maximum error at any point (uniform approximation).

3. Test your program on $f(x) = x^{5/2}$ using 11 uniformly spaced points from $0$ to $1$ including the endpoints (linspace(0.,1.,11)) and use $1000$ uniformly spaced points to find the maximum error at any point (uniform approximation).

4. Test your program on $f(x) = x^{5/2}$ using the 11 points $x_i = \left( \frac{i-1}{n-1} \right)^2$ for $i=1,\ldots,11$ and use $1000$ uniformly spaced points to find the maximum error at any point (uniform approximation).

5. Test your program on $f(x) = \frac{1}{1+x^2}$ using 25 uniformly spaced points from $-5$ to $5$ and use $10000$ uniformly spaced points to find the maximum error at any point (uniform approximation).

Problem 3: Derivatives via interpolants, two ways

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

Strategy 1 We use a central difference formula to approximate the derivative: $$p(x) = (f(x+h) - f(x-h))/(2h).$$

Strategy 2 We first compute a polynomial interpolant to $f$ at $n+1$ data points, then evaluate the derivative of the polynomial interpolant. $$p(x) = \sum_{i=0}^{n} f_i \ell_i'(x)$$ where $\ell_i'(x)$ is the derivative of the elementary Lagrange polynomial.

Both strategies have a parameter: $h$ for the central difference and $n$ for the interpolation. For strategy 2, we'll have to work out the derivative of the elemenary Lagrange polynomial $\ell_i(x)$.

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

• $f(x) = e^x, 0 \le x \le 5$
• $f(x) = 1/(1+x^2), -5 \le x \le 5$
• $f(x) = e^{3x} \sin (200 x^2)/(1+20x^2), 0 \le x \le 1$.

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 derivatives of these three functions and plot their exact derivatives.

2. Implement a computer code for strategy 1. Evaluate the error for $10^{-10} \le h \le 0.1$. Show a plot of how the error changes for these values of $h$. 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 $250 \ge n \ge 5$. Show a plot of how the error changes for these values of $n$. 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.

Problem 4: Derivative formula for non-equally spaced point sets

1. Use the tools developed in the reading and class to determine a formula to approximate the derivative that uses 4 values of $f$ that are not equally spaced: $$x_0, x_0 - 2h, x_0+h, x_0+3/2 h.$$

2. Use the same set of points to approximate the second derivative as well

3. Compare these formala on $f(x) = e^x$ for $0 \le x \le 5$.

Problem 5: Gautschi Exercise 3.13

1. Construct a trapezoidal-like formula $$\int_0^h f(x) \, dx = a f(0) + b f(h) + E(f), \quad 0 < h < \pi$$ which is exact for $f(x) = \cos x$ and $f(x) = \sin x$.

2. Does this formula integrate constants exactly?

3. (Ignore part (b) if you are looking at the book.)

Problem 6: Gautschi Exercise 3.36

The Gaussian quadrature rule for the Chebyshev weight function $$w(t) = \frac{1}{\sqrt{(1-t^2)}}$$ is known to be: $$\int_{-1}^1 f(t)(1-t^2)^{-1/2} dt \approx \frac{\pi}{n} \sum_{k=1}^n f(t_k^C)$$ where $$t_k^C = \cos\bigl(\frac{2k-1}{2n} \pi \bigr).$$ Use this fact to show that the unit disk has area $\pi$.