LinBairstow algorithm for Polynomial Roots

02162022, 12:56 PM
Post: #1




LinBairstow algorithm for Polynomial Roots
I have posted an HP41C implementation for the LinBairstow algorithm that finds real and complex roots for realcoefficient polynomials. The program assumes that the current SIZE in the HP41C 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 HP41CX 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 

02212022, 11:53 AM
Post: #2




RE: LinBairstow 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, HPIL 821.62A & 64A & 66A, Debian11 64bitsPC & Raspb PI4 w/ ILPER, VIDEO80, V41R9F & EMU71 

02212022, 10:18 PM
Post: #3




RE: LinBairstow algorithm for Polynomial Roots  
02222022, 11:02 PM
(This post was last modified: 03022022 01:57 AM by Thomas Klemm.)
Post: #4




RE: LinBairstow 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 DurandKerner method. In an earlier thread I mentioned Polynomials for the HP41 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 / DurandKerner method. Example \(P(x)=2x^59x^4+15x^3+65x^2267x+234=0\) Start the Program Code: XEQ "LINBST" Insert the Coefficients Code: A<0>? Initialize the Guesses Code: R INIT? Results Code: R1=2.00000 Summary Factors \(2x^59x^4+15x^3+65x^2267x+234=\) \((x^2+1.5x4.5)(x^24x+13)(2x4)=\) \((x1.5)(x+3)(x^24x+13)2(x2)=\) \((2x3)(x2)(x+3)(x^24x+13)\) Solutions \(x_1=2\) \(x_2=1.5\) \(x_3=2+3i\) \(x_5=23i\) \(x_5=3\) 

02232022, 06:31 PM
Post: #5




RE: LinBairstow algorithm for Polynomial Roots
(02212022 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,PrimeTi VOY200,Nspire CXII CASCasio fxCG50...Sharp PCG850,E500,2500,1500,14xx,13xx,12xx... 

« Next Oldest  Next Newest »

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