3.2.2 Interpolating Polynomials

Given the set , consider the two functions and , defined as follows:

is a d-degree polynomial with

The above defines , the   Kronecker delta. The set G   represents the function using two distinct elements of g:  

we here envision the unary function g as a set, as defined in section . From this, we may deduce that G is also a function, and that . It follows that the functions and are well defined, for our choice of G. Since , the function ,

interpolates G:

is the linear Lagrange interpolating polynomial   of G.

may be expressed in standard polynomial form:

is the coefficient of in , a d-degree polynomial. The leading coefficient,   , is of special interest, and may be denoted simply by :

The set G, and the associated polynomial , are:      

• monotonically decreasing if ,
• constant if , and
• monotonically increasing if ;

where:

Consider , a richer representation of g,

The representation has one of the preceding properties if all two-member subsets of have the same property:  

All three properties are considered to be satisfied by sparse representations of g since

where . For G = g, the usual definitions of constancy and monotonicity are equivalent to those given here. Let   state that has one of the above properties:

For all representations ,

The Lagrange interpolating polynomial for is defined as follows:

Using the constant and linear interpolating polynomials we will construct constant bounds for many common functions.

Jeff Tupper

March 1996