Introduction

This method finds all the roots of a one-variable polynomial function. By root, we mean x | f(x) = 0, and by polynomial, we mean f(x) = sum(i = 0 to n) a_i * x^i where a_i belongs to the real numbers.

Method

Bairstow method relies on synthetic division. When a polynomial of grade n is divided by a polynomial of grade 1 (which is a root), the resulting polynomial is of grade n – 1. Dividing n times is a slow approach and doesn’t allow us to find complex roots. Instead, by dividing by a polynomial of grade 2 (which is the product of two roots), the resulting polynomial is of grade n – 2. This is half the time than using grade 1 polynomials and the quadratic factor allows us to find complex roots.

Dividing a polynomial by two of its roots is not a feasible option, since that’s what the method tries to find. Instead, the method receives two starting values, p and q, which make the polynomial x² – px – q. After doing the synthetic division, the constants p and q are optimized, getting closer to making the remaining almost 0. After finding p and q that make the division exact, roots can be found using the quadratic formula. After this, the original polynomial gets divided by the found roots and the process repeats, until the remaining polynomial is of grade 2 (solved with quadratic formula) or grade 1 (solved by finding x).

Here’s a video that summarizes the method.

Examples

Singularities

Of all the methods for finding roots covered in this course, this is the only one that can find all the roots in a single run. This is also the only method that can find complex roots (this version is not programmed for such, but it can be programmed). Also, it has the same converging rate as Newton-Raphson.

This method doesn’t fail, even when the value given is too far from a good value, which also outstands all the other methods.

Flowchart

bairstow

Code

Conclusions

Bairstow method appears to be the best method for solving polynomial equations. The main problem resides that it only works for polynomials. But, on converging rate and efficiency, this method is far better than any other seen on this course.

On another hand, this method is harder to implement than the other methods, because it requires additional methods (such as synthetic division or linear equation solver) and some data structure for multiple values (array or vector).

Advertisements