A Newton’s iteration converges quadratically to nonisolated solutions too

Zeng, Zhonggang

doi:10.1090/mcom/3657

A Newton’s iteration converges quadratically to nonisolated solutions too
HTML articles powered by AMS MathViewer

by Zhonggang Zeng;

Math. Comp. 92 (2023), 2795-2824

DOI: https://doi.org/10.1090/mcom/3657

Published electronically: June 15, 2023

HTML | PDF | Request permission

Abstract:

The textbook Newton’s iteration is practically inapplicable on nonisolated solutions of unregularized nonlinear systems. With a simple modification, a version of Newton’s iteration regains its local quadratic convergence to nonisolated zeros of smooth mappings assuming the solutions are semiregular as properly defined regardless of whether the system is square, underdetermined or overdetermined. Furthermore, the iteration serves as a de facto regularization mechanism for computing singular zeros from empirical data. Even if the given system is perturbed so that the nonisolated solution disappears, the iteration still locally converges to a stationary point that approximates a solution of the underlying system with an error bound in the same order of the data accuracy. Geometrically, the iteration approximately converges to the nearest point on the solution manifold. This extension simplifies nonlinear system modeling by eliminating the zero isolation process and enables a wide range of applications in algebraic computation.

References

J. Backelin, Square multiples n give infinitely many cyclic n-roots, Reports, Matematiska Institutionen 8, Stockholms universitet, 1989.
Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W. Wampler, Numerically solving polynomial systems with Bertini, Software, Environments, and Tools, vol. 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3155500, DOI 10.1137/1.9781611972702
Adi Ben-Israel, A Newton-Raphson method for the solution of systems of equations, J. Math. Anal. Appl. 15 (1966), 243–252. MR 205445, DOI 10.1016/0022-247X(66)90115-6
Paul T. Boggs, The convergence of the Ben-Israel iteration for nonlinear least squares problems, Math. Comp. 30 (1976), no. 135, 512–522. MR 416018, DOI 10.1090/S0025-5718-1976-0416018-3
Xiaojun Chen, Zuhair Nashed, and Liqun Qi, Convergence of Newton’s method for singular smooth and nonsmooth equations using adaptive outer inverses, SIAM J. Optim. 7 (1997), no. 2, 445–462. MR 1443628, DOI 10.1137/S1052623493246288
M. T. Chu, On a numerical treatment for the curve-tracing of the homotopy method, Numer. Math. 42 (1983), no. 3, 323–329. MR 723629, DOI 10.1007/BF01389577
Barry H. Dayton, Tien-Yien Li, and Zhonggang Zeng, Multiple zeros of nonlinear systems, Math. Comp. 80 (2011), no. 276, 2143–2168. MR 2813352, DOI 10.1090/S0025-5718-2011-02462-2
D. W. Decker, H. B. Keller, and C. T. Kelley, Convergence rates for Newton’s method at singular points, SIAM J. Numer. Anal. 20 (1983), no. 2, 296–314. MR 694520, DOI 10.1137/0720020
Jean-Pierre Dedieu and Myong-Hi Kim, Newton’s method for analytic systems of equations with constant rank derivatives, J. Complexity 18 (2002), no. 1, 187–209. MR 1895083, DOI 10.1006/jcom.2001.0612
Peter Deuflhard, A short history of Newton’s method, Doc. Math. Extra vol.: Optimization stories (2012), 25–30. MR 2991465
John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
Hartmut Führ and Ziemowit Rzeszotnik, On biunimodular vectors for unitary matrices, Linear Algebra Appl. 484 (2015), 86–129. MR 3385055, DOI 10.1016/j.laa.2015.06.019
Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913, DOI 10.56021/9781421407944
Jonathan D. Hauenstein and Charles W. Wampler, Isosingular sets and deflation, Found. Comput. Math. 13 (2013), no. 3, 371–403. MR 3047005, DOI 10.1007/s10208-013-9147-y
Herbert B. Keller, Geometrically isolated nonisolated solutions and their approximation, SIAM J. Numer. Anal. 18 (1981), no. 5, 822–838. MR 629667, DOI 10.1137/0718056
Nick Kollerstrom, Thomas Simpson and “Newton’s method of approximation”: an enduring myth, British J. Hist. Sci. 25 (1992), no. 3(86), 347–354. MR 1192856, DOI 10.1017/S0007087400029150
Tsung-Lin Lee, Tien-Yien Li, and Zhonggang Zeng, A rank-revealing method with updating, downdating, and applications. II, SIAM J. Matrix Anal. Appl. 31 (2009), no. 2, 503–525. MR 2530261, DOI 10.1137/07068179X
Yuri Levin and Adi Ben-Israel, A Newton method for systems of $m$ equations in $n$ variables, Proceedings of the Third World Congress of Nonlinear Analysts, Part 3 (Catania, 2000), 2001, pp. 1961–1971. MR 1977075, DOI 10.1016/S0362-546X(01)00325-X
Anton Leykin, Jan Verschelde, and Ailing Zhao, Newton’s method with deflation for isolated singularities of polynomial systems, Theoret. Comput. Sci. 359 (2006), no. 1-3, 111–122. MR 2251604, DOI 10.1016/j.tcs.2006.02.018
T. Y. Li and Zhonggang Zeng, A rank-revealing method with updating, downdating, and applications, SIAM J. Matrix Anal. Appl. 26 (2005), no. 4, 918–946. MR 2178205, DOI 10.1137/S0895479803435282
M. Z. Nashed and X. Chen, Convergence of Newton-like methods for singular operator equations using outer inverses, Numer. Math. 66 (1993), no. 2, 235–257. MR 1245013, DOI 10.1007/BF01385696
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 273810
Victor Y. Pan, Solving a polynomial equation: some history and recent progress, SIAM Rev. 39 (1997), no. 2, 187–220. MR 1453318, DOI 10.1137/S0036144595288554
Andrew J. Sommese and Charles W. Wampler II, The numerical solution of systems of polynomials, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2005. Arising in engineering and science. MR 2160078, DOI 10.1142/9789812567727
G. W. Stewart, On the perturbation of pseudo-inverses, projections and linear least squares problems, SIAM Rev. 19 (1977), no. 4, 634–662. MR 461871, DOI 10.1137/1019104
G. W. Stewart, Matrix Algorithms, Volume I, Basic Decompositions, SIAM, Philadelphia, 1998.
G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
Kunio Tanabe, Continuous Newton-Raphson method for solving an underdetermined system of nonlinear equations, Nonlinear Anal. 3 (1979), no. 4, 495–503. MR 537333, DOI 10.1016/0362-546X(79)90064-6
Charles W. Wampler and Andrew J. Sommese, Numerical algebraic geometry and algebraic kinematics, Acta Numer. 20 (2011), 469–567. MR 2805156, DOI 10.1017/S0962492911000067
Per-Ȧke Wedin, Perturbation bounds in connection with singular value decomposition, Nordisk Tidskr. Informationsbehandling (BIT) 12 (1972), 99–111. MR 309968, DOI 10.1007/bf01932678
T. J. Ypma, Finding a multiple zero by transformations and Newton-like methods, SIAM Rev. 25 (1983), no. 3, 365–378. MR 710467, DOI 10.1137/1025077
Zhonggang Zeng, The approximate irreducible factorization of a univariate polynomial. Revisited, ISSAC 2009—Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 367–374. MR 2742725, DOI 10.1145/1576702.1576752
Zhonggang Zeng, The numerical greatest common divisor of univariate polynomials, Randomization, relaxation, and complexity in polynomial equation solving, Contemp. Math., vol. 556, Amer. Math. Soc., Providence, RI, 2011, pp. 187–217. MR 2882669, DOI 10.1090/conm/556/11014
Zhonggang Zeng, Sensitivity and computation of a defective eigenvalue, SIAM J. Matrix Anal. Appl. 37 (2016), no. 2, 798–817. MR 3516864, DOI 10.1137/15M1016266
Zhonggang Zeng, On the sensitivity of singular and ill-conditioned linear systems, SIAM J. Matrix Anal. Appl. 40 (2019), no. 3, 918–942. MR 3987528, DOI 10.1137/18M1197990