1. Limited time only! Sign up for a free 30min personal 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!

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

    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


    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.
  4. Nov 28, 2008 #3
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook