Computational Complexity Analysis of Interval Methods in Solving Uncertain Nonlinear Systems

摘要

This paper analyzes the computational complexity of validated interval methods for uncertain nonlinear systems and steady-state enclosure. Interval analysis produces guaranteed enclosures that account for uncertainty and round-off, but its adoption is often limited by computational cost in high dimensions. We develop an algorithm-level worst-case framework that makes explicit the dependence on the problem dimension $n$, the initial search region size $\mathrm{Vol}(X_0)$, the target tolerance $\varepsilon$, and the costs of validated primitives (inclusion-function evaluation, Jacobian evaluation, and interval linear algebra). Within this framework, we derive worst-case time and space bounds for interval bisection, subdivision$+$filter, interval constraint propagation, interval Newton, and interval Krawczyk, and identify dominant cost drivers. We also show that the computation of the determinant and inverse of interval matrices via naive Laplace expansion exhibits factorial growth with increasing matrix dimension, motivating specialized interval linear algebra. We complement the worst-case bounds with computational results on two application-motivated biochemical steady-state models (a Hill-type regulatory network and an enzyme-saturation-based winner-take-all circuit) in dimensions $n\in\{2,5,10\}$, including instances that process millions of boxes. The resulting analysis and experiments support the practical design of validated solvers for uncertainty-aware steady-state screening tasks such as robust operating-point certification and multistability assessment.