# 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.

-

You can find a nice concise exposition of Newton's method for algebraic systems of equations in the paper below. There it is applied to the algebraic equations that arise from (multivariate) polynomial factorization - but the ideas are quite general (Newton-Hensel methods are fundamental for effective algebraic computation). For a more general and more detailed presentation see the chapter on "Hensel algorithms" in Zippel's textbook Effective Polynomial computation, and see also my sci.math post for references to expositions of Mora, Ribenboim, von zur Gathen et. al.

Zippel, R. $\$ Newton's Iteration and the Sparse Hensel Algorithm,
Proc. 1981 ACM Sympos. Symbolic and Algebraic Computation, Utah, 1981, pp. 68-72

-

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$.

-