# Bairstow's method: Rate of convergence

In numerical analysis, I was asked whether Bairstow's algorithm convergence rate is quadratic.

My initial feeling was that it does, since it is essentially Newton's method for a system of non-linear equations, and Newton's method converges quadratically in one dimension (When f is from R to R).

A quick search on the internet seemed to indicate that indeed, the rate is quadratic as long as the roots are of multiplicity 1.

However, I have real trouble proving this. I was trying to imitate the proof of Newton's method in one dimesnsion found in Kincaid and Cheney's book "Numerical Analysis", but ran into some trouble since there isn't a simple "second derivative" for a vector valued function (unless I want to use tensors, and that's way beyond our course material).

So I'm stuck. How do I show that the rate of convergence is quadratic (or that it's not if the roots aren't simple)?

• The Kantorovich theorem is what's used for proving the quadratic convergence rate of multivariate Newton-Raphson, IIRC. There should be something on this in the book by Ortega and Rheinboldt. – J. M. is a poor mathematician Dec 19 '10 at 2:07

Actually, a straightforward componentwise analysis should do the job. First prove the quadratic rate for the fixed point iteration $x\leftarrow\phi(x)$, where $\phi:\mathbb{R}^n\to\mathbb{R}^n$ and the jacobian of $\phi$ is zero at the solution $\alpha=\phi(\alpha)$. Simply do what you do in 1 dimension, e.g., use Taylor's theorem with second order remainder. Then for the Newton method one has to substitute $\phi(x)=x-J(x)f(x)$ where $J$ is the jacobian of $f$, and show that the jacobian of such $\phi$ is zero at a solution $\alpha$ of $f(\alpha)=0$ if $J(\alpha)\neq0$.
Zippel, R. $\$ Newton's Iteration and the Sparse Hensel Algorithm,