In this dissertation we discuss the construction and convergence of high order structure preserving numerical methods for problems in Lagrangian mechanics. Specifically, we make use of the discrete mechanics framework to construct symplectic integrators which have convergence which is optimal, in a certain sense. We then demonstrate how this optimal convergence can be leveraged to construct integrators of arbitrarily high order or with geometric convergence. We further show how these methods can be used to construct continuous approximations to the dynamics of a Lagrangian system, and show that these approximations are also very high order and have excellent structure preserving properties. We discuss the formulation of symplectic integrators on both vector spaces and Lie groups, using a Galerkin construction to induce a variational integrator. We begin with the formulation for vector spaces, and then extend this construction to Lie groups through the use of a convenient coordinate chart. We provide the necessary conditions for optimal convergence for both the vector space and Lie group constructions, and demonstrate that many canonical systems automatically satisfy these conditions. We close with several numerical experiments demonstrating the predicted convergence, and discuss further extensions of this work