jon@sep.stanford.edu

Newton's iteration for square roots

(1) |

Quadratic convergence means that the square of the error at one iteration is proportional to the error at the next iteration

(2) |

Another interesting feature of the Newton iteration is that all iterations (except possibly the initial guess) are above the ultimate square root. This is obvious from equation (2).

We can insert spectral functions in the Newton square-root iteration,
for example and .Where the first guess *a _{0}* happens to match ,it will match at all iterations.
Something inspires Wilson to write the Newton iteration as

(3) |

(4) |

Now we are ready for the algorithm:
Compute the right side of (4)
by polynomial division forwards and backwards and then add 1.
Then abandon negative lags and take half of the zero lag.
Now you have *A*_{t+1}(*Z*) / *A*_{t}(*Z*).
Multiply out (convolve) the denominator *A*_{t}(*Z*),
and you have the desired result *A*_{t+1}(*Z*).
Iterate as long as you wish.

We show that *A*_{t+1}(*Z*) is minimum phase:
Both sides of (4) are positive, as noted earlier.
Both terms on the right are positive.
Since the Newton iteration always overestimates,
the 1 dominates the rightmost term.
After masking off the negative powers of *Z* (and half the zero power),
the right side of (4) adds two wavelets.
The 1/2 is wholly real,
and hence its real part always dominates the real part of the rightmost term.
Thus (after masking negative powers) the wavelet on
the right side of (4) has a positive real part,
so the phase cannot loop about the origin.
This wavelet multiplies *A*_{t}(*Z*) to give the final wavelet *A*_{t+1}(*Z*)
and the product of two minimum-phase wavelets is minimum phase.

Claerbout is interested in factoring the Laplacian

(5) |

Burg is interested in extending the Wilson algorithm to cross spectra.

(6) |

4/12/1998