Some Modifications of Newton’s Method
for Solving Systems of Equations
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.
Vladimir A. Srochko, Dr. Sci. (Phys.–Math.), Prof., Irkutsk State University, 1, K.Marx st., Irkutsk, 664003, Russian Federation, e-mail: firstname.lastname@example.org
Srochko V.A. Some Modifications of Newton’s Method for Solving Systems of Equations. The Bulletin of Irkutsk State University. Series Mathematics, 2018, vol. 26, pp. 91-104. https://doi.org/10.26516/1997-7670.2018.26.91
- Bakhvalov N.C., Zhidkov N.P., Kobelkov G.M. Chislennye metody [Numerical methods]. Moscow, Laboratory of Basic Knowledge Publ., 2002, 632 p. (in Russian)
- 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., 2015, vol. 55, no. 12, pp. 1986–1998. https://doi.org/10.1134/S0965542515120040
- Vasilyev F. P. Metody optimizatsii [Optimization Methods]. Moscow, Faktorial Press, 2002, 824 p. (in Russian)
- Demyanov V. F., Malozemov V. N. Vvedenie v minimaks [Introduction to minimax]. Moscow, Science Publ., 1972, 368 p.(in Russian)
- Dennis J., Schnabel R. Numerical methods for unconditional optimization and solution of nonlinear equations. Moscow, Mir Publ., 1988. 440 p.
- Ermakov V.V., Kalitkin N.N. The optimal step and regularization of Newton’s method Comput. Math. Math. Phys., 1981, vol. 21, no. 2, pp. 491-497. https://doi.org/10.1016/0041-5553(81)90022-7
- Ortega J., Reinboldt V. Iterative methods for solving nonlinear systems of equations with many variables. Moscow, Mir Publ., 1975. 558 p.
- Srochko V.A. Chislennye metody [Numerical methods]. Saint Petersburg, Lan Publ., 2010, 208 p. (in Russian)
- Cordero A., Torregrosa J.R . Variants of Newton’s method using fifth-order quadrature formulas. Appl. Math. Comput., 2007, vol. 190, pp. 686-698. https://doi.org/10.1016/j.amc.2007.01.062
- Nesterov Yu. Modified Gauss-Newton scheme with worst case guarantees for global performance. Optimization Methods and Software. 2007, vol. 22, no. 3, pp. 469-483. https://doi.org/10.1080/08927020600643812
- Petkovic M., Neta B., Petkovic L., Dzunic J. Multipoint methods for solving nonlinear equations. New York, Academic Press, 2012.
- Spedicato E., Huang Z. Numerical Experience with Newton-like Methods for Nonlinear Algebraic Systems. Computing, 1997, vol. 58, pp. 69-89. https://doi.org/10.1007/BF02684472