Linearization of the eikonal equation suggests the following algorithm of traveltime computation:
Equation (5) can be solved numerically with a simple explicit upwind finite-difference method. For a numerical test of the algorithm, I chose to solve it by a less efficient but more robust ``brute-force'' implicit method, applying one of the generic linear solvers. The gradient operator was computed with centered finite differences. The implicit method is unconditionally stable. Its accuracy corresponds to the accuracy of the finite-difference gradient approximation. I found it helpful to regularize the linear solver with a smoothing preconditioner. The regularization assures that the traveltime remains a smooth function of the spatial coordinates.
An important feature of the suggested algorithm is that it does not require an iterative solver to iterate until the full convergence. A few iteration steps of the estimation process can be interlaced with re-linearization in the main loop of the algorithm.
Theoretically, a global convergence of the described procedure cannot be guaranteed for all cases. However, I observed a stable convergence in the preliminary numerical tests.