# Order of Convergence (mostly a limits question)

1. Nov 28, 2008

### darkchild

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. Nov 28, 2008

### Staff: Mentor

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 } > 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

3. Nov 28, 2008

[
Thanks.