# 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. –  Ｊ. Ｍ. Dec 19 '10 at 2:07

A proof of the quadratic convergence rate for Newton's method in 2 variables may be found in the book Elements of Numerical Analysis by P. Henrici (J. Wiley, 1964).

Also proved is the condition for this to apply to Bairstow's method.

-
Zippel, R. $\$ Newton's Iteration and the Sparse Hensel Algorithm,
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$.