Newton Polynomials

This page is a brief introduction to the utility of Newton Polynomials find finding equations to calculate estimates of integrals and derivatives using discrete data points. It is not meant to be an exhaustive explanation or proof of Newton Polynomials.

Introduction

An interpolating polynomial is a polynomial that can be used to interpolate between a set of data points. Generally, an interpolating polynomial for an $$N$$-point data set will have $$N$$ coefficients and will therefore be a $$N-1$$st order polynomial. For example, to create an interpolating polynomial for five points, you would need to use a fourth-order polynomial. Higher-order interpolating polynomials suffer from overshoot/undershoot/oscillation issues in the presence of perturbances but lower-order interpolating polynomials can be useful in determining estimates of integrals and derivatives.

One issue with finding the coefficients of interpolating polynomials has to do with the linear algebra problem involved in finding the coefficients for interpolating polynomials. The following example shows both problems noted above. The top graph demonstrates the numerical issues that can happen when the linear algebra has an ill-conditioned matrix while the lower graph - which uses shifted versions of the years - demonstrates the overshoot/undershoot/oscillation problem:

• The top graph seems to follow the data points with the black line from polyfit, however, it turns out there are some significant residuals as evidenced by the black circles in the lower plot. The polynomial formed by the general linear regression version has all kinds of issues - a 12th order polynomial should not be that "fuzzy" but unavoidable roundoff errors are causing it to be like that!
• The bottom graph does a much better job of hitting all the data points and of being a smooth curve, but at the expense of a mild undershoot near the beginning and a large undershoot at the end. The residuals are seven orders of magnitude smaller, but it is unlikely that the actual data set follows this pattern.