Show that an iterative method converges to sqrt(a)

Question

Okay, i think i solved it but it seems too easy:

$\lim_\limits{x\to \infty}$ $x_n = \lim_\limits{x\to \infty}$ $x_{n+1} = \sqrt{a}$ the iterative method is: $x_{n+1}$ = $\frac{x_n(x_n^2 + 3a)}{3x_n^2 + a}$ I let $x_n$ be $\sqrt{a}.$ And crunched the equation. Is this right, and if not, what did i do wrong?

Answer 1

I'm not sure what you are doing.

I assume $a>0$. Suppose the sequence defined by $x_{0}$ and $$ x_{n+1}=\frac{x_{n}\left(x_{n}^{2}+3a\right)}{3x_{n}^{2}+a}\text{ for }n\geq0\tag{1} $$ is well-defined and has limit $x$ such that $3x^{2}+a\neq0$ and $x\neq0$. Taking limits on both sides of (1), $$ x=\frac{x\left(x^{2}+3a\right)}{3x^{2}+a}. $$ Dividing both sides by $x$ (we can do this since we assumed $x\neq0$), $$ 1=\frac{x^{2}+3a}{3x^{2}+a}. $$ Equivalently, $$ x^{2}=a $$ and hence $x=\pm \sqrt{a}$.

Answer 2

You have not shown $x_n$ converges to $\sqrt{a}$, you have only shown $\sqrt{a}$ is a fixed point of the iteration.

In general, when someone set up a sequence $x_n$ by iteration of a function $f(x)$ and ask one to show the sequence $x_n$ converges to some number $\alpha$. What it really means is

Given a function $f : D \to D$ where $D \subset \mathbb{R}$ ( or $\mathbb{C}$ or whatever appropriate).
For suitable choice of $x_0 \in D$, the sequence defined by the iteration $$x_{n+1} = f(x_n), \quad\text{ for } n \ge 0$$ will converge to $\alpha$, i.e. $\lim\limits_{n\to\infty} x_n = \alpha$, independent of precise choice of $x_0$.

If the explicit range of $x_0$ is not given, it usually mean either "for $x_0$ sufficiently close to $\alpha$" or "for all $x_0$ falling in some obvious choice of domain".

For the problem at hand, $\displaystyle\;f(x) = \frac{x(x^2+3a)}{3x^2+a}$ and $\alpha = \sqrt{a}$.

To show $x_n$ converges to $\alpha = \sqrt{a}$, showing $f(\alpha) = \alpha$ is not enough. At the least, you need to show there is some $\epsilon > 0$ and $\lim\limits_{n\to\infty} x_n = \alpha$ whenever $|x_0 - \alpha| < \epsilon$.

It turns out we can do much better than that.

For any $a > 0$, we are going to show for any $x_0 \in \mathbb{C}$ with $\Re x_0 > 0$, we have $\lim\limits_{n\to\infty} x_n = \alpha = \sqrt{a}$.

Consider following auxiliary sequence $$y_n = \frac{x_n - \alpha}{x_n + \alpha} \quad\iff\quad x_n = \alpha \left( \frac{1+y_n}{1-y_n} \right) $$ It is easy to verify $$y_{n+1} = \frac{x_{n+1}-\alpha}{x_{n+1} + \alpha} = \frac{x_n(x_n^2 + 3\alpha^2) -\alpha(3x_n^2+\alpha^2)}{x_n(x_n^2 + 3\alpha^2) +\alpha(3x_n^2+\alpha^2)} = \left(\frac{x_n-\alpha}{x_n+\alpha}\right)^3 = y_n^3 $$ Since this is true for all $n$, we obtain following closed form for $y_n$ and hence for $x_n$:

$$y_n = y_0^{3^n}\quad\implies\quad x_n = \alpha \left( \frac{1+y_0^{3^n}}{1-y_0^{3^n}} \right) $$

When $\Re x_0 > 0$, we have $|y_0|= \left|\frac{x_0 - \alpha}{x_0 + \alpha}\right| < 1$. This forces $|y_n| = |y_0|^{3^n} \to 0$ as $n \to \infty$.
As a result,

$$\lim_{n\to\infty} x_n = \alpha \left(\frac{1+0}{1-0}\right) = \alpha = \sqrt{a}$$

By a similar argument, when $\Re x_0 < 0$, $|y_0| > 1$ and $$\lim_{n\to\infty} x_n = \lim_{n\to\infty} \alpha\left(\frac{y_0^{-3^n}+1}{y_0^{-3^n}-1}\right) = \alpha\left(\frac{0+1}{0-1}\right) = -\alpha = -\sqrt{a}$$