Lin-Bairstow algorithm for Polynomial Roots
02-16-2022, 12:56 PM
Post: #1 Namir Senior Member Posts: 850 Joined: Dec 2013
Lin-Bairstow algorithm for Polynomial Roots
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.

Enjoy!

Namir
02-21-2022, 11:53 AM
Post: #2
 floppy Member Posts: 153 Joined: Apr 2021
RE: Lin-Bairstow algorithm for Polynomial Roots
Thanks for the contribution. Does it differ from other existing programs in modules? and what are the advantages or disadvantages?

HP71 & Multimod, HP41CV/CX & Nov64d, PILBOX, HP-IL 821.62A & 64A & 66A, Debian11 64bits-PC & Raspb PI4 w/ ILPER, VIDEO80, V41R9F & EMU71
02-21-2022, 10:18 PM
Post: #3 Namir Senior Member Posts: 850 Joined: Dec 2013
RE: Lin-Bairstow algorithm for Polynomial Roots
(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
02-22-2022, 11:02 PM (This post was last modified: 03-02-2022 01:57 AM by Thomas Klemm.)
Post: #4
 Thomas Klemm Senior Member Posts: 1,814 Joined: Dec 2013
RE: Lin-Bairstow algorithm for Polynomial Roots
(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:

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$$
02-23-2022, 06:31 PM
Post: #5
 robve Senior Member Posts: 360 Joined: Sep 2020
RE: Lin-Bairstow algorithm for Polynomial Roots
(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

"I count on old friends" -- HP 71B,Prime|Ti VOY200,Nspire CXII CAS|Casio fx-CG50...|Sharp PC-G850,E500,2500,1500,14xx,13xx,12xx...
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)