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
$$\lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|} = \lambda$$
then $p_n \to p$ linearly if $0 < \lambda < 1$. If $\lambda = 0$ then the sequence converges superlinearly, and the order of convergence is $\alpha$ such that
$$\lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^\alpha} > 0.$$

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 > 0$ for some $\alpha > 1$ you stop.

 

[gikiian]

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

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 > 0$ for some $\alpha > 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 $∞ >$$\lambda > 0$ for some $\alpha > 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 < \lambda < \infty$ then $|p_n - p|^\alpha \to 0$ about as fast as $|p_{n+1} - p| \to 0$.

It may turn out that
$$\lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^k} = 0$$
but
$$\lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^{k+ 1}} = \infty$$
in which case $k < \alpha < 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 .