A composite polynomial zerofinding matrix algorithm (Q1903777): Difference between revisions

A numerically well-founded matrix algorithm is presented for the calculation of the roots of a polynomial and its multiplicity. The companion matrices given by Frobenius, \textit{G. Schmeisser} [Linear Algebra Appl. 193, 11-18 (1993; Zbl 0793.15009)] and \textit{M. Fiedler} [ibid. 141, 265-270 (1990; Zbl 0721.15005)] are introduced and their properties discussed. A three-stage algorithm is presented for finding the common divisor of the polynomial and its derivative, computing the simple roots of the reduced polynomial using Schmeisser's or Fiedler's matrix, and calculating the multiplicity of each root by a numerically reasonable modification of \textit{J.-L. Lagouanelle's} limiting formula [C. R. Acad. Sci., Paris, Ser. A 262, 626-627 (1966; Zbl 0196.48103)]. A special treatment of small roots on account of their accuracy is proposed. Ten examples illustrate the power of the algorithm.