The Extended Kalman Filter, a well-established and straightforward extension of the Kalman filter, requires a computationally intensive linearization step. In this paper, the use of the simultaneous perturbation is proposed for the computation of the gradient in a far more efficient way than the usual numerical derivatives. The resulting algorithm is applied to the problem of on-line calibration of traffic dynamics models and empirical results are presented. The use of the simultaneous perturbation gradient approximation provides significant improvement over the base case, and comparable results to those obtained by the more computationally intensive finite difference gradient approximation.