×

Newton methods to solve a system of nonlinear algebraic equations. (English) Zbl 1310.65055

Summary: Fundamental insight into the solution of systems of nonlinear equations was provided by M. J. D. Powell [Numerical Methods nonlinear algebraic Equations, Conf. Univ. Essex 1969, 87–114 (1970; Zbl 0277.65028)]. It was found that Newton iterations, with exact line searches, did not converge to a stationary point of the natural merit function, i.e., the Euclidean norm of the residuals. Extensive numerical simulation of Powell’s equations produced the unexpected result that Newton iterations converged to the solution from all initial points, where the function is defined, or from those points where the Jacobian is nonsingular, if no line search is used. The significance of Powell’s example is that an important requirement exists when utilizing Newton’s method to solve such a system of nonlinear equations. Specifically, a merit function, which is used in a line search, must have properties consistent with those of a Lyapunov function to provide sufficient conditions for convergence. This implies that level sets of the merit function are properly nested, either globally, or in some finite local region. Therefore, they are topologically equivalent to concentric spherical surfaces, either globally or in a finite local region. Furthermore, an exact line search at a point, far from the solution, may be counterproductive. This observation, and a primary aim of the present analysis, is to demonstrate that it is desirable to construct new Newton iterations, which do not require a merit function with associated line searches.

MSC:

65H10 Numerical computation of solutions to systems of equations

Citations:

Zbl 0277.65028
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Powell, M.J.D.: In: Rabinowitz, P. (ed.) A Hybrid Method for Nonlinear Equations, in Numerical Methods for Nonlinear Algebraic Equations, pp. 87-114. Gordon and Breach, London (1970)
[2] Byrd, R.H., Marazzi, M., Nocedal, J.: On the convergence of Newton iterations to non-stationary points. Math. Progr. 99, 127-148 (2004) · Zbl 1072.90038 · doi:10.1007/s10107-003-0376-8
[3] LaSalle, J.P.: The Stability of Dynamical Systems. SIAM, Philadelphia (1976) · Zbl 0364.93002 · doi:10.1137/1.9781611970432
[4] Goh, B.S.: Convergence of numerical methods in unconstrained optimization and the solution of nonlinear equations. J. Optim. Theor. Appl. 144, 43-55 (2010) · Zbl 1183.90386 · doi:10.1007/s10957-009-9583-7
[5] Vincent, T., Grantham, W.: Nonlinear and Optimal Control Systems. Wiley, New York (1997)
[6] Barbashin, E.A., Krasovskii, N.N.: On the stability of a motion in the large. Dokl. Akad. Nauk. SSR 86, 453-456 (1952) · Zbl 0047.33001
[7] Powell, M.J.D.: How bad are the BFGS methods when the objective function is quadratic. Math. Progr. 34, 34-47 (1986) · Zbl 0581.90068 · doi:10.1007/BF01582161
[8] Goh, B.S.: Global attractivity and stability of a scalar nonlinear difference equation. Comput. Math. Appl. 28, 101-107 (1994) · Zbl 0817.39006 · doi:10.1016/0898-1221(94)00097-2
[9] Fan, J.Y., Yuan, Y.X.: On the quadratic convergence of the Levenberg-Marquardt method without non-singularity assumption. Computing 74, 23-39 (2005) · Zbl 1076.65047 · doi:10.1007/s00607-004-0083-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.