Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T11:36:31.815Z Has data issue: false hasContentIssue false
  • English
  • Français

Fast local convergence with single and multistep methods for nonlinear equations

Published online by Cambridge University Press:  17 February 2009

James P. Abbott  and
Richard P. Brent
Richard P. Brent
Affiliation:
Computer Centre, Australian National University, Canberra 2600, Australia.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Methods which make use of the differential equation ẋ(t) = −J(x)−1f(x), where J(x) is the Jacobian of f(x), have recently been proposed for solving the system of nonlinear equations f(x) = 0. These methods are important because of their improved convergence characteristics. Under general conditions the solution trajectory of the differential equation converges to a root of f and the problem becomes one of solving a differential equation. In this paper we note that the special form of the differential equation can be used to derive single and multistep methods which give improved rates of local convergence to a root.

Type
Research Article
Information
The ANZIAM Journal , Volume 19 , Issue 2 , December 1975 , pp. 173 - 199
Copyright
Copyright © Australian Mathematical Society 1975

References

[1]Avila, J. H., Continuation methods for nonlinear equation, (Ph.D. Thesis Computer Science Center, University of Maryland, 1971).Google Scholar
[2]Bittner, L., ‘Einige kontinuierliche Analogien von Iterationsverfahren, in Functionalanalysis, Approximationstheorie Numerische Mathematik, ISNM7, (Birkhauser Verlag, Basel), (1967),114–135.Google Scholar
[3]Boggs, P. T., The solution of nonlinear operator equations by A-stable integration techniques, (Ph.D. Thesis, Cornell University, 1970).Google Scholar
[4]Boggs, P. T., ‘The solution of nonlinear systems of equations by A-stable integration techniques’, SIAM J. Numer. Anal. 8 (1971),767–785.CrossRefGoogle Scholar
[5]Branin, F. H. Jr, ‘Widely convergent method for finding multiple solutions of simultaneous nonlinear equations’, IBM J. Rex. Develop. 16 (1972),504–522.CrossRefGoogle Scholar
[6]Broyden, C. G., ‘A new method of solving nonlinear simultaneous equations’, Comput. J., 12 (1969),94–99.CrossRefGoogle Scholar
[7]Chao, K. S., Liu, D. K. and Pan, C. T., A systematic search method for obtaining multiple solutions of simultaneous nonlinear equations, IEEE Transactions on Circuits and Systems, Vol. CAS-22, 9, 09 1975.Google Scholar
[8]Dahiquist, G. G., ‘A special stability problem for linear multistep methods’, BIT 3 (1963),27–43.CrossRefGoogle Scholar
[9]Davidenko, D. F., ‘On a new method of numerical solution of systems of nonlinear equations’, Dokl. Akad. Nauk, USSR (N.S.) 88 (1953),601–602.Google Scholar
[10]Deist, F. H. and Sefor, L., ‘Solution of systems of nonlinear equations by parameter variation’, Comput. J. 10 (1967),78–82.CrossRefGoogle Scholar
[11]Deuflhard, P., ‘A modified Newton method for the solution of ill-conditioned systems of nonlinear equations with application to multiple shooting’, Numer. Math. 22 (1974), 289–315.CrossRefGoogle Scholar
[12]Gavurin, M. K., ‘Nonlinear functional equations and continuous analogs of iterative methods’, Izv. Vyss. Ucebn. Saved. Mathematika 6 (1958),18–31;Google Scholar
English Transl., Tech. Rep. 68–70, Computer Science Center, Univ. of Maryland, 1968.Google Scholar
[13]Gear, C. W., Numerical initial value problems in ordinary differential equations, (PrenticeHall, Englewood Cliffs, N.J. 1971).Google Scholar
[14]Gear, C. W. and Tu, K. W., ‘The effect of variable mesh size on the stability of multistep methods’, SIAMJ. Numer. Anal. 11 (1974),1025–1043.CrossRefGoogle Scholar
[15]Gear, C. W. and Watanabe, D. S., ‘Stability and convergence of variable order multistep methods’, SIAM J. Numer. Anal. 11 (1974),1044–1058.CrossRefGoogle Scholar
[16]Hale, J. K., Ordinary differential equations, (Wiley-Interscience, N.Y., 1969).Google Scholar
[17]Henrici, P., Discrete variable methods for ordinary differential equations, (John Wiley, N.Y. 1962).Google Scholar
[18]Kizner, W., ‘A numerical method for finding solutions of nonlinear equations’, SIAM J. Appl. Math. 12 (1964),424–428.CrossRefGoogle Scholar
[19]Kleinmichel, H., ‘Stetige Analoga und lterationsverfahren für nichtlineare Gleichungen in Banachräumen’, Math. Nachr. 37 (1968),313–344.CrossRefGoogle Scholar
[20]Lasalle, L. and Lefshetz, S., Stability by Liapunov's direct method with applications, (Academic Press, N.Y. 1961).Google Scholar
[21]Lawson, J. D., ‘An order five Runge-Kutta process with extended region of stability’, SIAM J. Numer. Anal. 3 (1966),593–597.CrossRefGoogle Scholar
[22]Meyer, G. H., ‘On solving nonlinear equations with a one parameter operator embedding’, SIAM J. Numer. Anal. 4 (1968),739–752.CrossRefGoogle Scholar
[23]Nordsieck, A., ‘On the numerical integration of ordinary differential equations’, Maths. Comp. 16 (1962),22–49.CrossRefGoogle Scholar
[24]Ortega, J. and Rheinboldt, W., Iterative solution of nonlinear equations in several variables, (Academic Press, N.Y., 1970).Google Scholar
[25]Ortega, J. and Rockoff, M., ‘Nonlinear difference equations and Gauss-Seidel type iterative methods’, SIAM J. Numer. Anal. 3 (1966),497–513.CrossRefGoogle Scholar
[26]Ostrowski, A., Solution of equations and systems of equations, (Academic Press, N.Y., 2nd ed, 1966).Google Scholar
[27]Rheinboldt, W. C., ‘Local mapping relations and global implicit function theorems’, Trans. Amer. Math. Soc. 138 (1969),183–198.Google Scholar
[28]Voigt, R. G., ‘Rates of convergence for a class of iterative procedures’, SIAM J. Numer. Anal. 8 (1971),127–134.CrossRefGoogle Scholar
[29]Yakovlev, M. N., ‘On some methods of solving nonlinear equations’, Trudy Mat. Inst. Steklov. 84 (1965),8–40;Google Scholar
English Transl. Tech. Rep. 687ndash;75 (Computer Science Center, Univ. of Maryland, 1968).Google Scholar