![next](icons/next.png) |
![up](icons/up.png) |
![previous](icons/previous.png) |
![](icons/left.png) | A second-order fast marching eikonal solver | ![](icons/right.png) |
![[pdf]](icons/pdf.png) |
Next: Accuracy
Up: Rickett & Fomel: Second-order
Previous: Introduction
Under a high frequency approximation, propagating wavefronts may be
described by the eikonal equation,
![\begin{displaymath}
\left( \frac{\partial t}{\partial x} \right)^2 +
\left( \fra...
... +
\left( \frac{\partial t}{\partial z} \right)^2 =s^2(x,y,z),
\end{displaymath}](img5.png) |
(1) |
where
is the traveltime,
is the slowness, and
,
and
represent the spatial Cartesian coordinates.
The fast marching method solves equation (1) by
directly mimicking the advancing wavefront.
Every point on the computational
grid is classified into three groups:
points behind the wavefront, whose traveltimes are known and fixed;
points on the wavefront, whose traveltimes have been calculated, but
are not yet fixed; and points ahead of the wavefront.
The algorithm then proceeds as follows:
- Choose the point on the wavefront with the smallest traveltime.
- Fix this traveltime.
- Advance the wavefront, so that this point is behind it, and
adjacent points are either on the wavefront or behind it.
- Update traveltimes for adjacent points on the wavefront by
solving equation (1) numerically.
- Repeat until every point is behind the wavefront.
The update procedure (step 4.) requires the solution of the following
quadratic equation for
,
where
is a backward
difference operator at
grid point,
,
is a forward
operator, and
finite-difference operators in
and
are defined similarly.
The roots of the quadratic equation,
,
can be calculated explicitly as
![\begin{displaymath}
t = \frac{ -b \pm \sqrt{b^2 -4ac}}{2a}.
\end{displaymath}](img21.png) |
(3) |
Solving equation (2) amounts to accumulating
coefficients
,
and
from its non-zero terms, and evaluating
with equation (3).
If we choose a two-point finite-difference operator, such as
where
,
and
.
Coefficients
,
and
can now be calculated from
,
, and
,
where the summation index,
, refers to the six terms in
equation (2) subject to the various min/max
conditions.
This two-point stencil, however, is only accurate to first-order.
If instead we choose a suitable three-point finite-difference
stencil, we may expect the method to have second-order accuracy. For
example, the second-order upwind stencil,
Coefficients,
,
and
can be accumulated from
,
and
as before, and if the traveltime,
is not available, first-order values may be substituted.
![next](icons/next.png) |
![up](icons/up.png) |
![previous](icons/previous.png) |
![](icons/left.png) | A second-order fast marching eikonal solver | ![](icons/right.png) |
![[pdf]](icons/pdf.png) |
Next: Accuracy
Up: Rickett & Fomel: Second-order
Previous: Introduction
2013-03-03