A cell exclusion algorithm for determining all the solutions of a nonlinear system of equations (Q1354280): Difference between revisions

New algorithms are given for finding numerically all real solutions of nonlinear systems of equations (1) \(F(x)=0\), \(F:\Omega\subset\mathbb{R}^N\to\mathbb{R}^N\), where \(\Omega\) is a bounded region and \(F\in C(\Omega)\). The algorithms are called cell exclusion algorithms (CEAs) and are based upon a cellular partitioning of \(\Omega\) (such as boxes) and a cell-discarding condition (CDC). For a sequence of refining cellular partitionings, the CDC is applied to obtain successively smaller cells which may contain solutions of (1). CDCs which can be used are based upon, e.g., Lipschitz conditions on the components of \(F\), or ``monotonically decomposable'' functions, i.e., \(F=G-H\) where \(G\), \(H\) are isotone maps. Thus CEAs can be applied to maps \(F\) having components which are of bounded variation over \(\Omega\). One of the main advantages of the CEA lies in the low computational cost of applying the CDC. The algorithms have the same features as interval arithmetic techniques and are shown to have complexity \({\mathcal O}(1/\varepsilon)\) where \(\varepsilon\) is the tolerance to which (1) is to be solved.