Question regarding Newton's method

[duragezic]

I have a Numerical Methods assignment due. I've been scratching my head with this one. Among other things, we are required to write a program to find the smallest positive root to a certain equation. I'm certain of the smallest positive root due to the fact my program works for the most part and by checking the result with a calculator. My fixed point method also finds that same, smallest root.

The problem is we are required to take in multiple input values (initial guesses). The actual smallest root is at 3.0764xxx. So, given an input of 3.5 or 4.0, then it seems that no matter what, Newton's method will converge on a further root. The next root following the one we want of 3.0764 is 3.199xxx, and there's a lot more after that. So when they go to grade our programs using multiple initial guesses, only guesses lying inbetween something like .237 and 3.137 (the latter number is just shy of the midpoint between the smallest root we want and the one after it) will actualy cause Newton's method to converge on the smallest positive root of 3.0764. If you give it 3.5, it will converge to the following root of 3.199.

I've talked to my prof but he is quite hard to get a clear answer from. Any ideas if this is even possible to ALWAYS get to the SMALLEST root, even if the input value is a fair bit outside that range (i.e. it will "see" the 3.199 root or some other so converge to that)?

 

[Armitage]

Plot out your function and see what it really looks like. Newtons method works with the slope of the graph - it will always converge to the root that the slope at your starting point is pointing toward. If the slope at your starting point isn't in the direction of the root you want, or there is another root between your starting point and the smallest root, you won't find it.

So ... I'm not quite sure how you would go about finding the smallest[ root working from a given starting point via Newtons method. Ussually, you would use some other search method to find all of the roots over the interval of interest (using Newtons method to actually find the roots) and then pick the smallest one.

 

[duragezic]

Yep, right. I did check the plot of it on my calculator, zoomed in at areas, and it's kinda problematic in some areas of initial guesses (which is why the prof used this equation I'm sure). Having the smallest positive root of 3.0764 yet the next one is 3.199 something.


So it seems pretty much impossible to make it always converge to that smallest root if the initial guess is too far off? Which is stupid, the prof will sit and talk about problems with Newton's method and choosing an initial guess (as well as making sure f'(x) doesn't become zero and cause divide-by-zero) is important, yet we just get this assigned. I specifically asked him about this issue and if we are to output:"given input/initial value will not converge to smallest root", but he didn't bother to answer that question.

 

[thesurge]

Wait... so you aren't allowed to modulate newton's method (specifically the starting root value) after an x_1 input value is given? Then everyone's programs will basically be the same? You could just make the input value arbitrary and always start at the negative limit for the primitive type (dunno what language you are using) you are setting it as and work from there.

 

[duragezic]

Nope. We must take in the initial guess/value from a file, so they will test our program with whatever initial values they choose.

I'm thinking I must just have to write "will not converge to smallest root" if the input value isn't within the range I've found that will work. It's like there is no way to make all initial guesses converge to the smallest root.. Newton's method just doens't work that way. But more than likely that "cop-out" approach isn't acceptable to him, yet he won't specify if it is or not. Hence why over 50% of the class is failing right now, and he doesn't curve.

 

[Reckoner]

When do the keg stands commence?

 

[duragezic]

The keg stands commence? Eh? LOL

Paging Dr. Pizza, or maybe eLui? Is there anyway to make NM work and avoid having it hit other roots?

 

[DrPizza]

Don't forget to page RossGr; there are a couple others good at this stuff as well...

I'm kinda scratching my head, simply because Newton's method fails in several types of situations. It seems rather retarded of your professor to have you use Newton's method, but if Newton's method fails (and it does in certain situations), then you fail...

I'm sure that you will learn more methods in Numerical Methods (sounds similar to Numerical Analysis) which offer faster convergence and other improvements to Newton's method.

But, it seems that if you have to use Newton's method, starting with the initial value given, you're going to have trouble. You could, perhaps, use the intermediate value theorem and step backwards first toward zero; then use Newton's method from, say, the first time you have a change in sign...