Efficient estimation of sparse Jacobian matrices by differences

摘要

In difference Newton-like methods for solving F(x)=0, the Jacobian matrix F′(x) is approximated by differences between values of F. If F′(x) is sparse, a consistent partition of its columns can be exploited to approximate F′(x) using relatively few values of F. We provide a local convergence theory for the resulting methods. A superlinearly convergent stable cyclic secant method, in which at each iteration two values of F are required and several columns of the Jacobian matrix approximation are updated simultaneously, is developed.