Convergence of 10^-2^n. Linear, quadratic, cubic, quartic, hectic

[gikiian]

Homework Statement

Show that the sequence {(p_{n})}^{∞}_{n=0}=10^{-2^{n}} converges quadratically to 0.

Homework Equations

\stackrel{limit}{_{n→∞}}\frac{|p_{n+1}-p|}{|p_{n}-p|^{α}}=λ

where

• α is order of convergence; α=1 implies linear convergence, α=2 implies quadratic convergence, and so on, provided that 0<λ<1.
• λ is the asymptotic error constant; in scope of the course (Numerical Analysis), 0<λ<1, so I do not have to play with my solution further if I get λ=0 or λ=1

The Attempt at a Solution

I think the algorithm for the solution should be the following:

Check if the sequence converges for α=1 by substituting α=1 in the equation, and solving for λ.
- If λ turns out to be 0<λ<1, then the order of convergence is 1.
- If λ turns out to be λ=0, λ=1, or 1<λ<∞, then don't play further with the solution.
- If λ turns out to be λ=∞, it means that the sequence diverges for α=1. Hence we must next substitute α=2 in the equation, and solve again for λ.
- If λ turns out to be 0<λ<1, then the order of convergence is 2.
- If λ turns out to be λ=0, λ=1, or 1<λ<∞, then don't play further with the solution.
- If λ turns out to be λ=∞, it means that the sequence diverges for α=2. Hence we must next substitute α=3 in the equation, and then solve again for λ. And so on.

I realize that there is a bug in the above algorithm. I only need someone to make me identify the bug.

Following is the solution according to the procedure stated above:

Substituting for α=1 in the equation:

⇒\stackrel{limit}{_{n→∞}}\frac{|10^{-2^{n+1}}-0|}{|10^{-2^{n}}-0|^{1}}=λ

⇒\stackrel{limit}{_{n→∞}}\frac{10^{-2^{n+1}}}{10^{-2^{n}}}=λ

⇒\stackrel{limit}{_{n→∞}}\frac{10^{2^{n}}}{10^{2^{n+1}}}=λ

⇒\stackrel{limit}{_{n→∞}}\frac{10^{2^{n}}}{10^{2^{n}.2}}=λ

⇒\stackrel{limit}{_{n→∞}}\frac{10^{2^{n}}}{(10^{2^{n}})^2}=λ

⇒\stackrel{limit}{_{n→∞}}\frac{1}{10^{2^{n}}}=λ

⇒\frac{1}{∞}=λ

⇒0=λ

⇒λ=0

... but according to the textbook (Burden Faries), the sequence has to quadratically converge to p=0. In other words, solving for λ with α=2 must give 0<λ<1, but it is clear that this is not going to happen.I just need to know what is wrong with my solution/algorithm.

 

[jaytech]

Try checking how you substitute n+1 for n.

 

[gikiian]

Are you saying that 10^{-2^{n}} should equal 10^{(-2)^{n}} instead of 10^{-(2^{n})}?

 

[jaytech]

I'm saying the n+1 term is 10^-2(n+1). I don't see that in your steps, or it isn't marked clearly.

 

[pasmith]

Homework Statement

Show that the sequence {(p_{n})}^{∞}_{n=0}=10^{-2^{n}} converges quadratically to 0.

Homework Equations

\stackrel{limit}{_{n→∞}}\frac{|p_{n+1}-p|}{|p_{n}-p|^{α}}=λ

where

• α is order of convergence; α=1 implies linear convergence, α=2 implies quadratic convergence, and so on, provided that 0<λ<1.
• λ is the asymptotic error constant; in scope of the course (Numerical Analysis), 0<λ<1, so I do not have to play with my solution further if I get λ=0 or λ=1

The Attempt at a Solution

I think the algorithm for the solution should be the following:

Check if the sequence converges for α=1 by substituting α=1 in the equation, and solving for λ.
- If λ turns out to be 0<λ<1, then the order of convergence is 1.
- If λ turns out to be λ=0, λ=1, or 1<λ<∞, then don't play further with the solution.
- If λ turns out to be λ=∞, it means that the sequence diverges for α=1. Hence we must next substitute α=2 in the equation, and solve again for λ.
- If λ turns out to be 0<λ<1, then the order of convergence is 2.

This is inconsistent with the wikipedia definition, which says that if p_n \to p and
<br /> \lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|} = \lambda<br />
then p_n \to p linearly if 0 &lt; \lambda &lt; 1. If \lambda = 0 then the sequence converges superlinearly, and the order of convergence is \alpha such that
<br /> \lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^\alpha} &gt; 0.<br />

Thus your errors are that
(1) if you find that \lambda = 0 with \alpha = 1 then you should proceed to \alpha = 2, and
(2) if you find that \lambda &gt; 0 for some \alpha &gt; 1 you stop.

 

[gikiian]

This is inconsistent with the wikipedia definition, which says that if p_n \to p and
<br /> \lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|} = \lambda<br />
then p_n \to p linearly if 0 &lt; \lambda &lt; 1. If \lambda = 0 then the sequence converges superlinearly, and the order of convergence is \alpha such that
<br /> \lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^\alpha} &gt; 0.<br />

Thus your errors are that
(1) if you find that \lambda = 0 with \alpha = 1 then you should proceed to \alpha = 2, and
(2) if you find that \lambda &gt; 0 for some \alpha &gt; 1 you stop.

Thanks a million! :!)

 

[gikiian]

Thus your errors are that
(1) if you find that \lambda = 0 with \alpha = 1 then you should proceed to \alpha = 2, and

Why should I proceed? Wouldn't the sequence be shown to be superlinear already?

Or can it be superlinear and quadratic at the same time?!

(2) if you find that ∞ &gt;\lambda &gt; 0 for some \alpha &gt; 1 you stop.

Do you mind this correction?

 

[gikiian]

Why should I proceed? Wouldn't the sequence be shown to be superlinear already?

Or can it be superlinear and quadratic at the same time?!

Got it! Quadratic convergence is a form of superlinear convergence.

Do you mind this correction?

I still did not get this. Will we stop even if λ turns out to be ∞?

 

[gikiian]

I am becoming clearer on this. Just correct me if I'm wrong. My new algorithm goes like:

Substitute α=1 into the equation, and solve for λ
- If λ∈(0,1), then the order of convergence is 1
- If λ=1, then the sequence converges sublinearly
- If λ=0, then the order of convergence is greater than 1
- - Substitute α=2 into the equation, and solve for λ
- - If λ>0, then the order of convergence is 2
- - If λ=0, then the order of convergence is greater than 2
- - - Substitute α=3 into the equation, and solve for λ
- - - If λ>0, then the order of convergence is 3
- - - If λ=0, then the order of convergence is greater than 3
- - - - Substitute α=4 ... (repeat until λ turns out to be λ>0)

 

[pasmith]

Got it! Quadratic convergence is a form of superlinear convergence.



I still did not get this. Will we stop even if λ turns out to be ∞?

There's no reason for \alpha to be an integer.

The interpretation of \lambda = \infty is that |p_n - p|^{\alpha} \to 0 faster than |p_{n+1} - p| \to 0, and the interpretation of \lambda = 0 is the reverse. If 0 &lt; \lambda &lt; \infty then |p_n - p|^\alpha \to 0 about as fast as |p_{n+1} - p| \to 0.

It may turn out that
<br /> \lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^k} = 0<br />
but
<br /> \lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^{k+ 1}} = \infty<br />
in which case k &lt; \alpha &lt; k + 1.

 

[Ray Vickson]

I am becoming clearer on this. Just correct me if I'm wrong. My new algorithm goes like:

Substitute α=1 into the equation, and solve for λ
- If λ∈(0,1), then the order of convergence is 1
- If λ=1, then the sequence converges sublinearly
- If λ=0, then the order of convergence is greater than 1
- - Substitute α=2 into the equation, and solve for λ
- - If λ>0, then the order of convergence is 2
- - If λ=0, then the order of convergence is greater than 2
- - - Substitute α=3 into the equation, and solve for λ
- - - If λ>0, then the order of convergence is 3
- - - If λ=0, then the order of convergence is greater than 3
- - - - Substitute α=4 ... (repeat until λ turns out to be λ>0)

If you are speaking of a general sequence $\{ p_n \}$, rather than your original sequence, then some of your statements are incorrect. For $\alpha = 1$, just having $\lambda = 1$ does not guarantee convergence at all; the sequence may diverge (eg. $p_n = n$). If $\lambda = 0$ the sequence does converge superlinearly, but that does not mean the convergence is quadratic; we could, for example, have order $\alpha = 1 + p$ with $0 < p < 1$, etc. Many algorithms produce sequences that have quadratic convergence, but non-integer orders do occur as well for some convergent algorithms. For example, the secant method for solving f(x) = 0 has convergence order $(1+\sqrt{5})/2 \doteq 1.62$; see, eg., http://en.wikipedia.org/wiki/Secant_method or
http://www.ugrad.cs.ubc.ca/~cs302/secant.pdf . Muller's method of solving f(x) = 0 has order of convergence $\alpha \doteq 1.84$, being the positive root of the equation $x^3-x^2-x-1=0$; see, eg., http://en.wikipedia.org/wiki/Muller's_method .