Lin-Bairstow algorithm for Polynomial Roots

[Namir]

I have posted an HP41C implementation for the Lin-Bairstow algorithm that finds real and complex roots for real-coefficient polynomials. The program assumes that the current SIZE in the HP-41C is 100. The program has the following features:

1. The program handles polynomials up to order 19.
2. The program uses a default input scheme. The default input for coefficient A(0) is 1. The program stores any new input for the current coefficient A(i) as the default input for the next coefficient A(i+1). To use the default input value, simply press R/S key when prompted to enter the value of a polynomial coefficient.

The Excel .CSV and .XLSX files that I posted on my web site include the listing, registers table, and instructions. The .XLSX has color formatting of the code. Since the program is close to 400 steps, I am also including a .RAW file that you can load on the HP-41CX emulator that is available from TOS. This will save you a lot of time to input the listing and check the code.

To download the .CSV file click here. To download the .XLSX file click here. To download the .RAW file click here.

Enjoy!

Namir

[floppy]

Thanks for the contribution. Does it differ from other existing programs in modules? and what are the advantages or disadvantages?

[Namir]

(02-21-2022 11:53 AM)floppy Wrote:  Thanks for the contribution. Does it differ from other existing programs in modules? and what are the advantages or disadvantages?

I don't think I have seen the algorithm in any module. Someone correct me if I am wrong.

Namir

[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\)

[robve]

(02-21-2022 11:53 AM)floppy Wrote:  Thanks for the contribution. Does it differ from other existing programs in modules? and what are the advantages or disadvantages?

All methods have some pros and cons. The usual caveats apply to Bairstow: lacking convergence and being unstable for polynomials of degrees above 8 or 10 (depending on the implementation and fp precision). When the method appears to be stuck and diverges, one can try to reset/perturb the parameters to continue the search. This can be done automatically.

No method is immune to difficulties with higher degree polynomials and/or root multiplicities, see also Wilkinson's polynomial.

- Rob