Newton's method initial value

[Alphax]

Homework Statement

Use Newton's method with x1 = 1 to find the root of the equation x3 - x = 1 to correct six decimal places.

Do the question again with x1 = 0.6

Do the question again with x1 = 0.57

You probably need to do it in an excel sheet. With each try, it takes longer to find root of the equation. My question is why Newton's method is so sensitive to the value of initial approximation.

Homework Equations

The Attempt at a Solution

I am not seeking the answers to Newton's method. I am trying to understand why Newton's method is sensitive to inaccurate initial approximation. For this problem, 1 is much closer to the root of the equation than 0.6 or 0.57, and this is the reason why I was able to find the answer faster. As the initial approximation is further from the root of the equation, the answer takes longer time to solve.

So, why is the value of initial approximation have an impact on the time it takes to solve the equation.

 

[SammyS]

Homework Statement

Use Newton's method with x1 = 1 to find the root of the equation x3 - x = 1 to correct six decimal places.

Do the question again with x1 = 0.6

Do the question again with x1 = 0.57

You probably need to do it in an excel sheet. With each try, it takes longer to find root of the equation. My question is why Newton's method is so sensitive to the value of initial approximation.

Homework Equations

The Attempt at a Solution

I am not seeking the answers to Newton's method. I am trying to understand why Newton's method is sensitive to inaccurate initial approximation. For this problem, 1 is much closer to the root of the equation than 0.6 or 0.57, and this is the reason why I was able to find the answer faster. As the initial approximation is further from the root of the equation, the answer takes longer time to solve.

So, why is the value of initial approximation have an impact on the time it takes to solve the equation.

Note: Use the X² and X₂ icons for superscripts (exponents) and subscripts.

Graph y = x³ - x - 1, and consider what sequence of approximate roots you get with each of those starting points.

 

[jedishrfu]

Not sure if this will help:

http://en.wikipedia.org/wiki/Newton's_method

there's a graphics that illustrates the method and as you watch you might begin to see why choices take longer:

http://en.wikipedia.org/wiki/Newton's_method#mediaviewer/File:NewtonIteration_Ani.gif

 

[Alphax]

please elaborate

The sequence of approximate roots appears to be all over the place initially, it takes a while to converge to the correct 6 decimal places.

Can you please elaborate on your comment. I am not the sharpest when it comes to calculus.

Thanks in advance.

Note: Use the X² and X₂ icons for superscripts (exponents) and subscripts.

Graph y = x³ - x - 1, and consider what sequence of approximate roots you get with each of those starting points.

 

[D H]

Note: Use the X² and X₂ icons for superscripts (exponents) and subscripts.

Graph y = x³ - x - 1, and consider what sequence of approximate roots you get with each of those starting points.

That's not really the problem here. The equation x³-x-1=0 has only one real root. The other two roots are complex.Alphax, try these values for your initial guess:

x₁=0.577 (you did this already)
x₁=0.57735
x₁=0.577350269
x₁=0.57735026918962

What happens on the first first step?

If that doesn't help you see what's going on, try x₁=0.5773502691896257.

 

[Alphax]

tried the suggestion

I tried the examples you suggested.

I notice Newton's method takes longer as the decimals gets longer. The number of decimals determines the time it takes to converge. But I am not sure why. What's so special about complex number?

That's not really the problem here. The equation x³-x-1=0 has only one real root. The other two roots are complex.


Alphax, try these values for your initial guess:

x₁=0.577 (you did this already)
x₁=0.57735
x₁=0.577350269
x₁=0.57735026918962

What happens on the first first step?

If that doesn't help you see what's going on, try x₁=0.5773502691896257.

 

[D H]

It's not the number of decimals. Try 1.2345678901234. That won't take long at all.This is either homework or it is a homework-like question, so you should have written down the relevant equations. What are the relevant equations for Newton's method?

 

[pasmith]

Homework Statement

Use Newton's method with x1 = 1 to find the root of the equation x3 - x = 1 to correct six decimal places.

Do the question again with x1 = 0.6

Do the question again with x1 = 0.57

You probably need to do it in an excel sheet. With each try, it takes longer to find root of the equation. My question is why Newton's method is so sensitive to the value of initial approximation.

Homework Equations

The Attempt at a Solution

I am not seeking the answers to Newton's method. I am trying to understand why Newton's method is sensitive to inaccurate initial approximation. For this problem, 1 is much closer to the root of the equation than 0.6 or 0.57, and this is the reason why I was able to find the answer faster. As the initial approximation is further from the root of the equation, the answer takes longer time to solve.

So, why is the value of initial approximation have an impact on the time it takes to solve the equation.

Look at the graph of $x^3 - x - 1$ for $-1.5 < x < 1.5$. Observe that it has turning points. What happens if you use Newton's method and start at or near a turning point?

 

[Alphax]

It's not the number of decimals. Try 1.2345678901234. That won't take long at all.


This is either homework or it is a homework-like question, so you should have written down the relevant equations. What are the relevant equations for Newton's method?

The equations is

X_(n+1) = X_n - ( f(X_n) / f'(X_n) )

 

[Alphax]

Look at the graph of $x^3 - x - 1$ for $-1.5 < x < 1.5$. Observe that it has turning points. What happens if you use Newton's method and start at or near a turning point?

If you use Newton's method at or near a turning point, also known as local min/max points. The tangent line at the the point will produce a gentle slope that will have a large x-intercept. The value produce in the subsequent steps are large values due to the gentleness of the slope at the local maximum and minimum.

Also, if the initial approximation is further away from the real root, it will take longer to find the root. The real root to the problem x³-x-1 = 0 has a real root of 1.325. So, if the initial approximation is Try 1.2345678901234, it will only take 3 iterations to find the root.

So, to sum it up, the Newton's method is sensitive to the initial approximation that is further from the real root, and initial approximation that is near or at a turning point.

 

[Alphax]

Also, the answer received 'may' vary from machine to machine. This is due to rounding-off error.

http://www.physics.nyu.edu/grierlab/idl_html_help/mathematics4.html

 

[Alphax]

Please let me know if I am on the right track. Thanks in advance.

 

[D H]

The equations is

X_(n+1) = X_n - ( f(X_n) / f'(X_n) )

Good.

Regarding your three subsequent posts questions, yes, you're on track. You're missing a key point, however. What happens to the denominator in the second term on the right hand side of the above expression when X_n is a turning point?

 

[Alphax]

Good.

Regarding your three subsequent posts questions, yes, you're on track. You're missing a key point, however. What happens to the denominator in the second term on the right hand side of the above expression when X_n is a turning point?

f'(X_n) = 0 when X_n is a turning point. This means the there's no slope.

 

[D H]

What happens when you divide a non-zero number by another number that is very close to zero? This is one of the reasons why Newton's method fails at times.

Newton's method is very good when an estimate x_n is close to a zero of f(x) and when f'(x) is well removed from zero. Then Newton's method exhibits "quadratic behavior" -- each iteration more or less doubles the number of places of accuracy. On the other hand, all kinds of bad things can happen when an estimate x_n is close to a zero of f'(x).

 

[Alphax]

What happens when you divide a non-zero number by another number that is very close to zero? This is one of the reasons why Newton's method fails at times.

Newton's method is very good when an estimate x_n is close to a zero of f(x) and when f'(x) is well removed from zero. Then Newton's method exhibits "quadratic behavior" -- each iteration more or less doubles the number of places of accuracy. On the other hand, all kinds of bad things can happen when an estimate x_n is close to a zero of f'(x).

This is my first post on this website. I appreciate it. DH.

 

[D H]

Welcome aboard, Alphax!

Newton's method is very powerful, when it works. When it doesn't work, it can send the search for a root off to never-never land. Oftentimes a combination of approaches works best. If possible, it's best to keep the search for a root "bracketed". Rather than working from one point to another, a bracketed approach works with a pair of points. At one of the points, call it x_a, the value of the function will be negative: f(x_a)<0. At the other point, call it x_b, the function value will be positive: f(x_b)>0. The zero of f(x) must lie between x_a and x_b if the function is continuous.

A simple approach to finding the zero is to look at the midpoint, x_m=(x_a+x_b)/2. This midpoint becomes the new x_a if f(x_m)<0; otherwise it becomes the new x_b. Every iteration halves the search interval. Eventually the interval will become small enough that you can essentially say you found the root.

This bisection technique is rather slow compared to other techniques, but it has one saving grace: It is guaranteed to work. Bisection can be combined with Newton's technique (and with other techniques as well).

For example, your function is f(x)=x³-x-1. With this, f(0)=-1 and f(2)=5. This suggests using x_a=0 and x_b=2, with the zero being somewhere between x_a=0 and x_b=2. Since f(0) is closer to zero than is f(2), this suggests trying an initial guess with Newton's method that is closer to 0 than 2. An initial guess of x₁=0.5 with Newton's method yields x₂=-5. This is outside the brackets, so we reject it and use bisection instead. The midpoint of 0 and 2 is 1, and since f(1)=-1, this becomes our new x_a. Any initial value between 1 and 2 works quite nicely with Newton's method.