CCM, Part III

(1)

CCM, Part III Daniele Boffi

Convection diffusion

Stabilization Hyperbolic PDE’s Parabolic PDE’s

CCM, Part III

Daniele Boffi

Dipartimento di Matematica, Universit`a di Pavia http://www-dimat.unipv.it/boffi

Complexity and its Interdisciplinary Applications

(2)

Convection diffusion equation

As usual. . . a one dimensional example

( − εu

⁰⁰

(x ) + bu

⁰

(x ) = 0 0 < x < 1 u(0) = 0, u(1) = 1

Non-homogeneous boundary conditions (!)

P´ eclet number P = |b|L/(2ε) (L = 1 in our case) Closed form solution can be explicitly computed

u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

(3)

Convection diffusion equation

As usual. . . a one dimensional example

( − εu

⁰⁰

(x ) + bu

⁰

(x ) = 0 0 < x < 1 u(0) = 0, u(1) = 1

Non-homogeneous boundary conditions (!) P´ eclet number P = |b|L/(2ε) (L = 1 in our case)

Closed form solution can be explicitly computed u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

(4)

Convection diffusion equation

As usual. . . a one dimensional example

( − εu

⁰⁰

(x ) + bu

⁰

(x ) = 0 0 < x < 1 u(0) = 0, u(1) = 1

Non-homogeneous boundary conditions (!) P´ eclet number P = |b|L/(2ε) (L = 1 in our case) Closed form solution can be explicitly computed

u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

(5)

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

(6)

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

(7)

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε 1 then u(x ) ' x

If b/ε 1 then u(x ) ' exp(−b(1 − x )/ε)

In the second case, boundary layer of size O(ε/b)

(8)

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε 1 then u(x ) ' x

If b/ε 1 then u(x ) ' exp(−b(1 − x )/ε)

In the second case, boundary layer of size O(ε/b)

(9)

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε 1 then u(x ) ' x

If b/ε 1 then u(x ) ' exp(−b(1 − x )/ε)

In the second case, boundary layer of size O(ε/b)

(10)

Convection diffusion equation (cont’ed)

Approximation by finite elements a(u, v ) =

Z

1 0

εu

⁰

(x )v

⁰

(x ) + bu

⁰

(x )v (x ) dx

After some computations. . . stiffness matrix is (uniform mesh):

b 2 − ε

h

u

i +1

+ 2ε h u

i

+

− b 2 − ε

h

u

i −1

Local (discrete) P´ eclet number is P(h) = |b|h/(2ε), so that our system has the structure

(P(h) − 1)u

i +1

+ 2u

i

− (P(h) + 1)u

_{i −1}

= 0

(11)

Convection diffusion equation (cont’ed)

Approximation by finite elements a(u, v ) =

Z

1 0

εu

⁰

(x )v

⁰

(x ) + bu

⁰

(x )v (x ) dx

After some computations. . . stiffness matrix is (uniform mesh):

b 2 − ε

h

u

i +1

+ 2ε h u

i

+

− b 2 − ε

h

u

i −1

Local (discrete) P´ eclet number is P(h) = |b|h/(2ε), so that our system has the structure

(P(h) − 1)u

i +1

+ 2u

i

− (P(h) + 1)u

_{i −1}

= 0

(12)

Convection diffusion equation (cont’ed)

Approximation by finite elements a(u, v ) =

Z

1 0

εu

⁰

(x )v

⁰

(x ) + bu

⁰

(x )v (x ) dx

After some computations. . . stiffness matrix is (uniform mesh):

b 2 − ε

h

u

i +1

+ 2ε h u

i

+

− b 2 − ε

h

u

i −1

Local (discrete) P´ eclet number is P(h) = |b|h/(2ε), so that our system has the structure

(P(h) − 1)u

i +1

+ 2u

i

− (P(h) + 1)u

_{i −1}

= 0

(13)

Convection diffusion equation (cont’ed)

(P(h) − 1)u

_{i +1}

+ 2u

_i

− (P(h) + 1)u

_{i −1}

= 0 General solution

u

i

=

1 −

_1+P(h)

1−P(h)

i

1 −

_1+P(h)

1−P(h)

N

i = 1, . . . , N

If P(h) > 1 solution oscillates!

(14)

Convection diffusion equation (cont’ed)

(P(h) − 1)u

_{i +1}

+ 2u

_i

− (P(h) + 1)u

_{i −1}

= 0 General solution

u

i

=

1 −

_1+P(h)

1−P(h)

i

1 −

_1+P(h)

1−P(h)

N

i = 1, . . . , N

If P(h) > 1 solution oscillates!

(15)

Stabilization techiniques

•

Upwind (finite differences)

•

Artificial viscosity, streamline diffusion (loosing consistency)

•

Petrov–Galerkin, SUPG (strongly consistent)

(16)

Stabilization techiniques

•

Upwind (finite differences)

•

Artificial viscosity, streamline diffusion (loosing consistency)

•

Petrov–Galerkin, SUPG (strongly consistent)

(17)

Stabilization techiniques

•

Upwind (finite differences)

•

Artificial viscosity, streamline diffusion (loosing consistency)

•

Petrov–Galerkin, SUPG (strongly consistent)

(18)

Hyperbolic equations

Let’s consider the model problem (one dimensional convection equation)







∂u

∂t + a ∂u

∂x = 0, t > 0, x ∈ R u(x , 0) = u

₀

(x ), x ∈ R Solution is a traveling wave u(x , t) = u

₀

(x − at).

We consider a finite difference approximation.

(19)

Hyperbolic equations

Let’s consider the model problem (one dimensional convection equation)







∂u

∂t + a ∂u

∂x = 0, t > 0, x ∈ R u(x , 0) = u

₀

(x ), x ∈ R Solution is a traveling wave u(x , t) = u

₀

(x − at).

We consider a finite difference approximation.

(20)

Hyperbolic equations (cont’ed)

u

_jⁿ

' u(x

_j

, t

_n

)

∂u

∂t + a ∂u

∂x = 0 u

_jⁿ⁺¹

= u

_jⁿ

− ∆t

∆x (h

_{j +1/2}ⁿ

− h

ⁿ_{j −1/2}

) where h

_{j +1/2}

= h(u

j

, u

j +1

) is a numerical flux Indeed,

∂

∂t U

j

= − (au)(x

_{j +1/2}

) − (au)(x

_{j −1/2}

) with

U

_j

=

Z

x_{j +1/2} x_{j −1/2}

u, dx

(21)

Hyperbolic equations (cont’ed)

u

_jⁿ

' u(x

_j

, t

_n

)

∂u

∂t + a ∂u

∂x = 0 u

_jⁿ⁺¹

= u

_jⁿ

− ∆t

∆x (h

_{j +1/2}ⁿ

− h

ⁿ_{j −1/2}

) where h

_{j +1/2}

= h(u

j

, u

j +1

) is a numerical flux

Indeed,

∂

∂t U

j

= − (au)(x

_{j +1/2}

) − (au)(x

_{j −1/2}

) with

U

_j

=

Z

x_{j +1/2} x_{j −1/2}

u, dx

(22)

Hyperbolic equations (cont’ed)

u

_jⁿ

' u(x

_j

, t

_n

)

∂u

∂t + a ∂u

∂x = 0 u

_jⁿ⁺¹

= u

_jⁿ

− ∆t

∆x (h

_{j +1/2}ⁿ

− h

ⁿ_{j −1/2}

) where h

_{j +1/2}

= h(u

j

, u

j +1

) is a numerical flux Indeed,

∂

∂t U

j

= − (au)(x

_{j +1/2}

) − (au)(x

_{j −1/2}

) with

U

_j

=

Z

x_{j +1/2} x_{j −1/2}

u, dx

(23)

Hyperbolic equations (cont’ed)

Courant–Friedrichs–Lewy (CFL) condition

a ∆t

∆x

≤ 1

Very clear geometrical interpretation (see also multidimensional extension and generalization to systems)

Remark: implicit schemes (in time) don’t have restrictions, but

add artificial diffusion

(24)

Hyperbolic equations (cont’ed)

Courant–Friedrichs–Lewy (CFL) condition

a ∆t

∆x

≤ 1

Very clear geometrical interpretation (see also multidimensional extension and generalization to systems)

Remark: implicit schemes (in time) don’t have restrictions, but

add artificial diffusion

(25)

Hyperbolic equations (cont’ed)

Courant–Friedrichs–Lewy (CFL) condition

a ∆t

∆x

≤ 1

Very clear geometrical interpretation (see also multidimensional extension and generalization to systems)

Remark: implicit schemes (in time) don’t have restrictions, but

add artificial diffusion

(26)

Parabolic problems

Heat equation

∂u(t)

∂t − ∆u(t) = f (t)

Variational formulation: for each t, find u(t) ∈ V = H

₀¹

(Ω) s.t.

∂u(t)

∂t , v

+ a(u(t), v ) = (f (t), v ) ∀v ∈ V Space semidiscretization. Take V

_h

⊂ V and, for each t, look for u

h

(t) ∈ V

h

such that

∂u

_h

(t)

∂t , v

_h

+ a(u

_h

(t), v

_h

) = (f (t), v

_h

) ∀v

_h

∈ V

_h

(27)

Parabolic problems

Heat equation

∂u(t)

∂t − ∆u(t) = f (t)

Variational formulation: for each t, find u(t) ∈ V = H

₀¹

(Ω) s.t.

∂u(t)

∂t , v

+ a(u(t), v ) = (f (t), v ) ∀v ∈ V

Space semidiscretization. Take V

_h

⊂ V and, for each t, look for u

h

(t) ∈ V

h

such that

∂u

_h

(t)

∂t , v

_h

+ a(u

_h

(t), v

_h

) = (f (t), v

_h

) ∀v

_h

∈ V

_h

(28)

Parabolic problems

Heat equation

∂u(t)

∂t − ∆u(t) = f (t)

Variational formulation: for each t, find u(t) ∈ V = H

₀¹

(Ω) s.t.

∂u(t)

∂t , v

+ a(u(t), v ) = (f (t), v ) ∀v ∈ V Space semidiscretization. Take V

_h

⊂ V and, for each t, look for u

h

(t) ∈ V

h

such that

∂u

_h

(t)

∂t , v

_h

+ a(u

_h

(t), v

_h

) = (f (t), v

_h

) ∀v

_h

∈ V

_h

(29)

Parabolic problems (cont’ed)

Fully discretized problem

•

Explicit Euler u

_hⁿ⁺¹

− u

ⁿ_h

∆t , v

_h

!

+ a(u

_hⁿ

, v

_h

) = (f

ⁿ

, v

_h

) ∀v

_h

∈ V

_h

•

Implicit Euler u

ⁿ⁺¹_h

− u

ⁿ_h

∆t , v

_h

!

+ a(u

ⁿ⁺¹_h

, v

_h

) = (f

ⁿ⁺¹

, v

_h

) ∀v

_h

∈ V

_h

(30)

Parabolic problems (cont’ed)

Fully discretized problem

•

Explicit Euler u

_hⁿ⁺¹

− u

ⁿ_h

∆t , v

_h

!

+ a(u

_hⁿ

, v

_h

) = (f

ⁿ

, v

_h

) ∀v

_h

∈ V

_h

•

Implicit Euler u

ⁿ⁺¹_h

− u

ⁿ_h

∆t , v

_h

!

+ a(u

ⁿ⁺¹_h

, v

_h

) = (f

ⁿ⁺¹

, v

_h

) ∀v

_h

∈ V

_h

(31)

Parabolic problems (cont’ed)

θ-method (somewhat inbetween explicit and implicit)

0 ≤ θ ≤ 1 u

_hⁿ⁺¹

− u

_hⁿ

∆t , v

h

!

+(1 − θ)a(u

ⁿ_h

, v

h

) +

θa(uⁿ⁺¹_h

, v

h

) =

(1 − θ)(fⁿ

, v

h

) +

θ(fⁿ⁺¹

, v

h

) ∀v

_h

∈ V

_h

In one space dimension (finite differences, and f = 0)

u

ⁿ⁺¹_i

− u

_iⁿ

∆t = 1

h

²(1 − θ)(u_{i +1}ⁿ

− 2u

_iⁿ

+ u

_{i −1}ⁿ

)+

θ(uⁿ⁺¹_{i +1}

− 2u

ⁿ⁺¹_i

+ u

ⁿ⁺¹_{i −1}

)

(32)

Parabolic problems (cont’ed)

θ-method (somewhat inbetween explicit and implicit) 0 ≤ θ ≤ 1

u

_hⁿ⁺¹

− u

_hⁿ

∆t , v

h

!

+(1 − θ)a(u

ⁿ_h

, v

h

) +

θa(uⁿ⁺¹_h

, v

h

) =

(1 − θ)(fⁿ

, v

h

) +

θ(fⁿ⁺¹

, v

h

) ∀v

_h

∈ V

_h

In one space dimension (finite differences, and f = 0) u

ⁿ⁺¹_i

− u

_iⁿ

∆t = 1

h

²(1 − θ)(u_{i +1}ⁿ

− 2u

_iⁿ

+ u

_{i −1}ⁿ

)+

θ(uⁿ⁺¹_{i +1}

− 2u

ⁿ⁺¹_i

+ u

ⁿ⁺¹_{i −1}

)

(33)

Parabolic problems (cont’ed)

θ-method (somewhat inbetween explicit and implicit) 0 ≤ θ ≤ 1

u

_hⁿ⁺¹

− u

_hⁿ

∆t , v

h

!

+(1 − θ)a(u

ⁿ_h

, v

h

) +

θa(uⁿ⁺¹_h

, v

h

) =

(1 − θ)(fⁿ

, v

h

) +

θ(fⁿ⁺¹

, v

h

) ∀v

_h

∈ V

_h

In one space dimension (finite differences, and f = 0)

u

ⁿ⁺¹_i

− u

_iⁿ

∆t = 1

h

²(1 − θ)(u_{i +1}ⁿ

− 2u

_iⁿ

+ u

_{i −1}ⁿ

)+

θ(uⁿ⁺¹_{i +1}

− 2u

ⁿ⁺¹_i

+ u

ⁿ⁺¹_{i −1}

)

(34)

Parabolic problems (cont’ed)

If u(0) = sin(πx ) then the solution in [0, 1] with homogeneous Dirichlet boundary conditions is

u(t) = sin(πx ) exp(−π

²

t) In particular, it goes to zero as t → +∞

Study of discrete (absolute) stability Discrete solution has the form

u

ⁿ_i

= α

ⁿ

sin(πih)

Stability condition |α| ≤ 1

(35)

Parabolic problems (cont’ed)

If u(0) = sin(πx ) then the solution in [0, 1] with homogeneous Dirichlet boundary conditions is

u(t) = sin(πx ) exp(−π

²

t) In particular, it goes to zero as t → +∞

Study of discrete (absolute) stability Discrete solution has the form

u

ⁿ_i

= α

ⁿ

sin(πih)

Stability condition |α| ≤ 1

(36)

Parabolic problems (cont’ed)

If u(0) = sin(πx ) then the solution in [0, 1] with homogeneous Dirichlet boundary conditions is

u(t) = sin(πx ) exp(−π

²

t) In particular, it goes to zero as t → +∞

Study of discrete (absolute) stability Discrete solution has the form

u

ⁿ_i

= α

ⁿ

sin(πih)

Stability condition |α| ≤ 1

(37)

Parabolic problems (cont’ed)

u

ⁿ⁺¹_i

− u

_iⁿ

= k

h

²

(1 − θ)(u

ⁿ_{i +1}

− 2u

ⁿ_i

+ u

_{i −1}ⁿ

)+

θ(u

ⁿ⁺¹_{i +1}

− 2u

_iⁿ⁺¹

+ u

ⁿ⁺¹_{i −1}

) u

ⁿ_i

= α

ⁿ

sin(πih)

Some trigonometry

sin π(i + 1)h − 2 sin(πih) + sin π(i − 1)h = 2 sin(πih) cos(πh) − 2 sin(πih) =

sin(πih)(−4 sin

²

(πh/2)) Hence

α − 1 = k

h

²

((1 − θ) + θα)(−4 sin

²

(πh/2))

(38)

Parabolic problems (cont’ed)

u

ⁿ⁺¹_i

− u

_iⁿ

= k

h

²

(1 − θ)(u

ⁿ_{i +1}

− 2u

ⁿ_i

+ u

_{i −1}ⁿ

)+

θ(u

ⁿ⁺¹_{i +1}

− 2u

_iⁿ⁺¹

+ u

ⁿ⁺¹_{i −1}

) u

ⁿ_i

= α

ⁿ

sin(πih)

Some trigonometry

sin π(i + 1)h − 2 sin(πih) + sin π(i − 1)h = 2 sin(πih) cos(πh) − 2 sin(πih) =

sin(πih)(−4 sin

²

(πh/2))

Hence

α − 1 = k

h

²

((1 − θ) + θα)(−4 sin

²

(πh/2))

(39)

Parabolic problems (cont’ed)

u

ⁿ⁺¹_i

− u

_iⁿ

= k

h

²

(1 − θ)(u

ⁿ_{i +1}

− 2u

ⁿ_i

+ u

_{i −1}ⁿ

)+

θ(u

ⁿ⁺¹_{i +1}

− 2u

_iⁿ⁺¹

+ u

ⁿ⁺¹_{i −1}

) u

ⁿ_i

= α

ⁿ

sin(πih)

Some trigonometry

sin π(i + 1)h − 2 sin(πih) + sin π(i − 1)h = 2 sin(πih) cos(πh) − 2 sin(πih) =

CCM, Part III

CCM, Part III

Daniele Boffi

Complexity and its Interdisciplinary Applications

Convection diffusion equation

As usual. . . a one dimensional example

( − εu

(x ) + bu

(x ) = 0 0 < x < 1 u(0) = 0, u(1) = 1

Non-homogeneous boundary conditions (!)

P´ eclet number P = |b|L/(2ε) (L = 1 in our case) Closed form solution can be explicitly computed

u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

Convection diffusion equation

As usual. . . a one dimensional example

( − εu

(x ) + bu

(x ) = 0 0 < x < 1 u(0) = 0, u(1) = 1

Non-homogeneous boundary conditions (!) P´ eclet number P = |b|L/(2ε) (L = 1 in our case)

Closed form solution can be explicitly computed u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

Convection diffusion equation

As usual. . . a one dimensional example

( − εu

(x ) + bu

(x ) = 0 0 < x < 1 u(0) = 0, u(1) = 1

Non-homogeneous boundary conditions (!) P´ eclet number P = |b|L/(2ε) (L = 1 in our case) Closed form solution can be explicitly computed

u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1

exp(b/ε) − 1

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε  1 then u(x ) ' x

If b/ε  1 then u(x ) ' exp(−b(1 − x )/ε)

In the second case, boundary layer of size O(ε/b)

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε  1 then u(x ) ' x

If b/ε  1 then u(x ) ' exp(−b(1 − x )/ε)

In the second case, boundary layer of size O(ε/b)

Convection diffusion equation (cont’ed)

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε  1 then u(x ) ' x

If b/ε  1 then u(x ) ' exp(−b(1 − x )/ε)

In the second case, boundary layer of size O(ε/b)

Convection diffusion equation (cont’ed)

Approximation by finite elements a(u, v ) =

Z

εu

(x )v

(x ) + bu

(x )v (x ) dx

After some computations. . . stiffness matrix is (uniform mesh):

 b 2 − ε

h



u

+ 2ε h u

+



− b 2 − ε

h

 u

Local (discrete) P´ eclet number is P(h) = |b|h/(2ε), so that our system has the structure

(P(h) − 1)u

+ 2u

− (P(h) + 1)u

= 0

Convection diffusion equation (cont’ed)

Approximation by finite elements a(u, v ) =

Z

εu

(x )v

(x ) + bu

(x )v (x ) dx

After some computations. . . stiffness matrix is (uniform mesh):

 b 2 − ε

h

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε 1 then u(x ) ' x

If b/ε 1 then u(x ) ' exp(−b(1 − x )/ε)

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε 1 then u(x ) ' x

If b/ε 1 then u(x ) ' exp(−b(1 − x )/ε)

u(x ) = exp(bx /ε) − 1 exp(b/ε) − 1 If b/ε 1 then u(x ) ' x

If b/ε 1 then u(x ) ' exp(−b(1 − x )/ε)

b 2 − ε

u

b 2 − ε

u

b 2 − ε

u

1 −

1 −

1 −

1 −