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.