Some modifications of Newton's method for solving systems of equations

V. A. Srochko

The Bulletin of Irkutsk State University. Series Mathematics, Tome 26 (2018), pp. 91-104

Résumé

The problem of numerical solving a system of nonlinear equations is considered. Elaboration and analysis of two modifications of the Newton's method connected with the idea of parametrization are conducted. The process of choosing the parameters is directed to provision of the monotonicity property for the iteration process with respect to some residual. The first modification uses Chebyshev's residual of the system. In order to find the direction of descent we have proposed to solve the subsystem of the Newtonean linear system, which contains only the equations corresponding to the values of the functions at a current point, which are maximum with respect to the modulus. This, generally speaking, implies some diminution of the computational complexity of the modification process in comparison to the process typical of Newton's method. Furthermore, the method's efficiency grows: the subsystem can have its solution, when the complete system is not compatible. The formula for the parameter has been derived on account of the condition of minimum for the parabolic approximation for the residual along the direction of descent. The second modification is connected with the Euclidean residual of the system. It uses the Lipscitz constant for the Jacobi matrix. The upper bound estimate for this residual in the form of a strongly convex function has been obtained. As a result, the new modification has been constructed. Unlike that for Newton's method, it provides for nonlocal reduction of the Euclidean residual on each iteration. The fact of global convergence with respect to the residual for any initial approximation at the rate of geometric progression has been proved.

Détail

Keywords: nonlinear system of equations, Newton's method with parameter
Mots-clés : modifications.

Bibliographie

[1] Bakhvalov N. C., Zhidkov N. P., Kobelkov G. M., Numerical methods, Laboratory of Basic Knowledge Publ., M., 2002, 632 pp. (in Russian) | MR

[2] Budko D. A., Cordero A., Torregrosa J. R., “New family of iterative methods based on the Ermakov-Kalitkin scheme for solving nonlinear systems of equations”, Comput. Math. Math. Phys., 55:12 (2015), 1986–1998 | DOI

[3] Vasilyev F. P., Optimization Methods, Faktorial Press, M., 2002, 824 pp. (in Russian)

[4] Demyanov V. F., Malozemov V. N., Introduction to minimax, Science Publ., M., 1972, 368 pp. (in Russian) | MR

[5] Dennis J., Schnabel R., Numerical methods for unconditional optimization and solution of nonlinear equations, Mir Publ., M., 1988, 440 pp.

[6] Ermakov V. V., Kalitkin N. N., “The optimal step and regularization of Newton's method”, Comput. Math. Math. Phys., 21:2 (1981), 491–497 | DOI | MR | Zbl

[7] Ortega J., Reinboldt V., Iterative methods for solving nonlinear systems of equations with many variables, Mir Publ., M., 1975, 558 pp.

[8] Srochko V. A., Numerical methods, Lan Publ., Saint Petersburg, 2010, 208 pp. (in Russian)

[9] Cordero A., Torregrosa J. R., “Variants of Newton's method using fifth-order quadrature formulas”, Appl. Math. Comput., 190 (2007), 686–698 | DOI | MR | Zbl

[10] Nesterov Yu., “Modified Gauss-Newton scheme with worst case guarantees for global performance”, Optimization Methods and Software, 22:3 (2007), 469–483 | DOI | MR | Zbl

[11] Petkovic M., Neta B., Petkovic L., Dzunic J., Multipoint methods for solving nonlinear equations, Academic Press, New York, 2012 | MR

[12] Spedicato E., Huang Z., “Numerical Experience with Newton-like Methods for Nonlinear Algebraic Systems”, Computing, 58 (1997), 69–89 | DOI | MR | Zbl