Numerical method: iteratation to converge on root

[thisischris]

Hello!

I'm having trouble understanding the method/reasoning behind finding the root of an equation though iterative convergence.

x² - 4x + 1 = 0
x² = + 4x - 1
x = 4 - 1/x

I can understand that once we input a 'root' the equation will equal be equal on both sides. (Due to the remainder theorem) However I can't grasp why it converges to a root in all cases...

I also can't seem to understand how if we set x as 3, then we get x or x₀ as 3.667...
x = 4 - 1/(3) = 3.667
I obviously understand the equation it just doesn't quite fit how x is equal to 2 different values neither of which are a root?

How would it account for a equation that would have a 'higher' Y value for: x₀ . Which 'goes past' the root? (I've drawn a blue line over the graph).

 

[CAF123]

Are you familiar with the Newton- Raphson method, in particular the form which involves the derivative of a function?
I don't think the iterative process needs to converge to a root in all cases. It depends on the value chosen for the initial x. (e.g if you take initial x to be close to a stationary point, x(1) will be be given by drawing a tangent line to the sp and thus it might take you further from your iniital approximation.)

 

[HallsofIvy]

Hello!

I'm having trouble understanding the method/reasoning behind finding the root of an equation though iterative convergence.

x² - 4x + 1 = 0
x² = + 4x - 1
x = 4 - 1/x

I can understand that once we input a 'root' the equation will equal be equal on both sides. (Due to the remainder theorem) However I can't grasp why it converges to a root in all cases...

Good! You shouldn't grasp that because it isn't true. IF the sequence converges THEN it must converge to a solution to the equation. But there will always exist initial values for which the sequence does not converge.

I also can't seem to understand how if we set x as 3, then we get x or x₀ as 3.667...
x = 4 - 1/(3) = 3.667
I obviously understand the equation it just doesn't quite fit how x is equal to 2 different values neither of which are a root?

They are not. What you should have is x_{n+1}= 4- 1/x_n where x_n and x_{n+1} are different numbers. They are successive terms in the sequence.

How would it account for a equation that would have a 'higher' Y value for: x₀ . Which 'goes past' the root? (I've drawn a blue line over the graph).

I don't know what you mean by that.

 

[thisischris]

I don't know what you mean by that.

Thank you for your help!

Let say the function (the iterative function?) equals x_(n+1) = x² + 9999999999999999
which translates to y = x² + 9999999999999999
If we assume x is a root and hence intersects the y=x line, let's say there is a root at 3 x-coordinate... If we input 2.5/2.6/2.8/2.99999999 however we would get a very large Y value and if we input the very large y value back into the iterative function it would go 'way past' the root (3 in this case).

Obviously the root isn't 3 in this example but I'm only asking if this could 'occur', not too sure how I could 'find' an actual equation that replicates this behavior if that makes sense.

 

[HallsofIvy]

You have chosen an example which clearly does not have a real root! It is impossible for your sequence to converge to a non-existant root!

 

[thisischris]

You have chosen an example which clearly does not have a real root! It is impossible for your sequence to converge to a non-existant root!

I do realize that. I'm guessing though, that I'm thinking of an something that doesn't exist.

Thank you for everyones help!

 

[D H]

I can understand that once we input a 'root' the equation will equal be equal on both sides. (Due to the remainder theorem) However I can't grasp why it converges to a root in all cases...

What you have done is to re-write the expression f(x)=0 with f(x)=x^2-4x+1 into the form x=g(x) with g(x)=4-1/x and then used this latter expression as an iterative method x_{n+1} = g(x_n). There's a name for this technique: It's called "fixed point iteration". The reason it's called this is that the point at which x=g(x) is called a "fixed point" of the function g(x).

And it doesn't always work.

What if there isn't such a point? For example, the expression x^2-x+1=0 can be rewritten as x=1-1/x. The sequence x_{n+1} = 1 - 1/x_n won't converge. It will instead either blow up or it will cycle between three values. Note that there are no real zeros of x^2-x+1. The function g(x)=1-1/x does have fixed points, but they're complex.

Another problem arises with the example at hand. There are two real roots of f(x)=x^2-4x+1, 2+√3 and 2-√3. Pick an initial value that is not one of these roots and the iterator x_{n+1} = 4-1/x_n will either blow up because you happened to hit x_n=1/4 or it will converge to 2+√3. It won't find that other root, 2-√3. The reason is that for small epsilon in the vicinity of x=2-√3, g(x+\epsilon) \approx x + (7+4\sqrt 3)\epsilon. That factor of 7+4√3 makes an initial guess near the 2-√3 diverge away from that solution.

Yet another example is x^2-2x+1=0. Here the fixed point iterator is x_{n+1} = 2-1/x_n. This will converge to 1 for any initial guess greater than 1, but the convergence is extremely slow. The reason for this slow convergence is that the derivative of g(x)=2-1/x is exactly 1 at the solution point x=1.

Fixed point iteration can be a useful tool because it is so easy to formulate. It doesn't always work. A solution has to exist, and the absolute value of the derivative needs to be less than 1 in the vicinity of the solution in order for the technique to converge to that solution.

 

[thisischris]

Another problem arises with the example at hand. There are two real roots of f(x)=x^2-4x+1, 2+√3 and 2-√3. Pick an initial value that is not one of these roots and the iterator x_{n+1} = 4-1/x_n will either blow up because you happened to hit x_n=1/4 or it will converge to 2+√3. It won't find that other root, 2-√3. The reason is that for small epsilon in the vicinity of x=2-√3, g(x+\epsilon) \approx x + (7+4\sqrt 3)\epsilon. That factor of 7+4√3 makes an initial guess near the 2-√3 diverge away from that solution.

This is exactly what I'm asking about if I understand what you mean by 'small epsilon'. I assume it's not likely to be asked in a question, which would have this behavior present?

 

[D H]

Suppose you use the iterator x_{n+1} = 4-1/x_n with an initial value that is just 1/100 away from one of the roots 2±√3. If you start with x_0 = 2+\surd 3 + 1/100, the next element in the sequence is closer to 2+√3 than is the initial guess. That initial error of 1/100 shrinks by a factor of almost 14. Now look at what happens with a guess near the smaller root. If you start with x_0 = 2-\surd 3 + 1/100, the next element in the sequence is further from 2-√3 than is the initial guess. Instead of shrinking, that initial error of 1/100 grows by a factor of over 13.