Order of Convergence (mostly a limits question)

[darkchild]

SOLVED: Order of Convergence (mostly a limits question)

Homework Statement

Sequence: x_n = (2x³_n-1 + a)/3x²_n-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(E_n)/E²_n-1
n->infinity

exists and is positive.

E represents the error in the nth term of the sequence; it is given that E_n = a^1/3 - x_n

Homework Equations

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

The Attempt at a Solution

Homework Statement

I plugged the expression for x_n into E_n, and used E_n-1 = a^1/3 - x_n-1. Then I substituted u = a^1/3 and v = x_n-1 and factored. My final limit:

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

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 a^1/2 and x_n-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.

 

[Mark44]

From the hint, (u + 2v)(u - v)^2 = (u + 2v)(u^2 - 2uv + v^2) = u^3 - 3uv^2 + 2v^3

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

Now, substitute for x_n in the numerator, and you should eventually get to this:
\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)}

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

 

[darkchild]

[
Thanks.