Graeffe's root squaring method

[Albert Chan]

11-18-2022, 12:42 PM

Werner Wrote:- the Graeffe squaring process quickly overflows; in this case, you obtained 12+ digits of the correct answer - but you cannot know that unless you performed one or more additional steps, which would overflow. I tried it out with smaller degrees (in excel..) and I could only confirm about 6 digits before overflow. And then remains the Newton-Rhapson step to refine the value, but all I have is the abs value, not the estimate of the root, so I have n possible complex roots to verfiy. The link to Cleve Moler's article says just that. (thanks for that link BTW!)

P(x) = 2 + 3x + 5x^2 + 7x^3 + 11x^4 + ...

All P roots inside complex unit circle.

We can assume min root real part closer to -1 than +1, to keep imag part small.
Root squaring process gives min abs root ≈ 0.8, so I would first try x = 0.8*cis(3/4*pi ≈ 2.36)

CAS> p := makelist(ithprime, 148+1,1,-1) :;
CAS> f := horner(p, x) :;
CAS> newton(f, x = 0.8*exp (3/4*pi*i))

−0.645758096347+0.483177676218*i

CAS> polar(Ans)

[0.806513599261, 2.49922322693]

Magnitude matched root squaring produced min --> this (and its conjugate) is the root to seek.