From: "cristini paul" Subject: Re: all the roots of a complex funtion Date: Fri, 25 Jun 1999 10:38:43 +0200 Newsgroups: sci.math.num-analysis Jagath Gamage wrote in message news:377230BF.1903246E@tele.ntnu.no... > Hi, > > I need an algorithm which is able to find all the roots of a general > complex function (not > necessarily a complex polynomial) efficiently. > If somebody have had some experience in this matter, I would like to > hear from them. > > Thanks > > Jagath Gamage > Classical algorithms for finding roots are not that efficient because you often need to have good initial guesses. The best way is to use Davies algorithm. You need to define a contour in the complex plane and then you can find all the roots which are inside. B. Davies 1986, Locating the zeros of an analytic function, J. Comput. Phys. 66 36-49. I experienced myself this algorithm and it is really great. In that way you are really sure that you are not missing any root. -- Cristini Paul CNRS-LMA-ASM2 31, Chemin joseph Aiguier 13402 Marseille Cedex 20 mailto: cristini@lma.cnrs-mrs.fr ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: all the roots of a complex funtion Date: 25 Jun 1999 12:36:48 GMT Newsgroups: sci.math.num-analysis In article <377230BF.1903246E@tele.ntnu.no>, Jagath Gamage writes: |> Hi, |> |> I need an algorithm which is able to find all the roots of a general |> complex function (not |> necessarily a complex polynomial) efficiently. |> If somebody have had some experience in this matter, I would like to |> hear from them. |> I don't believe you really want _all_ (since there may be infinitely many). for complex analytic function's zeroes Laguerres method is known to work well. P. Henrici's book Computationally Complex Analysis has it in Volume II (at least i believe that it is in II). You may also consider the problem as a problem of finding all solutions of a system of two equations in two unknowns (Re and Im of function and argument) and use some code which can locate all zeroes of such a system (in a box). INTBIS in netlib/toms (code number 681) does that job. http://www.netlib.org -> browse repository -> select toms ->select 681 hope that helps peter ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: algorithm for polynomial roots Date: 4 Oct 1999 09:02:24 GMT Newsgroups: sci.math.num-analysis Keywords: Finding complex roots (Hiranos, Jenkins&Traub) In article <37F496FC.6D20@my.real.address>, sherpa writes: |> Hallo everybody, |> I don't know how to find all the roots of a polynomial (real and |> complex). I know there are numerical algorithms but I have no |> documentation on them. In particular I don't know how to find the |> complex roots. |> Can anyone point me any good reference (books, sites, code, etc.)? |> Thank you. there are lots of different methods. the easiest to understand is Hiranos method: see the paper by Murota in SIAM J. Num Anal. 19, 1982, 793--799. this works always. It is a generalization of the well known damped Newton method computing corrections from the complete taylor expansion of the polynomial at a given point. practically more useful is this one: Jenkins&Traub: a three stage variable shift iteration for polynomial roots and its realtion to generalized raleigh iteration. num. math. 14, (1970),252-263. code for this one is in netlib/toms (rpoly and cpoly) http://www.netlib.org but also methods based on the minimization of |P(z)|**2 (as a function of two real variables Re(z) and Im(z)), published in an early article in BIT (early 60's), named "specc" and "sperc" works fine. hope this helps peter ============================================================================== From: rstrand@ihug.com.au Subject: Re: algorithm for polynomial roots Date: Mon, 04 Oct 1999 18:13:07 GMT Newsgroups: sci.math.num-analysis In article <37F496FC.6D20@my.real.address>, sherpa wrote: > Hallo everybody, > I don't know how to find all the roots of a polynomial (real and > complex). I know there are numerical algorithms but I have no > documentation on them. In particular I don't know how to find the > complex roots. > Can anyone point me any good reference (books, sites, code, etc.)? > Thank you. > The Jenkins and Traub algorithm, which has already been cited in a previous post, is probably the best algorithm. There are two versions of this one for real coefficients and one for complex coefficients. The ACM Journal has published code for this in one of their algorithms (I think it's around algorithm 457 or so). The other popular method is to construct a matrix who's eigenvalues are the roots of the original polynomal. I recall MATLAB used this method. Both of the above methods do not perform well on multiple roots (mainly the accuracy suffers). A method based on the GCD, Sterm sequences and a polynomial solving algorithm by Stewart (III) (also in math Comp) was specifically developed to handle multiple roots by Dunaway (???). This algorithm was presented in the Mathematics of Computation Journal in the '70. Ages ago, I wrote routines for real coefficient polynomials. I used using Bairstow's method for quadratic factors and Newton's method for linear factors. I used the root bounding and weak/strong iteration tests of Jenkins and Traub. It's important to have a proper termination routine, the best one is the Adams et al method. The method worked fine ,even on deg 30 to deg 50 polynomials with complex roots, but it is not as good as the J & T method. Regards Rob Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: Complex Roots + Muller's/Newton's method Date: 2 Dec 1999 09:17:16 GMT Newsgroups: sci.math.num-analysis Keywords: How do methods of computing complex roots work? In article <823e3l$8od$1@news2.inter.net.il>, "Idan Nof" writes: |> Can someone please explain me, what's the reason behind |> the convergence of some root finding NA methods to complex roots ? |> Since the only methods which I know of to converge to complex roots, |> are Newton's and Muller's, It'll be best to demonstrate using them. |> (never mind if the method is initialized with real/complex values) For a restriction of a complex function f to R with the property f: R->R (e.g. a polynomial with real coefficients but complex roots) Newtons method will _not_ work if initialized with reals. You mean Laguerres method, probably. This one and Mullers method approximate the function locally by a quadratic (Mullers method does that by interpolating three points on the graph of f) and take a zero of the quadratic as the next guess for the zero. Clearly this one can be complex, hence these methods can find complex roots from real initial values. hope that helps peter ============================================================================== From: Dave Rusin Subject: Re: Complex Roots + Muller's/Newton's method Date: Thu, 2 Dec 1999 13:39:18 -0600 (CST) Newsgroups: [missing] To: idannof@hotmail.com >May I ask how shall imagine the geometric convergence of Newton's Well, I think most people simply imagine the real version, with a tangent line to a curve crossing the horizontal axis near the root; they just remember that everything "stands for" something of twice that dimension. But more accurately you can do it this way: the graph of a complex function is the set of points (x, f(x)) with both coordinates complex. Taking real and imaginary coordinates, that's just viewing f as a function from the plane R^2 to itself; the graph is then a surface in R^4. (OK, I realize your imagination is probably limited to R^3; go ahead and visualize a surface in R^3 lying over the x-y plane -- that's the domain of f -- knowing that there's supposed to be another axis perpendicular to everything visible; it and the z axis span the range space.) So now what's Newton's method? Well, just as in the real case, you draw a tangent to the graph and see where that crosses the domain -- the set of points (x, 0) where the second coordinate is zero. Remember, those two "coordinates" are _complex_ numbers, or if you prefer, they're vectors in the plane. So here's what's happening geometrically: somewhere in R^4 sits a 2-dimensional surface. Tangent to it somewhere is a 2-dimensional plane. Underneath it is another 2-dimensional plane (the domain). You're simply observing that if the point of tangency is itself close to the domain plane, then the tangent plane will intersect the domain plane very close to where the surface itself intersects that same domain plane. The 3D view is almost perfect. Imagine a paraboloid which crosses the xy plane in some circle. Pick a point on the paraboloid a little above the xy plane. Draw the tangent plane there, and notice that the line where the tangent plane meets the xy plane is very close to the circle where the paraboloid meets the xy plane. The only difference between that and the true picture is that in R^4 there's a little more room for things to wiggle around, and so having two 2-dimensional things meet along a line or curve is pretty special; when the two 2-dimensional things are in "general position", they meet in isolate points. (e.g., where do the planes {(2,5,x,y} | x, y real} and { (u,v,3,7) | u, v real} meet?) So somehow the thing represented by the paraboloid should be meeting the thing represented by the xy plane in just one point, not a circle; the thing represented by the tangent plane also meets the thing represented by the xy plane in just one point. So the 3D picture's a bit off, but the conclusion is still the same: the two points of intersection with the domain plane are pretty close to each other. Newton's method for complex functions then simply iterates the process (approximate root) -> (point on surface) -> (tangent plane) -> (point of intersection of tangent plane & domain plane) = (new approximate root). For that matter, there's no reason to limit this discussion to 2 variables. Given any F : R^n -> R^n we expect isolated points where F(p) = 0. Given a point p0 close to p, we get a point (p0, F(p0)) in R^(2n) lying on the graph, draw the n-dimensional tangent plane there, and let p1 be the point of intersection between that tangent plane and the domain plane. Iterate as needed. dave