2.0  Bairstow's Method of Finding the Roots of Polynomial Equations.

2.1  A Brief Description of Methodology.

In Bairstow's Method, the equation to be solved is divided by a quadratic, the coefficients, r and s, of which, are initially specified as the ïnput guesses". This results in a reduced polynomial and a remainder. Based upon the coefficients of the original polynomial, and those of the dividing quadratic, the parameters r and s are then adjusted to new values using a Taylor's series expansion, with the objective of reducing the remainder to zero. This process is continuously repeated until the division remainder approaches zero to within a specified limit. The resulting roots of the dividing quadratic are then taken as the same as two of those of the original polynomial. The latter is then reduced by the roots found, and the whole process repeated until all the roots have been determined.

A more detailed description may be found in [1].

2.2  Failure Mechanisms and Restrictions.

As it stands there are basically four problems with this method, as follows.

(i) If the ïnitial guesses" of the coefficients of the dividing quadratic are unsuitable, the method can diverge. The reason for this is analysed in Appendix A.

(ii) If the required output precision is too tight, the method can hunt and fail to converge to a solution. The reason for this is also analysed in Appendix A.

(iii) The method is only applicable to polynomials with real coefficients. It can however, deal with these to any exponent order.

(iv) When the polynomial to be factored contains multiple identical or very close roots, the method can produce results that are outside the required precision.

These problems limit the applicability of the method, especially when high order polynomials need to be factored. However, because the method is most conducive to computer implementation in a spreadsheet, these problems can be eliminated. The first three problems are easily eliminated. The fourth is more difficult.

2.3  Problem Elimination.

The solutions to the problems described here, are as incorporated in the computer spreadsheet implementations associated with this paper.

2.3.1  Divergence.

The problem of divergence is eliminated by monitoring the remainder after each fourth division of the iterated quadratic, to see whether it is increasing or decreasing. If it is increasing, and continues to do so to exceed a predetermined limit, the original value of s is adjusted by unity, and the whole process restarted. This is repeated until the remainder stops diverging, and converges towards zero. The limit set in the Bairstow spreadsheet is 1E ± 100. See Appendix A.

2.3.2  Hunting.

To eliminate the problem of hunting, first note that precision is initially specified by how close the remainder should approach zero before the root is taken. The value specified in the Bairstow spreadsheet is 1E - 10. To avoid hunting, if the roots have not been found before 100 iteration cycles, this limit is continuously reduced by a multiplicative factor of 1.01, until it reaches the level of precision to which the method has achieved. The roots are then taken, the limit reset to the above value, and the process restarted to find the next pair of roots. See Appendix A.

2.3.3  Complex Coefficients.

The fact that the Bairstow Method is only applicable to polynomials with real coefficients is a serious limitation. The method itself cannot be modified to accommodate polynomials with such characteristics, but these types of equations can themselves be reformatted to make them applicable.

Consider the following generalised equation,


y= n
å
i=0 
 Ai xi
(2.1)

where


Ai = ai +jbi
(2.2)


To find the roots of (2.1) using Bairstow's Method, first multiply (2.1) by its complex conjugate equation, i.e.


yc = n
å
k=0 
 Bk xk
(2.3)

where


Bk = ak -jbk
(2.4)

This results in,


yyc = n
å
i=0,k=0 
 A(n-i) B(n-k) x(2n-i-k)
(2.5)


and where all the coefficients are real. Equate (2.5) to zero and normalise the coefficient of the highest exponent to unity. Eq.(2.1) has thereby been converted to a polynomial of twice the order, but with real coefficients. The roots of (2.5) will be the complex conjugate pairs of (2.1) and (2.3), and any real roots in (2.1) and (2.3) will therefore be duplicated in the roots of (2.5).

To identify which roots of (2.5) belong to (2.1), first the number of all real roots will obviously be one half of all duplicated real roots. The complex roots can then be identified by applying Descartes' Rule of Signs to the imaginary coefficients of (2.1). This latter process may require a trial reconstruction of (2.1) from selected pairs of roots of (2.5), if the roots of (2.1) contain both positive and negative imaginary components.

Simple examples of the above procedure are given in Appendix B.

Note that the process of multiplying high order polynomials with complex conjugate coefficients, has been facilitated on the second sheet of the Polynomial Construction spreadsheet associated with this paper.

2.3.4  Multiple Roots.

When all the roots are real and identical, they can easily be determined from the appropriate comparison of a(n-1), the coefficient of x(n-1), and a0, the constant term in the polynomial. Apart from this one case, this is the most difficult problem associated with any root extraction algorithm. Multiple roots not being correctly identified, and appearing as slightly separated singular roots. Sometimes small conjugate imaginary components also appear, when only real roots are expected. This can also occur when two roots are not quite identical, but very close. The worst case occurs when there (n - 1) identical roots, and one singular root, especially when the multiples and the singular are widely separated. To avoid this specific case, a new algorithm, independent of the Bairstow Method, has been developed that will identify all such roots with 100% accuracy and precision. The algorithm is based upon a specific relationship, that in this case, exists between the original polynomial and its first derivative.

In all remaining cases, extraction of all multiple root combinations are subject to the Bairstow Method as modified herein. Accordingly, if the number of identical roots is small, typically less than half the total number of roots, they are generally identified correctly. It is believed that this is because the method, being quadratically convergent, each half of an identical pair of roots is located in conjunction with one of the singular roots. If however, the number of identical roots exceeds one half of the total number of roots, this does not apply, especially when one of the multiple roots is the first to be taken. The problem appears to be due to the fact that with identical roots, when the polynomial is graphed, the curve does not cross the x axis, but just touches it at one singular point, plus the nature of iterative analysis being a non-continuous process, the method is unable to converge to the exact root. The difficulty is partly alleviated in the Bairstow spreadsheet application associated with this paper, by subjecting every reduced equation to a new part multiplicity root check algorithm before continuing with the Bairstow analysis. This produces a good result when all the singular roots have been identified, and only multiple roots are left in the reduced equation. Where this is not the case, the remainder of the division process oscillates close to zero at the location of the remaining multiple roots by an amount determined by the iteration amplitude. In the application here, this continues until the hunting avoidance mechanism reduces the required precision to that attained by the iteration process and the "roots" are then taken. Errors with multiple complex roots are not so great because of the variation resulting from the opposing imaginary components.

The Bairstow Method cannot be modified to eliminate this difficulty, and so, another method of elimination must be used. The method selected here, which applies to multiple complex roots as well as real, is as follows.

First, a simple algorithm has been included in the Bairstow spreadsheet to indicate when multiple root errors may be present in the results, and the multiple roots thereby detected as very close singular roots, straddling them with errors of up to ±3%. Thus when this is the case, all the roots found can be copied to the Polynomial Construction spreadsheet, and inserted into the input cells in ascending order. The resulting polynomial coefficients can then be directly compared with those of the original equation, for which appropriate input cells have been provided. If there are discrepancies, the individual roots can then be iterated by any amount, up or down, until the resulting polynomial coefficients exactly match those of the original equation. The final roots are then precise.

When the multiple roots involved are integer, or posses just a small number of decimal places, this process is relatively easy and a satisfactory result achieved quite quickly. If the multiple roots are complex, and/or involving very high precision, the iteration process will be more difficult and require some patience and good interpretative skills.



M3 Version 1.0.0
Ó P.G.Bass, January 2010

On to the Next Section:- Spreadsheet Implementations

Back to the Introduction to this Paper:- Bairstow Polynomial Roots

Back to the Home Page for this Site:- Home