9478

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+