One-parameter families of iterative methods for the simultaneous determination of multiple complex zeros of a polynomial are considered. Acceleration of convergence is performed by using Newton’s and Halley’s corrections for a multiple zero. It is shown that the convergence order of the constructed total-step methods is five and six, respectively. By applying the Gauss-Seidel approach, further improvements of these methods are obtained. The lower bounds of the $R$-order of convergence of the improved (single-step) methods are derived. Accelerated convergence of all proposed methods is attained with negligible number of additional operations, which provides a high computational efficiency of these methods. Convergence analysis and numerical results are given.