5. Homework #5ΒΆ

For all programming assignments, please turn in your code along with your solution. Submissions should be made on Sakai.

Problem 1

Express the following polynomial in the correct form for evaluation by Horner’s method:

\[p(t) = 5t^3 - 3t^2 + 7t - 2\]

Problem 2

How many multiplications are required to evaluate a polynomial \(p(t)\) of degree \(n-1\) at a given point \(t\)

  1. Represented in the monomial basis?
  2. Represented in the Lagrange basis?
  3. Represented in the Newton basis?

Problem 3

  1. Determine the polynomial interpolant to the data

    \[\begin{split}\begin{array}{ccccc} t & 1 & 2 & 3 & 4 \\ p(t) & 11 & 29 & 65 & 125 \end{array}\end{split}\]

    using the monomial basis.

  2. Determine the Lagrange polynomial interpolant to the same data and show that the resulting polynomial is equivalent to that obtained in part (a).

  3. Compute the Newton polynomial interpolant to the same data using each of the three methods discussed in class (triangular matrix, incremental interpolation, and divided differences) and show that each produces the same result as the previous two methods.

Problem 4

  1. For a given set of data points \(t_1,\ldots,t_n\), define the function \(\pi(t)\) by

    \[\pi(t) = (t-t_1)(t-t_2)\ldots (t-t_n)\]

    Show that

    \[\pi'(t_j) = (t_j - t_1)\ldots (t_j - t_{j-1})(t_j - t_{j+1})\ldots (t_j - t_n)\]

    Hint: If \(f_1,\ldots,f_n\) are functions of a variable \(t\), then

    \[\frac{d}{dt} \prod_{i=1}^n f_i = \sum_{i=1}^n f_i' \prod_{j\neq i} f_j\]

  2. Use the result of part (a) to show that the \(j^{th}\) Lagrange basis function can be expressed as

    \[l_j(t) = \frac{\pi(t)}{(t-t_j)\pi'(t_j)}\]

Problem 5 (Extra Credit)

Horner’s rule provides an efficient method for evaluating a polynomial \(p(t) = \sum_{i=0}^n a_i t^i\) of degree \(n\) at any \(t=t_0\). In this exercise, we will develop a procedure for computing its derivative \(p'(t)\) at \(t_0\). Notice that for any \(t_0\), we can divide \(p(t)\) by \((t-t_0)\) to get quotient and remainder:

(1)\[p(t) = q(t)(t-t_0) + p(t_0)\]

where the quotient polynomial \(q(t)\) has degree \(n-1\):

\[q(t) = \sum_{i=0}^{n-1} b_i t^i\]

One can easily verify that \(p'(t_0) = q(t_0)\). So if we can find the coefficients \(b_i\) of the quotient polynomial \(q(t)\), we can use Horner’s rule to compute \(p'(t_0)\). If we substitute the expressions of \(p(t)\) and \(q(t)\) in equation (1) and equate the coefficients of \(t^i\) on the LHS and RHS, and solve for the coefficients \(b_i\) and remainder \(p(t_0)\), we get a series of equations that can be organized as a recursion relation:

\[\begin{split}\begin{eqnarray*} b_{n-1} &=& a_n \\ b_{i-1} &=& a_i + t_0b_i \enspace \mbox{for } i=1\ldots n-1 \\ p(t_0) &=& a_0 + t_0b_0 \end{eqnarray*}\end{split}\]

Write a program that uses the above recursion relation to evaluate both the polynomial \(p(t)\) and it’s derivative \(p'(t)\) at \(t=t_0\). Show its output on few example polynomial functions (which you are free to choose).