Accelerating Inexact Newton Schemes for Large Systems of Nonlinear Equations

Abstract

Classical iteration methods for linear systems, such as Jacobi iteration, can be accelerated considerably by Krylov subspace methods like GMRES. In this paper, we describe how inexact Newton methods for nonlinear problems can be accelerated in a similar way and how this leads to a general framework that includes many well-known techniques for solving linear and nonlinear systems, as well as new ones. Inexact Newton methods are frequently used in practice to avoid the expensive exact solution of the large linear system arising in the (possibly also inexact) linearization step of Newton’s process. Our framework includes acceleration techniques for the “linear steps” as well as for the “nonlinear steps” in Newton’s process. The described class of methods, the accelerated inexact Newton (AIN) methods, contains methods like GMRES and GMRESR for linear systems, Arnoldi and Jacobi–Davidson for linear eigenproblems, and many variants of Newton’s method, like damped Newton, for general nonlinear problems. As numerical experiments suggest, the AIN approach may be useful for the construction of efficient schemes for solving nonlinear problems.