Semenov's Algorithm for Solving Systems of Nonlinear Equations

An algorithm due to V. Yu. Semenov computes all the roots that lie in some rectangular domain of of a system of equations (not necessarily polynomial) given by a function , provided the system has no repeated roots in the domain.

We demonstrate the method by considering a cubic equation on the unit square in the complex plane (this is equivalent to a system of two real equations of degree 3). The coefficients of the equation are chosen using three two-dimensional sliders. Semenov's method works by decomposing the rectangle into smaller ones and then performing two tests on them. If a rectangle passes the first test, there are no roots of the equation inside the rectangle. Such a rectangle is colored yellow and eliminated from further consideration. If a rectangle passes the second test, there is either one or no roots in this rectangle. Such a rectangle is colored orange and stored for further inspection. Rectangles that fail both tests are colored blue and subdivided, and the procedure is then repeated on the resulting smaller rectangles. If the system has no multiple roots, eventually only a finite number of orange rectangles are left. The roots can now be found by using Newton's method (Mathematica's FindRoot), taking the centers of the orange rectangles as starting values.

Choose an equation using the sliders, then click on the successive integers to see the result for the corresponding iteration. Continue until there are no blue rectangles left. Click on 0 before trying a different equation.

If a system has a repeated root, there will always be blue rectangles around the root.

Suppose we have a system of equations in variables:

in some region , where all the functions are of class . Suppose also that the system has no multiple roots in . For each , let be a positive real number such that and let be a positive real number such that , where is the Jacobian of the system. Let . Semenev's two tests are based on the following two facts.

1. Suppose that for some with , we have . Then the system has no root in the region .

2. Suppose . Then the system has at most one root in the region .

V. Yu. Semenov, "The Method of Determining All Real Nonmultiple Roots of Systems of Nonlinear Equations," The Journal of Computational Mathematics and Mathematical Physics, 47(9), 2007 p. 1428.