Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Order of Convergence (mostly a limits question)

  1. Nov 28, 2008 #1
    SOLVED: Order of Convergence (mostly a limits question)

    1. The problem statement, all variables and given/known data
    Sequence: xn = (2x3n-1 + a)/3x2n-1. It is given that it converges to the cube root of a.

    Verify that the order of convergence of this sequence is quadratic; i.e., verify that

    lim absolute value(En)/E2n-1
    n->infinity

    exists and is positive.

    E represents the error in the nth term of the sequence; it is given that En = a1/3 - xn


    2. Relevant equations

    Hint: consider (u+2v)(u-v)2.

    3. The attempt at a solution
    1. The problem statement, all variables and given/known data
    I plugged the expression for xn into En, and used En-1 = a1/3 - xn-1. Then I substituted u = a1/3 and v = xn-1 and factored. My final limit:

    lim abs((u+2v)(u-v)2)
    n->inf. 3v2(u-v)2

    My problem is that I have no idea how to take this limit using the variable n. Even if I had left this expression in terms of a1/2 and xn-1 I wouldn't know what to do, because I don't know how to work in how x changes as it's <i>subscript</i> goes to infinity.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
    Last edited: Nov 28, 2008
  2. jcsd
  3. Nov 28, 2008 #2

    Mark44

    Staff: Mentor

    From the hint, [tex](u + 2v)(u - v)^2 = (u + 2v)(u^2 - 2uv + v^2) = u^3 - 3uv^2 + 2v^3[/tex]

    It's given that [tex]x_n = \frac{2x_{n - 1}^3 + a}{3x_{n - 1}^2}[/tex]
    and you want to show that [tex]\lim_{x \rightarrow \infty} \frac{E_n}{E_{n - 1}^2 } > 0[/tex]
    So [tex]\frac{E_n}{E_{n - 1}^2} = \frac{a^{1/3} - x_n}{(a^{1/3} - x_{n - 1}^2)^2}[/tex]
    [tex]= \frac{a^{1/3} - x_n}{a^{2/3} - 2a^{1/3}x_{n - 1} + x_{n - 1}^2}[/tex]

    Now, substitute for [tex]x_n[/tex] in the numerator, and you should eventually get to this:
    [tex]\frac{-a + 3a^{1/3}x_{n - 1}^2 - 2x_{n - 1}^3}{3x_{n - 1}^2(a^{2/3} - 2a^{1/3} + x_{n - 1}^2)}[/tex]

    The numerator looks a lot like the result from the hint, but with the signs reversed, and with u = a^(1/3), and v = x_(n - 1). Using the hint will simplify the final expression above to something that involves a^(1/3) and x_(n - 1).

    In the limit, I think it's reasonable to assume that x_(n - 1) converges to a^(1/3), and you should end up with a limiting value that is positive, which is what you wanted to show for quadratic convergence of this method -- Newton's method or Newton-Raphson, it looks like.
    Mark
     
  4. Nov 28, 2008 #3
    [
    Thanks.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook