Bairstow's method is an iterative technique used to find the root of a polynomial.

Recall that a polynomial can be written as f(x) = (x-r1)(x-r2)...(x-rn)), where rk is one root of the polynomial, k being between 1 and n.

We can take this polynomial, and divide it by (x - t), where t is our guess for the root. If we do, and there is no remainder, then our guess was correct. If there is a remainder, then our guess wasn't dead on, so we get to try again. Eventually, the remainder will disappear, and you will find a root of an equation! The method can then be reapplied to the quotient, to find yet another root.

The n'th order polynomial fn= a0 + a1x + a2x2 ... + anxn can be divided by (x - t) to get the (n-1)th ordered polynomial f(n-1)= b1 + b1x + b2x2 ... + bnx(n-1) with a remainder R = b0. These coefficients can be calculated by the relationship:

bn = an
bk = ak + b(k+1)t:  for k from (n-1) to 0

As previously stated, if the remainder b0 is equal to zero, then t is one root of the polynomial.

This is for real roots. If you wish to evaluate complex roots, divide the polynomial by a quadratic factor, (x2 -rx -s). This yields the equation

f(n-2)= b2 + b3x ... b(n-1)x(n-3) + bnx(n-2) and a remainder:
R = b1(x-r) + b0

Once again, we need to use a little recursion to find the values of the coefficients.

bn = an
b(n-1) = a(n-1) + rbn
bk = ak + rb(k+1) + sb(i+2):  for k from (n-2) to 0

Now, since it's unlikely that we would actually guess the correct values of r and s to get the correct root off the bat, we need to try and get closer to it. Bairstow's method does this by solving a series of other values, similar to the way that the coefficients of b were solved.

cn = bn
c(n-1) = b(n-1) + rbn
ck = bk + rc(k+1) + sc(i+2):  for k from (n-2) to 0

Once you have that, you find the solution to this system of equations:

c2δr + c3δs = -b1
c1δr + c2δs = -b0

Where δs and δr are how much you change s and r respectively. Plug them into the equations at the beginning and keep going. Repeat Until Dead. Or just keep on doing this until you get close enough. At that point the root x will be: x = (r +- (r2 + 4s))/2

Once you've got that done, you don't have to stop. You can keep going, doing the same thing to the quotient, finding an entirely brand new root or set of roots. That's the cool thing about this method. That and the fact that it can be used to determine complex roots. This makes up for the fact that it can only be used on polynomials. And also the fact that it's fairly complicated. There might be some stability problems, if you keep dividing but I'm not quite sure what might cause them.


Node Your Homework!