Improving the efficiency of interval analysis by Kevorkian's decomposition technique
Kiyotaka Yamamura, Akio Ushida, Kazuo Horiuchi · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1992
Abstract The algorithm of interval analysis proposed by Krawczyk, Moore, and Jones (henceforth called the Krawczyk algorithm) is a well‐known algorithm for finding all solutions of nonlinear equations. In this algorithm, the initial region (which is given by ann‐dimensional rectangle) is divided into small subregions, and the existence of a solution in each subregion is examined. Therefore, it can find all solutions. However, the computation time of the Krawczyk algorithm grows exponentially with the dimension, hence it is not a practical algorithm for large‐scale problems although high‐speed computers are used. In this paper, Kevorkian's method is introduced to the Krawczyk algorithm to improve the computational efficiency. Kevorkian's method is a decomposition method for nonlinear equations. It reduces large‐scale nonlinear equations with sparse Jacobians into smaller equations. By this reduction, the computational efficiency of the Krawczyk algorithm is improved substantially. First, a new algorithm of interval analysis is proposed in which Kevorkian's method is introduced to the Krawczyk algorithm. Then a new permutation algorithm (algorithm for decomposing nonlinear equations) that makes the interval arithmetic well defined is proposed. The effectiveness of the proposed algorithm also is verified by numerical examples.