Next: Spectral factorization Up: The square root of Previous: Root-finding recursions

## The convergence rate

We can now analyze which of the particular choices of is more appropriate as far as the convergence rate is concerned.

If we consider the general form of the square root iteration

we can estimate the convergence rate by the difference between the actual estimation at step (n+1) and the analytical value . For the general case, we obtain

or
 (7)

 sqroot Figure 2 Convergence plots for different recursive algorithms, shown in Table 1.

The possible selections for from Table 1 clearly show that the recursions described in the preceding subsection generally have a linear convergence rate (that is, the error at step n+1 is proportional to the error at step n), but can converge quadratically for an appropriate selection of the parameter , as shown in Table 7. Furthermore, the convergence is faster when is closer to .

 Convergence Muir 1 linear Secant xn-1 quasi-quadratic Newton xn quadratic

We therefore conclude that Newton's iteration has the potential to achieve the fastest convergence rate. Ideally, however, we could use a fixed which is a good approximation to the square root. The convergence would then be slightly faster than for the Newton-Raphson method, as shown in Figure 2.

Next: Spectral factorization Up: The square root of Previous: Root-finding recursions
Stanford Exploration Project
4/20/1999