×

Numerical experience with Newton-like methods for nonlinear algebraic systems. (English) Zbl 0866.65033

The authors report results of extensive numerical tests of several Newton-like iteration methods applied to a collection of 31 systems of nonlinear equations. The systems are all of the general form \(F(x)=0\) where \(F:\mathbb{R}^n\to \mathbb{R}^n\) and the size \(n\) can be regarded as a parameter. Hence the systems are examined for \(n=10,50,100\). The methods tested are of the general form \(x_{i+1}=x_i - p_i\) where \(p_i =H_iF(x_i)\) and \(H_i\) is an approximation to \(F'(x_i)^{-1}\). Among the methods tested are Newton’s method, Broyden’s two methods, two methods of Greenstadt, a class of ABS methods, and methods of Thomas and of Martinez. Besides varying \(n\), also two sets of starting values are used. The conclusions show Newton’s method to have the greatest robustness and speed of convergence, however, at the price of a generally higher overhead cost than the update methods. Among the quasi-Newton methods, the method of Thomas appears to be the method of choice. A few examples portraying basins of attraction for some of the methods with \(n=2\) are given. As is to be expected, they exhibit a fractal-type of structure.
Reviewer’s remarks: The authors express surprise that the number of iterations required for satisfying the stopping condition varied little with respect to \(n\). However, in view of the mesh independence principle [see, e.g., E. L. Allgower, K. Böhmer, F. A. Potra and W. C. Rheinboldt, SIAM J. Numer. Anal. 23, 160-169 (1986; Zbl 0591.65043)] this is to be expected for systems of equations arising from discretizations of a large class of operator equations. A number of the examples fall precisely into this category. Some of the citations for the test functions appear to be inaccurate.

MSC:

65H10 Numerical computation of solutions to systems of equations

Citations:

Zbl 0591.65043
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allgower, E. L., Georg, K.: Computational solution of nonlinear systems of equations. Lectures in Applied Mathematics Vol. 26, New Providence: American Mathematical Society 1990. · Zbl 0688.00015
[2] Ascher, U. M., Russel, R. D.: Numerical boundary value ODEs. Boston: Birkhäuser 1985.
[3] Abaffy, J., Spedicato, E.: ABS projection algorithms: mathematical techniques for linear and nonlinear algebraic equations. Chichester: Ellis Horwood 1989. · Zbl 0691.65022
[4] Broyden, C. G.: A class of methods for solving nonlinear simultaneous equations. Math. Comp.19, 577–593 (1965). · Zbl 0131.13905 · doi:10.1090/S0025-5718-1965-0198670-6
[5] Gheri, G., Mancino, O. G.: A significant example to test methods solving systems of nonlinear equations. Calcolo8, 107–114 (1971). · Zbl 0222.65071 · doi:10.1007/BF02575578
[6] Huang, Z.: Row update ABS methods for systems of nonlinear equations. Optimiz. Methods Software3, 41–60 (1994). · doi:10.1080/10556789408805555
[7] Huang, Z., Spedicato, E.: Numerical testing of quasi-Newton and some other related methods for nonlinear systems. Report DMSIA 94/1, University of Bergamo (1994).
[8] Huang, Z, Spedicato, E.: Numerical experiments wiyh Newton’s Brent’s and Huang type methods for nonlinear systems. Report DMSIA 94/1, University of Bergamo (1994).
[9] Martínez, J. M.: A quasi-Newton method with modification of one column per iteration. Computing33, 353–362 (1984). · Zbl 0546.90102 · doi:10.1007/BF02242278
[10] Martínez, J. M.: Algorithms for solving nonlinear systems of equation. In: Algorithms for continuous optimization: the state of the art (Spedicato, E., ed.). NATO ASI Series, Dordrecht; Kluwer 1994.
[11] Ortega, J. M., Rheinboldt, W. C.: Iterative solution of nonlinear equations in several variables. New York: Academic Press, 1970. · Zbl 0241.65046
[12] Potra, F. A., Rheinboldt, W. C.: On the monotone convergence of Newton’s method. Computing36, 81–90 (1986). · Zbl 0572.65034 · doi:10.1007/BF02238194
[13] Roose, A., Kulla, V., Lomp, M., Meressoo, T.: Test examples of systems of non-linear equations. Estonian Software and Computer Service Company, Tallin 1990. · Zbl 0696.65044
[14] Roberts, S. M., Shipman, J. S.: On the closed form solution of Troesch’s problem. J. Comput. Physics21, 291–304 (1976). · Zbl 0334.65062 · doi:10.1016/0021-9991(76)90026-7
[15] Spedicato, E., Greenstadt, J.: On some classes of variationally derived Quasi-Newton algorithms for systems of nonlinear algebraic equation. Numer. Math.29, 363–380 (1978). · Zbl 0414.65025 · doi:10.1007/BF01432875
[16] Thomas, S. W.: Sequential estimation techniques for Quasi-Newton algorithms. Report TR 75-227, Cornell University 1975.
[17] Toint, Ph. L.: Numerical solution of large sets of algebraic nonlinear equations. Math. Comp.46, 175–189 (1986). · Zbl 0614.65058 · doi:10.1090/S0025-5718-1986-0815839-9
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.