next up previous notation contents
Next: 3.3.2 Charts Up: 3.3 Linear Interval Arithmetic Previous: 3.3 Linear Interval Arithmetic

3.3.1 Interpolating Polynomials

Given the set tex2html_wrap_inline35567 , consider the three functions tex2html_wrap_inline35569 , tex2html_wrap_inline35571 , and tex2html_wrap_inline35573 , defined as follows:

figure17144

tex2html_wrap_inline34175 is a d-degree polynomial with tex2html_wrap_inline35579 . Consider the function tex2html_wrap_inline34165 , along with a representative G, tex2html_wrap_inline35585 . We may deduce that G is a function, and that:

math17172

It follows that the functions tex2html_wrap_inline35589 , tex2html_wrap_inline35591 , and tex2html_wrap_inline35593 are well defined, for our choice of G. Since tex2html_wrap_inline35597 , the function tex2html_wrap_inline34201 ,

math17189

interpolates G. tex2html_wrap_inline31337 is the quadratic Lagrange interpolating polynomial of G.  

tex2html_wrap_inline31337 may be expressed in standard polynomial form:

math17203

with

align17215

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

math17254

The set G, and the associated polynomial tex2html_wrap_inline31337 , are:       where:

math17268

Consider tex2html_wrap_inline34233 , a richer representation of g; tex2html_wrap_inline35635 . The representation tex2html_wrap_inline34233 has one of the preceding properties if all three-member subsets of tex2html_wrap_inline34233 have the same property:

math17279

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

math17283

where tex2html_wrap_inline35643 . For G = g, the usual definitions of linearity and concavity are equivalent to those given here. Let tex2html_wrap_inline35647 state that tex2html_wrap_inline34233 has one of the above properties:  

math17289

For all representations tex2html_wrap_inline34251 ,

math17293

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


next up previous notation contents
Next: 3.3.2 Charts Up: 3.3 Linear Interval Arithmetic Previous: 3.3 Linear Interval Arithmetic
Jeff TupperMarch 1996