Question

Consider the funetion \(f\) given in the following table. $$ \begin{array}{ccccc} x & 1 & 2 & 4 & 6 \\ \hline f(x) & 2 & 3 & 5 & 9 \end{array} $$ a) Construct a divided difference table for \(f\) by hand, and write the Newton form of the inter- polating polynomial using the divided differences. b) Assume you are given a new data point for the function: \(x=3, y=4\). Find the new interpolating polynomial. (Hint: Think about how to update the interpolating polynomial you found in part (a).) c) If you were working with the Lagrange form of the interpolating polynomial instead of the Newton form, and you were given an additional data point like in part (b), how easy would it be (compared to what you did in part (b)) to update your interpolating polynomial?

Short answer

In this exercise, we constructed a Newton interpolating polynomial using the divided differences of a given function, added a new data point, and updated the polynomial accordingly. We found that updating a Newton interpolating polynomial was simpler and more efficient compared to updating a Lagrange interpolating polynomial. This is because for Newton's form, we only needed to update the divided differences table and add a new term to the polynomial, while in the Lagrange form, we would have to recalculate all the individual terms and include a new product of terms for the new data point.

Step-by-step solution

Construct the divided difference table for \(f\) by hand

First, we need to compute the divided differences for the given data points \((x, f(x))\). To do this, we work our way through the rows of the divided difference table, with each row building on differences computed in the previous row: $$ \begin{array}{ccccc} x & f(x) & f[x_i, x_{i+1}] & f[x_i, x_{i+1}, x_{i+2}] & f[x_i, x_{i+1}, x_{i+2}, x_{i+3}] \\ \hline 1 & 2 & & & \\ & & 1 & & \\ 2 & 3 & & 0.5 & \\ & & 2 & & 0.1667 \\ 4 & 5 & & 2 & \\ & & 4 & \\ 6 & 9 & \\ \end{array} $$

Write the Newton interpolating polynomial

Now, we'll use the computed divided differences to write the Newton interpolating polynomial \(P(x)\): $$P(x) = 2 + (x - 1) + (x - 1)(x - 2)\frac{1}{2} + (x - 1)(x - 2)(x - 4)\frac{1}{6}$$

Add a new data point, \((x, y) = (3, 4)\)

We have a new data point \((3, 4)\) to add to our existing table. Let's update our divided differences table with this new point: $$ \begin{array}{cccccc} x & f(x) & f[x_i, x_{i+1}] & f[x_i, x_{i+1}, x_{i+2}] & f[x_i, x_{i+1}, x_{i+2}, x_{i+3}] & f[x_i, x_{i+1}, x_{i+2}, x_{i+3}, x_{i+4}] \\ \hline 1 & 2 & & & & \\ & & 1 & & & -0.1 \\ 2 & 3 & & 0.5 & & \\ & & -1 & & 0.1667 & \\ 3 & 4 & & -2 & \\ & & 1 & \\ 4 & 5 & & 0.5 & \\ & & 2 & & -0.1667 \\ 6 & 9 & \\ \end{array} $$

Update the interpolating polynomial with the new data point

Using the updated divided differences, the new interpolating polynomial \(P'(x)\) is constructed: $$P'(x) = 2 + (x - 1) + (x - 1)(x - 2)\frac{1}{2} + (x - 1)(x - 2)(x - 4)\frac{1}{6} + (x - 1)(x - 2)(x - 4)(x - 3)(-0.1)$$

Compare updating Newton and Lagrange interpolating polynomials

For the Newton form of interpolating polynomial, adding a new data point required updating the divided differences table and then simply adding a new term to the polynomial. In contrast, updating a Lagrange interpolating polynomial with a new data point can be more time consuming, as it requires recalculating the individual terms for each original data point and then multiplying them by a new product of terms based on the new data point. Therefore, updating a Newton interpolating polynomial can often be more efficient and easier than updating a Lagrange interpolating polynomial.

Key concepts

Newton interpolating polynomial

Interpolation is a common numerical method used to estimate unknown values that lie between a set of known data points. One type of interpolation is the Newton interpolating polynomial, named after Sir Isaac Newton. It is particularly effective when the set of data points changes, as adding a new data point results in simply adding one additional term to the polynomial. This polynomial represents an n-th degree polynomial constructed as sums of products of the data points and their corresponding divided differences.

In the given exercise, constructing a Newton interpolating polynomial involved calculating a table of divided differences from the given data, and then formulating the polynomial using these divided differences. As illustrated in the step-by-step solution, after computing the divided differences for each of the data points, the polynomial was expressed in the Newton form, considering the coefficients derived from the divided differences and the specific structure allowing each term to build off the previous ones.

Lagrange interpolating polynomial

Another form of polynomial interpolation is the Lagrange interpolating polynomial. Unlike the Newton polynomial, the Lagrange polynomial is constructed directly from the given data points, without the need for divided differences. Each term of a Lagrange polynomial is a product of Lagrange basis polynomials, which are specifically designed to take the value of 1 at their respective data point and 0 at all others.

This form of the polynomial can be more cumbersome to update with new data points, as it requires a full recomputation for each data point rather than a simple expansion. In terms of the effort involved, adding a new data point to the Lagrange polynomial is generally less straightforward compared to the Newton method, predominantly because each Lagrange basis polynomial needs to be recalculated to include the newly added point.

Polynomial updating

The process of polynomial updating refers to modifying an existing interpolating polynomial to incorporate additional data points. For the Newton polynomial, updating is relatively simple: the existing structure of the polynomial allows for a new term to be added for each new data point without altering the previous terms. This characteristic makes the Newton form more adaptable and dynamic in scenarios where data is being continuously collected or updated.

As shown in the exercise solution, when a new data point was added, the divided differences table was updated first. The new polynomial was then formed by adding a term to the existing polynomial that integrated the new data point. In contrast, with the Lagrange polynomial, the introduction of a new point necessitates a complete reevaluation of the polynomial, signifying a more labor-intensive updating process.

Numerical analysis

The field of numerical analysis focuses on the development and use of algorithms to solve mathematical problems through numerical approximation. This discipline is imperative for handling problems that do not have closed-form solutions or are too complex for analytical solutions. Numerical analysis covers a multitude of topics, including interpolation, numerical differentiation and integration, solving of differential equations, and linear algebra problems.

In the context of polynomial interpolation, numerical analysis provides methods like Newton and Lagrange interpolations to estimate values and model trends based on discrete data points. The effectiveness and computation time of these methods are essential considerations when addressing real-world problems. As illustrated by the exercise, the choice of interpolation method can significantly affect the ease and efficiency with which models can be updated and refined when new information becomes available.