1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 7, 2014 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

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

    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

    3. 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:

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

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

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

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

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

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

    [itex]⇒\frac{1}{∞}=λ[/itex]

    [itex]⇒0=λ[/itex]

    [itex]⇒λ=0[/itex]

    ... 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.
     
    Last edited: Mar 7, 2014
  2. jcsd
  3. Mar 7, 2014 #2
    Try checking how you substitute n+1 for n.
     
  4. Mar 7, 2014 #3
    Are you saying that [itex]10^{-2^{n}}[/itex] should equal [itex]10^{(-2)^{n}}[/itex] instead of [itex]10^{-(2^{n})}[/itex]?
     
  5. Mar 7, 2014 #4
    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.
     
  6. Mar 7, 2014 #5

    pasmith

    User Avatar
    Homework Helper

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

    Thus your errors are that
    (1) if you find that [itex]\lambda = 0[/itex] with [itex]\alpha = 1[/itex] then you should proceed to [itex]\alpha = 2[/itex], and
    (2) if you find that [itex]\lambda > 0[/itex] for some [itex]\alpha > 1[/itex] you stop.
     
  7. Mar 7, 2014 #6
    Thanks a million!!!!!!!!!! :!!)
     
  8. Mar 7, 2014 #7
    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???!


    Do you mind this correction?
     
    Last edited: Mar 7, 2014
  9. Mar 8, 2014 #8
    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 ∞?
     
  10. Mar 8, 2014 #9
    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)
     
  11. Mar 8, 2014 #10

    pasmith

    User Avatar
    Homework Helper

    There's no reason for [itex]\alpha[/itex] to be an integer.

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

    It may turn out that
    [tex]
    \lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^k} = 0
    [/tex]
    but
    [tex]
    \lim_{n \to \infty} \frac{|p_{n+1} - p|}{|p_n - p|^{k+ 1}} = \infty
    [/tex]
    in which case [itex]k < \alpha < k + 1[/itex].
     
  12. Mar 8, 2014 #11

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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 [Broken] . 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 .
     
    Last edited by a moderator: May 6, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Convergence of 10^-2^n. Linear, quadratic, cubic, quartic, hectic
  1. Convergence of n^(1/n) (Replies: 1)

Loading...