ALGORITHM

Linearization of the eikonal equation suggests the following algorithm of traveltime computation:

1.

Start with an initial traveltime field $\tau_0$. The initial traveltime may be the result of a previous computation or (for simple models) the result of an approximate analytic evaluation.

2.

Compute the finite-difference gradient $\nabla \tau_0$ and the corresponding slowness model n₀ with equation (2).

3.

Compute the slowness perturbation n₁ as the difference between the true slowness model n and n₀. Exit the computation if the perturbation is smaller than the desired accuracy.

4.

Solve numerically equation (5) for the traveltime perturbation $\tau_1$.

5.

Update the traveltime field $\tau_0$ by adding $\tau_1$ to it.

6.

Repeat the loop.

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 $\nabla$ 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.