EXPLANATION FILE OF PROGRAM LAGRANGE
====================================
Lagrange Interpolation
----------------------
Lagrange interpolation is based on the simple premise that for every set of
sequential table values, there exists a unique polynomial curve that passes
through each and all of table values. The Lagrange polynomial for the cubic
case is
f1(x-x2)(x-x3)(x-x4)
f(x) = L3(x) = ---------------------
(x1-x2)(x1-x3)(x1-x4)
f2(x-x1)(x-x3)(x-x4)
+ ---------------------
(x2-x1)(x2-x3)(x2-x4)
(5.2.1)
f3(x-x1)(x-x2)(x-x4)
+ ---------------------
(x3-x1)(x3-x2)(x3-x4)
f4(x-x1)(x-x2)(x-x3)
+ ---------------------
(x4-x1)(x4-x2)(x4-x3)
The other orders of the Lagrange formula foIlow the same general pattern. ln
all cases, N + 1 table values are required for an Nth-degree polynomial fit.
Although the above equation may look formidable, we can easily see that when
x = x1 much canceling occurs and f(x) = f1 is obtained. The same procedure
applies for x2, x3, and x4. Therefore, this polynomial is the required cubic
because it passes through aIl the points. The uniqueness of this particular
curve fit foIlows from a theorem in polynomial theory. Note also that the in-
dependent variables (the xi's need not be equaIly spaced, a freedom that can
be used to advantage.
The Lagrange interpolation formulae for aIl orders are easy to program be-
cause of their simple and repetitive structure (see program Lagrange).
The inputs to program LAGRANGE are the number of table values, V, the table
values themselves, X(I) and Y(I), the interpolation point, X, and the degree
of the interpolation, N. The subroutine returns the interpolated value Y, and
an error check, N. If N is returned as zero, then a condition that called for
more table values than were available to the subroutine was encountered.
The interpolation is expected to become more accurate as the number of table
points employed in a given interval is increased. ln the sin x cubic interpo-
lation performed by the demonstration program, the accuracy obtained is fair-
ly good (better than 0.000001) using only 14 table values.
The table values used for the sin x interpolation example were not equally
spaced in x. For small values of x, sin x = x and there is not much curvature
to the function. Therefore, table values were concentrated in the high x
region where the function has considerably more curvature. The technique
employed for obtaining the table values will be discussed later. Hoowever, as
you can see from the observed errors, the choice was roughly optimal in terms
of minimizing the maximum error.
Perhaps the most important precaution associated with using LAGRANGE is res-
triction on the allowable range of the input interpolation point, X. The
interlation point must obey the following rule:
x(1) <= x <= x(V-N)
For example, if the number of table values is 14, and a cubic fit is chosen,
then x(l) <= x <= x(ll). It is also very important that the input table values
be in ascending x(I) order, and that no two table positions be equal [X(I) <>
X(I + 1)).
In another section, we will consider another algorithm called Newton divi-
ded-differences interpolation. The mechanics of this algorithm will appear
very different from the Lagrange formulation, but the resulting curve fits
are, in principle, identical (See file Newton.txt).
From [BIBLI 01].
--------------------------------------------------
End of file lagrange.txt