Newton's Method - Cube Root Of 5

[twoski]

Homework Statement

Use Newtons method to compute the cube root of 5. Do the first 10 iterations. $x_{(0)}=1$

determine the fixed points of the iteration and determine whether they are repelling/attracting. if attracting, then determine if the convergence is linear or quadratic. draw the x$^{(k+1)} vs. x^{(k)}$ diagram. for what values of $x^{(0)}$ does Newton's method converge?

The Attempt at a Solution

So i did the first 10 iterations for x^(n). After n=5, all following iterations will give the same value.

I am confused as to how we determine what the fixed points are and whether they are attracting/repelling.

 

[mfb]

Fixed points are points where x^(n+1)=x^(n). See how this can happen with Newton, and it will directly give you all fixed points. If there is some sequence converging to that point, it is attracting, but there is a more formal method to judge this in general: see how the difference to the fixed point evolves for points close to this fixed point.

 

[twoski]

So in the case of this assignment, anything from n=6 and up can be considered a fixed point. To determine whether they are attracting or repelling, I'm still not quite sure what to do. Which sequence converges to the point?

 

[mfb]

So in the case of this assignment, anything from n=6 and up can be considered a fixed point.

The fixed point is a value for x, it has nothing to do with n. Your values are approximations to that fixed point - with infinite precision, they would always change, approaching the fixed point.

To determine whether they are attracting or repelling, I'm still not quite sure what to do. Which sequence converges to the point?

What about the series you calculated?

 

[twoski]

So my 10 iterations are meant to help me find a value for x which i can say is a fixed point? My professor mentioned that a fixed point must intersect with the line y=x. If i draw out the graph of $x^{3}-5$ it would seem that the points of intersection should be around 3 and -0.5, more or less. 1.709975 appears to be where the graph intersects with the x axis.

 

[mfb]

So my 10 iterations are meant to help me find a value for x which i can say is a fixed point?

I think you should give an analytic expression for the fixed point.

My professor mentioned that a fixed point must intersect with the line y=x.

Be careful how he used y and x here. y is not the same as your f(x).

1.709975 appears to be where the graph intersects with the x axis.

Which is approximately the cube root of 5.

 

[twoski]

I'm completely lost here, so I'm backtracking and starting with the definition of a fixed point. It is an element of the function's domain that is mapped to itself by the function. Since i have to find a fixed point for each Newton iteration, i must compare each result of the 10 completed Newton iterations and if they are the same then i can conclude that a point is fixed if the previous point is the same. However, each point after the 4th iteration is technically not the same since they differ by very very small amounts. I assume we are supposed to approximate since it would be unlikely for there to be no fixed points.

Therefore i would say that the fixed points of the Newton iteration are from x^(5) to x^(10)? If i have to determine it analytically then would i just say $\sqrt[3]{5}$?

After each iteration, the value becomes slightly smaller and smaller, so would that mean it is converging on $\sqrt[3]{5}$?

 

[mfb]

I'm completely lost here, so I'm backtracking and starting with the definition of a fixed point. It is an element of the function's domain that is mapped to itself by the function.

Good.

Since i have to find a fixed point for each Newton iteration, i must compare each result of the 10 completed Newton iterations and if they are the same then i can conclude that a point is fixed if the previous point is the same.

No! That would mean you just look at 10 arbitrary values.
You have to determine it analytically.

If i have to determine it analytically then would i just say $\sqrt[3]{5}$?

Right.

After each iteration, the value becomes slightly smaller and smaller, so would that mean it is converging on $\sqrt[3]{5}$?

The value becomes smaller? The difference to your fixed point gets smaller. It does converge, indeed.

 

[twoski]

By determining the fixed points "analytically" am i just taking the x value that my iterations appear to be converging on and calling that my fixed point?

The iterations are just meant to approximate a fixed point, correct?

So if my Newton iterations are always pointing towards a certain value of x then how can they ever be repelling?

 

[mfb]

By determining the fixed points "analytically" am i just taking the x value that my iterations appear to be converging on and calling that my fixed point?

That happens to be the same here, but it does not have to in the general case.

The iterations are just meant to approximate a fixed point, correct?

They are meant to find a numerical value for the point.

So if my Newton iterations are always pointing towards a certain value of x then how can they ever be repelling?

There are functions which are not as nice as your x^3-5. Try to find the first zero of cos(x), starting with x=0.1.

 

[twoski]

In a general case, how would i analytically determine a fixed point? Say my iterations don't appear to converge to a point but instead oscillate or something, how am i supposed to interpret what it means?

I'm getting confused when i search for better notes on this material, half the time i end up finding notes on "fixed point iterations" which apparently isn't the same as Newton's method. Newton's method seems to be used exclusively for determining the zeroes for a function, i don't understand what it means when they ask me to find "fixed points of the Newton iteration"... If I've done the iteration properly then the series should show me the zeroes for the function, but are those the same as the fixed points?

 

[mfb]

In a general case, how would i analytically determine a fixed point?

Write down the formula of the iteration, set initial and final point equal and solve.

Say my iterations don't appear to converge to a point but instead oscillate or something, how am i supposed to interpret what it means?

It means that your method is not converging for that starting value.

If I've done the iteration properly then the series should show me the zeroes for the function, but are those the same as the fixed points?

They are, and you can show that based on the formula of the Newton method.

 

[twoski]

Alrght, so now i need to determine for which initial values Newton's method will converge for this problem. Is there a general method for doing this?

I also have to use the Chord method to solve this same problem. When i use the chord method, the values for x^(n) seem unpredicable. Obviously it should have the same fixed points as the Newton iteration but i can't determine that based on the iterations. How would i do this analytically?