PRECONDITIONERS FOR THE INTERVAL GAUSS-SEIDEL METHOD

For the overall interval Newton/bisection algorithm to be efficient, the image box X̄ should be as small as possible. To do this, the linear interval system is multiplied by a preconditioner matrix Y before the interval Gauss-Seidel method is applied. In this paper, a technique for computing such preconditioner matrices Y is described. This technique involves optimality conditions expressible as linear programming problems. In many instances, the resulting preconditioners give an X̄ of minimal width. They can also be applied when F′ approximates a singular matrix, and the optimality conditions can be altered to describe preconditioners with a given structure. This technique is illustrated with some simple examples and with numerical experiments. These experiments indicate that the new preconditioner results in significantly less function and Jacobian evaluations, especially for ill-conditioned problems, but it requires more computation to obtain.