1
$\begingroup$

My question is : How to approximately guess the root of a function...

By root i mean is the starting point guess when used in case of Newton's method or any other root formulating methods. (Without calculators!)


I searched for the answers and came across the following solutions:

  1. Graphs: Of course! The point where the curve intersect with the $x-$axis...We find an integer or a simple decimal number close to it and define it as the starting point!
  2. Bisection method: We find out the interval $[a,b]$ where the root lies and if it follows certain conditions (link given) we can use $a$ or $b$ as starting points.

But suppose 1) I cannot plot the graph and 2) It is a very complex function (consists of trig., log, etc etc) and guessing the roots is not possible...not even the intervals...

So is there a better method to find the starting point?


For example the function is something like : $$\dfrac{\sin{x}}{x}=\log{x}$$ or $$x^8+24x^6+32x^3+12x+1=0$$ (I guess i exaggerated!)

Thanks!


P.S. - This may seem like a duplicate. But in all the questions i have seen in SE, none answer these questions (or i may have looked over some) concretely!

$\endgroup$
  • $\begingroup$ Why can't you plot the graph? To do so requires evaluating the function at a number of $x$ values, which you need to be able to do to apply any root-finding algorithm. The "without calculators" requirement sounds like a test situation. In that case the functions will not be that tough to evaluate. For your first example, how do you evaluate $\sin x$ and $\log x$ without a calculator? It can be done, but it takes a while for each point. $\endgroup$ – Ross Millikan Jun 17 '15 at 4:18
  • $\begingroup$ @RossMillikan Well I can use sin/log tables...The only problem is the "time-factor" which i am now neglecting. And when i said "can't plot the graph" it meant "I am bad at plotting graphs accurately! Also plotting polynomials beyond fourth degree is not possible for me. $\endgroup$ – NeilRoy Jun 17 '15 at 4:22
  • $\begingroup$ You don't need to plot graphs accurately. All you need is to find $x$ values where the function is positive and negative. $\endgroup$ – Ross Millikan Jun 17 '15 at 4:28
  • $\begingroup$ @RossMillikan By accurately i mean what i plot ... looks ... totally different :) $\endgroup$ – NeilRoy Jun 17 '15 at 4:38
1
$\begingroup$

I don't think there is a magic answer-you have to think about the specific problem. For your first example, I would note that $\frac {\sin 1}1 \gt 0 = \log 1, \frac {\sin e}e \lt \frac 1e \lt 1=\log e$, so I have a bracket. For the second I would note that $f(0)=1$ and the only terms that can go negative are $32x^3+12x$ and I would note that $f(-1)=-18$ and again I have a bracket. Since this goes to $+\infty$ as $x \to -\infty$ there will be another root below $-1$. $x^8$ is so big that I would try $f(-2)$, find it is positive, and have a bracket on that root.

$\endgroup$
  • $\begingroup$ Thanks! But what i wanted was a third method which will help me in some situations where the equations may be more complex! However big that method might be...just to make sure it will always work! $\endgroup$ – NeilRoy Jun 17 '15 at 4:28
  • 1
    $\begingroup$ There can't be a method that will always work unless you can understand the function. Think of $f(x)=1+\frac {\log |x-\pi|}{10000}$ It has two roots near $\pi $, but they are hard to find. If you aren't allowed a calculator, you have to trust the teachers to give you reasonable functions to find roots of. $\endgroup$ – Ross Millikan Jun 17 '15 at 4:35
  • $\begingroup$ Nah! I guess this is more of self interest than what the teachers give! $\endgroup$ – NeilRoy Jun 17 '15 at 4:45
  • $\begingroup$ If it is self interest, why aren't you allowed a calculator? $\endgroup$ – Ross Millikan Jun 17 '15 at 4:57
  • $\begingroup$ Just to see if there is a method there which allows so...(If there are no other methods...never mind then!) $\endgroup$ – NeilRoy Jun 17 '15 at 4:59
1
$\begingroup$

Here is a reasonable method that would work for finding a zero of a nice differentiable function $f$ with limits at the endpoints of its domain.

Step 1

First find the sign of $f$ as it approaches the two endpoints of its domain. There are only three cases. If $f$ fluctuates in sign near an endpoint, we are done. Otherwise $f$ has stable signs near both endpoints, and the signs are either opposite or the same.

Step 2 - Case 1 (Opposite signs)

Choose $a,b$ such that $f(a),f(b)$ are of opposite signs, by moving $a,b$ sufficiently towards the respective endpoints of the domain. This can be done by binary search for finite endpoints or by repeated doubling for infinite endpoints, but usually it helps to observe the function carefully.

For $f(x) = \ln(x) - \frac{\sin(x)}{x}$, $f(x) \to -\infty$ as $x \to 0$ and $f(x) \to \infty$ as $x \to \infty$. A possible choice of $(a,b)$ would be $(\frac{1}{4},4)$.

Step 2 - Case 2 (Same sign)

If $f$ has any zero at all, its derivative $f'$ must have a zero too, by a suitable extension of Rolle's theorem. So we just repeat the procedure on $f'$. In many cases, eventually we will end up in Case 1.

For $f$ that is a polynomial with even degree, $f(x) \to \infty$ in both directions, but $f'$ will be a polynomial with odd degree, and so Case 1 applies to $f'$.

After we find sufficient approximations of the zeros of $f'$, for at least one of them $f$ will be of the opposite sign compared with the sign of the limits.

Step 3

We now have an interval on which we can do binary search for a zero of $f$.

Notes

For some not nice functions $f$, it will not work well, such as for $f(x) = \frac{1}{x^2+1}(\cos(\frac{1}{2x})-\cos(\frac{1}{3x})-\cos(\frac{1}{5x})+3)$.

Note also that Newton-Raphson fails in a lot of different ways. The conclusion is that it is extremely important to understand the function before attempting to find its zeros. Any algorithm only works for certain types of functions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.