Homework 4

Due: Thursday 4/05

---

1. Write down the polynomial that interpolates $f(x) = e^x$ at the points $x_0 = 0$, $x_1 = 1$ in Lagrange form (using Lagrange basis functions) and in Newton's form (using divided differences). Check that these polynomials are the same.

2. It was mentioned in class that the Vandermonde matrix can be very badly conditioned and is therefore not ideal for accurately solving $n$ point interpolation problems. However, some of this ill-conditioning can be mitigated by scaling the data. Suppose we are given data points $(x_0,y_0), (x_1,y_1), \ldots (x_n, y_n)$ with $x_0 < x_1 < \ldots x_n$. Our goal will be to scale the $x$ values by letting

   \[ z_i = \frac{x_i-\alpha}{\beta}, \]

   where $\alpha$ and $\beta$ are given numbers with $\beta >0$. The data point $(x_i,y_i)$ now change to $(z_i,y_i)$. Also the interpolation polynomial now changes to

   \[ P_n(z) = a_0 + a_1z + \ldots + a_nz^n, \]

   1. The original data interval is $x_0 \leq x \leq x_{n}$. What is the data interval when using $z = (x- \alpha)/\beta$? What matrix equation must be solved to find the $a_i's$ in the above formula for $P_n(z)$?

   2. Taking a hint from the previous step, the data will be scaled so that the new data interval is going to be $-1\leq z \leq 1$. What must $\alpha$ and $\beta$ be here?

   3. Consider the follow population data for the USA over the 100 year period between $1900$ and $2000$.

      \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c} x & 1900 & 1910 & 1920 & 1930 & 1940 & 1950 & 1960 & 1970 & 1980 & 1990 & 2000\\\hline y & 76.21 & 92.23 & 106.0 & 123.2 & 151.3 & 179.3 & 203.3 & 226.5 & 248.8 & 281.4 & 308.7 \end{array}

      The $y$ values represent the population of the USA in millions. Using the direct approach (Vandermonde), plot the interpolation function using the original $x_i$ data. You should use MATLAB's vander command to construct the Vandermode matrix $\mathbf{V}$. Using MATLABs cond commmand, what is the condition number $\kappa_2(\mathbf{V})$ of the associated Vandermonde matrix $\mathbf{V}$?

   4. Using the same population data from part $(c)$, scale the data to $[-1,1]$ and find the coefficients for $P_n(z)$? What is the condition number in this case? Once the a_i's are computed the resulting (unscaled) polynomial is

      \[ P_n(x) = a_0 + a_1\left(\frac{x- \alpha}{\beta}\right) + \ldots + a_n\left(\frac{x-\alpha}{\beta}\right)^n. \]

      Plot this function and compare it with the function you found in part (c). Remark on the difference between the two.

3. Here, we consider the following function

   \[ g(x) = \begin{cases}2 + 3x^2 + \alpha x^3,& \text{if } -1 \leq x \leq 0,\\ 2 + \beta x^2 - x^3 &\text{if } 0 \leq x \leq 1. \end{cases} \]

   1. For what values of $\alpha$ and $\beta$, if any, is $g(x)$ a cubic spline for $-1\leq x \leq 1$? These values are to be used for the remainder of the problem

   2. What were the data points that gave rise to this cubic spline?

   3. For what values of $\alpha$ and $\beta$ is $g(x)$ a natural cubic spline?

   4. For what values of $\alpha$ and $\beta$ is $g(x)$ a clamped cubic spline?

4. Using B-splines, find a natural cubic spline (by hand) that interpolates the table

   \[ \begin{array}{c|c|c|c} x & -1 & 0 & 1 \\\hline y & 13 & 7 & 9 \end{array} \]

5. Let $\mathbf{A}$ be the $5\times 3$ identity matrix

   \[ \mathbf{A} = \begin{bmatrix}1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix} \]

   and let $\mathbf{b} = (b_1,b_2,b_3,b_4,b_5)^{\top} \in \mathbb{R}^5$. Find the least squares solution of

   \[ \mathbf{A}\mathbf{x} = \mathbf{b} \]

   and calculate it's residual $\mathbf{r} = \mathbf{b} - \mathbf{A}\mathbf{x}$ and 2 - norm $\|\mathbf{r}\|_2$.