Convergence and Stability Improvement of Quasi-Newton Methods by Full-Rank Update of the Jacobian Approximates

Abstract

A system of simultaneous multi-variable nonlinear equations can be solved by Newton’s method with local q-quadratic convergence if the Jacobian is analytically available. If this is not the case, then quasi-Newton methods with local q-superlinear convergence give solutions by approximating the Jacobian in some way. Unfortunately, the quasi-Newton condition (Secant equation) does not completely specify the Jacobian approximate in multi-dimensional cases, so its full-rank update is not possible with classic variants of the method. The suggested new iteration strategy (“T-Secant”) allows for a full-rank update of the Jacobian approximate in each iteration by determining two independent approximates for the solution. They are used to generate a set of new independent trial approximates; then, the Jacobian approximate can be fully updated. It is shown that the T-Secant approximate is in the vicinity of the classic quasi-Newton approximate, providing that the solution is evenly surrounded by the new trial approximates. The suggested procedure increases the superlinear convergence of the Secant method φS=1.618… to super-quadratic φT=φS+1=2.618… and the quadratic convergence of the Newton method φN=2 to cubic φT=φN+1=3 in one-dimensional cases. In multi-dimensional cases, the Broyden-type efficiency (mean convergence rate) of the suggested method is an order higher than the efficiency of other classic low-rank-update quasi-Newton methods, as shown by numerical examples on a Rosenbrock-type test function with up to 1000 variables. The geometrical representation (hyperbolic approximation) in single-variable cases helps explain the basic operations, and a vector-space description is also given in multi-variable cases.

Keywords

• quasi-Newton methods
• multi-variable nonlinear equations
• full-rank Jacobian approximate update
• Rosenbrock function
• super-quadratic convergence
• efficiency