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
Bibliographic Information
- Zhonggang Zeng
- Affiliation: Department of Mathematics, Northeastern Illinois University, Chicago, Illinois 60625
- MR Author ID: 214819
- ORCID: 0000-0001-8879-8077
- Email: zzeng@neiu.edu
- Received by editor(s): November 8, 2019
- Received by editor(s) in revised form: August 14, 2020
- Published electronically: June 15, 2023
- Additional Notes: Research was supported in part by NSF under grant DMS-1620337.
This work is dedicated to the memory of Tien-Yien Li (1945-2020) - © Copyright 2023 American Mathematical Society
- Journal: Math. Comp. 92 (2023), 2795-2824
- MSC (2020): Primary 65H10, 49M15, 65N12; Secondary 65F22, 65F20, 41A25
- DOI: https://doi.org/10.1090/mcom/3657