TABLE OF CONTENTS Direct methods for solving the equation for the Newton step are a good idea if
the Jacobian can be computed and stored efficiently and
the cost of the factorization of the Jacobian is not excessive or
iterative methods do not converge for your problem.
Even when direct methods work well, Jacobian factorization and storage of that factorization may be more expensive than a solution by iteration. However, direct methods are more robust than iterative methods and do not require your worrying about the possible convergence failure of an iterative method or preconditioning.
If the linear equation for the Newton step is solved exactly and the Jacobian is computed and factored with each nonlinear iteration (i.e., ? = 0 in Algorithm nsolg), one should expect to see q-quadratic convergence until finite-precision effects produce stagnation (as predicted in Theorem 1.2). One can, of course, approximate the Jacobian or evaluate it only a few times during the nonlinear iteration, exchanging an increase in the number of nonlinear iterations for a dramatic reduction in the cost of the computation of the steps.
In this chapter we solve the equation for the Newton step with Gaussian elimination. As is standard in numerical linear algebra (see [23, 32, 74, 76], for example), we distinguish between the factorization and the solve. The typical implementation of Gaussian elimination, called an LU factorization, factors the coefficient matrix A into a product of a permutation matrix and...
