Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

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  
more informative and more enjoyable (for both the author and a reader)  
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)