Why Does Initial Approximation Affect Convergence Speed in Newton's Method?

In summary: If you use Newton's method at or near a local maximum or minimum, the tangent line will be nearly horizontal, meaning the slope will be close to 0. This will result in a small value for the next approximation, making it take longer to converge to the root. This is why the initial approximation is important, as it affects the slope of the tangent line and the subsequent approximations.
  • #1
Alphax
11
0

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.
 
Physics news on Phys.org
  • #2
Alphax said:

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 X2 and X2 icons for superscripts (exponents) and subscripts.

Graph y = x3 - x - 1, and consider what sequence of approximate roots you get with each of those starting points.
 
  • #4
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.

SammyS said:
Note: Use the X2 and X2 icons for superscripts (exponents) and subscripts.

Graph y = x3 - x - 1, and consider what sequence of approximate roots you get with each of those starting points.
 
  • #5
SammyS said:
Note: Use the X2 and X2 icons for superscripts (exponents) and subscripts.

Graph y = x3 - 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 x3-x-1=0 has only one real root. The other two roots are complex.Alphax, try these values for your initial guess:

x1=0.577 (you did this already)
x1=0.57735
x1=0.577350269
x1=0.57735026918962

What happens on the first first step?

If that doesn't help you see what's going on, try x1=0.5773502691896257.
 
  • #6
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?


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


Alphax, try these values for your initial guess:

x1=0.577 (you did this already)
x1=0.57735
x1=0.577350269
x1=0.57735026918962

What happens on the first first step?

If that doesn't help you see what's going on, try x1=0.5773502691896257.
 
  • #7
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?
 
  • #8
Alphax said:

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 [itex]x^3 - x - 1[/itex] for [itex]-1.5 < x < 1.5[/itex]. Observe that it has turning points. What happens if you use Newton's method and start at or near a turning point?
 
  • #9
D H said:
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) = Xn - ( f(Xn) / f'(Xn) )
 
  • #10
pasmith said:
Look at the graph of [itex]x^3 - x - 1[/itex] for [itex]-1.5 < x < 1.5[/itex]. 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 x3-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.
 
  • #11
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
 
Last edited by a moderator:
  • #12
Please let me know if I am on the right track. Thanks in advance.
 
  • #13
Alphax said:
The equations is

X(n+1) = Xn - ( f(Xn) / f'(Xn) )
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 Xn is a turning point?
 
  • #14
D H said:
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 Xn is a turning point?

f'(Xn) = 0 when Xn is a turning point. This means the there's no slope.
 
  • #15
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 xn 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 xn is close to a zero of f'(x).
 
  • #16
D H said:
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 xn 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 xn is close to a zero of f'(x).

This is my first post on this website. I appreciate it. DH.
 
  • #17
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 xa, the value of the function will be negative: f(xa)<0. At the other point, call it xb, the function value will be positive: f(xb)>0. The zero of f(x) must lie between xa and xb if the function is continuous.

A simple approach to finding the zero is to look at the midpoint, xm=(xa+xb)/2. This midpoint becomes the new xa if f(xm)<0; otherwise it becomes the new xb. 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)=x3-x-1. With this, f(0)=-1 and f(2)=5. This suggests using xa=0 and xb=2, with the zero being somewhere between xa=0 and xb=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 x1=0.5 with Newton's method yields x2=-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 xa. Any initial value between 1 and 2 works quite nicely with Newton's method.
 

Related to Why Does Initial Approximation Affect Convergence Speed in Newton's Method?

1. What is Newton's method initial value?

Newton's method initial value is a numerical method used to find the root of a function. It starts with an initial guess and uses the derivative of the function to iteratively improve the guess until it reaches the root.

2. How does Newton's method initial value work?

The method starts with an initial guess, x0, and uses the formula xn+1 = xn - f(xn)/f'(xn) to find a new guess. This process is repeated until the difference between two consecutive guesses is small enough, indicating that the root has been found.

3. What is the importance of choosing a good initial value in Newton's method?

The choice of initial value can greatly affect the convergence and accuracy of Newton's method. A good initial value should be close to the actual root and reduce the number of iterations needed to find the root. Choosing a poor initial value can lead to divergent or inaccurate results.

4. Can Newton's method fail to find a root?

Yes, Newton's method can fail to find a root if the initial value is not close enough to the actual root or if the function has multiple roots. In some cases, it may also converge to a local minimum or maximum instead of the root.

5. How can one improve the convergence of Newton's method initial value?

There are several ways to improve the convergence of Newton's method, including using a better initial guess, choosing a different root-finding method, or using a modified version of Newton's method such as the Secant method. In some cases, using a combination of these methods may be the most effective approach.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
750
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
  • Calculus
Replies
13
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
3K
  • Calculus and Beyond Homework Help
Replies
4
Views
4K
Replies
1
Views
10K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
Replies
7
Views
2K
Back
Top