Regresar

Optimal r-order of an adjoint Broyden method without the assumption of linearly independent steps

Abstract:

Quasi-Newton methods based on least change secant updating formulas that solve linear equations Ax=b in n=dim(x)=dim(b) steps can be expected to solve the smooth nonlinear systems n-step quadratically, i.e. with an r-order of =21/n=1+1/n+O(1/n2). The best rate one can generally expect is n-k for some fixed k, where n is the positive root of n(-1)=1. Irrespective of the shift k, the ratio [image omitted] tends to 1 for large n. To show that this asymptotically optimal rate is actually achieved, one usually has to impose a priori some kind of linear independence condition on the sequence of steps taken by the quasi-Newton iteration in question. Without any such assumptions, we establish in this paper the convergence order n for the adjoint Broyden formula proposed by Schlenkrich et al. [S. Schlenkrich, A. Griewank, and A. Walther, Local convergence analysis of TR1 updates for solving nonlinear equations, MATHEON Preprint 337 (2006)]. It requires the evaluation of adjoint vectors, is invariant with respect to linear transformations on the variable domain, and combines the properties of bounded deterioration and hebkp_redity.