A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods

Let F be a mapping from real n-dimensional Euclidean space into itself. Most practical algorithms for finding a zero of F are of the form \[ {xk + 1} = {x_k} - B_k- 1F{x_k},\] where \ Bₖ\ is a sequence of nonsingular matrices. The main result of this paper is a characterization theorem for the superlinear convergence to a zero of F of sequences of the above form. This result is then used to give a unified treatment of the results on the superlinear convergence of the Davidon-Fletcher-Powell method obtained by Powell for the case in which exact line searches are used, and by Broyden, Dennis, and Moré for the case without line searches. As a by-product, several results on the asymptotic behavior of the sequence \ Bₖ\ are obtained. An interesting aspect of these results is that superlinear convergence is obtained without any consistency conditions; i.e., without requiring that the sequence \ Bₖ\ converge to the Jacobian matrix of F at the zero. In fact, a modification of an example due to Powell shows that most of the known quasi-Newton methods are not, in general, consistent. Finally, it is pointed out that the above-mentioned characterization theorem applies to other single and double rank quasi-Newton methods, and that the results of this paper can be used to obtain their superlinear convergence.