Next: 3.3.2 Charts
Up: 3.3 Linear Interval Arithmetic
Previous: 3.3 Linear Interval Arithmetic
Given the set ,
consider the three functions ,
, and
, defined as follows:
is a d-degree polynomial with
.
Consider the function ,
along with a representative G, .
We may deduce that G is 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 quadratic Lagrange interpolating polynomial of G.
may be expressed in standard polynomial form:
with
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:
- concave down if ,
- linear if , and
- concave up if ;
where:
Consider , a richer representation of g;
.
The representation has one of the preceding
properties if all three-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 linearity and concavity are equivalent
to those given here.
Let state that has one of the above properties:
For all representations ,
Using the linear and quadratic interpolating polynomials we will
construct linear bounds for many common functions.
Next: 3.3.2 Charts
Up: 3.3 Linear Interval Arithmetic
Previous: 3.3 Linear Interval Arithmetic