On the superlinear convergence of the successive approximations method

Abstract

The Ostrowski theorem is a classical result which ensures the attraction of all the successive approximations xk+1 = G(xk) near a fixed point x*. Different conditions [ultimately on the magnitude of G′(x*)] provide lower bounds for the convergence order of the process as a whole.

In this paper, we consider only one such sequence and we characterize its high q-convergence orders in terms of some spectral elements of G′(x*); we obtain that the set of trajectories with high q-convergence orders is restricted to some affine subspaces, regardless of the nonlinearity of G.

We analyze also the stability of the successive approximations under perturbation assumptions.

Authors

Emil Cătinaş
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)

Keywords

fixed point; successive approximations; nonlinear system of equations in Rn; inexact Newton method; perturbed Newton method; linear systems of equation in Rn; residual; local convergence; q-convergence orders.

Cite this paper as:

E. Cătinaş, On the superlinear convergence of the successive approximations method, J. Optim. Theory Appl., 113 (2002) no. 3, pp. 473-485
doi: 10.1023/A:1015304720071

PDF

Scanned paper.

Latex-pdf version of the paper.

About this paper

Publisher Name

Kluwer Academic Publishers-Plenum Publishers

Print ISSN

0022-3239

Online ISSN

1573-2878

MR

0022-3239

Online ISSN

1573-2878

Google Scholar citations

[1] Ortega, J. M., and Rheinboldt, W. C., Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, NY, 1970. 484 JOTA: VOL. 113, NO. 3, JUNE 2002

[2] Potra, F. A., On Q-Order and R-Order of Convergence, Journal of Optimization Theory and Applications, Vol. 63, pp. 415–431, 1989.

[3] Rheinboldt, W. C., Methods for Solûing Systems of Nonlinear Equations, SIAM, Philadelphia, Pennsylvania, 1998.

[4] Potra, F. A., Q-Superlinear Convergence of the Iterates in Primal–Dual InteriorPoint Methods, Mathematical Programming (to appear).

[5] Ostrowski, A. M., Solution of Equations and Systems of Equations, Academic Press, New York, NY, 1966.

[6] Householder, A. S., The Theory of Matrices in Numerical Analysis, Dover, New York, NY, 1974.

[7] Argyros, I., and Szidarovszky, F., The Theory and Applications of Iteration Methods, CRC Press, Boca Raton, Florida, 1993.

[8] Argyros, I., On the Convergence of the Modified Contractions, Journal of Computational and Applied Mathematics, Vol. 55, pp. 183–189, 1994.

[9] Brown, P. N., A Local Convergence Theory for Combined Inexact-Newton Finite-Difference Projection Methods, SIAM Journal on Numerical Analysis, Vol. 24, pp. 407–434, 1987.

[10] Brown, P. N., and Saad, Y., Convergence Theory of Nonlinear Newton–Krylov Algorithms, SIAM Journal on Optimization, Vol. 4, pp. 297–330, 1994.

[11] Catinas, E., Newton and Newton–Krylov Methods for Solving Nonlinear Systems in n , PhD Thesis, Babes–Bolyai University of Cluj–Napoca, Cluj– Napoca, Romania, 1999.

[12] Catinas, E., On the High Convergence Orders of the Newton–GMBACK Methods, Revue d’Analyse Numerique et de Theorie de l’Approximation, Vol. 28, pp. 125–132, 1999.

[13] Catinas, E., A Note on the Quadratic Convergence of the Inexact Newton Methods, Revue d’Analyse Numerique et de Theorie de l’Approximation, Vol. 29, pp. 129–134, 2000.

[14] Catinas, E., Inexact Perturbed Newton Methods and Applications to a Class of Krylov Solvers, Journal of Optimization Theory and Applications, Vol. 108, pp. 543–570, 2001.

[15] Catinas, E., The Inexact, Inexact Perturbed, and Quasi-Newton Methods are Equivalent Models, Mathematics of Computation (to appear).

[16] Dembo, R. S., Eisenstat, S. C., and Steihaug, T., Inexact Newton Methods, SIAM Journal on Numerical Analysis, Vol. 19, pp. 400–408, 1982.

[17] DENNIS, J. E., JR., and MORE´ , J. J., A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods, Mathematics of Computation, Vol. 28, pp. 549–560, 1974.

[18] Dennis, J. E., JR., and More , J. J., Quasi-Newton Methods, Motivation and Theory, SIAM Review, Vol. 19, pp. 46–89, 1977.

[19] Dennis, J. E., JR., and Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Series in Computational Mathematics, Prentice-Hall, Englewood Cliffs, New Jersey, 1983.

[20] Deuflhard, P., and Potra, F. A., Asymptotic Mesh Independence of Newton– Galerkin Methods via a Refined Mysovskii Theorem, SIAM Journal on Numerical Analysis, Vol. 29, pp. 1395–1412, 1992.

2002

Related Posts