Register to reply

Orders of convergence - how to prove that a sequence converges linearly/quadratically

Share this thread:
muso07
#1
Mar14-10, 08:17 AM
P: 54
1. The problem statement, all variables and given/known data
Which of the following converge quadratically and which converge linearly?
a) 1/n^2
b) 1/2^(2n)
c) 1/sqrt(n)
d) 1/e^n


2. Relevant equations
All I've got in my lecture notes is: The sequence converges with order a if there exist constants a and C and integer N such that |x_(n+1) -x*| <= C|x_n -x*|^a, and n>=N.


3. The attempt at a solution
For a), I got the terms 1, 1/4, 1/9, etc, and concluded that it must converge linearly since I couldn't find a constant C such that x_(n+1) <= C(x_n). But I'm not sure if it's right, and I don't know how to explain it if it is right.

For b), I also had that it converges linearly, for the same reasons as above. Again, don't know how to explain it if it's right.

c) Same

d) Same

My answers seem really wrong because I don't think all of them converge linearly but I can't seem to find any constants C such that it works for quad convergence. I'm so confused..
Phys.Org News Partner Science news on Phys.org
World's largest solar boat on Greek prehistoric mission
Google searches hold key to future market crashes
Mineral magic? Common mineral capable of making and breaking bonds
jbunniii
#2
Mar14-10, 02:36 PM
Sci Advisor
HW Helper
PF Gold
jbunniii's Avatar
P: 3,171
For (a), it's certainly true for all [itex]n[/itex] that

[tex]\left| \frac{1}{(n+1)^2} - 0 \right| \leq \left| \frac{1}{n^2} - 0 \right|[/tex]

(i.e., [itex]C = a = 1[/itex]) so this shows that the sequence converges (to zero) at least linearly.

If it were to converge quadratically, you would have to furnish a constant [itex]C[/itex] such that

[tex]\left| \frac{1}{(n+1)^2} \right| \leq C \left| \frac{1}{n^2} \right|^2[/tex]

for sufficiently large [itex]n[/itex].

But this is equivalent to

[tex]n^4 \leq C (n+1)^2[/tex]

so it's clear that no such [itex]C[/itex] exists, since the left hand side grows at a higher order than the right hand side. Therefore the sequence in (a) does NOT converge quadratically.

Try writing out in detail a similar argument for the other parts. If you can show me in detail what you have done for part (b) I'll try to help you find a suitable constant, if it exists, or to prove that one cannot exist.
muso07
#3
Mar14-10, 04:55 PM
P: 54
Wow, your explanation made so much more sense than the one in the lecture notes. So they all converge linearly, since they are all decreasing sequences.

b) If it converges quadratically, then
[tex]\left|\frac{1}{2^{2(n+1)}}\right|\leq C\left|\frac{1}{2^{2n}}\right|^{2}[/tex]
[tex](2^{n})^{4}\leq C(2^{n+1})^{2}[/tex]
which won't work because the LHS grows at a higher order, like you said about the first one. So it converges linearly.

c) Quadratically:
[tex]
\left|\frac{1}{\sqrt{n+1}}\right|\leq C\left|\frac{1}{\sqrt{n}}\right|^{2}
[/tex]
[tex]
n \leq C\sqrt{n+1}
[/tex]
Again won't work because LHS grows at a higher order. So it converges linearly.

d) Quadratically:
[tex]
\left|\frac{1}{e^{n+1}}}\right|\leq C\left|\frac{1}{e^{n}}\right|^{2}
[/tex]
[tex]
(e^{n})^{2} \leq Ce^{n+1}
[/tex]
Same as previous.

Is that right? It seems a bit weird that my lecturer would give us four sequences that converge linearly...

jbunniii
#4
Mar14-10, 06:21 PM
Sci Advisor
HW Helper
PF Gold
jbunniii's Avatar
P: 3,171
Orders of convergence - how to prove that a sequence converges linearly/quadratically

Quote Quote by muso07 View Post
Is that right? It seems a bit weird that my lecturer would give us four sequences that converge linearly...
I agree it's a bit weird, but I believe your answers are correct.

Check out this Wikipedia page to see some examples of sequences that converge quadratically:

http://en.wikipedia.org/wiki/Rate_of_convergence

You need to have more rapid decay to achieve quadratic convergence, for example

[tex]\left\{\frac{1}{2^{2^n}}\right\}[/tex]
muso07
#5
Mar14-10, 06:37 PM
P: 54
Cheers, that helped a lot. :)


Register to reply

Related Discussions
Prove sequence converges Calculus & Beyond Homework 7
Prove the sequence n/2^n converges to 0 Calculus & Beyond Homework 5
Prove the sequence converges uniformly Calculus & Beyond Homework 4
Prove that this sequence converges Calculus & Beyond Homework 16
How to prove a sequence converges linearly or quadractically? General Math 4