7. Introduction to the numerical integration of PDE.
As an example, we consider the following PDE with one variable;• Finite difference method is one of numerical method for the PDE.

Accuracy requirements

Usually τ is more restricted by stability than by accuracy.
Notation for the discretization ofSummary of the key concept on numerical method for PDE.
• Local truncation error: The amount that the exact solution of PDE fails tosatisfy the the finite difference equation.

ex.) One-step method.

• Global discretization error
Definitions: (Consistency)

Definitions: (Convergence)

Definitions: (Zero-Stability - a stability criteria with h0)

Definitions: (Absolute Stability - a stability criteria with a fixed h)Remark: Purpose of stability analysis is to determine τ0(h) whichguarantee that the perturbation does not glow. This is the case if
Note that for the case of Zero-stability, the dimension (size) of the.
matrix C0(h) increase as n

lp norm and l norm are defined byTheorem: (Lax’s equivalence theorem)
Zero (or Absolute) - stability.
Convergence
Zero (or Absolute) - stability and Consistency

Convergence.Some explicit integration method for a linear wave equation.
• Some basic schemes forare presented.

(1) FTCS (Forward in Time and Central difference Scheme).

(2) Lax (- Friedrich) scheme.

(3) Leap-Flog scheme(4) Lax-Wendroff scheme(5) 1st order upwind scheme

Some explicit integration method for a linear wave equation continued.
• Lax, Lax-Wendroff, 1st order upwind schemes can be understood as
FTCS scheme +.Diffusion term.
(1) Explicit Euler scheme (FTCS : Forward in Time and Central difference).

(2) Lax (- Friedrich) scheme.

(3) Lax-Wendroff scheme.

(4) 1st order upwind scheme(weakest diffusion)(Can be used also for negative c.)von Neumann stability analysis.
• A method to analyze the stability of numerical scheme for linear PDE(assuming equally spaced grid points and periodic boundary condition).
• Consider that the finite difference equation has the following solution.

• Then the perturbation

can be also written

Substituting the Fourier transform above, we have
Amplification factor g(θ) is defined by

The von Neumann condition for zero stability:

The von Neumann condition for absolute stability:Another derivation of von Neumann stability condition.

Then we apply absolute stability condition for the ODE.
Recall:Test problem:
Characteristic polynomial Q:

Definition: The region of absolute stability for a one-step method is the set

Therefore for the PDE, the region of absolute stability is the set

Note

l2 norm.
Parceval’s theorem.

Characteristic polynomials for a particular FD scheme.
A substitution ofto a FD equation, and the mode

decomposition results in a equation for each Fourier component
Then, substituting
we have characteristic polynomials.

.

A solution to the polynomial becomes an amplification factor for eachmode θ.

If the exact values

are known,
conveniently shows amplification rate andphase error of each mode.

Note: θ = 0, corresponds to low frequency (long wavelength).
θ = π, corresponds to high frequency (short wavelength).

Finite volume discretization
Another concept for deriving finite difference approximation suitable forthe conservation law; PDEs of the conservative form
j–1/2
j–1

j+1/2
jj+1

unit volume
Define a flux at the interface j–1/2, j+1/2,
explicit Euler scheme in time as, then discretize PDE using

However, there is no grid point (no data!) at j-1/2, j+1/2…
Useto evaluate
One can rewrite explicit Euler, Lax, Lax-Wendroff, 1st order upwind using(1) Explicit Euler :(1) Explicit Euler :(2) Lax :(3) Lax-Wendroff :(4) 1st order upwind :κ – scheme : A parametrization of representative linear schemes. (Van Leer)
For a linear PDE, write a Taylor expansion in time

Approximate the second term in RHS as

j–1/2

And the third term as
j–2

j–1

j+1/2
jj+1

j–2

κ– scheme (continued)
Deriving a FD scheme explicitly for wnj , one finds that the coefficients of wnj
Are effectively proportional to κ – 2 µ|ν| . Hence one parameter may be eliminated.
A choice
results in the form of κ – scheme derived by Van Leer.
κ – scheme becomesκ = 1/3 Quickest scheme
Leonard (1979)
κ = 1/2 Quick scheme
κ = 0 Fromm scheme (optimal)

Different from the Van Leer’s choiceµ= κ = 1

Lax-Wendroffκ – 2µν = –1 Warming & BeamMethod of lines : (yet another idea for discretization.)In the κ– scheme (and the linear scheme we have seen) a dependence on thetime step τ is included in the Courant number ν. To avoid this, one discretizes
PDE along spatial direction first as
For the FD operator Lh , choose e.g. κ – scheme, then apply ODE integration
scheme such as RK4.

Monotonicity preservation of a linear advection equation

A linear advection equation
preserves monotonicity i.e. if f(0,x): monotonic
since its general solution is.

f(t,x): monotonic,Consider a finite difference scheme that generates numericalapproximationto.
: data at the time step n.

Definition: (Monotonicity preserving scheme)
A numerical scheme is called monotonicity preserving if for every nonincreasing (decreasing ) initial data
the numerical solution
is non-increasing (decreasing).

Godunov’s thorem
For the uniform gridand the constant time stepthe (explicit or implicit) one-step scheme, in whichat the(n+1)th step is uniquely determined fromat the nth step, is written

Theorem: (Godunov: Monotonicity preservation)
The above one-step scheme is monotonicity preserving if and only if

Theorem: (Godunov’s order barrier theorem)
Linear one-step second-order accurate numerical schemes for the convection
equationcannot be monotonicity preserving, unlessRemarks:• If the numerical scheme keeps the monotonicity, a numerical solution do
not shows (unphysical) oscillations (such as at the discontinuity).
• In these theorems, the stencils cm for the one-step FD formula are assumed
to be the same at all grid points (Linear scheme).
• Practically, one can not have the 2nd order linear one-step scheme.

Godunov’s thorem (continued)
For the linear s-step multi-step scheme, the same Godunov’s theorems holds.

cf.) Local truncation error of the linear one step scheme,

Two 2nd order schemes: Lax-Wendroff and Warming & Beam schemes
From the local truncatoin error formula,the 2nd order scheme needs to satisfy
Choice of 3 grid points j – 1, j, j +1, (m = – 1, 0, +1) results in Lax-Wendroff.

( Explicit Euler + Diffusion term centered at j.)
Choice of 3 grid points j – 2, j – 1, j, (m = –2, –1, 0) results in Warming & Beam.

( 1st order upwind + Diffusion term centered at j-1.)
Writing these in the flux form
Lax-Wendroff:
Warming & Beam:Total variation diminishing (TVD) property.
• Total variation of a function

TV(f) is defined byDefinition: (TVD). If TV(f) does not increase in time,f(t,x) is called total variation diminishing or TVD.
• For f(t,x) a solution to,, we have

which is independent of t, hence f(t,x) is TVD.
This motivates to derive a numerical scheme whose total variation of a solution
does not increase in time step,
Definition: A numerical scheme with this property is called TVD scheme.
Theorem: (TVD property)
The scheme
is TVD if and only if
Corollary: TVD scheme is monotonicity preserving.

Monotonicity preserving scheme with flux limiter function. (Flux limted schemes)• Godunov’s theorem does not allow the 2nd order linear one-step scheme.
• Conditions to be satisfied by the 1st ordermonotonicity preserving scheme are• Considering that the number of grid
points for the 1st order scheme are 2 points,
resulting scheme is the 1st-order upwind.

Lax-Wendroff scheme is understood as modifying the flux of 1st order upwind.

1st order upwind ( c > 0 ):Lax-Wendroff :Consider a non-linear scheme that modify the flux with a limiter function(The value ofdiffers at each cell boundary.)

Condition for the flux with a limiter function to be monotonicity preserving.
• Derive sufficient condition for the schemewith the flux
to be the monotonicity preserving. Substituting the flux in the scheme,• Sufficient condition for the scheme to be monotonic isThis is satisfied if the flux limiter function• Let the flux limitersatisfies

to be a function of the slope ratio

Sufficient region forto have monotonicity preserving scheme.
2White region in the right panel for
and B=0 line forare allowed.
Lax-Wendroff: B = 1
Warming Beam: B = rIf(i.e. the flow is not monotonic at rj )1
1
0

1st order upwind.

If, many choices. It is desirable to have 2nd order scheme
for a smooth flow around rj = 1.

1st order upwind:
Lax-Wendroff:
Warming & Beam:Minmod limiter and Superbee limiter and high resolution scheme.
is called the flux limiter function, or the slope limiter function.
Minmod and Superbee are
two representative limiters.
Lax-Wendroff: B = 1

21

Warming Beam: B = r

10Sweby (1985) showed that theadmissible limiter regions for the2nd order TVD scheme are thosebounded by these two limiters.
Schemes that is 2nd order in thesmooth flow region, and do not
oscillate at the discontinuity iscalled high resolution scheme.

Minmod limiter

Superbee limiter

2TVD

110

Next steps.
• Numerical schemes for the conservation laws (non-linear PDE).
Including – understand characteristicsintroduction of weak solutions and shocks.
introduction of monotonicity and TVD property.
conservative form of FD schemes.
application of various numerical schemes(linear schemes, Godunov scheme,
high resolution schemes (MUSCL), artificial viscosity etc.)• Numerical schemes for the system equations – ex) the Euler system
Including – characteristics, shocks and Rankine-Hugoniot conditions.
application of various numerical schemes
approximate Riemann solver, (Godunov scheme, Roe scheme)High resolution schemes (MUSCL)• Discretization in higher dimension and general domain.