Optimal Order of One-Point and Multipoint Iteration

ABSTRACT

The problem is to calculate a simple zero of a nonlinear function ƒ by iteration. There is exhibited a family of iterations of order 2n-1 which use n evaluations of ƒ and no derivative evaluations, as well as a second family of iterations of order 2n-1 based on n — 1 evaluations of ƒ and one of ƒ′. In particular, with four evaluations an iteration of eighth order is constructed. The best previous result for four evaluations was fifth order. It is proved that the optimal order of one general class of multipoint iterations is 2n-1 and that an upper bound on the order of a multipoint iteration based on n evaluations of ƒ (no derivatives) is 2n. It is conjectured that a multipoint iteration without memory based on n evaluations has optimal order 2n-1.

REFERENCES

• 1: BRENT, R., WINOGRAD, S., AND WOLFE, P. Optimal iterative processes for root-finding. Numer. Math. ~0 (1973), 327-341.
• 2: JARaATT, P. Some efficient fourth order multipoint methods for solving equations. BIT 9 (1969), 119-124.
• 3: KING, R.R. A family of fourth-order methods for nonlinear equations. SIAM J. Numer. Anal. 10 (1973), 876-879.
• 4: KROGH, F.T. Efficient algorithms for polynomial interpolation and numerical differentiation. Math. Comp. 2~ (1970), 185-190.
• 5: KUNG, H. T., ASh TR~UB, J.F. Computational complexity of one-point and multipoint iteration. Report, Computer Sci. Dep., Carnegie-Mellon U., Pittsburgh, Pa. To appear in Complexity of Real Computation, R. Karp, Ed., American Mathematical Society, Providence, R. I.
• 6: KUNG, H. T., AND TRXUB, J.F. Optimal order for iterations using two evaluations. Report, Computer Sci. Dep., Carnegie-Mellon U., Pittsburgh, Pa., 1973. To appear in SIAM J. Numev. Anal.
• 7: James M. Ortega , Werner C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 8: OSTROWSKI, A.M. Solution of Equations and Systems of Equations, 2nd ed. Academic Press, New York, 1966.
• 9: J. F. Traub, On functional iteration and the calculation of roots, Proceedings of the 1961 16th ACM national meeting, p.51.101-51.104, January 1961 [doi>10.1145/800029.808506]
• 10: TRAUB, J.F. Iterative Methods for the Solution of Equations. Prentice-Hall, Englewood Cliffs, N. J., 1964.
• 11: TRAUB, J. F. Computational complexity of iterative processes. SIAM J. Comput. 1 (1972), 167-179.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms, Measurement, Performance, Theory, Verification