       solving systems of transcendental equations

• To: mathgroup at smc.vnet.net
• Subject: [mg92899] solving systems of transcendental equations
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Fri, 17 Oct 2008 05:24:52 -0400 (EDT)

```I am writing to advertise my two demonstrations on the Wolfram
demonstrations site:

http://demonstrations.wolfram.com/SemenovsAlgorithmForSolvingSystemsOfNonlinearEquations/
and
http://demonstrations.wolfram.com/SolvingSystemsOfTranscendentalEquations/

They both illustrate a method of numerically finding roots of systems
of non-linear (possibly transcendental) equations in n-variables in a
rectangular region in a rectangular domain in R^n. Questions
concerning doing this sort of thing with Mathematica appear
periodically in this forum. The method illustrated in these
demonstrations is due to V.Yu. Semenov, whose paper was published last
year in a Russian language journal. The only other account of the work
in English that I am aware of is a review (by myself) in Mathematical
Reviews. I think the demonstrations are a much better way of
presenting the contents of the paper.

Here is a brief explanation of the method. Suppose we are given a
system of n-equations in n variables and a rectangular region in R^n
where we want o find all solutions (with 100% certainty). The
functions defining the equations have to be of class C^2 (twice
differentiable with continuous second derivative). Let's at first
assume that we know the equations have no multiple roots in the
specified region.

The algorithm works as follows. There are two tests (described
precisely in the first of the above demonstrations). Each test can be
performed on any rectangular region. If the first test is passed by
the region we know for sure that the system has no roots in the
region. If the second test is passed then we know for sure that there
is at most a single root in the region. We start with our given region
and perform Test 1 on it. If it is passed, there are no roots and we
are done. If it fails we go to the second test. If it is passed, we
know there is at most one root in the region and we apply the built-in
Mathematica function FindRoot to find it. If the second test fails we
subdivide the rectangular region into 4 smaller rectangles of equal
size and apply  Test 1 to each. All the rectangles that pass Test 1
are colored yellow in the demonstrations and are eliminated form
further search. On the remaining rectangles we perform Test 2. Those
that pass Test  2 (they contain at most one root) are colored orange
and left for later. The ones that fail both tests are colored blue and
subdivided again. Test 1 and Test 2 are then performed on the
rectangles of the subdivision. One can prove that, if there are no
repeated roots in the region, the process will end in a finite number
of steps (in other words, there will be no blue rectangles left). At
this stage all the roots have been isolated and we can find them using
FindRoot (with initial point in the middle of the orange rectangles).

If the system has multiple roots inside the specified rectangular
area, the above process will never finish. There will always remain
blue rectangles around the point where the multiple root is located,
but their total area will become arbitrarily small. Thus we can always
stop the process when the enclosing area becomes small enough. Like
other numerical methods, Semenov's method cannot distinguish between a
multiple root and a cluster of roots very close together.

The reason why there are two demonstrations is that I wrote the first
one too test the correctness of the method. For this reason, in the
first demonstration the equations are all polynomials (cubics), in
which case one can find all the roots using NSolve. The demonstration
lets one specify the cubic and see the roots (computed by NSolve) and
observe that they are correctly isolated by Semenov's method.

In the second demonstration I tried some transcendental equations that
the present version of Mathematica cannot solve. Three of these are
given by an analytic equation in one complex variable (an analytic
equation in one complex variable corresponds to two real analytic
equations in two complex variables). These kind of equations will
(probably) be solvable in the next version of Mathematica (I took them
from a paper by Adam Strzebonski describing the forthcoming method of
solving transcendental complex univariate equations). But the fourth
example consists of two real equations not derived form a single
complex analytic one, which is something that Mathematica will not be
able to solve by means of built in functions for at least a couple of
versions.

I think it would be nice to make an Add On package for Mathematica
based on Semenov's method, but I am not going to do this. Still, the
demonstrations contain all the information needed for this purpose.

Finally, one last remark. I have been reviewing papers for Math.
Reviews (AMS journal) for about 2 decades. Most of these papers have
been non computational and thus non-suitable for making
demonstrations. However, in the last few years I got interested in
computational mathematics and have been regularly reviewing papers in
this area. I am very excited about using Mathematica Demonstrations as
a modern form of review, for this type of papers. I think it is vastly
than a traditional text based review. It shows how right WRI has been
to develop the capabilities of Mathematica beyond mere computation
contrary to what various modern Luddites (or one particular one) have
been arguing on this forum.

Andrzej Kozlowski

```

• Prev by Date: Re: Variable amount of Buttons in Mathematica
• Next by Date: selecting sections (unix)
• Previous by thread: Re: labeling axes in a ContourPlot
• Next by thread: selecting sections (unix)