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