Lagrange Coefficients

Suppose that you know a function, f, for each of several values of its argument, but you need to know its value for some other argument. Let S be the set of arguments where the value is known.

This arises when we are interpolating in a large table for some mathematical function and indeed this is the original context of Lagrange’s invention. The table gives some logarithms thus:

2.3567 0.372304301812888
2.3568 0.372322729498556
2.3569 0.372341156402345
2.3570 0.372359582524324
2.3571 0.372378007864557

but you need to know log(2.356940377234422). Linear interpolation uses the logs of 2.3569 and 2.3570 but since the log function is not actually linear this is a poor estimate. If LC is the Scheme function
((fileVal "LagCoef") '() 0 zero? 1 + - * /)
then
(LC '(2.3567 2.3568 2.3569 2.3570 2.3571) 2.356940377234422)
returns the value (0.02247651411873753 -0.1539520941702458 0.8028547344459583 0.3624684129231309 -0.0338475673175809) which comprises the coefficients for forming a linear combination of the entries from the table. That combination gives 0.37234859645491425 and log(2.356940377234422) = 0.3723485964549145 .
(LC '(-2 -1 0 1 2) 0.40377234422)
Yields the same 5 value and thus tables of Lagrange coefficients have been published for equal intervals.
(LC '(0 1) ⅔) yields (⅓ ⅔)
which should match the intuition that if you are twice as far from 0 as from1 then weight that function value at 1 twice that at 0. f(⅔) ≅ ⅓f(0) + ⅔f(1).

The Math

If p is a polynomial of degree n−1 and S is a set of n distinct reals then

p(x) = sum[i in S] (p(i) *
    (product[j in S but not i] (x - j))/
    (product[j in S but not i] (i - j)))

The coefficients are the quotient of products in the above.

It is not necessary that the arg values be spread uniformly but it is necessary that they be distinct. (LC args x) is a polynomial in x whose degree is one less than the length of args. It is in fact the unique polynomial that takes on all the tabulated values. That the polynomial is the correct sort of function to invoke here is related to the fact that interesting functions tend to have small higher derivatives and also the reason that Taylor series work.

Other Uses of the Formula

The above was the original motivation for Lagrange coefficients but the logic of polynomials fitting given data depends only on the logical properties of fields and Lagrange’s formula can be applied in finite fields as well. Whereas polynomials fitting tabulated values above is a bit mysterious, recent applications are to fit the data to polynomials, as in Shamir secret sharing where polynomial coefficients are selected randomly except for the constant which is the secret. The polynomial values are distributed among a committee members. If the polynomial is of degree q−1 then a quorum of q members of the committee can collaborate to reproduce the entire polynomial and the p(0) yields the secret.

Another application is Reed-Soloman erasure coding where a polynomial of degree q is fit thru q+1 portions of data to be stored in less than perfectly reliable places. The polynomial is evaluated and stored for several other arguments as well and if some of either set are lost then the polynomial is still determined by the surviving values, if at least q+1 of them survive.