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

1. (Due September 9) We want to estimate the range of a function (2 + x) * (1 − 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;
• first, use naive interval computations to check monotonicity, and, if monotonicity is confirmed, use it to get a more accurate estimate for the range.

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

• find the exact range by using calculus;
• estimate the range by applying naive (straightforward) interval computations to the original intervals

3. (Due September 11) Write a program that implements all operations of interval arithmetic: addition, subtraction, multiplication, 1/x, and division. Submit printouts of the code and of the test results, be prepared to show how the program works if needed.

• the range of 1/x is only bounded when the set of possible values of x does not contain 0; thus, the inverse interval 1/[a,b] is only defined when the interval [a,b] does not contain 0;
• the main need for interval arithmetic operations comes from naive interval computations, where the result of one operation are used as inputs for another interval arithmetic operation; in view of this, please program interval arithmetic operations so that they return the interval, not just print its endpoints; in an object-oriented programming language like Java, the most convenient way is to return an interval as an object;
• endpoints come from measurements; we saw many examples in class when endpoints are not integers; please make sure that your operations are defined for real numbers, not just for intervals.
4. (Due September 16) Use naive interval computations to check whether the function f(x1, x2) = (x1 − 2)2 + (x1 − 2)(x2 + 1) − (x2 + 1)2 is monotonic with respect to at least one of its variables when x1 is in [2,3] and x2 is in [−1,0]. If it is monotonic, use this monotonicity to improve the naive-interval-computations enclosure of the range of the given function on the given intervals (you still need to use naive interval computations with respect to the variable for which the function is not monotonic).

Comment: Please do not change the expression when using interval computations; as we saw in class, an equivalent transformation can change the resulting enclosure.

5. (Due September 18) Use mean value method to find an enclosure for the range of a function f(x) = 2x − 3x2 on the interval [0,0.8].

• First, check for monotonicity; if you cannot confirm monotonicity, use the mean value method.
• Then, to get a more accurate enclosure, divide the original interval into two halves, repeat the same procedure for both halves, and take the union of the resulting enclosures.

6. (Due September 23) Use the mean value form (with checking monotonicity first) 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].

7. (Due September 25) 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 6.

8. (Due September 30) Use optimal-side bisection to compute the enclosure for the expression 2(x1)2 − 3x1 * x2 + 3(x2)2 when x1 is in the interval [0.2, 1], and x2 is in the interval [0, 0.6].

9. (Due October 2) Add several iterations of optimal-side bisection to the program that you developed for Problem 7. Test your method on the example of a function and intervals that we had in Problem 6.

10. (Due October 7) Prepare a topic for your class project:

• an ideal project is something related to uncertainty in a research project on which you are working already;
• alternatively, if there is any aspect of computing that excites you, google that topic (e.g., robotics) + interval computations, choose a paper you feel will be of interest to you, and show to the instructor; you will then need to prepare a report (oral and written) on this paper;
• third option is joining one of the projects mentioned in class (see class notes).
The project does not have to be on bisection or whatever we had in class, but it has to be related to interval computations (or at least with uncertainty).

11. (Due October 7) 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, 0.8]. Divide this interval into two, then divide the remaining intervals into two again, etc. At each iteration, dismiss subintervals where maximum cannot be attained. Stop when you get intervals of width 0.1.

12. (Due October 9) Use the constraints method to solve the following two problems:

• find x1 and x2, both from the interval [0, 2], for which x1 − x2 = 0 and x1 * x2 = 1;
• find x1 and x2, both from the interval [0, 2], for which x1 − x2 = 0 and x1 * x2 = 10.
Comment: once we conclude that the variables belong to narrower intervals ([0.5, 2] in this problem), we bisect these narrower intervals, and not the original wider ones ([0, 2] in this problem).

13. (Due October 21) Submit a written report on what you did for the class project.

14. (Due October 23) Use both linearization algorithms that we studied in class (Algorithm 1 that uses partial derivatives and Algorithm 2 which does not) to estimate the range of the function f(x) = x − 2x2 on the interval [0, 0.2]. (The linearization-based Algorithm 2 is also described in the handout). Compare the two estimates with the exact range (which you can compute by using calculus).

15. (Due October 28) Write a program that uses linearization-based Algorithm 2 to estimate the range of a given function on a given box.

16. (Due October 30) Write a program that uses the Monte-Carlo Cauchy algorithm (as described in the handout) to estimate the range of a given function on a given box.

17. (Due November 4) If use the simplest "and"- and "or"-operations, and our degrees of belief in A, B, and C are, correspondingly, 0.6, 0.7, and 0.4, what is our degree of belief in (A & B) \/ C?

18. (Due November 4) For a membership function μ(x) = 1 − |x|, what are the α-cuts corresponding to α = 0.5? to α = 0.2?

19. (Due November 4) Let us assume that the quantity x is described by the membership function μ(x) = 1 − |x|, and the quantity y is described by the membership function μ(y) = 1 − |1 − y|. Use the values α = 0.2, 0.4, 0.6, 0.8, and 1.0 to form membership functions for z = x + y and t = x * y.

20. (Due November 6) Follow the first two steps of bisection to locate the square root of 3, i.e., the solution to the equation x2 − 3 = 0 on the interval [0, 2].

21. (Due November 6) Use the explanations that we had in class to write down a Java method which computes ci = (f(x1, ..., xi−1, xi + h, xi+1, ..., xn) − f(x1, ..., xi−1, xi − h, xi+1, ..., xn))/(2h).

22. (Due November 11) Suppose that we have three alternatives, for which the gains are in the intervals [10, 12], [5, 7], and [9, 15].

• is there an alternative which is guaranteed to be optimal (i.e., for which the gain is the largest)?
• list all alternatives which can be optimal;
• which alternative(s) should we select if we use Hurwicz optimism-pessimism criterion with α = 0, 0.5, and 1.

23. (Due November 13) Write down:

• an expression for which an optimizing compiler improves the estimates provided by straightforward interval computations, and
• an expression for which an optimizing compiler worsens improves the estimates provided by straightforward interval computations.

24. (Due November 13) If we use 2-digit decimal numbers, what will be the result of multiplying the intervals [0.60, 0.75] and [0.12, 1.50]?