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

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.

- 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
(x_{1})^{2} − x_{1}
* x_{2} − (x_{2})^{2} when x_{1} is
in the interval [0.2, 1], and x_{2} 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.

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

8. (Due September 24) Use optimal-side bisection to compute the enclosure for
the expression 2(x_{1})^{2} + 3x_{1}
* x_{2} + 3(x_{2})^{2} when x_{1} is
in the interval [0.2, 1], and x_{2} 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 + x^{2} 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 x
_{1}and x_{2}, both from the interval [0, 1.6], for which x_{1}− x_{2}= 0 and x_{1}* x_{2}= 0.25; - find x
_{1}and x_{2}, both from the interval [0, 1.6], for which x_{1}− x_{2}= 0 and x_{1}* x_{2}= 5.0.

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 + 2x^{2} 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
x^{2} − 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.

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.

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**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)}.

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.