Interval Computations,
Homeworks for the course
CS 5391/6391, Fall 2015

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

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

3. (Due September 10) Use centered form to estimate ranges from Problems 1 and 2.

4. (Due September 10) 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:

5. (Due September 17) Use the centered form to find an enclosure for the range of a function f(x) = x − 2x2 on the interval [0,0.8].

6. (Due September 17) Use the centered 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 17) Write a method that computes an enclosure for the range of any given function on any given box by:

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 Problems 5 and 6.

8. (Due September 24) 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.6, 0].

9. (Due September 24) Use the interval-based optimization algorithm 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. At each iteration, dismiss subintervals where maximum cannot be attained. Stop when you get intervals of width 0.1.

10. (Due September 24) Use the constraints method to solve the following two problems:

Comment: once we conclude that the variables belong to narrower intervals, we bisect these narrower intervals, and not the original wider ones ([0, 1.6] in this problem).

11. (Due October 1) Use both linearization algorithms described in the first handout (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.2, 0]. Compare the two estimates with the exact range (which you can compute by using calculus).

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

13. (Due October 8) 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.

14. (Due October 15) If use the simplest "and"- and "or"-operations, and our degrees of belief in A, B, and C are, correspondingly, 0.5, 0.8, and 0.9, what is our degree of belief in (A & B) \/ C?

15. (Due October 15) For a membership function μ(x) = 1 − |x|/2, what are the α-cuts corresponding to α = 0.5? to α = 0.2?

16. (Due October 15) 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.25, 0.5, 0.75, and 1.0 to form membership functions for z = x − y and t = x * y.

17. (Due October 22) Follow the first three steps of bisection to locate the square root of 5, i.e., the solution to the equation x2 − 5 = 0 on the interval [0, 4].

18. (Due October 29) Suppose that we have three alternatives, for which the gains are in the intervals [1, 12], [5, 8], and [9, 10].

Comment: see the decision making handout and November 6, 2013 notes.

19. (Due October 29) Write down:

Comment: see October 7, 2013 notes.

20. (Due October 29) If we use 2-digit decimal numbers, what will be the result of multiplying the intervals [0.50, 0.65] and [0.11, 1.20]?

Comment: see October 21, 2013 notes.

21. (Due November 12; due November 5 for extra credit) Write a program that implements the Krawczyk method for solving systems of interval linear equations, and test it on some example with narrow intervals.

The problem and the corresponding algorithm are described in Chapter 7 of the book. Test your program first on an example from the book, to make sure that you coded everything correctly.

Here is a brief description of the problem:

To describe Krawczyk's algorithm, we need to introduce the following auxiliary notations: In these terms, Krawczyk's algorithm consists of the following steps:

22. (Due November 19) Use affine arithmetic to estimate the range of the function from Problem 2.

Comment: affine arithmetic is described in the first handout (paper) and in the third handout (slides).

23. (Due November 25) Write a program that implements arithmetic operations in affine arithmetic, test it on the example from Problem 22.

24. (Due December 3)