Methods For Interval Linear Equations

10. Using the inverse

Suppose we have a matrix P' which bounds the exact inverse P of A. In Section 4, we
discussed how to obtain P'. Note that P'b bounds the hull h of the solution set. The bound
on h would generally not be sharp even if P' were the exact inverse P. This is because P can
contain matrices which are not inverses of any matrix in A. However, this provides another
bound on h which can be intersected with bounds obtained by methods such as those we
have described.

We can bound P more sharply than by the way described in Section 4 by using methods
such as ours to solve the equations which P must satisfy. Thus, we can solve for the ith
column of P by solving Ax = . We can solve for the ith row of P by solving . If
we solve for both the rows and the columns, we can intersect the two results .

The wider the vector b in Ax = b the wider the solution set. From this point of view,
the equation Ax = is ideal in that the right hand vector is real and all components
are zero except one. This suggests that there can be advantages in using a method which
computes the inverse of A

11. Choosing a method

In practice, we must decide whether to use any of the methods we have described, and,
if so, which one(s). We first note that if the center of A is "near" the identity matrix,
then its inverse B = is near the identity. In this case, there is little need to use any
of our methods. We can use B to precondition the system without unduly enlarging the
solution set. We can then use the hull method to determine the hull of the preconditioned
system. The question of what is meant by "near the identity matrix" will be left to a user.
Alternatively, the center of A might be near a matrix which is the identity with rows and
columns permuted.

Suppose the center of A is near the identity matrix. Then the center of A-1 is near
the identity. That is, its off-diagonal elements are likely to contain zero. Therefore, a row of
A-1 is unlikely to be SD. In this case, it is unlikely that our second method is applicable,
and there is probably little point in using the fourth or sixth method.

For any problem, a reasonable first step is to obtain bounds xB on the hull h using the
hull method. One can also use the method from [3] and find the intersection of the two
methods Thereafter, we might use the following procedural steps. They involve a great deal
of computing, but the work is polynomially bounded .

(1) If is near the (perhaps permuted) identity matrix, accept the results of the hull
method as a sufficiently sharp solution. Thus, go to step (10).

(2) If xB is SD in all but a few components, solve for h using the first method (in Section
3). Then go to step (10).

(3) Use the hull method to obtain bounds on A-1 by solving Ax = for i = 1, ..., n. (The
method in [3] can also be used.) Also solve for i = 1,..., n to bound AT-1: Then
intersect the two bounds on A-1: Denote the resulting bound on A-1 by PB.

(4) For i = 1, ., n, if all but a few components of row i of PB are SD, solve for using the
second method (in Section 4). If all components of h are obtained in this way, go to step

(5) Compute the bound PBb on h: Intersect it with xB and the result from step (4).

(6) If at least one component of h has been shown to be SD, the third method (in Section
6) is applicable. Use it to bound h. Intersect the solution with the result of step (5).

(7) Use the fourth method (in Section 7) to bound for i = 1, ..., n. Skip any value of i for
was obtained sharply in step (4). Intersect the result with the result from step (6).

(8) If at least one component of h has been found to be SD, use the fifth method (in Section
8) to bound h. Intersect the result with the result from previous steps.

(9) Use the sixth method (in Section 9) to bound h. Intersect the result with the result from
previous steps.

(10) Stop.

The amount of work to apply this procedure is not particularly excessive if the crude
bounds reveal that h or A-1 is SD. If this is not the case, our procedure is useful only if
sharpness is so important that a considerable amount of computing is warranted.

There are cases in which there is no need to use our methods. If A is an M-matrix, then
interval Gaussian elimination will obtain the hull h sharply. See [5].

12. Some special cases

The essential requirement in our methods is that we are able to express certain products in
which a factor is unknown except for its sign. For example, in the first method, we needed
to be able to express Ax when x is unknown. If is SD, we can use (2.3) to express
in terms of the endpoints of : But suppose that for a given value of j, the element is
real (i.e., a degenerate interval) for all i = 1,..., n. Then the "endpoints" of are equal,
and is expressed in terms of their coincident value. Therefore, need not be SD.

If all but a few columns of A are real, the first method can be used to determine the hull
h with a reasonable amount of computing. If a given column of A is real, the corresponding
component of x does not have to be made SD in the third method, nor does it have to be
eliminated in the fifth method.

Similar statements can be made for the dual methods. Now, however, we must be able
to express both pTA and pT b for a row pT of P. Consider the matrix which
is the matrix P augmented with the vector b as an added column . If all but a few rows of
R are real, the second method can determine the hull. If a row (or rows) of R is real, the
corresponding component of a row of P need not be SD in the fourth and sixth methods.

Even if every element of A except one is real, then every element of P can be a nonde-
generate interval. It is unlikely that we shall know that a row of R is real. Therefore, the
dual methods generally do not " simplify " in this way.

13. A non-polynomial method

The methods we have described fail if the crude methods fail to obtain bounds on the
solution. In this section, we describe how the hull of the solution set of Ax = b can be
obtained as the solution of an optimization problem. The optimization problem is not
a linear programming problem, so the work to solve it is not polynomially bounded. We
include it as an alternative for two reasons. First, it does not require that some other method
provide crude bounds. Second, it is similar to the methods we have described. The difference
is that the formulation of the optimization problem includes nonlinear constraints.

Equation (2.3) can be written as

Since the maximum of two function can be expressed as their average plus half their difference,
we have

Row i of the equation Ax = b can be written

From (14.1), (14.2), and (14.3), we therefore obtain

A point x is in the solution set of Ax = b only if the intervals in the left and right members

intersect. This imposes the constraints


for i = 1, ..., n.

We can obtain the kth component of the hull by minimizing and maximizing subject
to the constraints (14.4). The function j is not differentiable at = 0. We can obtain
constraints which are differentiable if we replace   by and add the constraints

The problem now becomes: For k = 1, ..., n,
minimize and maximize
subject to

14. References

[1] Hansen, E. R., Interval arithmetic in matrix computations, part I, SIAM J. Numer. Anal.
2, 308-320, 1965.
[2] Hansen, E. R., Global Optimization Using Interval Analysis, Marcel Dekker, 1992.
[3] Hansen, E. R., Sharpening interval computations, paper presented at the First Scandi-
navian workshop on interval methods and their application, Copenhagen, 2003.
[4] Hansen, E. R. and Walster, G. W. Global Optimization Using Interval Analysis, (second
ed.), Marcel Dekker, 2004.
[5] Heindl, G., Kreinovich, V., and Lakeyev, A. (1998), Solving linear interval systems is
NP-hard even if we exclude overflow and underflow, Reliable Computing, 4, 383-388.
[6] Neumaier, A., Interval Methods for Systems of Equations, Cambridge University Press,
London, 1990.

Prev Next