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.

Comments:

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

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:

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:

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:

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

29. (Due November 1) Write down:

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)

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:

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

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