310
6. Semi-Lagrangian Methods
If the Courant numbers along the x- and y-axes are less than unity, this scheme
reduces to the upstream biased Lax-Wendroff method (3.38). Von Neumann stability analysis can be used to show that the preceding bilinear and biquadratic
semi-Lagrangian schemes are unconditionally stable (Bates and McDonald 1982).
The preceding interpolation formula generalizes to higher-order polynomials
and three dimensions in a straightforward way. Since the evaluation of a threedimensional high-order interpolating polynomial requires considerable computation, the exact formulae are sometimes approximated. Ritchie et al. (1995), for
example, simplify the full expression for three-dimensional cubic interpolation
by neglecting the "corner" points.
6.1.2 Variable Velocity
Now consider the case where the velocity is a function of space and time, and the
backward trajectory of each fluid parcel must be estimated by a numerical integration . The truncation error in the variable-velocity case can again be determined
by expanding 1/I(x, t) in a Taylor series about the estimated departure point and
evaluating an expression of the form
I
l:!.t
(n+l
1/Ij -1/Id
)
+ l:!.t
1 ( 1/Id -
n
) '
(6.13)
where 1/Id = 1/1 (x') , r") and the summation represents an (r +s)-order polynomial
interpolation of 1/In to the departure point. The first term in the preceding is determined by the error in the trajectory calculation, and the second term is determined
by the error in the interpolation of 1/In to the estimated departure point. The error
generated in interpolating 1/1 to the estimated departure point is the same as that
for the constant velocity case, but the estimated departure point will not generally coincide with the true departure point, and as a consequence, the 1/I'J+I will
no longer be identical to 1/Id . In order to determine the difference between 1/It 1
and 1/Id , let x n denote the position of a fluid parcel at time t" and suppose that
backward trajectories are computed subject to the initial condition x n +
1 = X iFirst suppose the trajectory is computed using Euler 's method
xl! = x n+1 - u(x n+l, tn)l:!.t.
J
As before, define s = x j - x') = x n +I - x'} .Then
s = u(x n+l , tn)l:!.t
= l:!.t [U(x'} ,t
n)
+ s :: (x'), t
n)
+ 0 (s2) ]
= udl:!.t + 0 [(l:!.t)2].
(6.14)
(6.15)
(6.16)
where Ud = u(x'} ,t n ) and the last equality is obtained by substituting (6.14) into
(6.15). The difference between 1/It l and 1/Id is then determined by substituting
6. Semi-Lagrangian Methods
If the Courant numbers along the x- and y-axes are less than unity, this scheme
reduces to the upstream biased Lax-Wendroff method (3.38). Von Neumann stability analysis can be used to show that the preceding bilinear and biquadratic
semi-Lagrangian schemes are unconditionally stable (Bates and McDonald 1982).
The preceding interpolation formula generalizes to higher-order polynomials
and three dimensions in a straightforward way. Since the evaluation of a threedimensional high-order interpolating polynomial requires considerable computation, the exact formulae are sometimes approximated. Ritchie et al. (1995), for
example, simplify the full expression for three-dimensional cubic interpolation
by neglecting the "corner" points.
6.1.2 Variable Velocity
Now consider the case where the velocity is a function of space and time, and the
backward trajectory of each fluid parcel must be estimated by a numerical integration . The truncation error in the variable-velocity case can again be determined
by expanding 1/I(x, t) in a Taylor series about the estimated departure point and
evaluating an expression of the form
I
l:!.t
(n+l
1/Ij -1/Id
)
+ l:!.t
1 ( 1/Id -
n
) '
(6.13)
where 1/Id = 1/1 (x') , r") and the summation represents an (r +s)-order polynomial
interpolation of 1/In to the departure point. The first term in the preceding is determined by the error in the trajectory calculation, and the second term is determined
by the error in the interpolation of 1/In to the estimated departure point. The error
generated in interpolating 1/1 to the estimated departure point is the same as that
for the constant velocity case, but the estimated departure point will not generally coincide with the true departure point, and as a consequence, the 1/I'J+I will
no longer be identical to 1/Id . In order to determine the difference between 1/It 1
and 1/Id , let x n denote the position of a fluid parcel at time t" and suppose that
backward trajectories are computed subject to the initial condition x n +
1 = X iFirst suppose the trajectory is computed using Euler 's method
xl! = x n+1 - u(x n+l, tn)l:!.t.
J
As before, define s = x j - x') = x n +I - x'} .Then
s = u(x n+l , tn)l:!.t
= l:!.t [U(x'} ,t
n)
+ s :: (x'), t
n)
+ 0 (s2) ]
= udl:!.t + 0 [(l:!.t)2].
(6.14)
(6.15)
(6.16)
where Ud = u(x'} ,t n ) and the last equality is obtained by substituting (6.14) into
(6.15). The difference between 1/It l and 1/Id is then determined by substituting