Bairstow's method

From Wikipedia, the free encyclopedia

In numerical analysis, Bairstow's method is an efficient algorithm for finding the roots of a real polynomial of arbitrary degree. The algorithm first appeared in the appendix of the 1920 book "Applied Aerodynamics" by Leonard Bairstow. The algorithm finds the roots in complex conjugate pairs using only real arithmetic.

See root-finding algorithm for other algorithms.

[edit] Description of the method

Bairstow's approach is to use Newton's method to adjust the coefficients u and v in the quadratic x2 + ux + v until its roots are also roots of the polynomial being solved. The roots of the quadratic may then be determined, and the polynomial may be divided by the quadratic to eliminate those roots. This process is then iterated until the polynomial becomes quadratic or linear, and all the roots have been determined.

Long division of a polynomial

P(x)=\sum_{i=0}^n a_i x^i

by x2 + ux + v yields a quotient

Q(x)=\sum_{i=0}^n b_i x^i

and a remainder cx + d such that

P(x)=(x^2+ux+v)\left(\sum_{i=0}^n b_i x^i\right) + (cx+d).

The variables c, d, and the {bi} are functions of u and v. They can be found recursively as follows.

\,b_n = b_{n-1} = 0,
\,b_i=a_{i+2}-ub_{i+1}-vb_{i+2} \qquad (i=n-2,\ldots,0),
\,c=a_1-ub_0-vb_1,
\,d=a_0-vb_0.

The quadratic evenly divides the polynomial when

c(u,v)=d(u,v)=0. \,

Values of u and v for which this occurs can be discovered by picking starting values and iterating Newton's method in two dimensions

\begin{bmatrix} u\\ v\end{bmatrix}  := \begin{bmatrix} u\\ v\end{bmatrix} - \begin{bmatrix} \frac{\partial c}{\partial u}&\frac{\partial c}{\partial v}\\[3pt] \frac{\partial d}{\partial u} &\frac{\partial d}{\partial v}\end{bmatrix}^{-1} \begin{bmatrix} c\\ d\end{bmatrix}

until convergence occurs.

[edit] Performance

Bairstow's algorithm inherits the quadratic convergence of Newton's method, except in the case of quadratic factors of multiplicity higher than 1, when convergence can be rather slow.

[edit] External links

Languages