fixed point iteration

• Feb 1st 2014, 08:36 PM
prasum
fixed point iteration
verify that the iteration x_{i+1}=x_{i}^{2}-2 will converge to solution epsilon=2 of the equation x^2-x-2=0 only of for some n0 all iterates xn with n>=n0 are equal to 2 ie only accidently

in this do i have to prove or just verify
if i have to prove then how?
i know
x(n+1)=g(x(n))
interval [a,b]
a<=x<=b , a<=g(x)<=b and mod of first derivative of g is less than 1
• Feb 2nd 2014, 05:59 AM
BobP
Re: fixed point iteration
I don't understand the latter part of the first sentence, ' only of for some ...' .

Anyway, the iteration given will not converge to either root of the quadratic, (unless the first iterate happens to be a root, if that can be called convergence).

Suppose that a root of the quadratic is $\alpha$ and that the error in the n'th iterate is $\epsilon_{n}$ so that $x_{n}=\alpha + \epsilon_{n},$ and similarly $x_{n+1}=\alpha + \epsilon_{n+1}.$

Substitute those into the iterative formula and simplify. For convergence, $|\epsilon_{n+1}|$ has to be less than $|\epsilon_{n}|.$
• Feb 4th 2014, 08:41 PM
johng
Re: fixed point iteration
Hi,
I don't believe BobP's answer is quite correct. The attachment shows a solution to the problem. Also, there are several questions that I have about the iterated function that arose while looking at this question. I plan to start another thread about these questions.

Attachment 30122
• Feb 5th 2014, 01:58 AM
BobP
Re: fixed point iteration
Quite correct johng, sloppy of me.

I was looking at it from the somewhat practical point of view of having a first approximation in the (close) neighbourhood of a root and the sequence converging to that root, (rather than some other one further away or, later, returning to the neighbourhood having gone walkabout and just happening to hit the root (exactly) on its way back).

For this example, a first iterate x(0)=1 or some other start value that just happens to hit this value at some stage gets you the root x=-1, but in practice this wouldn't (shouldn't) happen. The first iterate would be closer to -1 and the sequence abandoned when seen to be diverging.