4.4 Fully-discrete analysis

Stability issues have been discussed separately for time (Section 4.1.2) and space (Section 4.3) discretizations. The global picture (fully discrete analysis), taking into account both discretizations is, in general, very difficult to study. However, it is possible in some particular cases to address the problem and in the following lines, we shall perform a fully discrete analysis of the advection equation (169View Equation), using a Legendre collocation method in space and a forward Euler scheme in time. Using the notation of Section 4.1
∂U J ∂U J|| P (x) ∀x ∈ [− 1,1], U JN+1(x) = U JN(x) − Δt ---N-+ Δt --N-|| --N+1-----, (174 ) ∂x ∂x x=−1 PN+1 (− 1)
where the last term imposes the boundary condition ∀J, U J(x = − 1) = 0 N. We consider this relation at the Legendre–Gauss collocation points ({xi}i=0...N), which are zeros of PN+1 (x); the square of this expression taken at these collocation points gives
( ) ( ) ( J || )2 J || ∀i ∈ [0,N ], UJ+1 (xi) 2 = U JN(xi) 2 + Δt2 ∂U-N-| − 2ΔtU JN(xi) ∂U-N-| . N ∂x |x=xi ∂x |x=xi
We multiply by (1 − xi)wi, where {wi} i=0...N are the Legendre–Gauss weights, and sum over i to obtain
N N N | ∑ ( J+1 )2 ∑ ( J )2 ∑ J ∂U-JN|| (1 − xi) U N (xi) wi = (1 − xi) UN (xi) wi − 2Δt (1 − xi)UN (xi)wi ∂x | i=0 i=0 ( ) i=0 x=xi ∑N ∂U J || 2 + Δt2 ---N-|| (1 − xi)wi. i=0 ∂x x=xi
For stability we require that a certain discrete energy of J UN be bounded in time:
∑N ( J+1 )2 ∑N ( J )2 (1 − xi) UN (xi) wi ≤ (1 − xi) U N (xi) wi, (175 ) i=0 i=0
which means that
( | )2 | 2∑N ∂U-JN| ∑N J ∂U-NJ| Δt ∂x || (1 − xi)wi − 2Δt (1 − xi)UN (xi)wi ∂x || ≤ 0. i=0 x=xi i=0 x=xi
With the exactness of the Legendre–Gauss quadrature rule for polynomials of degree lower than 2N + 1, we have
∑N ( J | )2 ∫ 1( J )2 ∂U-N-|| (1 − x )w = ∂U-N- (1 − x)dx, ∂x |x=x i i −1 ∂x i=0 i
and, with an additional integration by parts,
N | ∫ ∫ ∑ J ∂U-JN|| 1 J ∂UNJ- 1- 1 ( J )2 (1 − xi)U N(xi)wi ∂x | = (1 − x)U N ∂x dx = 2 UN (x) dx. i=0 x=xi − 1 −1
The stability condition obtained from energy analysis translates into an upper bound for the timestep, which can be seen as an accurate estimate of the CFL restriction on the timestep:
∫1 ( J )2 ( ) Δt ≤ ----−(1-U-N)(x)---dx--- ≃ 𝒪 -1- . (176 ) ∫1 ∂UJN- 2 N 2 −1 ∂x (1 − x)dx

4.4.1 Strong stability-preserving methods

The above fully-discrete analysis must, in principle, be performed for every time-marching scheme. Therefore, it is very convenient to have a way of extending the results from the first-order Euler method to higher-order methods. Strong stability-preserving Runge–Kutta and multistep methods preserve these kinds of stability properties, including those following from nonlinear stability analysis. A general review of the subject has been done by Shu [200Jump To The Next Citation Point], and we list some results here.

If we consider the general time ODE:

dU ---N-= LN UN , (177 ) dt
arising from the spatial discretization of the PDE (116View Equation), we suppose that, after discretization in time using the first-order forward Euler scheme, the strong stability requirement ∥U J+1∥ ≤ ∥U J∥ N N gives a CFL restriction of the type (176View Equation)
Δt ≤ ΔtF E. (178 )
We can then write an s-stage Runge–Kutta method in the form
U(N0)= UJN , i−∑ 1( ) U (i)= α + Δtβ L U (k) , i = 1,...s, N i,k i,k N N k=0 UJN+1 = U(Ns),
and see that, as long as αi,k ≥ 0 and βi,k ≥ 0, all of the intermediate stages are simply convex combinations of forward Euler operators. If this method is strongly stable for LN, under the condition (178View Equation), then the intermediate stages can be bounded and the Runge–Kutta scheme is stable under the CFL condition
α Δt ≤ cΔtF E, c = min -i,k. (179 ) i,k βi,k

In the same manner, one can devise strong stability-preserving explicit multistep methods of the form

∑ s ( ) U JN+1 = αiU JN+1−i+ ΔtβiLN U JN+1−i , i=1
which can also be cast into convex combinations of forward Euler steps and, therefore, these multistep methods are also stable, provided that
αi Δt ≤ cΔtF E, c = mini ---. (180 ) βi
Examples of useful coefficients for Runge–Kutta and multistep strong stability-preserving methods can be found in [200, 117]. The best of these methods are those for which the CFL coefficient c is as large as possible.
  Go to previous page Go up Go to next page