Method and apparatus for solving overdetermined systems of interval linear equations

1. A computer-readable storage device storing instructions that when executed by a computer cause the computer to perform a method for solving an overdetermined system of interval linear equations within a computer system, wherein the computer-readable storage device does not include computer instruction signals embodied in a transmission medium, and wherein the method comprises:

receiving a representation of the overdetermined system of interval linear equations Ax=b, wherein A is a matrix with m rows corresponding to m equations, and n columns corresponding to n variables, wherein x includes n variable components, b includes m scalar components, and m>n;

storing the representation in a memory within the computer system;

performing a Gaussian Elimination operation to transform Ax=b into the form

[

T

W

]

⁢

x

=

[

u

v

]

,

thereby facilitating arithmetic operations in the computer;

wherein T is a square upper triangular matrix of order n, u is an interval vector with n components, v is an interval vector with m−n components, and W is a matrix with m−n rows and n columns;

wherein W is zero except in the last column, which is represented as a column vector z with m−n components;

performing an interval intersection operation based on the equations z i x n =v i (i=1, . . . , m−n) and T nn x n =u n to solve for

x

n

=

u

n

⁢

T

nn

⁢

⋂

i

=

1

m

-

n

⁢

v

i

z

i

,

which are bounds for an unknown solution of x n ;

if x n is not the empty interval, performing a back substitution operation using x n and Tx=u to solve for the remaining components (x n−1 , . . . , x 1 ) of x;

using the components of x to determine the accuracy of a computation performed in an arithmetic unit.

2. The computer-readable storage device of claim 1 , wherein before performing the Gaussian Elimination operation, the method further comprises using a preconditioning matrix B to precondition the system of interval linear equations Ax=b to generate a modified system BAx=Bb that can be solved with reduced interval width.

3. The computer-readable storage device of claim 2 , wherein the method further comprises generating the preconditioning matrix B by:

determining a non-interval matrix A c , which is the approximate center of the interval matrix A;

augmenting the m by n matrix A c to produce an n by n partitioned matrix

C

=

[

A

c

′

0

A

c

″

I

]

,

wherein A c ′ is an n by n matrix, A c ″ is an m−n by n matrix, I is the identity matrix of order m−n, and 0 is an n by m−n matrix of zeros; and

calculating the approximate inverse of the partitioned matrix C to produce the preconditioning matrix B.

4. The computer-readable storage device of claim 1 , wherein receiving Ax=b involves linearizing an initial system of nonlinear equations to form the system of interval linear equations Ax=b.

5. The computer-readable storage device of claim 1 , wherein performing the Gaussian Elimination operation involves performing column interchanges in the system of interval linear equations Ax=b.

6. The computer-readable storage device of claim 1 , wherein if x n is determined to be the empty interval during the interval intersection operation, the method further comprises concluding that the overdetermined system of interval linear equations Ax=b is inconsistent.

7. The computer-readable storage device of claim 6 , wherein if Ax=b is determined to be inconsistent, the method further comprises:

selecting equations to remove from Ax=b to make a resulting system of equations consistent; and

removing the selected equations.

8. The computer-readable storage device of claim 7 , wherein if Ax=b is determined to be inconsistent, the method further comprises determining that at least one of the following is true:

an theory underlying Ax=b is false;

an error model underlying Ax=b is false; and

measurement error was involved in generating Ax=b.