WOLFRAM|DEMONSTRATIONS PROJECT

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
n

of a system of equations (not necessarily polynomial) given by a
2
C
function
n

→
n

, 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.