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:

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].

1-2. A sample solution to Problems 1 and 2

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.

Comments:

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).

4. A sample solution to Problem 4

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].

5. A sample solution to Problem 5

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].

8. A sample solution to Problem 8

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:

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.

11. A sample solution to Problem 11

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

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].

23. (Due November 13) Write down:

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]?