Visualizingand Understanding the Components of Lagrange and Newton Interpolation
One of the standard topics in numerical analysis courses is the subject of interpolation with particular emphasis on the Lagrange and Newton Interpolating formulas. In both cases, the usual approach is highly computational as one works to construct the polynomial of degree n that passes through interpolating points.
However, as Richard Hamming, one of the giants of modern numerical analysis, put it, “The purpose of computing is insight, not numbers” [3]. In this article, we will look graphically at the functionalcomponents of each of these two interpolating formulas to see the kinds of deeper insights that can be achieved.
The Lagrange Interpolating Formula Suppose that we have the points, , …,, where all of the are different, though not necessarily uniformly spaced. These interpolating points then determine a unique polynomial of degree (or possibly lower, if the points happen to lie on such a curve). One way to express the equation of this polynomial is with the Lagrange Interpolating Formula:
Equivalently, if we write this formula without the summationnotation, it becomes
Notice that this polynomial is composed of distinct polynomial terms, each of degree (provided). Either way, both of these are rather daunting expressions for students and consequently it is not surprising that many tend to miss some of the key underlying concepts.
As an example, consider the three interpolating points, , and that determine the quadratic function whose graph is shown in Figure 1. Clearly, this function
passes through each of the three interpolating points. The corresponding expression for this interpolating polynomial is
(1)
. (2)
More to the point here, this function is a linear combination of three distinct quadratic functions, shown in the first expression. Let’s see how each of these functions behaves, as shown in Figure 2. (The heavier fourth curve shown is the Lagrange interpolating polynomial.) Although the shapes of two of the curves totally miss the shape of the interpolating polynomial, each of the three quadratics passes through just one of the interpolating points. Moreover, not only does each one completely miss the other two interpolating points, but also each quadratic has its real zeros precisely in line vertically with the other two interpolating points. In addition, observe that each pair of quadratic components share a common zero. To see why, notice that the component quadratic functions are constructed in such a way that each of them has a pair of factors that correspond to two of the three interpolating points. It is not coincidence that there is such correspondence between the zeros and the interpolating points.
Furthermore, look at the first term in the first expression (1) for. Corresponding to the first interpolating point , the coefficient of is precisely equal to the value, 2, of y at this point. Also, at this point where , the factors in the numerator precisely cancel the factors in the denominator, so the total contribution of this first term at is . Similarly, the second term in the expression (1) for is constructed in such a way that when , we have , and so on for the third term. In general, for any , the terms in the Lagrange formula are constructed in such a way that each one has zero contribution at all but one of the interpolating points and contributes precisely the given value of at the remaining interpolating point.
The NewtonInterpolating Formula Again, suppose that we have the points , , …, ,where all of the are different. For simplicity, we consider the case where these ’s are uniformly spaced with for each . These interpolating points determine a unique polynomial of degree (or possibly lower, if the points happen to lie on such a curve). Another way to express the equation of this polynomial is with the Newton Forward Interpolating Formula:
(3)
where
,
,
,
Notice that this polynomial is also composed of distinct polynomial terms, but each of degree , . Term by term, each polynomial is of one degree higher than the previous one.
At a quick glance, the above formula is obviously very similar to the formula for the th degree Taylorpolynomial approximation for a function at :
(4)
Let’s see just how close the two are. Consider what happens to Newton’s interpolating formula (3) as the stepsize . Clearly, thequantitiesin the polynomial expression (3) converge toward the successive derivatives of the function at . Moreover, as , all of the interpolating points approach , though they do retain the uniform spacing. As all the interpolating points coalesce at , we see that the products of the various factors all converge toward and so approach the successive powers of . Thus, the Taylorpolynomial of degree for a function is the limit of the Newton interpolating polynomials as .
We next consider how Newton’s interpolating formula comes about (which might reflect Newton’s own thought process in originally developing the formula). Suppose we start with the first two points and , which determine a line whose algebraic representation can be written
Now suppose we also have the third point . Unless the three points happen to be collinear, which is highly unlikely, the line determined by the first two points will miss the third point. In particular, if we extend that line until it reaches , then the height along the line is
The question we pose is: How can we adapt the above linear function to create a quadratic function that also passes through the third point? To do so, we want to introduce a quadratic term that forces the entire quadratic function to pass through the third point while maintaining the same two values and at and , respectively. To do this, we write the quadratic polynomial in the form
where A is some constant to be determined. Notice that the presence of the factors and guarantee that the quadratic term has zero contribution at the first two interpolating points.
To determine A, we impose the condition that the value of the quadratic function when must be . We therefore obtain
Consequently,
and so
.
Notice that the numerator is the second difference . Therefore, we write
and
When doing this in class, we suggest asking the students to extend the argument used to derive the cubic Newton interpolating formula.
Let’s find the interpolating quadratic using the Newton interpolating formula for the above example where the three interpolating points are , , and . We have
Notice that the sum of the first two terms, , determines the linear function that pass through the first two points and . Figure 3 shows the graphs of and . Let’s include the graph of the quadratic term, denoted by , to see how the quadratic term alone changes the interpolation polynomial based on the first two points into the interpolation polynomialbased onall three points. Figure 4 shows that the quadratic component has two real zeros precisely in linevertically with the first two interpolating points. Therefore, automatically contributes zero at and so that at and , which implies the presence of in does not alter the perfect fit of the first two points by . In addition, observe that at , the value of is the amount that “bends” the linear function at in order for the to pass through the third interpolating point .
To better understand the process of finding the interpolating polynomial by using Newton formula, we expand the data set of , , and to include two additional points , . These five points determine a quartic polynomial. We show these successive Newton interpolating polynomials in Figure 5. Once again, notice
that the linear function passes through the first two points, though it completely misses all the remaining points. The quadratic function passes through the first three points, but then misses all the subsequent points. The cubic function passes through the first four points, but comes nowhere near the final point. It is only the quartic function that passes through all five points.
The approach used to introduce Newton’s formula in many numerical analysis texts tends to be rather abstract and, as such, conveys little in the way of understanding to many students. Moreover, some texts give a somewhat misleading image of what is actually happening; they tend to say something to the effect that, if you have interpolating points, you usually need a polynomial of degree n to fit them, and any lower degree polynomial misses the points. The “derivation” and examplesused above actually suggest that this is not exactly the truth. However, it is misleading to suggest that the lower degree polynomials miss the points; they only miss the points further to the right.
Interpolation and Approximation of Functions Interpolation provides an important tool for approximating a function. When we work with a function that involves more than the basic operations, we may want to replace it with a polynomial for inexpensive and quick computations. In this case, often what comes to our mind is the Taylor approximation of a function, provided that the function is sufficiently differentiable. Because of the similarity of Taylor approximation and Newton formula, we now consider the interpolating polynomials in the Newton form for the approximation of functions.
As an example, we approximate the sine function on the interval . Let’s interpolate the sine function at the five uniformly spaced points , , ,, and . Just as we did earlier, we construct the successive Newton interpolating polynomials, shown in Figure 6. Notice that the quadratic interpolating polynomial fits the sine function reasonably well on the interval . As expected, the quadratic polynomial misses all the points on the right. The cubic polynomial and quartic polynomial are identical because the fourth difference is zero. This is the advantage of using the Newton formula that determines the degree of the interpolating polynomial as we construct it. Had we
used the Lagrange formula, we would only learn the degree of the interpolating polynomial after simplifying the expression for. Overall, approximate the sine function reasonably well on the entire interval .
On the other hand, the cubic Taylor polynomial for at , , is shown in Figure 7 along with the sine function and cubic interpolating polynomial. We see that the Taylor approximation achieves high accuracy between and roughly ,then the difference between the cubic Taylor polynomial and the sine function grows significantly as moves to the right beyond . Clearly, the interpolating polynomial gives us a better approximation of a function on a larger interval compared with the Taylor approximation.
Comparisons Between Lagrange and NewtonInterpolation The Lagrange and Newton interpolating formulas provide two different forms for an interpolating polynomial, even though the interpolating polynomial is unique. When we want a quick symbolic expression of the interpolating polynomial, the Lagrange formula seems to be the way to go. For this reason, the Lagrange form is most often used for deriving formulas for approximating derivatives and integrals. For example, many numerical analysis textbooks (for example, [1] and [2])establish the trapezoidal rule and Simpson’s rule by using the Lagrange formula for linear and quadratic interpolating polynomials to approximate the integrand, respectively. However, the Newton formula is much better for computation than the Lagrange formula.
When using the interpolating polynomials for working with functions that are stored in tabular form, we often choose the Newton formula. As we will show below, the forward differences that determine the coefficients of the Newton formula can be easily constructedusing a tabular form. More importantly, the Newton formula provides a generally accurate idea of when the degree n is sufficiently large by observing the size of the terms with higher-order forward differences. This is a useful technique in deciding what degree polynomial to use.
Suppose we are given five points , , , , and , which is based on an example in [1]. We construct the forward difference table for these five points, shown in Table 1.
Table 1 Forward difference table for the five points
0 / 2.0 / 1.414214 / 0.034924 / – 0.000822 / 0.000055 / – 0.0000051 / 2.1 / 1.449138 / 0.034102 / – 0.000767 / 0.000050
2 / 2.2 / 1.483240 / 0.033335 / – 0.000717
3 / 2.3 / 1.516575 / 0.032618
4 / 2.4 / 1.549193
The last five entries in the first row are used to determine the coefficients of the Newton interpolating polynomial
By applying the usual optimization approach from Calculus I to the fourth degree polynomial term
on the interval , we find that
.
Then the largest possible value the last term of that will contribute to the interpolating polynomial at any point in the interval is roughly.
This result may be improved on by following a common practice used in approximating functions with the Newton formula. When we want to approximate the function at a pointx that is inside the first half of the interval, we use the above Newton forward formula. Otherwise we use the Newton backward formula, or equivalently, we apply the Newton forward formula to the same table where the entries are listed in reverse order. If we stay with the original notation for the interpolating points for . We define the backward differences as follows. Let ,, and in general, , for . Then the Newton Backward Interpolating Formula can be expressed as
Assume that we wantto approximate the function between 2.0 and 2.2, the first half of the interval . Now the maximum value of the last term of on is only about . Since our data points are given to decimal places, the Newton forward formula of order greater than three won’t increase the accuracy of the approximation for x in the interval . Therefore, we have achieved the desired level of accuracy by using polynomials of degree three (or even lower). Table 2 gives the approximations of, , and by using , , and . The identical values of and at , , and confirm the above observation. A similar analysis can be given to the approximation of the function between 2.2 and 2.4 using the Newton backward formula. We present the results of approximations of , , and using Newton backward formula in Table 3.
Table 2 Example of use of Newton forward formula
2.03 / 1.424691 / 1.424777 / 1.424780 / 1.424780 / 1.4247802.09 / 1.445646 / 1.445683 / 1.445684 / 1.445684 / 1.445684
2.15 / 1.466600 / 1.466292 / 1.466289 / 1.466289 / 1.466289
Table 3 Example of use of Newton backward formula
2.24 / 1.497004 / 1.496660 / 1.496663 / 1.496663 / 1.4966632.31 / 1.519837 / 1.519869 / 1.519868 / 1.519868 / 1.519868
2.37 / 1.539408 / 1.539483 / 1.539480 / 1.539480 / 1.539480
In contrast, the Lagrange interpolation approach requires far more computation – each time you increase the number of interpolating points by one, you have to recalculate everything. This makes Lagrange interpolation less convenient for seeking the lowest degree interpolating polynomial that fits the data with a given error tolerance.
Interpolation and Regression From time to time, we may have a large set of data. If we have points (where is large), the interpolating polynomial is of the degree , presuming that the points do not fall onto a polynomial of lower degree. This high degree polynomial is an exact match to the data points, but can be a very poor match between those points. This can happen because the polynomialmay change direction up to times. In the process, the interpolating polynomial may shoot way up or down after passing through each interpolating point in order to reach the next turning point to come back down/up to hit the next interpolating point. We illustrate such a case in Figure 8where the interpolating points are , , , , , and . The problematic portions of the interpolating polynomial are between the first two interpolating points and between the last two interpolating points. Such an oscillatory behavior may dramatically affect the accuracy of approximationbetween interpolating pointsand make the approximation very sensitive to any changes of the interpolating points. Moreover, there is likely a high computational cost of using the interpolating function. If we opt for a lower degree polynomial by using the method we discussed above, we will have to constantly get back to the data to select a subset of interpolating points according to the value of x of interest in order to get a good approximation.
If the exact fit is not the only concern, we may overcome these difficulties by finding a lower degree polynomial that will give reasonable accuracy. One way to find such a lower degree polynomial is to use regression. A regression polynomial only attempts to capture the overall trend in a set of data and, as such, can potentially give much better approximations between the interpolating points, even though it doesn’t necessarily pass through any of them.
Concluding Remarks We began this article by quoting Richard Hamming’s famous statement about the purpose of computing being insight. While interpolation methods are too often considered simply as computational procedures, we hope that our emphasis on the components of those formulas provides much in the way of insight into where those formulas came from, why they work,and how they should be used.
References:
[1]Atkinson, K. 1988.An Introduction to Numerical Analysis,2nd Ed.New York: John Wiley & Sons.
[2]Burden, R. and Faires, J. 2010.Numerical Analysis, 9th Ed. Boston: Brooks/Cole.
[3]Hamming, R. 1987. Numerical Methods for Scientists and Engineers, 2nd Ed. New York: Dover Publications.
------
AbstractThis article takes a close look at Lagrange and Newton interpolation by examining graphically the components of each of these formulas. While interpolation methods are too often considered simply as computational procedures, we demonstrate howhope that our emphasis on the components of the polynomial terms in these formulas provides much in the way of insight into where these formulas came from, why they work, and how they should be used.
Keywordsinterpolating polynomial, Lagrange formula, Newton formula, Taylor polynomial
Suggested Running HeadComponents of Lagrange and Newton Interpolation
1