Efficient Solution of the Jacobian System in Newton's Method Close to a Root

摘要

Newton's Method constitutes a nested iteration scheme with the Newton step as the outer iteration and a linear solver of the Jacobian system as the inner iteration. We examine the interaction between these two schemes and derive solution techniques for the linear system from the properties of the outer Newton iteration. Contrary to inexact Newton methods, our techniques do not rely on relaxed tolerances for an iterative linear solve, but rather on computational speedup achieved by exploiting the properties of the Jacobian update. This update shows a pattern of increasing sparsity in the solution vicinity for many practical problems. In this paper, we specify the sparsity pattern and present derived solution techniques for both direct and iterative solvers.