Analyzing Quadratic & Linear Convergence

In summary, the given sequences converge linearly, as they are all decreasing sequences. Quadratic convergence would require a constant C that cannot be found, as the left-hand side of the inequality would grow at a higher order than the right-hand side. For examples of sequences that converge quadratically, please refer to the Wikipedia page on rate of convergence.
  • #1
muso07
54
0

Homework Statement


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


Homework 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.


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..
 
Physics news on Phys.org
  • #2


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.
 
  • #3


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
Code:
[tex]\left|\frac{1}{2^{2(n+1)}}\right|\leq C\left|\frac{1}{2^{2n}}\right|^{2}[/tex]
Code:
[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:
Code:
[tex]
\left|\frac{1}{\sqrt{n+1}}\right|\leq C\left|\frac{1}{\sqrt{n}}\right|^{2}
[/tex]
Code:
[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:
Code:
[tex]
\left|\frac{1}{e^{n+1}}}\right|\leq C\left|\frac{1}{e^{n}}\right|^{2}
[/tex]
Code:
[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...
 
Last edited:
  • #4


muso07 said:
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]
 
  • #5


Cheers, that helped a lot. :)
 

1. What is the difference between quadratic and linear convergence?

Quadratic convergence refers to a method of optimization where the error decreases at a rate of approximately the square of the previous error. Linear convergence, on the other hand, refers to a method where the error decreases at a constant rate. This means that quadratic convergence is faster than linear convergence.

2. How do you determine if a method has quadratic or linear convergence?

To determine the convergence rate of a method, we look at the ratio between successive errors. If the ratio is constant, then the method has linear convergence. If the ratio decreases as the error decreases, then the method has quadratic convergence.

3. What are the advantages of quadratic convergence over linear convergence?

The main advantage of quadratic convergence is its faster rate of error reduction. This means that it requires fewer iterations to reach a desired level of accuracy, which can save time and resources. Additionally, quadratic convergence is less sensitive to initial guesses compared to linear convergence.

4. Can a method have both quadratic and linear convergence?

Yes, a method can exhibit both quadratic and linear convergence, depending on the starting point. For example, a method may have quadratic convergence for a certain range of values, but then switch to linear convergence for other values.

5. What are some common methods that exhibit quadratic or linear convergence?

Some common methods that exhibit quadratic convergence include Newton's method and the secant method. Linear convergence can be seen in methods such as gradient descent and the bisection method.

Similar threads

Replies
1
Views
571
  • Calculus and Beyond Homework Help
Replies
1
Views
255
  • Calculus and Beyond Homework Help
Replies
4
Views
881
  • Calculus and Beyond Homework Help
Replies
3
Views
413
  • Calculus and Beyond Homework Help
Replies
4
Views
306
  • Calculus and Beyond Homework Help
Replies
34
Views
2K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
7
Views
1K
Back
Top