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

1. (Due September 6) Use calculus to find the range of a function (2 + x) * (1 − x) on the interval [0,4].

2. (Due September 6) Use calculus to find the range of a function (2 + x1) * (1 − x2) when x1 is in the interval [0, 4] and x2 is in the interval [−1, 3].

3. (Due September 6) Linearize the expression from Problem 1 around the interval's midpoint. Use the linearized expression to find the approximate value of the range of the original function.

4. (Due September 6) Linearize the expression from Problem 2 around the intervals' midpoints. Use the linearized expression to find the approximate value of the range of the original function.

5. (Due September 13) Use straightforward interval computations to estimate the range of the function from Problem 1.

6. (Due September 13) Use straightforward interval computations to estimate the range of the function from Problem 2.

7. (Due September 18) Use centered form to estimate the range of the function from Problem 1.

8. (Due September 18) Use centered form to estimate the range of the function from Problem 2.

9. (Due September 27) Write a program that uses linearization to estimate the range of a given function on given intervals. Test your program on examples from Problems 3 and 4. Turn in the printout of the program and the printout of the results.

10. (Due September 25) Apply the general interval computations algorithm -- checking monotonicity, centered form, bisection -- to estimate the range of the function from Problem 1. One iteration of bisection is enough, perform two iterations for extra credit.

11. (Due September 25) Apply the general interval computations algorithm -- checking monotonicity, centered form, bisection -- to estimate the range of the function from Problem 2. One iteration of bisection is enough, perform two iterations for extra credit.

12. (Due September 27) 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.

13. (Due October 2) 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 1 and 2.

14. (Due October 4) Write a program that use the Cauchy-based Monte-Carlo technique to find the range of a given function on a given box. Test it on an example of a simple function on a narrow box, e.g., for f(x1,x2) = x12 + x22 when x1 is in [0.9,1.1] and x2 is in [1.8,2.2]. For this example, you can find the exact range by using monotonicity.

15. (Due October 4) Use the constraints method to solve the following two problems:

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

16. (Due October 4) Use the interval-based optimization algorithm to locate the maximum of the function f(x) = 2x + 4x2 on the interval [−0.4, 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.

17. (Due October 30) Write a method for simulating the propagation of random errors. We assume that:

• we have a function f(x1, ...,xn) -- given, as usual, as a method that takes an array x and transforms it into a real number;
• we also have the measurement results X1, ..., Xn, and
• we have standard deviations d1, ..., dn.
The goal is to find the standard deviation d of the value y.

In your program, first, you apply f to the measurement results, getting Y = f(X1, ..., Xn). Then, you select the number of iterations N (e.g., N = 50).

After that, for k = 1, ..., N, you do the following:

• use the random number generator (RNG) to generate n numbers r1, ..., rn which are normally distributed with 0 mean and standard deviation 1;
one way to generate each of these n random numbers ri is to do the following:
• 12 times run the RNG that generates numbers uniformly distributed on the interval [0,1],
• subtract 0.5 from each of 12 values and
• add the resulting 12 differences;
• compute dyk = f(x1 + d1 * r1, ... xn + dn * rn) − Y.
After that, you compute d as the square root of the average ((dy1)2 + ... +(dyN)2)/N.

Test this program on some example. The resulting value should be close to the square root of the sum (c1 * d1)2 + ... + (cn * dn)2, where, as before, ci is the partial derivative of f with respect to xi.

18. (Due October 23) If out of 10 experts, 7 think that the statement is true, what degree of confidence shall we assign to this statement?

19. (Due October 23) If an expert marked her confidence in a statement as 6 on a scale from 0 to 8, what degree of confidence shall we assign to this statement?

20. (Due October 23) If we have μ(1)=0.1 and μ(2)=0.9, what value shall we assign to μ(1.4)? Use linear interpolation.

21. (Due October 23) If the expert's degrees of confidence in two statements A and B are 0.7 and 0.8, and we use min as an "an"-operation and max as an "or"-operation, what degree of confidence shall we assign to A & B? To A \/ B? If a statement C has a degree of confidence 0.9, what is our degree of belief in (A & B) \/ C?

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

23. (Due October 25) Let us assume that the property A is described by the membership function μ(x) = 1 − |x|/2, and the quantity B is described by the membership function μ(y) = 1 − |2 − y|/2. Use α-cuts for α = 0.25, 0.5, 0.75, and 1.0 to describe the properties A & B and A \/ B.

24. (Due October 25) Let us assume that the quantity x is described by the membership function μ(x) = 1 − |x|/2, and the quantity y is described by the membership function μ(y) = 1 − |2 − y|/2. Use the values α = 0.25, 0.5, 0.75, and 1.0 to form membership functions for z = x − y and t = x * y.

25. (Due October 30) Out of 10 experts, 6 think that the statement is true, 2 think that it is false, and the remaining 2 are unsure. How can we describe this situation:

• in intuionistic fuzzy logic?
• in Demspter-Shafer approach?

26. (Due October 30) If an expert marked her confidence in a statement as 6 on a scale from 0 to 8, what interval degree of confidence shall we assign to this statement?

27. (Due October 30) If the expert's degrees of confidence in two statements A and B are [0.6, 0.8] and [0.7, 0.9], and we use min as an "an"-operation and max as an "or"-operation, what degree of confidence shall we assign to A & B? To A \/ B? If a statement C has a degree of confidence [0.8, 1.0], what is our degree of belief in (A & B) \/ C?

28. (Due November 1) Suppose that we have three alternatives, for which the gains are in the intervals [0, 11], [4, 7], and [8, 9].

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

29. (Due November 1) 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.
Your examples should be different from examples given in class (similar is OK).

30. (Due November 1) If we only use 2-digit decimal numbers and we use rounding that preserves guaranteed bounds, what will be the result of multiplying the intervals [0.50, 0.65] and [0.13, 1.21]?

31. (Due November 8)

• If we have four measurement results 0.8, 0.9, 1.1, and 1.2, what is the sample mean? sample variance?
• If we have two independent random variables with means 1.0 and 2.0 and standard deviations 0.3 and 0.4, what will be the mean and standard deviation of their sum?
• If we have a random variable x with mean 1.0 and standard deviation 0.3, what will be the mean and standard deviation of 2x?
• If we know that x1 has mean 1.0 and standard deviation 0.1, x2 has mean 2.0 and standard deviation 0.2, and x1 and x2 are independent, what will linearlization technique tell us about the mean and standard deviation of y = f(x1, x2)= (x1)2 + (x2)2?

32. (Due November 13, for extra credit if earlier) 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).

33. (Due November 27, for extra credit if earlier)

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