# Thread: Interval on which a root exists

1. ## Interval on which a root exists

Hi,

lately I've been working with numerical methods for finding roots of functions.
They all need some sort of initial guess. How can I find on which interval a solution might exist?

Perhaps I could test to see if $f(x)f(y)<0$ for a lot of values of $x$ and $y$? Doesn't seem very efficient though..

Perhaps the forum should have a section on numerical analysis?

Thanks.

2. if $f(x)f(y)< 0$ then there exists a root $x_0\in (x,y)$. Finding 2 such values x,y is ofcourse guessing...

And it depends on the method, and the smoothness of the function whether we get sufficiently close to $x_0$

However, using the Bisection Method we will allways converge to $x_0$ (but it's among the slowest methods)

See: http://www.efunda.com/math/num_rootf...ootfinding.cfm

3. Yea sure, by the Intermediate Value Theorem and all that

I was wondering if this is an acceptable method of performing a search for an iterval?
That is, to use in an algorithm...

4. Originally Posted by Mollier
Hi,

lately I've been working with numerical methods for finding roots of functions.
They all need some sort of initial guess. How can I find on which interval a solution might exist?

Perhaps I could test to see if $f(x)f(y)<0$ for a lot of values of $x$ and $y$? Doesn't seem very efficient though..

Perhaps the forum should have a section on numerical analysis?

Thanks.
For polynomials finding an interval containing one or more roots is relativly easy (see papers in issues 1 and 2 of MHFzine)
and there are techniques for isolating roots base on Descartes' rule of signs and Sturm sequences.

Also if your function is smooth enough you can always look at the stationary points (they are either roots themselves, or if the function has different sign at adjacent extrema there is a single root between them)

CB

5. Originally Posted by CaptainBlack
For polynomials finding an interval containing one or more roots is relativly easy (see papers in issues 1 and 2 of MHFzine)
and there are techniques for isolating roots base on Descartes' rule of signs and Sturm sequences.

Also if your function is smooth enough you can always look at the stationary points (they are either roots themselves, or if the function has different sign at adjacent extrema there is a single root between them)

CB
Just a quick question before I go study your articles.
All of these find bounds for roots in polynomials. What if my function is not a polynomial?
Say I wanted to use Newton's method on $f(x)=e^x+cos(x)$ or something like that.
Do I go ahead and create a Taylor polynomial out of that and then find the interval?
Is that how it's done?

I apologize if these questions are silly..

6. Originally Posted by Mollier
Just a quick question before I go study your articles.
All of these find bounds for roots in polynomials. What if my function is not a polynomial?
Say I wanted to use Newton's method on $f(x)=e^x+cos(x)$ or something like that.
Do I go ahead and create a Taylor polynomial out of that and then find the interval?
Is that how it's done?

I apologize if these questions are silly..
You could read the second paragraph which is not about polynomials, and if there are no stationary points that too helps localise the root if there is one.

For the example you give there is an obvious root at x=0, then a sequence of roots for negative x which get closer and closer to the zeros of cos(x) as x goes to -infty

CB

7. Originally Posted by Mollier
Just a quick question before I go study your articles.
All of these find bounds for roots in polynomials. What if my function is not a polynomial?
Say I wanted to use Newton's method on $f(x)=e^x+cos(x)$ or something like that.
Do I go ahead and create a Taylor polynomial out of that and then find the interval?
Is that how it's done?

I apologize if these questions are silly..
Newton's method does NOT require an initial interval, just a single value. And while the closer that value is to the solution, the faster Newton's method will converge, it is NOT typically necessary that the initial value be close to the solution.

For your example, $f(x)= e^x+ cos(x)$, I would be inclined to take x= 0 as the initial value- just because it is easy!

8. I carefully read through your article in MHFzine 1 CaptainBlack and really enjoyed it. Thank you.

Thanks for clearing that up HallsofIvy.