Reconstruction, Approximation
and the
ENO - Schemes
CASA Seminar
Clemens A. Zarzer
4th October 2006
Outline
Motivation
Reconstruction
Outline
1 Motivation
2 Reconstruction
3 Approximation
4 ENO Reconstruction
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Motivation
Reconstruction
1D Conservation Law
ut (x, t) + fx (u(x, t)) = 0 x∈Ω
Domain Ω and one dimensional “cell-structure”:
Considered example:
u(x, t)2
f(u(x, t)) = . . . Burgers’ equation .
2
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Motivation
Reconstruction
Finite Volume Method
Balance form for cell Ii :
Z
ut (ξ, t) dξ + f(u(xi+ 1 , t)) − f(u(xi− 1 , t)) = 0 .
2 2
Ii
Idea: Approximate flux f by a numerical flux f̂:
d 1
ūi (t) = − f̂i+ 1 − f̂i− 1 ,
dt ∆xi 2 2
where Z xi+ 1
1 2
ūi (t) = u(ξ, t) dξ .
∆xi xi− 1
2
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Motivation
Reconstruction
Numerical Flux
Numerical flux-functions h(u, v) are the Godunov, the
Engquist-Osher or the Lax-Friedrichs flux-function, etc.
Approximation: f̂i+ 1 = h(u−
i+ 1
, u+
i+ 1
).
2 2 2
Hence u−
i+ 12
and u+
i+ 21
have to be reconstructed.
Figure: sketch of cell boundary
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Motivation
Reconstruction
Numerical Flux
Numerical flux-functions h(u, v) are the Godunov, the
Engquist-Osher or the Lax-Friedrichs flux-function, etc.
Approximation: f̂i+ 1 = h(u−
i+ 1
, u+
i+ 1
).
2 2 2
Hence u−
i+ 12
and u+
i+ 21
have to be reconstructed.
Figure: sketch of cell boundary
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Problem Specification
Motivation
Solution
Reconstruction
Problem Specification
one-dimensional reconstruction:
For given cell averages of the function v(x),
Z xi+1/2
1
v̄i := v(ξ) dξ , i ∈ {1, . . . , N}
∆xi xi−1/2
find a k-th order accurate estimates for the values of v(x) at the
cell boundaries.
Particularly the basis of this approximation is formed by
polynomials of degree at most k − 1.
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Problem Specification
Motivation
Solution
Reconstruction
Polynomial Setup
For each cell Ii a particular stencil is chosen.
Figure: k-th order “stencil” for cell Ii
Let S(i) = {Ii−r , . . . , Ii+s } - the cell stencil.
Let S̃(i) = {xi−r− 1 , . . . , xi+s+ 1 } - the point stencil.
2 2
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Problem Specification
Motivation
Solution
Reconstruction
Interpolating Polynomial
Based on the average values in the stencil a unique
polynomial is determined.
The unique polynomial for cell Ii is determined via
Z x 1
1 j+ 2
pi (ξ) dξ = v̄j , Ij ∈ S(i) .
∆xj x 1
j− 2
One easily proves the desired property,
pi (x) = v(x) + O(∆xi k ), x ∈ Ii .
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Problem Specification
Motivation
Solution
Reconstruction
Efficient Approach
Let vi+ 1 = pi (xi+ 1 ).
2 2
The values at the cell boundaries, vi+ 1 , depend linearly on
2
the given average values v̄j .
Hence there exist constants crj , such that:
k−1
X
vi+ 1 = crj v̄i−r+j ,
2
j=0
where
vi+ 1 = v(xi+ 1 ) + O(∆xi k ) .
2 2
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Problem Specification
Motivation
Solution
Reconstruction
Calculation of the Constants
Consider V(x) as the primitive function of v(x).
V(xi+ 1 ) can be expressed as
2
i
X Z xj+ 1 i
X
2
V(xi+ 1 ) = v(ξ) dξ = v̄j ∆xj .
2
j=−∞ xj− 12 j=−∞
Consequently one can compute the unique interpolating
polynomial Pi (x).
One easily proves: P0i (x) = pi (x), where
Z x 1
1 j+ 2
pi (ξ) dξ = v̄j , Ij ∈ S(i) .
∆xj x 1
j− 2
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Outline
Problem Specification
Motivation
Solution
Reconstruction
Calculation of the Constants
Pi (x) interpolates V(x) ∧ Pi (x)0 = pi (x)
Lagrange form of Pi (x)
k
X k
Y x − xi−r+l− 1
2
Pi (x) = V(xi−r−m− 1 )
2 xi−r+m− 1 − xi−r+l− 1
m=0 l=0 2 2
l6=m
Taking the derivative of Pi (x) and using that V(xi+ 1 ) can
2
be expressed by the average values, gives
k−1
(i)
X
pi (x) = αrj ∆xi−r+j v̄i−r+j .
j=0
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction
Problem Description
Approximation
Solution Concept
ENO Reconstruction
Approximation
one-dimensional conservative approximation:
Available data:
a set of point values of a function v(x)
Aim:
find a numerical flux v̂, which approximates v0 (x):
1
v̂i+ 1 − v̂i− 1 = v0 (xi ) + O(∆xi k ) ,
∆xi 2 2
Ii ∈ S(i).
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction
Problem Description
Approximation
Solution Concept
ENO Reconstruction
Solution Concept
Find a function h(x), such that
Z x+ ∆x
1 2
v(x) = h(ξ) dξ ,
∆x x− ∆x
2
then v0 (x) = 1 ∆x ∆x
∆x h x+ 2 −h x− 2 .
point values of v(x) =
ˆ average values of h(x)
reconstruction based on average values
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction Main Ideas
Approximation One-Dimensional ENO Reconstruction
ENO Reconstruction Numerical Results
Discontinuous Functions
Classical methods can not be applied to discontinuous
functions in general.
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction Main Ideas
Approximation One-Dimensional ENO Reconstruction
ENO Reconstruction Numerical Results
Main Idea
choose stencil for each cell with respect to the discontinuity
ADAPTIVE STENCIL
Particularly the left shift r is chosen such that, the
“discontinuous cell” is not included - if possible.
This requires a calculable quantity, which indicates the
“smoothness” of the function.
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction Main Ideas
Approximation One-Dimensional ENO Reconstruction
ENO Reconstruction Numerical Results
Newton Divided Differences
The Newton polynomial of degree k, interpolating V(x):
k
X j−1
Y
V[xi−r− 1 , . . . , xi−r+j− 1 ] (x − xi−r+m− 1 ) ,
2 2 2
j=0 m=0
where
V[xi+ 1 , . . . , xi+j− 1 ] − V[xi− 1 , . . . , xi+j− 3 ]
2 2 2 2
V[xi− 1 , . . . , xi+j− 1 ] =
2 2 xi+j− 1 − xi− 1
2 2
are the so-called Newton Divided Differences.
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction Main Ideas
Approximation One-Dimensional ENO Reconstruction
ENO Reconstruction Numerical Results
ENO Idea
Newton Divided Differences indicate smoothness
V(j) (ξ)
V[xi− 1 , . . . , xi+j− 1 ] = , for smooth functions
2 2 j!
1 in the case
V[xi− 1 , . . . , xi+j− 1 ] = O j
,
2 2 ∆x of discontinuities
Idea:
start with a two point stencil
add in each step another cell depending on the value of the
Newton Divided Differences
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction Main Ideas
Approximation One-Dimensional ENO Reconstruction
ENO Reconstruction Numerical Results
One-Dimensional ENO Reconstruction
ENO procedure:
1 Compute the divided differences, using the cell averages.
2 For cell Ii start with the two-point stencil S̃(i).
3 Assuming the actual stencil to be {xj+ 1 , . . . , xj+l− 1 }, add
2 2
xj− 12 if |V[xj− 12 , . . . , xj+l− 12 ]| < |V[xj+ 12 , . . . , xj+l+ 12 ]|
xj+l+ 21 otherwise
4 Repeat step 3. unless a k-th order stencil is obtained.
5 Use reconstruction method to compute the approximation
to v(x).
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction Main Ideas
Approximation One-Dimensional ENO Reconstruction
ENO Reconstruction Numerical Results
Numerical Results (1)
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction Main Ideas
Approximation One-Dimensional ENO Reconstruction
ENO Reconstruction Numerical Results
Numerical Results (2)
CASA Seminar Reconstruction, Approximation & ENO-Schemes
Reconstruction Main Ideas
Approximation One-Dimensional ENO Reconstruction
ENO Reconstruction Numerical Results
Burgers’ Equation
CASA Seminar Reconstruction, Approximation & ENO-Schemes
