Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

Majorizing sequences and error bounds for iterative methods


Author: George J. Miel
Journal: Math. Comp. 34 (1980), 185-202
MSC: Primary 65J05; Secondary 47H10
MathSciNet review: 551297
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given a sequence $ \{ {x_n}\} _{n = 0}^\infty $ in a Banach space, it is well known that if there is a sequence $ \{ {t_n}\} _{n = 0}^\infty $ such that $ \left\Vert {{x_{n + 1}} - {x_n}} \right\Vert \leqslant {t_{n + 1}} - {t_n}$ and $ \lim {t_n} = {t^\ast} < \infty $, then $ \{ {x_n}\} _{n = 0}^\infty $ converges to some $ {x^\ast}$ and the error bounds $ \left\Vert {{x^\ast} - {x_n}} \right\Vert \leqslant {t^\ast} - {t_n}$ hold. It is shown that certain stronger hypotheses imply sharper error bounds,

$\displaystyle \left\Vert {{x^\ast} - {x_n}} \right\Vert \leqslant \frac{{{t^\as... ...})}^\mu }}}{\left\Vert {{x_1} - {x_0}} \right\Vert^\mu },\quad \mu \geqslant 0.$

Representative applications to infinite series and to iterates of types $ {x_n} = G{x_{n - 1}}$ and $ {x_n} = H({x_n},{x_{n - 1}})$ are given for $ \mu = 1$. Error estimates with $ 0 \leqslant \mu \leqslant 2$ are shown to be valid and optimal for Newton iterates under the hypotheses of the Kantorovich theorem. The unified convergence theory of Rheinboldt is used to derive error bounds with $ 0 \leqslant \mu \leqslant 1$ for a class of Newton-type methods, and these bounds are shown to be optimal for a subclass of methods. Practical limitations of the error bounds are described.

References [Enhancements On Off] (What's this?)

  • [1] J. E. DENNIS, "Toward a unified convergence theory for Newton-like methods," Nonlinear Functional Analysis and Applications (L. B. Rail, Ed.), Academic Press, New York, 1971. MR 0278556 (43:4286)
  • [2] J. E. DENNIS, "A brief introduction to quasi-Newton methods," Numerical Analysis (G. H. Golub and J. Oliger, Eds.), Proc. Sympos. Appl. Math., vol. 22, Amer. Math. Soc., Providence, R. I., 1978. MR 533049 (80d:65003)
  • [3] J. E. DENNIS & J. J. MORÉ, "A characterization of superlinear convergence and its application to quasi-Newton methods," Math. Comp., v. 28, 1974, pp. 549-560. MR 0343581 (49:8322)
  • [4] J. E. DENNIS & J. J. MORÉ, "Quasi-Newton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 46-89. MR 0445812 (56:4146)
  • [5] W. B. GRAGG & R. A. TAPIA, "Optimal error bounds for the Newton-Kantorovich theorem," SIAM J. Numer. Anal., v. 11, 1974, pp. 10-13. MR 0343594 (49:8334)
  • [6] H. HANCOCK, Elliptic Integrals, Dover, New York, 1958. MR 0099454 (20:5893)
  • [7] L. V. KANTOROVICH, "Functional analysis and applied mathematics," Uspehi Mat. Nauk, v. 3, 1948, pp. 89-185 (Russian); English transl., Rep. 1509, National Bureau of Standards, Washington, D. C., 1952. MR 0027947 (10:380a)
  • [8] K. KNOPP, Theory and Application of Infinite Series, Blackie & Son Ltd., London and Glasgow, 1928.
  • [9] N. S. KURPEL', Projection-Iterative Methods for Solution of Operator Equations, Transl. Math. Monographs, vol. 46, Amer. Math. Soc., Providence, R. I., 1976. MR 0405140 (53:8935)
  • [10] P. LANCASTER, "Error analysis for the Newton-Raphson method," Numer. Math., v. 9, 1966, pp. 55-68. MR 0210315 (35:1208)
  • [11] G. J. MIEL, "On a posteriori error estimates," Math. Comp., v. 31, 1977, pp. 204-213. MR 0426418 (54:14361)
  • [12] G. J. MIEL, "Cones and error bounds for linear iterations," Aequationes Math. (To appear.) MR 577486 (81i:47040)
  • [13] G. J. MIEL, "The Kantorovich theorem with optimal error bounds," Amer. Math. Monthly, v. 86, 1979, pp. 212-215. MR 522348 (80c:65109)
  • [14] G. J. MIEL, Exit Criteria for Newton-Type Iterations, Research Paper No. 363, Dept. of Math. and Stat., Univ. of Calgary, 1977.
  • [15] G. J. MIEL, "Unified error analysis for Newton-type methods," Numer. Math. (To appear.) MR 553349 (81m:65095)
  • [16] J. M. ORTEGA, "The Newton-Kantorovich theorem," Amer. Math. Monthly, v. 75, 1968, pp. 658-660. MR 0231218 (37:6773)
  • [17] J. M. ORTEGA & W. C. RHEINBOLDT, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 0273810 (42:8686)
  • [18] A. M. OSTROWSKI, "La méthode de Newton dans les espaces de Banach," C. R. Acad. Sci. Paris Sér. A., v. 272, 1971, pp. 1251-1253. MR 0285110 (44:2334)
  • [19] L. B. RALL, "Quadratic equations in Banach spaces," Rend. Circ. Mat. Palermo, v. 10, 1961, pp. 314-332. MR 0144184 (26:1731)
  • [20] L. B. RALL, Computational Solution of Nonlinear Operator Equations, Wiley, New York, 1969. MR 0240944 (39:2289)
  • [21] L. B. RALL, "A note on the convergence of Newton's method," SIAM J. Numer. Anal., v. 11, 1974, pp. 34-36. MR 0343599 (49:8339)
  • [22] W. C. RHEINBOLDT, "A unified convergence theory for a class of iterative processes," SIAM J. Numer. Anal., v. 5, 1968, pp. 42-63. MR 0225468 (37:1061)
  • [23] J. ROCKNE, "Newton's method under mild differentiability conditions with error analysis," Numer. Math., v. 18, 1972, pp. 401-412.
  • [24] A. H. SHERMAN, "On Newton-iterative methods for the solution of systems of nonlinear equations," SIAM J. Numer. Anal., v. 15, 1978, pp. 755-771. MR 0483382 (58:3388)
  • [25] A. I. ZINČENKO, "A class of approximate methods for solving operator equations with nondifferentiable operators," Dopovīdī Akad. Nauk Ukrdïn. RSR, 1963, pp. 852-855. (Ukrainian)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65J05, 47H10

Retrieve articles in all journals with MSC: 65J05, 47H10


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1980-0551297-4
Keywords: Majorizing sequences, iterative methods, exit criteria
Article copyright: © Copyright 1980 American Mathematical Society