High-Order Predictor–Corrector Schemes for the Simultaneous Computation of Polynomial Roots with Known Multiplicities: Order Analysis and the Role of a Scalar-Derived Correction Factor

Source abstract

We study high-order predictor–corrector schemes for the simultaneous computation of polynomial roots with known multiplicities. The proposed method, BKM*, combines a fourth-order two-step modified Newton approximation, a coupled Ehrlich-type predictor of order six for multiple roots, and a final Gargantini–Farmer–Loizou correction. A local convergence analysis establishes a vector Q-order of at least eighteen, together with explicit leading error terms. The analysis is extended to a multiplicative correction factor applied to the final corrector: if the factor differs from one by O(εk), the local order is at least min(18,6+k). For a correction factor derived from a fifth-order scalar method, k=2, so the resulting weighted variant has an order of at least eight, and the weight reduces rather than increases the order. To isolate the role of the predictor, we also examine the composition of one PKM* step with the same corrector, which also has a local order of at least eighteen and requires fewer function evaluations per iteration. Experiments in 6000-digit arithmetic on polynomials of degrees 12, 20 and 21 confirm observed orders close to 18 and 8, and show that neither order-eighteen composition is uniformly faster: the composition with fewer function evaluations per iteration requires less computing time when both need the same number of iterations, whereas BKM* benefits from a more favourable pre-asymptotic phase from the more distant starting configurations.