Dynamic Relaxation is an explicit method that can be used for computing the steady state solution for a discretised continuum mechanics problem. The convergence speed of the method depends on the accurate estimation of the parameters involved, which is especially difficult for nonlinear problems. In this paper we propose a completely adaptive Dynamic Relaxation method in which the parameters are updated during the iteration process, converging to their optimal values. We use the proposed method for computing intra-operative organ deformations using non-linear finite element models involving large deformations, nonlinear materials and contacts. The simulation results prove the accuracy and computational efficiency of the method. The proposed method is also very well suited for GPU implementation.