## Interval Computations, Homeworks for the course CS 5351/CS 4365, Fall 2010

1. (Due September 9) Given the following number of people in each age bracket: [0, 60]: 1, [70, 80]: 2, [80, 100]: 1, compute the range of possible values of the variance.

2. (Due September 14) Write a program that, given n intervals (as in the privacy case), computes the range of possible values of the variance.

3. (Due September 16) We want to estimate the range of a function (1 + x) * (2 - x) on the interval [0,3]. Do the following:

• find the exact range by using calculus;
• estimate the range by applying naive (straightforward) interval computations to the original interval;
• use bisection and apply naive interval computations to both sub-intervals;
• use bisection and check monotonicity of the function on each of the sub-intervals, applying naive interval computations only if the function is not monotonic.

4. (Due September 21) We want to estimate the range of a function f(x1, x2) = (x1)2 - x1 * x2 +(1/2) * (x2)2 + x2 when x1 is in the interval [-1, 1], and x2 is in the interval [-2, 2].

• find the exact range by using calculus;
• estimate the range by applying naive (straightforward) interval computations to the original intervals;
• use bisection and apply naive interval computations to both sub-boxes.

5. (Due September 23) To estimate the range of a function f(x1, x2) = (x1)2 - x1 * x2 +(1/2) * (x2)2 + x2 when x1 is in the interval [-1, 1], and x2 is in the interval [-2, 2], we bisected the original box into four sub-boxes, with x1 in [-1, 0] and [0, 1], and x2 in [-2, 0] and [0, 2]. In class, we used monotonicity analysis to simplify and improve the estimation of the range for one of the 4 sub-boxes, when x1 is in [0, 1], and x2 is in [-2, 0]. Perform a similar analysis for the three remaining sub-boxes. Reminder: when there is no monotonicity, we have no other choice but to use naive interval computations.

6. (Due October 5) Propose a topic for a project that you want to do for this class.

7. (Due October 12) Assuming that the computer uses 2 decimal digits, compute the range of a + b * c, where a is in the interval [-1.1, -0.9], b is in the interval [0.010, 0.013], and c is in the interval [11, 15], with appropriate round-offs.

8. (Due October 12) Use both naive interval computations and centered form to estimate the range of the expression (x1)2 - x1 * x2 + (x2)2 when x1 is in the interval [0.2, 1], and x2 is in the interval [0, 0.6].

9. (Due October 14) Use the mean value form to estimate the range of the expression (x1)2 + x1 * x2 + (x2)2 when x1 is in the interval [0.2, 1], and x2 is in the interval [0, 0.6].

10. (Due October 19) Use the interval-based optimization algorithm that we learned in class to locate the maximum of the function f(x) = x + x2 on the interval [-0.8, 0]. Divide this interval into two, then divide the remaining intervals into two again, etc. Stop when you get intervals of width 0.1.

10a. (Due October 26) Use the interval-based optimization algorithm that we learned in class to locate the maximum of the function f(x) = x2 - x + 1 on the interval [-0.6, 1]. Divide this interval into two, then divide the remaining intervals into two again, etc. Stop when you get intervals of width 0.1.

11. (Due October 21)

• Implement four basic operations of interval arithmetic.
• Write a method that computes an enclosure for the range of a given function on a given box by using the Mean Value Form. Assume that a function is already implemented as a method f(x) with an array input, and that we have also already implemented a method that computes the enclosures for partial derivatives. For example, in Java, that would mean that we have a method
```public static Interval partial(Interval[] inputs, int i){}
```
that, given a box (described as an array of intervals) and an index i, estimates the range of the partial derivative of f over x i. Test your method on the example of a function and intervals that we had in Problem 9.

12. (Due October 26) Use the interval-based optimization algorithm that we learned in class to locate the maximum of the function f(x) = 2x12 - 2x1 * x2 + x22 + x1 on the box [-1, 1] X [-1, 1]. Two bisection cycles are enough.

13. (Due November 2) Write a method that uses the algorithm that we learned in class to locate the maximum of an arbitrary function on a given box. Just like in the previous programming assignment, Assume that a function is already implemented as a method f(x) with an array input, and that we have also already implemented a method that computes the enclosures for partial derivatives.

14. (Due October 28) Use the constraints method that we had in class to solve the following two problems:

• find x1 and x2, both from the interval [-10, 10], that satisfy the system of equations x1 + x2 = 0 and x1 * (1 + x2) = 0.21;
• find x1 and x2, both from the interval [-10, 10], that satisfy the system of equations x1 + x2 = 0 and x1 * (1 + x2) = 0.3.
15. (Due November 4) For the problem that we started in class -- applying constraints techniques to solving a cubic equation x3 - 3x2 + 3x - 9 = 0 for x in [0, 10], perform two loops for x in the first sub-interval [0, 5]. For the auxiliary variables, start with the ranges that we have obtained for them by analyzing the original interval [0, 10].

16. (Due November 9) A decision maker has three alternatives:

• for the first alternative a1, the range of possible benefits is [1.0, 2.0];
• for the second alternative a2, the range of possible benefits is [0.0, 3.0];
• for the third alternative a3, the range of possible benefits is [-1.0, 3.0].
Find out which alternative will be selected by each of the following four decision makers:
• a pessimist, for whom α = 0;
• an optimist, for whom α = 1;
• a decision maker for whom α = 0.5;
• a decision maker for whom α = 0.3.

17. (Due November 11) In the affine arithmetic, instead of intervals, we have generalized intervals. Each generalized interval consists of the following three fields:

• a number a0 (describing the results of computations with midpoints);
• an array a1, ..., an (describing the coefficients at Δai), and
• an interval [a] (describing the effect of quadratic and higher order terms).
In the beginning, each value from the original input interval [Xi - Δi, Xi + Δi] is represented as Xi - Δxi, i.e., as a generalized interval with
• a0 = Xi;
• ai = -1 and aj = 0 for all j =/= i; and
• [a] = [0, 0].
In addition to generalized intervals corresponding to different intermediate results, we can also store the array of values Δ1, ..., Δn. In Java, they can be stored as static. The task is to implement the following methods:
• a method that transforms each input interval into the corresponding generalized interval;
• a method for adding generalized intervals, i.e., a method that takes as inputs generalized inputs corresponding to two quantities a and b, and produces a generalized interval corresponding to c = a + b;
• a method for subtracting generalized intervals, i.e., a method that takes as inputs generalized inputs corresponding to two quantities a and b, and produces a generalized interval corresponding to c = a - b;
• a method for multiplying generalized intervals, i.e., a method that takes as inputs generalized inputs corresponding to two quantities a and b, and produces a generalized interval corresponding to c = a * b;
• a method that transforms the generalized interval (a0, (a1, ..., an), [a]) corresponding to the final result into the final interval estimate
a0 + a1 * [-Δ1, Δ1] + ... + an * [-Δn, Δn] + [a].