existence of real root(s) of a transcendental equation
in [Math]
|
From: simonsong on 8 Feb 2010 15:44 Hi, Is there an algorithm for checking the existence of real root(s) of an arbitrary (uni-variate) transcendental equation (not polynomial equation)? I'd appreciate it if you can provide references to the algorithm or the proof of the non-existence of such an algorithm (if either of them exist). Thanks. Simon
From: Dave L. Renfro on 8 Feb 2010 16:27 simonsong wrote: > Is there an algorithm for checking the existence of real > root(s) of an arbitrary (uni-variate) transcendental equation > (not polynomial equation)? I'd appreciate it if you can provide > references to the algorithm or the proof of the non-existence > of such an algorithm (if either of them exist). Thanks. What functions are you allowing? Only standard higher functions such as elliptic functions, Bessel functions, Lame functions, Mathieu functions, etc. that show up in physics, engineering, chemistry, etc.? Are you going to allow all the various kinds of hypergeometric functions? What about functions defined by power series expansions with at most a 2-term (or maybe at most a 3-term) coefficient recursion relationship? As for locating the roots, maybe you have some constraints, since you can simply do this by looking for sign changes by evaluating the function at dyadic rationals between -n and n that have denominators of 2^n, for n = 1, 2, 3, ... [I'm assuming you're only considering continuous functions.] Dave L. Renfro
From: simonsong on 9 Feb 2010 10:14 On Feb 8, 4:27 pm, "Dave L. Renfro" <renfr...(a)cmich.edu> wrote: > What functions are you allowing? Only standard higher functions > such as elliptic functions, Bessel functions, Lame functions, > Mathieu functions, etc. that show up in physics, engineering, > chemistry, etc.? Are you going to allow all the various kinds > of hypergeometric functions? What about functions defined by > power series expansions with at most a 2-term (or maybe at most > a 3-term) coefficient recursion relationship? > > As for locating the roots, maybe you have some constraints, > since you can simply do this by looking for sign changes > by evaluating the function at dyadic rationals between > -n and n that have denominators of 2^n, for n = 1, 2, 3, ... > [I'm assuming you're only considering continuous functions.] > > Dave L. Renfro Actually the function I encountered is of form: \sum_i a_i exp( -exp(x+i*h) ) = b where a_i, h, and b are constants, and x is the unknown. However my interest is not limited to this function. I am curious to know whether an algorithm for checking the existence of real roots exists for arbitrary continuous functions. If not, for what subset of the continuous functions does such an algorithm exist. Simon
From: Chip Eastham on 9 Feb 2010 10:39 On Feb 9, 10:14 am, simonsong <pengcheng.si...(a)gmail.com> wrote: > On Feb 8, 4:27 pm, "Dave L. Renfro" <renfr...(a)cmich.edu> wrote: > > > What functions are you allowing? Only standard higher functions > > such as elliptic functions, Bessel functions, Lame functions, > > Mathieu functions, etc. that show up in physics, engineering, > > chemistry, etc.? Are you going to allow all the various kinds > > of hypergeometric functions? What about functions defined by > > power series expansions with at most a 2-term (or maybe at most > > a 3-term) coefficient recursion relationship? > > > As for locating the roots, maybe you have some constraints, > > since you can simply do this by looking for sign changes > > by evaluating the function at dyadic rationals between > > -n and n that have denominators of 2^n, for n = 1, 2, 3, ... > > [I'm assuming you're only considering continuous functions.] > > > Dave L. Renfro > > Actually the function I encountered is of form: > \sum_i a_i exp( -exp(x+i*h) ) = b > > where a_i, h, and b are constants, and x is the unknown. > > However my interest is not limited to this function. I am curious to > know whether an algorithm for checking the existence of real roots > exists for arbitrary continuous functions. If not, for what subset of > the continuous functions does such an algorithm exist. > > Simon As Dave points out, if an "arbitrary continuous" real function on the real line (or a real interval) undergoes a sign change, then a real root exists (Intermediate Value Thm.). In principle one can detect changes in sign by evaluating the function at a countable dense subset, such as the rationals (or dyadic rationals as Dave suggests). Of course a continuous function can have a root without undergoing a sign change, so this approach will not answer the question more generally. I.e. you can define for any choice of countably many evaluation points a continuous real function that is positive at all those points but zero at one or more other points (roots). You (Simon) mentioned: > Actually the function I encountered is of form: > \sum_i a_i exp( -exp(x+i*h) ) = b > > where a_i, h, and b are constants, and x is the unknown. For sufficiently large x, this (finite?) sum of decaying superexponentials tends to zero, so one naturally asks, assuming b > 0, whether the sum ever exceeds b. A real root can then be isolated by various root finding techniques, such as the bisection method, that require only function evaluations (derivative-free), and so should meet your requirement of applying to "arbitrary continuous" functions (provided these can be evaluated effectively). regards, chip
From: Narasimham on 9 Feb 2010 13:52
On Feb 9, 1:44 am, simonsong <pengcheng.si...(a)gmail.com> wrote: > Hi, > Is there an algorithm for checking the existence of real root(s) of > an arbitrary (uni-variate) transcendental equation (not polynomial > equation)? I'd appreciate it if you can provide references to the > algorithm or the proof of the non-existence of such an algorithm (if > either of them exist). Thanks. > > Simon For F,G transcendents, y(x) = F(x) - G(x) = 0, then for y broadly : for real root to exist, function changes sign, but not its derivative. for complex root to exist, derivative changes sign, but not the function. Narasimham |