A Shamanskiĭ-like acceleration scheme for nonlinear equations at singular roots

Kelley, C. T.

doi:10.1090/S0025-5718-1986-0856706-4

A Shamanskiĭ-like acceleration scheme for nonlinear equations at singular roots
HTML articles powered by AMS MathViewer

by C. T. Kelley PDF

Math. Comp. 47 (1986), 609-623 Request permission

Abstract:

A variation of the Shamanskii method is used to obtain a superlinearly convergent method for a class of nonlinear equations having singular Fréchet derivative at the root. The cost of a superlinear step is one derivative evaluation and two function evaluations.

References

Richard P. Brent, Some efficient algorithms for solving systems of nonlinear equations, SIAM J. Numer. Anal. 10 (1973), 327–344. MR 331764, DOI 10.1137/0710031

Difference Equations and Iterative Processes

S. Chandrasekhar, Radiative transfer, Dover Publications, Inc., New York, 1960. MR 0111583
D. W. Decker and C. T. Kelley, Newton’s method at singular points. I, SIAM J. Numer. Anal. 17 (1980), no. 1, 66–70. MR 559463, DOI 10.1137/0717009
D. W. Decker and C. T. Kelley, Newton’s method at singular points. I, SIAM J. Numer. Anal. 17 (1980), no. 1, 66–70. MR 559463, DOI 10.1137/0717009
D. W. Decker and C. T. Kelley, Convergence acceleration for Newton’s method at singular points, SIAM J. Numer. Anal. 19 (1982), no. 1, 219–229. MR 646604, DOI 10.1137/0719012
D. W. Decker, H. B. Keller, and C. T. Kelley, Convergence rates for Newton’s method at singular points, SIAM J. Numer. Anal. 20 (1983), no. 2, 296–314. MR 694520, DOI 10.1137/0720020
D. W. Decker and C. T. Kelley, Sublinear convergence of the chord method at singular points, Numer. Math. 42 (1983), no. 2, 147–154. MR 720655, DOI 10.1007/BF01395307
D. W. Decker and C. T. Kelley, Expanded convergence domains for Newton’s method at nearly singular roots, SIAM J. Sci. Statist. Comput. 6 (1985), no. 4, 951–966. MR 801183, DOI 10.1137/0906064

Numerical Methods for Nonlinear Equations and Unconstrained Optimization

Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103

Analysis and Modification of Newton’s Method at Singularities

A. O. Griewank, Starlike domains of convergence for Newton’s method at singularities, Numer. Math. 35 (1980), no. 1, 95–111. MR 583659, DOI 10.1007/BF01396373
Andreas Griewank and M. R. Osborne, Newton’s method for singular problems when the dimension of the null space is $>1$, SIAM J. Numer. Anal. 18 (1981), no. 1, 145–149. MR 603436, DOI 10.1137/0718011
A. Griewank and M. R. Osborne, Analysis of Newton’s method at irregular singularities, SIAM J. Numer. Anal. 20 (1983), no. 4, 747–773. MR 708455, DOI 10.1137/0720050
A. Griewank, On solving nonlinear equations with simple singularities or nearly singular solutions, SIAM Rev. 27 (1985), no. 4, 537–563. MR 812453, DOI 10.1137/1027141
L. V. Kantorovich and G. P. Akilov, Functional analysis in normed spaces, International Series of Monographs in Pure and Applied Mathematics, Vol. 46, The Macmillan Company, New York, 1964. Translated from the Russian by D. E. Brown; Edited by A. P. Robertson. MR 0213845
Herbert B. Keller, Geometrically isolated nonisolated solutions and their approximation, SIAM J. Numer. Anal. 18 (1981), no. 5, 822–838. MR 629667, DOI 10.1137/0718056
C. T. Kelley, Solution of the Chandrasekhar $H$-equation by Newton’s method, J. Math. Phys. 21 (1980), no. 7, 1625–1628. MR 575595, DOI 10.1063/1.524647
C. T. Kelley, Approximate methods for the solution of the Chandrasekhar $H$-equation, J. Math. Phys. 23 (1982), no. 11, 2097–2100. MR 680006, DOI 10.1063/1.525251
C. T. Kelley and R. Suresh, A new acceleration method for Newton’s method at singular points, SIAM J. Numer. Anal. 20 (1983), no. 5, 1001–1009. MR 714695, DOI 10.1137/0720070
T. W. Mullikin, Some probability distributions for neutron transport in a half-space, J. Appl. Probability 5 (1968), 357–374. MR 235626, DOI 10.1017/s0021900200110058
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
L. B. Rall, Convergence of the Newton process to multiple solutions, Numer. Math. 9 (1966), 23–37. MR 210316, DOI 10.1007/BF02165226

Rates of Convergence of Newton’s method

G. W. Reddien, On Newton’s method for singular problems, SIAM J. Numer. Anal. 15 (1978), no. 5, 993–996. MR 507559, DOI 10.1137/0715064
G. W. Reddien, Newton’s method and high order singularities, Comput. Math. Appl. 5 (1979), no. 2, 79–86. MR 539566, DOI 10.1016/0898-1221(79)90061-0
V. E. Šamanskiĭ, On a modification of the Newton method, Ukrain. Mat. Ž. 19 (1967), no. 1, 133–138 (Russian). MR 0205451

Conic Methods for Unconstrained Minimization Problems and Tensor Methods for Nonlinear Equations

Robert B. Schnabel and Paul D. Frank, Tensor methods for nonlinear equations, SIAM J. Numer. Anal. 21 (1984), no. 5, 815–843. MR 760620, DOI 10.1137/0721054
E. Schröder, Ueber unendlich viele Algorithmen zur Auflösung der Gleichungen, Math. Ann. 2 (1870), no. 2, 317–365 (German). MR 1509664, DOI 10.1007/BF01444024
J. F. Traub, Iterative methods for the solution of equations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR 0169356