One embodiment of the present invention provides a system that bounds the solution set of a system of nonlinear equations specified by the set of linear equations Ax=b, wherein A is an interval matrix and b is an interval vector. During operation, the system preconditions the set of linear equations Ax=b by multiplying through by a matrix B to produce a preconditioned set of linear equations M₀x=r, wherein M₀=BA and r=Bb. Next, the system widens the matrix M₀ to produce a widened matrix, M, wherein the midpoints of the elements of M form the identity matrix. Finally, the system uses M and r to compute the hull h of the system Mx=r, which bounds the solution set of the system M₀x=r.