Math 753/853 HW4 Polynomial Interpolation

Problem 1

(a) Write a function polyeval(c,x) that implements Horner's method for polynomial interpolation without base points. I.e. given a vector of monomial coefficients $c$ you want to evaluate the polynomial

\begin{equation*} P(x) = \sum_{n=0}^{m-1} c_n x^n \end{equation*}

using Horner's method of nested multiplication. E.g. write the function so that it evaluates the polynomial

\begin{equation*} P(x) = c_0 + c_1 x + c_2 x^2 + c_3 x^3 + c_4 x^4 \end{equation*}

with this series of multiplications and additions

\begin{equation*} P(x) = c_0 + x \, [c_1 + x \, [c_2 + x \, [c_3 + x \, c_4]]] \end{equation*}

Your function should have inputs $c$ and $x$, and it should return $P(x)$. Make sure the function works when $x$ is a vector, returning a vector of values $P(x)$. Your function should also work equally well on all numerical types.

Warning: Note that the natural mathematical expressions for polynomials have indices that start at 0, but that Julia and many other programming languages use indices that start at 1. You'll have to negotiate this difference when writing your Horner evaluation function

In [ ]:

(b) Test your polyeval(c,x) function on a simple quadratic or cubic polynomial of your choice. Do this by constructing a simple polynomial function in Julia, e.g. $f(x) = 1 + 2x - 3x^2$, plotting a few points (x, f(x)) with dots, and then plotting the same polynomial as a smooth line using your polyeval function with inputs c=[1 2 -3] and an x vector created with linspace. Label the axes and add a legend that shows which symbol is for the datapoints and which is for polyeval.

In [ ]:

Problem 2

(a). Write a function polyeval(c,b,x) that implements Horner's method for polynomial interpolation with base points. E.g. given a vector of five coefficients c and four base points b you want to evaluate the polynomial

\begin{equation*} P(x) = c_0 + (x - b_0) \, [c_1 + (x - b_1) [c_2 + (x - b_2) [c_3 + (x - b_3) \, c_4]]] \end{equation*}

Your function should have inputs c, b, and x, and as in problem 1(a), it should work on vectors x of arbitrary numeric type.

In [ ]:

(b) As in problem 1(b), test your polyeval(c,b,x) function on a simple polynomial graphically.

In [ ]:

Problem 3

(a) To familiarize yourself with the Newton Divided Differences algorithm, work out on paper (or in text/markdown in this notebook) the cubic interpolating polynomial for the $(x,y)$ data points $(-2,8), (0, 4), (1,2), (3,-3)$.

In [ ]:

(b) Make a plot that verifies your interpolating polynomial graphically, showing the data points as dots and the interpolant as a smooth curve.

In [ ]:

Problem 4

(a) Write a function newtondivdiff(x,y) that returns (c,b), the polynomial coefficients c and the base points b for the polynomial interpolant that passes through the data points $(x_1, y_1), (x_2, y_2), \dots, (x_m, y_m)$. The return values $c$ and $b$ should be arranged to pass directly into your polyeval(c,b) function from problem 2.

In [ ]:

(b) Test your newtondivdiff(x,y) function with this series of steps

  1. construct a quadratic or cubic polynomial, e.g. $f(x) = 1 + 2x - 3x^2$
  2. construct a vector xdata with three values for a quadratic, or four for a cubic, e.g. xdata = [-2 -1 1].
  3. evaluate $f$ at xdata to get a vector of $y$ values ydata
  4. compute the coefficients c and basepoints b of the polynomial interpolant using newtondivdiff(xdata, ydata)
  5. evaluate your polynomial interpolant on a large number of $x$ points, e.g. x = linspace(-2, 2); y = polyeval(c,b,x)
  6. make a plot showing the datapoints xdata, ydata with dots and the smooth curve x,y with a line.
  7. label the axes and provide a legend
In [ ]:

Problem 5

The expected lifetime of an industrial fan decreases with operating temperature, according to the experimental data in this table

\begin{array}{c|c} temp~F & weeks \\ 77 & 57 \\ 104 & 45 \\ 122 & 38 \\ 140 & 32 \end{array}

Estimate the expected fan lifetime at 160 degrees Farenheit using polynomial interpolation. Make a plot showing the datapoints with dots and the interpolant over the range 50 to 160 weeks.

Problem 6

(a) Given these estimates of world human population over the last fifty years

\begin{array}{c|l} year & population~(billions) \\ 1960 & 3.026 \\ 1970 & 3.691 \\ 1980 & 4.449 \\ 1990 & 5.321 \\ 2000 & 6.128 \\ 2010 & 6.916 \end{array}

estimate the world population in 2025 by extrapolating the polynomial interpolant.

In [ ]:

(b) Add the current estimated world population of 7.404 billion in 2016 to the data set and give a revised estimate of 2025 population.

In [ ]:

(c) Make a plot showing the datapoints and the two polynomial interpolants over the range 1950 to 2030. Plot the interpolant without the 2016 data in blue and with the 2016 data in red.

In [ ]:

(d) What conclusions do you draw from the difference between the two curves?

In [ ]: