Method and apparatus for solving overdetermined systems of interval linear equations

摘要

One embodiment of the present invention provides a system that solves an overdetermined system of interval linear equations. During operation, the system receives 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, and wherein x includes n variable components, b includes m scalar components, and m>n. Next, the system performs a Gaussian Elimination operation to transform Ax=b into the form $\left[\begin{array}{c}T\\ W\end{array}\right]x=\left[\begin{array}{c}u\\ v\end{array}\right],$ wherein T is a square upper triangular matrix of order n, u is a vector with n components, v is a 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. Next, the system performs an interval intersection operation based on the equations z_ix_n=v_i (i=1, . . . , m-n) and T_nnx=u_n to solve for x_n. If x_n is not the empty interval, the system performs a back substitution operation using x_n and Tx=u to solve for the remaining components (x_n-1, . . . , x₁) of x.