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