NEIU Digital Commons

Newton’s Iteration at Nonisoated Solutions

SU 217

Newton’s iteration is arguably the most important and fundamental method for solving systems of nonlinear equations with a long and fascinating history. Its local quadratic convergence to isolated nonsingular solutions is well documented in the literature. It is also well-known that the iteration loses its quadratic rate of convergence, if it applies and converges at all, to nonisolated solutions with a dismal attainable accuracy in numerical computation. Even though solving systems of nonlinear equations is a standard topic in textbooks of numerical analysis, the elaboration has always been limited to isolated solutions. Models with nonisolated solutions frequently arise in applications. To avoid the difficulties on nonisolated solutions, scientific computing practioners routinely go to great lengths to isolate the solutions by introducing arbitrary auxiliary equations and variables. In this project, we formulate a notion of regularity for nonisolated solutions, establish a novel extension of Newton’s iteration for such solutions and prove its local quadratic convergence on exact equations along with local linear convergence on perturbed equations with empirical data. Furthermore, we provide a geometric interpretation of the convergence tendency, elaborate the modeling and applications involving nonisolated solutions, and demonstrate a software implementation with computing examples. Nonisolated solutions of a nonlinear system of equations present a challenge in numerical computation. Moreover, they can be highly sensitive to data perturbations. When the system is perturbed, represented with empirical data or solved using floating point arithmetic, the nonisolated solution can be substantially altered or even disappear altogether. However, the proposed extension of Newton’s iteration still converges to a stationary point that approximates an exact solution of the underlying system with accuracy in the same order of the data error. In other words, the new version of the Newton’s iteration also serves as a regularization mechanism for such an ill-posed zero-finding problem. Newton’s iteration evolves throughout the history tracing back to Babylonians with contributions from François Viète, Joseph Raphson, Thomas Simpson and many others. Replacing the inverse of the Jacobian matrix with certain types of generalized inverse started from Gauss for overdetermined systems. Calling the method “Newton’s iteration” is considered an “enduring myth” by historians. We shall also elaborate the development and extensions of Newton’s iteration in history.