Numerical Analysis

Math 370  MWF 2:30-3:25
Spring 1997  127 Fowler

(02.28.97) \underline{Newton Polynomials and Divided Differences} Previously we have shown that it is a relatively trivial task to write down the Lagrange polynomials for a set of nodes (x_{0}, f_{0}), (x_{1}, f_{1}), …, (x_{n}, f_{n}) The only problem is that these polynomials are rather annoying to evaluate because they have expressions like: (X −x_{0})(X −x_{1}) … (X −x_{i−1})(X −x_{i+1}) … (X −x_{n}) which can easily overflow or underflow if n gets large. One solution of this is to use the Newton interpolating polynomials instead. (Yes, this is the same Sir Isaac Newton who invented calculus, Newton’s Method, Laws of Gravitation, et cetera.) The general form of the Newton interpolating polynomial of degree n is

P_{n}(x) = a_{0} + a_{1}(x − x_{0}) + a_{2}(x − x_{0})(x − x_{1}) + … a_{n}(x − x_{0})(x − x_{1}) … (x − x_{n−1})

where a_{k} for k = 0 to n are “appropriate constants”. The neat thing about this form of the interpolating polynomial is that computing the appropriate constants a_{k} is actually quite easy. In addition Newton polynomials have the proprty that they can be written in nested form very easily. For example,

P_{4}(x) = [[[[a_{4}] ∗ (x − x_{3}) + a_{3}] ∗ (x − x_{2}) + a_{2}] ∗ (x − x_{1}) + a_{1}] ∗ (x − x_{0}) + a_{0}

Show that the nested form of the Newton Polynomial is exactly the same as “natural” form of the Newton Polynomial. (Which form uses more arithmetic operations when evaluated?)

P_{4}(x) = a_{0}+a_{1}(x−x_{0})+a_{2}(x−x_{0})(x−x_{1})+a_{3}(x−x_{0})(x−x_{1})(x−x_{2})+a_{4}(x−x_{0})(x−x_{1})(x−x_{2})(x−x_{3})

\underline{Example} For the general Newton Polynomial P_{n}(x) what is the value of a_{0}? [To think of this, figure out what x value one would have to evaluate P (x) at to get P (x) = a_{0}]

Using your answer for a_{0} find a formula for a_{1}

Can you surmise a formula for a_{2}? What about a_{k}?

Divided Differences The zeroth divided difference of the function f(x) with respect to x_{i} is denoted by f[x_{i}] and is given by f(x_{i}). In other words, f[x_{i}] is just the function f(x) evaluated at x_{i},

f[x_{i}] = f(x_{i})

The first divided difference of f with respect to x_{i} and x_{i+1} is denoted by f[x_{i}, x_{i+1}] and defined recursively in terms of zeroth divided differences:

f[x_{i}, x_{i+1}] = \frac{f[x_{i+1}] − f[x_{i}]}{x_{i+1} − x_{i}}

As you may have guessed, in general the kth divided difference of f with respect to x_{i}, x_{i+1}, …, x_{i+k} is given by

f[x_{i}, x_{i+1}, …, x_{i+k}] = \frac{f[x_{i+1}, x_{i+2}, …, x_{i+k}] − f[x_{i}, x_{i+1}, …, x_{i+k−1}]}{x_{i+k} − x_{i}}

The value of a_{k}, the coefficient of x^{k} of the Newton Polynomial is exactly the kth divided difference. \underline{Example} Consider the following data for a Bessel’s function J(x) evaluated at certain points.

\begin{matrix}x & 1.0 & 1.3 & 1.6 & 1.9 & 2.2 \\ J(x) & 0.7651977 & 0.6200860 & 0.4554022 & 0.2818186 & 0.1103623 \end{matrix}

Let’s use a divided difference table to compute the coefficients of a Newton interpolating polynomial for this function in order to find J(1.5)

i x_{i} f[x_{i}]  f[x_{i−1}, x_{i}]  f[x_{i−2}, …, x_{i}] f[x_{i−3}, …, x_{i}] f[x_{i−4}, …, x_{i}]

Thus, P_{4}(x) = and J(1.5) ≈ P_{4}(1.5) =

NOTE: Mon Classes Are Held In Fowler 201