In this work, we propose a novel preconditioned optimization method in the paradigm of Large Deformation Diffeomorphic Metric Mapping (LDDMM). The preconditioned update scheme is formulated for the non-stationary and the stationary parameterizations of diffeomorphisms, yielding three different LDDMM methods. The preconditioning matrices are inspired in the Hessian approximation used in Gauss-Newton method. The derivatives are computed using Frechet differentials. Thus, optimization is performed in a Sobolev space, in contrast to optimization in L(2) commonly used in non-rigid registration literature. The proposed LDDMM methods have been evaluated and compared with their respective implementations of gradient descent optimization. Evaluation has been performed using real and simulated images from the Non-rigid Image Registration Evaluation Project (NIREP). The experiments conducted in this work reported that our preconditioned LDDMM methods achieved a performance similar or superior to well-established-in-literature gradient descent non-stationary LDDMM in the great majority of cases. Moreover, preconditioned optimization showed a substantial reduction in the execution time with an affordable increase of the memory usage per iteration. Additional experiments reported that optimization using Frechet differentials should be preferable to optimization using L(2) differentials.