Automatic computation of partial derivatives and rounding error estimates with applications to large-scale systems of nonlinear equations

摘要

Recently, a new approach has been proposed to efficiently compute the accurate values of partial derivatives of a function or functions, and simultaneously to estimate the rounding errors in the computed function values. In this paper the use of the method in the solution of nonlinear equations is investigated.The method makes use of the computational graph and, when applied to the evaluation of a function, traverses it from the top ( = the function node) down to the bottom ( = the input variable nodes). A remarkable analogy is observed between the partial derivatives and the shortest paths on the computational graph. The top-down traversing on the computational graph has the following advantages over the existing algorithms using the bottom-up traversing: (1) The gradient of a function can be computed within the same complexity as that of the evaluation of the function alone (the complexity being independent of the number of input variables); (2) A fairly sharp estimate of the rounding error in the function evaluation is obtained, on the basis of which a computationally meaningful norm may be introduced in the space of residuals to afford a convergence criterion for an iterative method of solving the system of nonlinear equations. As an example, a system of nonlinear equations with 108 variables for a distillation tower of a chemical plant is numerically analyzed in detail. It is shown that by the use of the proposed method we could satisfactorily resolve two main problems encountered in computing a numerical solution of the system of nonlinear equations, i.e., how to compute the accurate Jacobian matrix and when we should stop the iteration.