A Finite-Difference Approximation to Newton Method's Jacobian Matrices

Abstract

Newton‟s Method, the most widely used and robust tool for the solution of systems of nonlinear algebraic equations, requires successive evaluations of the Jacobian matrix, whose columns can be seen as the directional derivatives of the system‟s residual vector, with respect to each of its degrees of freedom. By their turn, these directional derivatives can be conveniently approximated by finite-difference schemes. However, a naïve application of such idea to solve large order nonlinear algebraic equations would easily compromises its practical attractiveness, because the number of required algebraic operations grows with the square of the order of the system.
In this paper, we consider problems where the residual vector is define by sub-domains (or „elements‟), allowing the definition of element Jacobian matrices (of much smaller order than the global one), whose columns are again approximated by central-differences. So proceeding, the residual vector becomes locally supported, the global Jacobian matrix becomes sparse-banded, and much less numerical operations are required, since the number of operations in this case grows only linearly with order of the system.
Although the proposed finite-difference scheme implies in additional computational costs, if compared to the use of explicit formulas for the Jacobian matrices, its generality, simplicity and easy implementation encourages its use, whenever exact Jacobian matrices are not readily available. It can also be useful during the development of new families of finite elements, whose behavior can be quickly tested, before any consistent linearization of the residual vector is performed.
We have tested the proposed finite-difference approximation in problems of geometrically non-linear equilibrium of cable, membrane and shell structures, of elastic behavior, whose residual vectors and exact Jacobian matrices were already available in two different academic finite element programs, allowing quick performance assessments.
We have found out that the proposed approximate Jacobian matrices yield the same convergence rate and precision as the exact ones, with fairly acceptable extra computational costs. We defer a more comprehensive evaluation of relative computing costs to future papers, but we advance the notion that as the size of the problem is increased, the extra cost due to the proposed approximation becomes relatively smaller, whilst for small problems, the extra cost is relatively irrelevant.