Logo
Published on

The Dynamics of Iteration

Authors
  • avatar
    Name
    Vu Hung
    Twitter

Problem Statement

Consider the function

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

We define an iterative sequence by

xn+1=g(xn),x1=1.x_{n+1}=g(x_n),\qquad x_1=1.
  • Calculate x2,x3,x_2,x_3, and x4x_4 to three decimal places. By solving
L=L+2,L=\sqrt{L+2},

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

  • Show that
0<g′(x)<120<g'(x)<\frac12

for all x>0x>0.

  • Prove that
∣xn+1−L∣<12∣xn−L∣.|x_{n+1}-L|<\frac12|x_n-L|.

Hence deduce that the sequence converges to LL for any initial value x1>0x_1>0.

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

Hints

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

Solutions

(i)

x2=3≈1.732,x3=2+3≈1.932,x4≈1.983.x_2=\sqrt3\approx1.732,\quad x_3=\sqrt{2+\sqrt3}\approx1.932,\quad x_4\approx1.983.

If xn→L>0x_n\to L>0, then

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

Thus the positive limit is

L=2.L=2.

(ii)

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

For x>0x>0, this is positive and

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

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

∣xn+1−L∣=∣xn+2−L+2∣=∣xn−L∣xn+2+L+2<12∣xn−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 xn>0x_n>0 and L+2=2\sqrt{L+2}=2. Repeating this inequality gives

∣xn−L∣<(12)n−1∣x1−L∣→0,|x_n-L|<\left(\frac12\right)^{n-1}|x_1-L|\to0,

so xn→L=2x_n\to L=2 for any x1>0x_1>0.

(iv) From the fixed-point equation,

L2−L−2=0.L^2-L-2=0.

So take

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

Newton's method gives

xn+1=xn−f(xn)f′(xn)=xn−xn2−xn−22xn−1.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 xx such that f(x)=xf(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