next up previous [pdf]

Next: The convergence rate Up: The square root of Previous: The square root of

Root-finding recursions

Given a function $f(x)$ and an approximation for one of its roots $x_n$, we can find a better approximation for the root by linearizing the function around $x_n$

\begin{displaymath}f(x) \approx f(x_n)+(x_{n+1}-x_n) f'(x_n) \end{displaymath}

and by setting $f(x)$ to be zero for $x=x_{n+1}$. We find that
\begin{displaymath}
\fbox{$ \displaystyle
x_{n+1}=x_{n}-\frac{f(x_n)}{f'(x_n)}
$} \end{displaymath} (1)

  1. Newton-Raphson's method for the square root

    A common choice of the function $f$ is $f(x)=x^2-s$. This function has the advantage that it is easily differentiable, with $f'(x)=2x$. The recursion relation thus becomes

    \begin{displaymath}x_{n+1}=x_{n}-\frac{x_n^2-s}{2x_n}
=\frac{x_n}{2}+\frac{s}{2x_n} \end{displaymath}

    or

    \begin{displaymath}x_{n+1}=\frac{1}{2}\left(x_n+\frac{s}{x_n}\right) \end{displaymath}

    or, after rearrangement,
    \begin{displaymath}
\fbox{$ \displaystyle
x_{n+1}=\frac{s+x_n^2}{2 x_n}
$} \end{displaymath} (2)

    The recursion (2) converges to $\pm \sqrt{s}$ depending on the sign of the starting guess $x_0\ne 0$.

  2. Secant method for the square root

    A variation of the Newton-Raphson method is to use a finite approximation of the derivative instead of the differential form. In this case, the approximate value of the derivative at step $n$ is

    \begin{displaymath}f'(x_n)=\frac{f(x_n)-f(x_{n-1})}{x_{n}-x_{n-1}} \end{displaymath}

    For the same choice of the function $f$, $f(x)=x^2-s$, we obtain

    \begin{displaymath}x_{n+1}=x_{n}-\frac{x_n^2-s}{x_n+x_{n-1}}\end{displaymath}

    and
    \begin{displaymath}
\fbox{$ \displaystyle
x_{n+1}=\frac{s+x_{n}x_{n-1}}{x_n+x_{n-1}}
$} \end{displaymath} (3)

    In this case, recursion (3) also converges to $\pm \sqrt{s}$ depending on the sign of the starting guesses $x_0$ and $x_1$.

  3. Muir's method for the square root

    Another possible iterative relation for the square root is Francis Muir's, described by Claerbout (1995):

    \begin{displaymath}
\fbox{$ \displaystyle
x_{n+1}=\frac{s+x_{n}}{x_n+1}
$} \end{displaymath} (4)

    This relation belongs to the same family of iterative schemes as Newton and Secant, if we make the following special choice of the function $f(x)$ in (1):

    \begin{displaymath}
f(x)=
\vert x+\sqrt{s}\vert^{\frac{\sqrt{s}-1}{2\sqrt{s}}}
\vert x-\sqrt{s}\vert^{\frac{\sqrt{s}+1}{2\sqrt{s}}} \end{displaymath} (5)

    Figure 1 is a graphical representation of the function f(x).

    muf
    Figure 1.
    The graph of the function defined in Equation (1) used to generate Muir's iteration for the square root (solid line). The dashed lines are the plot of the two factors in the equation .
    muf
    [pdf] [png] [matlab]

  4. A general formula for the square root

    From the analysis of equations (2), (3), and (4), we can derive the following general form for the square root iteration:

    \begin{displaymath}
\fbox{$ \displaystyle
x_{n+1}=\frac{s+x_{n}\gamma}{x_n+\gamma}
$} \end{displaymath} (6)

    where $\gamma$ can be either a fixed parameter, or the value of the iteration at the preceding step, as shown in Table 1.

    Table 1: Recursions for the square root
      $\gamma$ Recursion
    Muir $1$ $x_{n+1}=\frac{s+x_n }{x_n+1 }$
    Secant $x_{n-1}$ $x_{n+1}=\frac{s+x_n x_{n-1}}{x_n+x_{n-1} }$
    Newton $x_n$ $x_{n+1}=\frac{s+x_n^2 }{2 x_n }$
    Ideal $\sqrt{s}$ $x_{n+1}=\frac{s+x_n\sqrt{s}}{x_n+\sqrt{s}}$

    The parameter $\gamma$ is the estimate of the square root at the given step (Newton), the estimate of the square root at the preceding step (Secant), or a constant value (Muir). Ideally, this value should be as close as possible to $\sqrt{s}$.


next up previous [pdf]

Next: The convergence rate Up: The square root of Previous: The square root of

2013-03-03