next up previous notation contents
Next: 3.3.23 Charts Up: 3.3 Linear Interval Arithmetic Previous: 3.3.21 Examples with Bumpy Functions

3.3.22 Binary Functions: Two-Step Method

The approach taken for binary functions with constant interval arithmetic may be used with linear interval arithmetic. As before, we focus on binary grid functions. When presented with a binary function, we will cut it into sections where each section may be extended to a grid function which fits into a class.

As with unary functions, we will partition the domain based on monotonicity, so we may handle the upper and lower bounds independently. Concavity is also used when partitioning:

figure22341

figure22349

An upper bound will be determined for tex2html_wrap_inline35733 in two stages: first, a bilinear upper bound tex2html_wrap_inline36833 of tex2html_wrap_inline35733 will be determined; then, a linear upper bound of h will be constructed; this upper bound will be an upper bound of g. A function tex2html_wrap_inline36833 is bilinear if both tex2html_wrap_inline36843 and tex2html_wrap_inline36845 are linear.

An approximate upper bound tex2html_wrap_inline36847 is constructed from g:

math22366

where tex2html_wrap_inline31337 is the bilinear Lagrange intepolating polynomial of the set G, a subgrid of g:

math22370

Let tex2html_wrap_inline36857 . The location of the subgrid g is constrained by which concavity class g belongs to:

math22374

math22389

We assume that tex2html_wrap_inline36863 ; if this is not the case we may extend g. Where g is concave up, we assume that G is finer than g:

math22404

math22408

For differentiable g, this corresponds to matching both the values and derivatives of g. When tex2html_wrap_inline36877 , the mixed partial at (p,q) is matched.

When tex2html_wrap_inline36881 , tex2html_wrap_inline36847 is an upper bound. This is shown by the following proof by contradiction; the diagram given accompanies the proof.

figure22418

Assume that tex2html_wrap_inline36847 fails, at (x',y'), to be an upper bound of g:

math22569

Consider tex2html_wrap_inline36913 , which has an upper bound tex2html_wrap_inline36915 , given by tex2html_wrap_inline31337 with
tex2html_wrap_inline36919 , since tex2html_wrap_inline36921 . Since tex2html_wrap_inline36923 is an upper bound of tex2html_wrap_inline35177 for tex2html_wrap_inline36927 , tex2html_wrap_inline36929 is an upper bound of tex2html_wrap_inline36931 . It follows that tex2html_wrap_inline36933 is an upper bound of tex2html_wrap_inline36915 , since both functions are linear; so tex2html_wrap_inline36937 , which contradicts our initial assumption.

When tex2html_wrap_inline36939 , tex2html_wrap_inline36847 is again an upper bound, and may be proven with a similar argument, which follows.

figure22590

Assume that tex2html_wrap_inline36847 fails, at (x',y'), to be an upper bound of g:

math22569

Consider tex2html_wrap_inline36913 , which has an upper bound tex2html_wrap_inline36915 , given by tex2html_wrap_inline31337 with
tex2html_wrap_inline36919 , since tex2html_wrap_inline36921 . Since tex2html_wrap_inline36923 is an upper bound of tex2html_wrap_inline35177 for tex2html_wrap_inline36927 , tex2html_wrap_inline36929 is an upper bound of tex2html_wrap_inline36931 . It follows that tex2html_wrap_inline36933 is an upper bound of tex2html_wrap_inline36915 , since both functions are linear; so tex2html_wrap_inline36937 , which contradicts our initial assumption.

When tex2html_wrap_inline36997 , tex2html_wrap_inline36847 is again an upper bound, and may be proven with the preceding argument. Alternatively, one may consider g'(x,y) = g(y,x), after ensuring that tex2html_wrap_inline37003 .

The proof does not hold for the last case, when tex2html_wrap_inline36877 . In any of the other three cases, we may take tex2html_wrap_inline37007 ; in this last case, we must further test g to determine an upper bound. We will not dwell on this since another method will be presented shortly.

After h is determined, we construct a linear upper bound of tex2html_wrap_inline37013 from tex2html_wrap_inline37015 . Given that

math22723

we may now treat h as a unary function of tex2html_wrap_inline32761 . Previous subsections detail how an upper bound of a unary function may be found.


next up previous notation contents
Next: 3.3.23 Charts Up: 3.3 Linear Interval Arithmetic Previous: 3.3.21 Examples with Bumpy Functions
Jeff TupperMarch 1996