Majorizing sequences and error bounds for iterative methods
Author:
George J. Miel
Journal:
Math. Comp. 34 (1980), 185202
MSC:
Primary 65J05; Secondary 47H10
MathSciNet review:
551297
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Given a sequence in a Banach space, it is well known that if there is a sequence such that and , then converges to some and the error bounds hold. It is shown that certain stronger hypotheses imply sharper error bounds, Representative applications to infinite series and to iterates of types and are given for . Error estimates with 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 for a class of Newtontype methods, and these bounds are shown to be optimal for a subclass of methods. Practical limitations of the error bounds are described.
 [1]
J.
E. Dennis Jr., Toward a unified convergence theory for Newtonlike
methods, Nonlinear Functional Anal. and Appl. (Proc. Advanced Sem.,
Math. Res. Center, Univ. of Wisconsin, Madison, Wis., 1970) Academic
Press, New York, 1971, pp. 425–472. MR 0278556
(43 #4286)
 [2]
J.
E. Dennis Jr., A brief introduction to quasiNewton methods,
Numerical analysis (Proc. Sympos. Appl. Math., Atlanta, Ga., 1978), Proc.
Sympos. Appl. Math., XXII, Amer. Math. Soc., Providence, R.I., 1978,
pp. 19–52. MR 533049
(80d:65003)
 [3]
J.
E. Dennis Jr. and Jorge
J. Moré, A characterization of superlinear
convergence and its application to quasiNewton methods, Math. Comp. 28 (1974), 549–560. MR 0343581
(49 #8322), http://dx.doi.org/10.1090/S00255718197403435811
 [4]
J.
E. Dennis Jr. and Jorge
J. Moré, QuasiNewton methods, motivation and theory,
SIAM Rev. 19 (1977), no. 1, 46–89. MR 0445812
(56 #4146)
 [5]
W.
B. Gragg and R.
A. Tapia, Optimal error bounds for the NewtonKantorovich
theorem, SIAM J. Numer. Anal. 11 (1974), 10–13.
MR
0343594 (49 #8334)
 [6]
Harris
Hancock, Elliptic integrals, Dover Publications, Inc., New
York, 1958. MR
0099454 (20 #5893)
 [7]
L.
V. Kantorovič, Functional analysis and applied
mathematics, Uspehi Matem. Nauk (N.S.) 3 (1948),
no. 6(28), 89–185 (Russian). MR 0027947
(10,380a)
 [8]
K. KNOPP, Theory and Application of Infinite Series, Blackie & Son Ltd., London and Glasgow, 1928.
 [9]
N.
S. Kurpel′, Projectioniterative methods for solution of
operator equations, American Mathematical Society, Providence, R. I.,
1976. Translated from the Russian; Translations of Mathematical Monographs,
Vol. 46. MR
0405140 (53 #8935)
 [10]
P.
Lancaster, Error analysis for the NewtonRaphson method,
Numer. Math. 9 (1966), 55–68. MR 0210315
(35 #1208)
 [11]
George
Miel, On a posteriori error
estimates, Math. Comp. 31
(1977), no. 137, 204–213. MR 0426418
(54 #14361), http://dx.doi.org/10.1090/S00255718197704264184
 [12]
George
J. Miel, Cones and error bounds for linear iterations,
Aequationes Math. 20 (1980), no. 23, 170–183.
MR 577486
(81i:47040), http://dx.doi.org/10.1007/BF02190512
 [13]
G.
J. Miel, The Kantorovich theorem with optimal error bounds,
Amer. Math. Monthly 86 (1979), no. 3, 212–215.
MR 522348
(80c:65109), http://dx.doi.org/10.2307/2321528
 [14]
G. J. MIEL, Exit Criteria for NewtonType Iterations, Research Paper No. 363, Dept. of Math. and Stat., Univ. of Calgary, 1977.
 [15]
George
J. Miel, Unified error analysis for Newtontype methods,
Numer. Math. 33 (1979), no. 4, 391–396. MR 553349
(81m:65095), http://dx.doi.org/10.1007/BF01399322
 [16]
James
M. Ortega, The NewtonKantorovich theorem, Amer. Math. Monthly
75 (1968), 658–660. MR 0231218
(37 #6773)
 [17]
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 [18]
Alexandre
Ostrowski, La méthode de Newton dans les espaces de
Banach, C. R. Acad. Sci. Paris Sér. AB 272
(1971), A1251–A1253. MR 0285110
(44 #2334)
 [19]
L.
B. Rall, Quadratic equations in Banach spaces, Rend. Circ.
Mat. Palermo (2) 10 (1961), 314–332. MR 0144184
(26 #1731)
 [20]
Louis
B. Rall, Computational solution of nonlinear operator
equations, With an appendix by Ramon E. Moore, John Wiley & Sons,
Inc., New YorkLondonSydney, 1969. MR 0240944
(39 #2289)
 [21]
L.
B. Rall, A note on the convergence of Newton’s method,
SIAM J. Numer. Anal. 11 (1974), 34–36. MR 0343599
(49 #8339)
 [22]
Werner
C. Rheinboldt, A unified convergence theory for a class of
iterative processes, SIAM J. Numer. Anal. 5 (1968),
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. 401412.
 [24]
Andrew
H. Sherman, On Newtoniterative methods for the solution of systems
of nonlinear equations, SIAM J. Numer. Anal. 15
(1978), no. 4, 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. 852855. (Ukrainian)
 [1]
 J. E. DENNIS, "Toward a unified convergence theory for Newtonlike 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 quasiNewton 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 quasiNewton methods," Math. Comp., v. 28, 1974, pp. 549560. MR 0343581 (49:8322)
 [4]
 J. E. DENNIS & J. J. MORÉ, "QuasiNewton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 4689. MR 0445812 (56:4146)
 [5]
 W. B. GRAGG & R. A. TAPIA, "Optimal error bounds for the NewtonKantorovich theorem," SIAM J. Numer. Anal., v. 11, 1974, pp. 1013. 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. 89185 (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', ProjectionIterative 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 NewtonRaphson method," Numer. Math., v. 9, 1966, pp. 5568. MR 0210315 (35:1208)
 [11]
 G. J. MIEL, "On a posteriori error estimates," Math. Comp., v. 31, 1977, pp. 204213. 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. 212215. MR 522348 (80c:65109)
 [14]
 G. J. MIEL, Exit Criteria for NewtonType Iterations, Research Paper No. 363, Dept. of Math. and Stat., Univ. of Calgary, 1977.
 [15]
 G. J. MIEL, "Unified error analysis for Newtontype methods," Numer. Math. (To appear.) MR 553349 (81m:65095)
 [16]
 J. M. ORTEGA, "The NewtonKantorovich theorem," Amer. Math. Monthly, v. 75, 1968, pp. 658660. 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. 12511253. MR 0285110 (44:2334)
 [19]
 L. B. RALL, "Quadratic equations in Banach spaces," Rend. Circ. Mat. Palermo, v. 10, 1961, pp. 314332. 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. 3436. 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. 4263. MR 0225468 (37:1061)
 [23]
 J. ROCKNE, "Newton's method under mild differentiability conditions with error analysis," Numer. Math., v. 18, 1972, pp. 401412.
 [24]
 A. H. SHERMAN, "On Newtoniterative methods for the solution of systems of nonlinear equations," SIAM J. Numer. Anal., v. 15, 1978, pp. 755771. 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. 852855. (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:
http://dx.doi.org/10.1090/S00255718198005512974
PII:
S 00255718(1980)05512974
Keywords:
Majorizing sequences,
iterative methods,
exit criteria
Article copyright:
© Copyright 1980
American Mathematical Society
