## 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:

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

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

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.

• 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.
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].
• First, check for monotonicity; if you cannot confirm monotonicity, use the centered form 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 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:

• first checking for monotonicity and then
• using the centered form -- either for the original function or (if the given function is monotonic) for the corresponding functions of one fewer variable.
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:

• find x1 and x2, both from the interval [0, 1.6], for which x1 − x2 = 0 and x1 * x2 = 0.25;
• find x1 and x2, both from the interval [0, 1.6], for which x1 − x2 = 0 and x1 * x2 = 5.0.
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].

• 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.
Comment: see the decision making handout and November 6, 2013 notes.

19. (Due October 29) 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.
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:

• we are given an interval n-by-n matrix A (i.e., matrix with interval components Aij) and an n-dimensional interval vector b with interval components bj;
• for different matrices A from the interval matrix A and for different vectors b from the interval vector b, we can solve the corresponding systems Ax = b and find the corresponding vector x with components xj;
• our objective is to find, for each j, the range of possible values of xj -- or, to be be more precise, an enclosure xj for this range; we can combine these n enclosures into an n-dimensional interval vector x.
To describe Krawczyk's algorithm, we need to introduce the following auxiliary notations:
• I denotes a unit matrix, i.e., a matrix with 1s on the main diagonal and 0s elsewhere;
• the product Z = XY of interval matrices X and Y is computed by the usual matrix multiplication formula:
Zij = Xi1 * Y1j + ... + Xin * Ynj;
• for every interval [x, y], we define |[x, y]| as max(|x|, |y|); this is the largest value of |z| for all real numbers z from this interval;
• for every interval matrix M, by m(M), we denote a matrix formed by midpoints m(M)ij of the corresponding intervals Mij;
• for every interval matrix M, we defined its norm ||M|| as
||M|| = max(|M11| + ... + |M1n|, ..., |Mn1| + ... + |Mnn|);
• for an interval vector v, its norm ||v|| is defined as
||v|| = max(|v1|, ..., |vn|).
In these terms, Krawczyk's algorithm consists of the following steps:
• first, we take the compute the matrix Y which is the inverse to the midpoint matrix m(A);
• then, we compute an interval matrix E = I − YA;
• the algorithm is applicable if ||E|| < 1; in this case, we compute the starting approximation X(0) with components
X(0)j = [−1, 1] * (||Yb|| / (1 − ||E||));
• after that, we iteratively use the current iteration X(k) to compute the next iteration X(k+1) as the component-wise intersection of X(k) and the vector
Yb + EX(k);
• we stop when the interval vector stops changing, i.e., when X(k+1) = X(k).

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)

• Write a program that implements the Krawczyk method of solving systems of nonlinear equations. This method is described in Section 8.2 of the textbook. A general system of nonlinear equations is described by the formula (8.11), Krawczyk's method is described by the formula (8.15) and the following formulas. It works under the condition (8.14). Assume that the interval extensions are already available. Test your program on the example from the book.
• Modify your program so that it will be applicable also to nonlinear equations in which some coefficients are only known with interval uncertainty. The corresponding modification is described in the last paragraph of Section 8.2.