The Dynamics of Iteration

Problem Statement

Consider the function

g(x)=\sqrt{x+2}.

We define an iterative sequence by

x_{n+1}=g(x_n),\qquad x_1=1.

L=\sqrt{L+2},

determine the exact positive limit $L$ that the sequence appears to be approaching.

0<g'(x)<\frac12

for all $x>0$ .

|x_{n+1}-L|<\frac12|x_n-L|.

Hence deduce that the sequence converges to $L$ for any initial value $x_1>0$ .

Define a function $f(x)$ such that Newton's method would converge to the same limit $L$ found in part (i), and write down the specific iterative formula for this $f(x)$ .

Hints

For (i): Substitute repeatedly into $x_{n+1}=\sqrt{x_n+2}$ , then solve the fixed-point equation.
For (ii): Differentiate $g(x)=\sqrt{x+2}$ and note where the derivative is largest for $x>0$ .
For (iii): Use either the mean value theorem or rationalise $\sqrt{x_n+2}-\sqrt{L+2}$ .
For (iv): Rearrange $L=\sqrt{L+2}$ into a polynomial equation.

Solutions

(i)

x_2=\sqrt3\approx1.732,\quad x_3=\sqrt{2+\sqrt3}\approx1.932,\quad x_4\approx1.983.

If $x_n\to L>0$ , then

L=\sqrt{L+2}\implies L^2-L-2=0 \implies (L-2)(L+1)=0.

Thus the positive limit is

L=2.

(ii)

g'(x)=\frac{1}{2\sqrt{x+2}}.

For $x>0$ , this is positive and

g'(x)<\frac{1}{2\sqrt2}<\frac12.

(iii) Since $L=2$ and $g(L)=L$ ,

\begin{aligned} |x_{n+1}-L| &=\left|\sqrt{x_n+2}-\sqrt{L+2}\right|\\ &=\frac{|x_n-L|}{\sqrt{x_n+2}+\sqrt{L+2}}\\ &<\frac12|x_n-L|, \end{aligned}

because $x_n>0$ and $\sqrt{L+2}=2$ . Repeating this inequality gives

|x_n-L|<\left(\frac12\right)^{n-1}|x_1-L|\to0,

so $x_n\to L=2$ for any $x_1>0$ .

(iv) From the fixed-point equation,

L^2-L-2=0.

So take

f(x)=x^2-x-2.

Newton's method gives

x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)} =x_n-\frac{x_n^2-x_n-2}{2x_n-1}.

Takeaways

Fixed point is the value of $x$ such that $f(x)=x$ .
Fixed points often reveal the likely limit of an iterative sequence.
A contraction inequality proves convergence by forcing errors to shrink geometrically.
Newton's method can target the same limit by solving the fixed-point equation as a root problem.

Further Readings

Connect with me