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 + x_{1}) * (1 − x_{2}) when
x_{1} is in the interval [0, 4] and x_{2} 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:

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

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

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(x_{1},x_{2}) =
x_{1}^{2} + x_{2}^{2} when
x_{1} is in [0.9,1.1] and x_{2} 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 x
_{1}and x_{2}, both from the interval [0, 3.2], for which x_{1}− x_{2}= 0 and x_{1}* x_{2}= 1.0; - find x
_{1}and x_{2}, both from the interval [0, 3.2], for which x_{1}− x_{2}= 0 and x_{1}* x_{2}= 20.0.

16. (Due October 4) Use the interval-based optimization algorithm
to locate the maximum of the function f(x) = 2x + 4x^{2}
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(x
_{1}, ...,x_{n}) -- given, as usual, as a method that takes an array x and transforms it into a real number; - we also have the measurement results X
_{1}, ..., X_{n}, and - we have standard deviations d
_{1}, ..., d_{n}.

In your program, first, you apply f to the measurement results,
getting Y = f(X_{1}, ..., X_{n}). 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
r
_{1}, ..., r_{n}which are normally distributed with 0 mean and standard deviation 1;

one way to generate each of these n random numbers r_{i}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 dy
_{k}= f(x_{1}+ d_{1}* r_{1}, ... x_{n}+ d_{n}* r_{n}) − Y.

Test this program on some example. The resulting value should be
close to the square root of the sum (c_{1} *
d_{1})^{2} + ... + (c_{n} *
d_{n})^{2}, where, as before, c_{i} is the
partial derivative of f with respect to x_{i}.

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.

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
x
_{1}has mean 1.0 and standard deviation 0.1, x_{2}has mean 2.0 and standard deviation 0.2, and x_{1}and x_{2}are independent, what will linearlization technique tell us about the mean and standard deviation of y = f(x_{1}, x_{2})= (x_{1})^{2}+ (x_{2})^{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**A**_{ij}) and an n-dimensional interval vector**b**with interval components**b**_{j}; - 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 x_{j}; - our
objective is to find, for each j, the range of possible values of
x
_{j}-- or, to be be more precise, an enclosure**x**_{j}for this range; we can combine these n enclosures into an n-dimensional interval vector**x**.

- I denotes a unit matrix, i.e., a matrix with 1s on the main diagonal and 0s elsewhere;
- the
product
**Z**=**X****Y**of interval matrices**X**and**Y**is computed by the usual matrix multiplication formula:**Z**_{ij}=**X**_{i1}***Y**_{1j}+ ... +**X**_{in}***Y**_{nj}; - 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**M**_{ij}; - for every interval matrix
**M**, we defined its norm ||**M**|| as|| **M**|| = max(|**M**_{11}| + ... + |**M**_{1n}|, ..., |**M**_{n1}| + ... + |**M**_{nn}|); - for an interval vector
**v**, its norm ||**v**|| is defined as|| **v**|| = max(|**v**_{1}|, ..., |**v**_{n}|).

- 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 − Y**A**; - the algorithm is applicable
if ||
**E**|| < 1; in this case, we compute the starting approximation**X**^{(0)}with components**X**^{(0)}_{j}= [−1, 1] * (||Y**b**|| / (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 vectorY **b**+**E****X**^{(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.