Fixed-point Iteration; $x=g(x)$ Method

• we rearrange $f(x)$ into an equivalent form $x=g(x)$, which usually can be done in several ways.
• Observe that if $f(r)=0$, where $r$ is a root of $f(x)$, it follows that $r=g(r)$.
• Whenever we have $r=g(r)$, $r$ is said to be a fixed point for the function $g$.
• The iterative form:
  
  $$x_{n+1}=g(x_n)  n=0,1,2,3,\ldots$$
  
  
  converges to the fixed point $r$, a root of $f(x)$.
• Example
  
  $$f(x)=x^2-2x-3=0$$
  
  
  Suppose we rearrange to give this equivalent form:
  
  $$x = g_1(x) =\sqrt{2x + 3}$$
  
  

• If we start with $x=4$ and iterate with the fixed-point algorithm, successive values of $x$ are
  

  $x_0=4$

  $x_1=\sqrt{11}=3.31662$

  $x_2=\sqrt{9.63325}=3.10375$

  $x_3=3.03439$

  $x_4=3.01144$

  $x_5=3.00381$

  
  and it appears that the values are converging on the root at $x = 3$.