On computational efficiency of the iterative methods for the simultaneous approximation of polynomial zeros

ABSTRACT

A measure of efficiency of simultaneous methods for determination of polynomial zeros, defined by the coefficient of efficiency, is considered. This coefficient takes into consideration (1) the R-order of convergence in the sense of the definition introduced by Ortega and Rheinboldt (Iterative Solution of Nonlinear Equations in Several Variables. Academic Press, New York, 1970) and (2) the number of basic arithmetic operations per iteration, taken with certain weights depending on a processor time. The introduced definition of computational efficiency was used for comparison of the simultaneous methods with various structures.

REFERENCES

• 1: ABERTH, O. Iteration methods for finding all zeros of a polynomial simultaneously. Math. Comput. 27 (1973), 339-344.
• 2: ALEFELD, G., AND HERZBERGER, J. On the convergence speed of some algorithms for the simultaneous approximation of polynomial roots. SIAM J. Numer. Anal. 11, 2 (1974), 237-243.
• 3: BORSCH-SUPAN, W. A posteriori error bounds for the zeros of polynomials. Numer. Math. 5, 4 ( 1963 ), 380-398.
• 4: BORSCH-SUPAN, W. Residuenabsch~itzung ffir PoIynom-Nullstellen mittels Lagrange- Interpolation. Numer. Math. 14, 3 (1970), 287-296.
• 5: DOPEY, K. Vidoizmenen metod na Newton za edinovremenno priblizitel'no presmyatane na vsichki koreni na dadeno algebrichno uravnenie. Fiz.-Mat. Spis. Bulgar. Akad. Nauk 5, 2 (1962), 136-139.
• 6: DURAND, E. Solution Numdriqi~e des Equations AlgSbraique (tome 1). Masson et Compagnie, Paris, 1960.
• 7: L. W. Ehrlich, A modified Newton method for polynomials, Communications of the ACM, v.10 n.2, p.107-108, Feb. 1967 [doi>10.1145/363067.363115]
• 8: KERNER, I.O. Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen. Numer. Math. 8, 3 (1966), 290-294.
• 9: LUBECK, O., MOORE, J., AND MENDEZ, R. A benchmark comparison of three supercomputers: Fujitsu VP-200, Hitachi $810/20, and Cray X-MP/2. Computer 18, 12 (1985), 10-24.
• 10: MAEHLY, H.J. Zur iterativen AuflSsung algebraischer Gleichungen. Z. Angew. Math. Phys. 5 {1954), 260-263.
• 11: MXLOVANOVI(~, G. V., AND PETKOVI(~, M.S. On the convergence order of a modified method for simultaneous finding polynomial zeros. Computing 30, 2 (1983), 171-178.
• 12: NOUREIN, A. W.M. An improvement on two iteration methods for simultaneous determination of the zeros of a polynomial. Int. J. Comput. Math. 6, 3 {1977), 241-252.
• 13: NOUREIN, A. W.M. An improvement on Nourein's method for the simultaneous determination of the zeroes of a polynomial (an algorithm). J. Cvmput. Appl. Math. 3, 2 (1977), 109-110.
• 14: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 15: OSTROWSKI, A. Solution of Eq~ations and Systems o{ Equations. Academic Press, New York, 1966.
• 16: PETKOVIC, M. S., AND MILOVANOVI(~, G.V. A note on some improvements of the simultaneous methods for determination of polynomial zeros. J. Comput. Appl. Math. 9, 1 (1983), 65-69.
• 17: TRAUB, J.F. Iterative Methods for the Solution of Equations. Prentice-Hall, Englewood Cliffs, N. J., 1964.
• 18: WEIERSTRASS, K. Neuer Bewei,~ des Satzes, dass jede Ganze Rationale Function einer Ver~inderlichen dargestellt werden kann als ein Product aus Linearen Functionen darselben Ver~,nderlichen. Ges. Werke 3 (1903), 251-269.

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Iterative methods

General Terms:
Measurement, Performance