Lin-Bairstow algorithm for Polynomial Roots

[Thomas Klemm]

(11C) Bairstow's Method explains the algorithm and gives an example.

Using Optimization to Extract Roots of Real Coefficient Polynomials is an older post by Namir with Matlab programs.
There are links to other algorithms, among them the Durand-Kerner method.

In an earlier thread I mentioned Polynomials for the HP-41 where you can find Quadratic factors which also uses Bairstow's method.

There I also mentioned an article in PRISMA, the magazine of the former CCD, where I first came across this method.

Thanks to Jürgen Keller and Martin Hepperle I finally found it in the collection of the PRISMA Zeitschriften 1982 – 1992:

• On page 84.4.27: Bairstow-Algorithmus.
• On page 84.2.18: "BSW" - BAIRSTOW-Verfahren.
• On page 85.2.13: Das Bairstow-Verfahren HP-15C/HP-41.
  

Recently Robert van Engelen wrote programs for both the Aberth method and the Weierstrass / Durand-Kerner method.

Example

\(P(x)=2x^5-9x^4+15x^3+65x^2-267x+234=0\)

Start the Program

Code:

XEQ "LINBST"

ORDER?
5
R/S

MAX ITERS?
10
R/S

TOLER%?
1E-5
R/S

Insert the Coefficients

Code:

A<0>?
234
R/S

A<1>?
-267
R/S

A<2>?
65
R/S

A<3>?
15
R/S

A<4>?
-9
R/S

A<5>?
2
R/S

Initialize the Guesses

Code:

R INIT?
1
R/S

S INIT?
1
R/S

Results

Code:

R1=2.00000
R/S

R2=1.50000
R/S

R1=2.00000
R/S

I1=3.00000
R/S

R2=2.00000
R/S

I2=-3.00000
R/S

R1=-3.00000
R/S

BEEP

Summary

Factors

\(2x^5-9x^4+15x^3+65x^2-267x+234=\)
\((x^2+1.5x-4.5)(x^2-4x+13)(2x-4)=\)
\((x-1.5)(x+3)(x^2-4x+13)2(x-2)=\)
\((2x-3)(x-2)(x+3)(x^2-4x+13)\)

Solutions

\(x_1=2\)
\(x_2=1.5\)
\(x_3=2+3i\)
\(x_5=2-3i\)
\(x_5=-3\)