How to prove a sequence converges linearly or quadractically?

[dinosoup]

I have a question from my assignment which requires me to prove that a sequence converges to 0 linearly, and another sequence that converges quadractically. I have no idea how to do this. The prof didn't talk much about it neither have the TA.

The textbook book just gives the following about convergence:

"A method that produces a sequence of {pn} of approximations that converge to a number p converges linearly if, for large values of n, a constant 0 < M < 1 exists with

|p - p(n+1)| <= M|p - pn|

The sequence converges quadractically if, for large values of n, a constant 0 < M exists with

|p - p(n+1)| <= M|p - pn|^2
"

The n, (n+1) are meant to be subscripts. Could someone prove an example sequence which converges linearly or quadractically? Or give me some tips on how to do so? Thanks.

 

[HallsofIvy]

Here are a couple of obvious ones:

$$\frac{3n+2}{n+1}$$ converges to 3 linearly because
$$|3-\frac{3(n+1)+2}{(n+1)+1}|= \frac{1}{n+2}$$
while $$|3-\frac{3n+2}{n+1}|= \frac{1}{n+1}$$

and certainly $$\frac{1}{n+2}< 1* \frac{1}{n+1}$$.

 

[HallsofIvy]

"quadratic" convergence is a little harder (which is why it wasn't in my first post. I had to think about it!) but here is an obvious example:

Take p₀= 1 and then define recursively:
p_n+1= (1/2)p_n².

That is: p₀= 1
p₁= 1/2
p₂= 1/2(1/4)= 1/8
p₃= 1/2(1/64)= 1/128 etc.

That clearly converges to 0. for any n, |p- p_n+1| = p_n+1= (1/2)p₂ so it obviously of quadratic convergence (with M= 1/2).

The recursive formula makes that obvious. I could have blown your mind by handing you the result: $$p_n= \frac{1}{2^{2^n-1}}$$!

You can get a sequence that converges to any number, m, by simply adding m to that sequence: would you have guessed that
$$p_n= \frac{(5)(2^{2^n}-1)}{2^{2^n-1}}$$ converges quadratically to 5?

You should now be able to create sequences that converge to any number with any power of convergence.

 

[matt grime]

Thanks for that clarifying post. I've never heard of these types of convergence, and it worried me slightly that a non-convergent (in the usual sense) sequence could be said to converge quadratically, as appeared in the original version of the first reply.

 

[dinosoup]

Hi thanks for your reply HallsofIvy. Though I counldn't figure out how to do the question from my assignment. But thanks again.