Bairstows Method  

A interesting iteration method that i have been searching is the Bairstow Method, which is based in the Müllers and the Newton-Raphson method.

It is very important because it allows to calculate all the polinomic roots, no matter if they are real or imaginary.



Here there are some steps that may help you to solve polynomials with this accurate method, i hope you enjoy learning this:

With a polinomyal like fn(x)you must find two factors, a cuadratic polynomial f2(x) = x2 – rx – s and fn-2(x)
.

This is the general procedure for Bairstow Method:

1.) With fn(x) and r0 and s0.

2.) With the Newton-Raphson method you calculate f2(x) = x2 – r0x – s0 and fn-2(x).

3.) You determine the roots f2(x) using the general formula.

4.) You calculate fn-2(x)= fn(x)/ f2(x)..

5.) Then you equal fn(x)= fn-2(x).

6.) If the grade of the polinomyal is greater than three, you must go back to step two.

7.) If no, you have sucesfully iterate a polynomial with Bairstows Method.

But as always we only learn making an example, so here it is.

EXAMPLE:

With the polynomial f5(x) = x5 - 3.5x4 + 2.75x3 + 2.125x2 - 3.875x + 1.25, determine the r and s values who make the equation equal to zero. Consider r0 = -1 y s0 = 2.
First iteration.

The syntethic division with the polynomial f2(x) = x2 -x + 2.0 takes as result:

f3(x) = x3 - 4.5x2 + 9.25x - 16.125 Residue = {30.75, -61.75}

Applying the Newton method we have:

-43.875.......16.75......dr.....-30.75

108.125.......-43.87.....ds.....61.75


r1 = -1.0 + 2.7636812508572213 =1.7636812508572213

s1 = 2.0 + 5.403374022767796 =7.403374022767796

Second iteration.

The syntethic division with the polynomial f2(x) = x2 -1.7636812508572213x - 7.403374022767796 giva as result:

f3(x) = x3 - 1.7363187491427787x2 + 7.091061199392814x - 1.776754563401905

Residue = {51.75640698828836, 105.68578319650365}

Applying the Newton method we have:



27.628006.......14.542693.......dr.........-51.75640

208.148405......27.62800........ds.........-105.68578


From were

r2 = 1.7636812508572213 - 0.04728019113442016 = 1.7164010597228012

s2 = 7.403374022767796 - 3.469106187802152 = 3.934267834965644
The syntethic division with the polynomial f2(x)= x2 - 1.7164010597228012x - 3.934267834965644 give as result:

f3(x) = x3 - 1.7835989402771988x2 + 3.622896723753395x + 1.3261878347051992

Residue = {12.654716254544885, 28.1881465309956}

Applying the Newton method we have:



13.83497........7.44188.........dr........-12.65471

65.679212.......13.83497........ds........-28.18814



From were

r3 = 1.7164010597228012 - 0.11666951305731528 = 1.599731546665486

s3 = 3.934267834965644 - 1.4835870659929915 = 2.4506807689726524

In brief

k..................r...............s.....................Residuo

0.................-1...............2..................30.75......-61.75

1...............1.76368.........7.403374............51.75640.....105.68578

2...............1.71640.........3.93426.............12.65471.....28.18814

3...............1.599731........2.450680............2.89958......8.1546

4...............1.33354.........2.18666.............0.760122.....2.522228

5...............1.11826.........2.113020............0.271940.....0.607688

6...............1.02705.........2.02317.............0.04313......0.11185

7...............1.00165.........2.00153.............0.00277......0.00634

8...............1.00000.........2.00000.............1.13930E-5...2.67534E-5

The solution is:

f3(x) = x3 - 2.53x2 + 2.25x - 0.625 y f2(x) = x2 - x - 2

The roots of f2(x) = x2 - x - 2, are

x1 = 2

x2 = -1