(15C) Bairstow's Method

[Albert Chan]

(02-25-2022 01:20 AM)Thomas Klemm Wrote:  \(P(x) = Q(x) \cdot T(x) + R(x)\)

\(P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0\)

\(T(x) = x^2 + p x + q\)

\(Q(x) = b_n x^{n-2} + b_{n-1} x^{n-3} + \cdots + b_4 x^2 + b_3 x + b_2\)

\(R(x) = b_1 ( x + p ) + b_0\)

quo(P*x²,T) = Q*x² + quo(R*x²,T) = Q*x² + b₁*x + b₀

This get all the b's. Same idea to get all the c's
HP Prime code (note: index 1 = head of list, index 0 = end of list)

Code:

#cas // P,T = polynomial, test quadratic
bairstow(P,T)
BEGIN
LOCAL b,c;
b := quo(extend(P,[0,0]),T);
c := quo(append(b,0),T);
c := linsolve([c[-2..-1],c[-1..0]],b[-1..0]);
RETURN T + [0,c[2],c[1]];
END;
#end

Example from Gerald's "Applied Numerical Analysis", p33

CAS> [1,1,1] // guess T = x^2+x+1
CAS> bairstow([1,-1.1,2.3,0.5,3.3],Ans)
[1,0.890309886867,1.06345302509]
[1,0.900024696323,1.10016130857]
[1,0.899999998585,1.09999999975]
[1,0.9,1.1]