Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does there currently exist a general algorithm (or set of algorithms used together) that will approximate all the zeros of any well behaved non-differential equation of a single variable which has a finite number of zeros?

(By "well-behaved", I mean differentiable, without "holes". By a set of algorithms, I mean (for example) a setup such that one algorithm can be used in cases when the other algorithm fails such that between all the algorithms or techniques in the set, at least one is guaranteed to work.)

Say for example I need all the real and imaginary solutions for a complicated looking, non-linear equation like:

$$ x^{-x^8} + \frac{(\ln x)^2}{x^3}+2x^{7/2}+\frac{\ln(5x^{3/2})}{\ln(3 + x^2)} - 10 = 0. $$ Note: Sorry if this example is flawed; its purpose is to show that I want an algorithm that can handle a rather arbitrary mix of polynomials, logs, powers, and other operations that is not your run of the mill n-th degree polynomial.

Anyway... Does there exist some algorithm or set of algorithms (known to man) that is guaranteed to find and approximation all the real and imaginary zeros for this equation of a single variable with finite number of zeros? If so, can you describe it or refer me to some information about it? For the algorithm to be useful, it must know when to stop - it must always have a way to stop searching for zeros after it has found all n zeros.

My algorithm options thus far are:

  1. No such general algorithm exists. Perhaps a computer faced with finding the zeros of such an equation should just brute force test millions upon millions of points and see what's close to zero.

  2. A computer should use the Lehmer–Schur algorithm and take care to avoid ill-behaved areas.

share|improve this question
    
An "algebraic equation" specifically only involves polynomials. I'm not sure what to call the kind of equation you're interested in, aside from the general name "transcendental equation". –  Antonio Vargas Nov 8 '13 at 1:09
    
I took the liberty of formatting your equation using LaTeX. I also went ahead and replaced "log base (3+x^2) of 5*x^(3/2)" with $\ln(5x^{3/2})/\ln(3+x^2)$ for clarity. –  Antonio Vargas Nov 8 '13 at 1:15
    
Oh, sorry Antonio. I assumed an "algebraic equation" as opposed to a "differential equations". I should change it to "non-differential equation". –  Anonymosity Nov 8 '13 at 1:24
    
One last comment: Numerically it appears that your equation has infinitely many roots. Also there are indeed places where the function is non-differentiable, so the Lehmer-Schur algorithm (for instance) would need to be very carefully applied to avoid the points of non-differentiability. –  Antonio Vargas Nov 8 '13 at 1:31
    
You can always write the algorithm so it stops itself. Either it stops when successive approximations get sufficiently close, or it stops when n cases of successive approximations have not gotten closer. I would suggest that looking for a magic bullet collection of algorithms is not so fruitful. There is a vast range of possible functions that have a vast range of possible roots, finite and infinite, complex and real. What works best is often specific to the problem, or may have a perfectly good approximation which is not in your algorithm basket. –  Betty Mock Nov 8 '13 at 2:12
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.