CCM, Part II

(1)

CCM, Part II Daniele Boffi

Elliptic PDE’s Finite differences Finite elements

CCM, Part II

Daniele Boffi

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

Complexity and its Interdisciplinary Applications

(2)

Elliptic PDE’s

One dimensional model problem (Ω =]a, b[)

( − u ⁰⁰ (x ) = f (x ) in Ω u(a) = u(b) = 0

Boundary value problem (other boundary conditions possible)

Generalization to Ω ∈ R ^d with boundary ∂Ω ( − ∆u = f in Ω

u = 0 on ∂Ω

Theorem: well-posedness (existence, uniqueness, stability)

(3)

Elliptic PDE’s

One dimensional model problem (Ω =]a, b[)

( − u ⁰⁰ (x ) = f (x ) in Ω u(a) = u(b) = 0

Boundary value problem (other boundary conditions possible) Generalization to Ω ∈ R ^d with boundary ∂Ω

( − ∆u = f in Ω

u = 0 on ∂Ω

Theorem: well-posedness (existence, uniqueness, stability)

(4)

Elliptic PDE’s

One dimensional model problem (Ω =]a, b[)

( − u ⁰⁰ (x ) = f (x ) in Ω u(a) = u(b) = 0

Boundary value problem (other boundary conditions possible) Generalization to Ω ∈ R ^d with boundary ∂Ω

( − ∆u = f in Ω

u = 0 on ∂Ω

Theorem: well-posedness (existence, uniqueness, stability)

(5)

Finite differences

Summary: easy to design (approximate derivatives with

difference quotients), easy to implement, very hard extension to general domains and boundary conditions

x 0 x ₁ x ₂ x ₃ x ₄ x ₅

a h ₃ b

Here N = 5, x 0 = a, x i = a +

i

P

j =1

h j , i = 1, . . . , N Denoting u i = u(x i ), u _i ⁰ = u ⁰ (x i ), first finite difference is

u _i ⁰ ' u _{i +1} − u _{i −1}

h _i + h _{i +1} second order accurate in h (consistent)

(6)

Finite differences

Summary: easy to design (approximate derivatives with

difference quotients), easy to implement, very hard extension to general domains and boundary conditions

x 0 x ₁ x ₂ x ₃ x ₄ x ₅

a h ₃ b

Here N = 5, x 0 = a, x i = a +

i

P

j =1

h j , i = 1, . . . , N Denoting u i = u(x i ), u _i ⁰ = u ⁰ (x i ), first finite difference is

u _i ⁰ ' u _{i +1} − u _{i −1}

h _i + h _{i +1} second order accurate in h (consistent)

(7)

Finite differences

Summary: easy to design (approximate derivatives with

difference quotients), easy to implement, very hard extension to general domains and boundary conditions

x 0 x ₁ x ₂ x ₃ x ₄ x ₅

a h ₃ b

Here N = 5, x 0 = a, x i = a +

i

P

j =1

h j , i = 1, . . . , N

Denoting u i = u(x i ), u _i ⁰ = u ⁰ (x i ), first finite difference is u _i ⁰ ' u _{i +1} − u _{i −1}

h _i + h _{i +1} second order accurate in h (consistent)

(8)

Finite differences

Summary: easy to design (approximate derivatives with

difference quotients), easy to implement, very hard extension to general domains and boundary conditions

x 0 x ₁ x ₂ x ₃ x ₄ x ₅

a h ₃ b

Here N = 5, x 0 = a, x i = a +

i

P

j =1

h j , i = 1, . . . , N Denoting u i = u(x i ), u _i ⁰ = u ⁰ (x i ), first finite difference is

u _i ⁰ ' u _{i +1} − u _{i −1}

h _i + h _{i +1} second order accurate in h (consistent)

(9)

Finite differences (cont’ed)

Approximation of second derivative

u _i ⁰⁰ ' u _{i +1/2} ⁰ − u ⁰ _{i −1/2}

h

i

+h

i +1

2 '

u

i +1

−u

i

h

i +1

− ^u

ⁱ

^−u _h

^{i −1}

i

h

i

+h

i +1

2 If h i = h (constant mesh size), simpler expression u ⁰⁰ _i ' u _{i −1} − 2u _i + u _{i +1}

h ² second order consistent Our approximate equation at x _i reads

−u _{i −1} + 2u i − u _{i +1}

h ² = f _i , i = 1, . . . , N − 1

(10)

Finite differences (cont’ed)

Approximation of second derivative

u _i ⁰⁰ ' u _{i +1/2} ⁰ − u ⁰ _{i −1/2}

h

i

+h

i +1

2 '

u

i +1

−u

i

h

i +1

− ^u

ⁱ

^−u _h

^{i −1}

i

h

i

+h

i +1

2 If h i = h (constant mesh size), simpler expression u ⁰⁰ _i ' u _{i −1} − 2u _i + u _{i +1}

h ² second order consistent Our approximate equation at x _i reads

−u _{i −1} + 2u i − u _{i +1}

h ² = f _i , i = 1, . . . , N − 1

(11)

Finite differences (cont’ed)

Approximation of second derivative

u _i ⁰⁰ ' u _{i +1/2} ⁰ − u ⁰ _{i −1/2}

h

i

+h

i +1

2 '

u

i +1

−u

i

h

i +1

− ^u

ⁱ

^−u _h

^{i −1}

i

h

i

+h

i +1

2 If h i = h (constant mesh size), simpler expression u ⁰⁰ _i ' u _{i −1} − 2u _i + u _{i +1}

h ² second order consistent

Our approximate equation at x _i reads

−u _{i −1} + 2u i − u _{i +1}

h ² = f _i , i = 1, . . . , N − 1

(12)

Finite differences (cont’ed)

Approximation of second derivative

u _i ⁰⁰ ' u _{i +1/2} ⁰ − u ⁰ _{i −1/2}

h

i

+h

i +1

2 '

u

i +1

−u

i

h

i +1

− ^u

ⁱ

^−u _h

^{i −1}

i

h

i

+h

i +1

2 If h i = h (constant mesh size), simpler expression u ⁰⁰ _i ' u _{i −1} − 2u _i + u _{i +1}

h ² second order consistent Our approximate equation at x _i reads

−u _{i −1} + 2u i − u _{i +1}

h ² = f _i , i = 1, . . . , N − 1

(13)

Finite differences (cont’ed)

Putting things together we are led to the linear system



 



 

 u 0 = 0

. . .

−u _{i −1} + 2u _i − u _{i +1}

h ² = f _i

. . . u N = 0

AU = F A = [tridiag(−1, 2, −1)]/h ²

(14)

Finite differences (cont’ed)

Putting things together we are led to the linear system



 



 

 u 0 = 0

. . .

−u _{i −1} + 2u _i − u _{i +1}

h ² = f _i

. . . u N = 0

AU = F A = [tridiag(−1, 2, −1)]/h ²

(15)

Weak formulations

Need for more general formulations.

Let’s consider space V = H ₀ ¹ (a, b) consisting of continuous functions on [a, b], piecewise differentiable with bounded derivative, and vanishing at endpoints.

Generalization to 2D requires Lebesgue integral and Hilbert spaces

H ¹ (Ω) = {v ∈ L ² (Ω) s.t. grad v ∈ L ² (Ω)} where

L ² (Ω) =

v : Ω → R integrable s.t. Z

Ω

v ² < ∞

(16)

Weak formulations

Need for more general formulations.

Let’s consider space V = H ₀ ¹ (a, b) consisting of continuous functions on [a, b], piecewise differentiable with bounded derivative, and vanishing at endpoints.

Generalization to 2D requires Lebesgue integral and Hilbert spaces

H ¹ (Ω) = {v ∈ L ² (Ω) s.t. grad v ∈ L ² (Ω)} where

L ² (Ω) =

v : Ω → R integrable s.t. Z

Ω

v ² < ∞

(17)

Weak formulations

Need for more general formulations.

Let’s consider space V = H ₀ ¹ (a, b) consisting of continuous functions on [a, b], piecewise differentiable with bounded derivative, and vanishing at endpoints.

Generalization to 2D requires Lebesgue integral and Hilbert spaces

H ¹ (Ω) = {v ∈ L ² (Ω) s.t. grad v ∈ L ² (Ω)}

where

L ² (Ω) =

v : Ω → R integrable s.t.

Z

Ω

v ² < ∞

(18)

Weak formulations (cont’ed)

Take our model equation, multiply by a generic v ∈ V (test function), and integrate over (a, b)

− Z b

a

u ⁰⁰ (x )v (x ) dx = Z b

a

f (x )v (x ) dx

Integrating by parts gives Z b

a

u ⁰ (x )v ⁰ (x ) dx = Z b

a

f (x )v (x ) dx

a : V × V → R , F ∈ V ^∗

a(u, v ) = Z b

a

u ⁰ (x )v ⁰ (x ) dx , F (v ) = Z b

a

f (x )v (x ) dx

(19)

Weak formulations (cont’ed)

Take our model equation, multiply by a generic v ∈ V (test function), and integrate over (a, b)

− Z b

a

u ⁰⁰ (x )v (x ) dx = Z b

a

f (x )v (x ) dx

Integrating by parts gives Z b

a

u ⁰ (x )v ⁰ (x ) dx = Z b

a

f (x )v (x ) dx

a : V × V → R , F ∈ V ^∗

a(u, v ) = Z b

a

u ⁰ (x )v ⁰ (x ) dx , F (v ) = Z b

a

f (x )v (x ) dx

(20)

Weak formulations (cont’ed)

Take our model equation, multiply by a generic v ∈ V (test function), and integrate over (a, b)

− Z b

a

u ⁰⁰ (x )v (x ) dx = Z b

a

f (x )v (x ) dx

Integrating by parts gives Z b

a

u ⁰ (x )v ⁰ (x ) dx = Z b

a

f (x )v (x ) dx

a : V × V → R , F ∈ V ^∗

a(u, v ) = Z b

a

u ⁰ (x )v ⁰ (x ) dx , F (v ) = Z b

a

f (x )v (x ) dx

(21)

Weak formulations (cont’ed)

Lax–Milgram Lemma

Find u ∈ V such that a(u, v ) = F (v ) ∀v ∈ V

This problem is well posed (exist., uniq., and stab.) provided

1 V Hilbert space

2 a bilinear, continuous, F linear, continuous

3 a coercive, that is there exists α > 0 s.t. a(v , v ) ≥ αkv k ² _V , ∀v ∈ V

kuk _V ≤ 1

α kF k _V

^∗

Stability estimate

(22)

Weak formulations (cont’ed)

Lax–Milgram Lemma

Find u ∈ V such that a(u, v ) = F (v ) ∀v ∈ V

This problem is well posed (exist., uniq., and stab.) provided

1 V Hilbert space

2 a bilinear, continuous, F linear, continuous

3 a coercive, that is there exists α > 0 s.t.

a(v , v ) ≥ αkv k ² _V , ∀v ∈ V

kuk _V ≤ 1

α kF k _V

^∗

Stability estimate

(23)

Weak formulations (cont’ed)

Lax–Milgram Lemma

Find u ∈ V such that a(u, v ) = F (v ) ∀v ∈ V

This problem is well posed (exist., uniq., and stab.) provided

1 V Hilbert space

2 a bilinear, continuous, F linear, continuous

3 a coercive, that is there exists α > 0 s.t.

a(v , v ) ≥ αkv k ² _V , ∀v ∈ V

kuk _V ≤ 1

α kF k _V

^∗

Stability estimate

(24)

Weak formulations (cont’ed)

In our case hypotheses of LM Lemma OK (Poincar´ e inequality)

Remark

If f is smooth enough, the unique solution to weak formulation solves the original equation as well (strong solution)

More general situation

( − div(ε grad u) + ~ β · grad u + σu = f in Ω

u = 0 on ∂Ω

a(u, v ) = Z

Ω

ε grad u · grad v d x + Z

Ω

v ~ β · grad u d x + Z

Ω

σuv d x

(25)

Weak formulations (cont’ed)

In our case hypotheses of LM Lemma OK (Poincar´ e inequality) Remark

If f is smooth enough, the unique solution to weak formulation solves the original equation as well (strong solution)

More general situation

( − div(ε grad u) + ~ β · grad u + σu = f in Ω

u = 0 on ∂Ω

a(u, v ) = Z

Ω

ε grad u · grad v d x + Z

Ω

v ~ β · grad u d x + Z

Ω

σuv d x

(26)

Weak formulations (cont’ed)

In our case hypotheses of LM Lemma OK (Poincar´ e inequality) Remark

If f is smooth enough, the unique solution to weak formulation solves the original equation as well (strong solution)

More general situation

( − div(ε grad u) + ~ β · grad u + σu = f in Ω

u = 0 on ∂Ω

a(u, v ) = Z

Ω

ε grad u · grad v d x + Z

Ω

v ~ β · grad u d x + Z

Ω

σuv d x

(27)

Weak formulations (cont’ed)

In our case hypotheses of LM Lemma OK (Poincar´ e inequality) Remark

If f is smooth enough, the unique solution to weak formulation solves the original equation as well (strong solution)

More general situation

( − div(ε grad u) + ~ β · grad u + σu = f in Ω

u = 0 on ∂Ω

a(u, v ) = Z

Ω

ε grad u · grad v d x + Z

Ω

v ~ β · grad u d x + Z

Ω

σuv d x

(28)

Weak formulations (cont’ed)

In general problem in weak form, when a is symmetric, is equivalent to the following variational problem:

Find u ∈ V such that J(u) = min

v ∈V J(v ), J(v ) = 1

2 a(v , v ) − F (v )

In the one dimensional model problem, we have

J(v ) = 1 2

Z b a

(v ⁰ (x )) ² dx − Z b

a

f (x )v (x ) dx

(29)

Weak formulations (cont’ed)

In general problem in weak form, when a is symmetric, is equivalent to the following variational problem:

Find u ∈ V such that J(u) = min

v ∈V J(v ), J(v ) = 1

2 a(v , v ) − F (v ) In the one dimensional model problem, we have

J(v ) = 1 2

Z b a

(v ⁰ (x )) ² dx − Z b

a

f (x )v (x ) dx

(30)

Finite elements (Galerkin method)

Consider a finite dimensional subspace V h ⊂ V (h refers to a mesh parameter).

Find u _h ∈ V _h such that a(u _h , v _h ) = F (v _h ) ∀v _h ∈ V _h Problem is solvable by Lax–Milgram

Suppose that V _h = span{ϕ ₁ , . . . , ϕ _N (h)}, so u _h =

N

P

j =1

u _j ϕ _j Problem can be written: find u = {u _j } s.t. for any i

a X ^N

j =1

u _j ϕ _j , ϕ _i

= F (ϕ _i )

(31)

Finite elements (Galerkin method)

Consider a finite dimensional subspace V h ⊂ V (h refers to a mesh parameter).

Find u _h ∈ V _h such that a(u _h , v _h ) = F (v _h ) ∀v _h ∈ V _h

Problem is solvable by Lax–Milgram

Suppose that V _h = span{ϕ ₁ , . . . , ϕ _N (h)}, so u _h =

N

P

j =1

u _j ϕ _j Problem can be written: find u = {u _j } s.t. for any i

a X ^N

j =1

u _j ϕ _j , ϕ _i

= F (ϕ _i )

(32)

Finite elements (Galerkin method)

Consider a finite dimensional subspace V h ⊂ V (h refers to a mesh parameter).

Find u _h ∈ V _h such that a(u _h , v _h ) = F (v _h ) ∀v _h ∈ V _h Problem is solvable by Lax–Milgram

Suppose that V _h = span{ϕ ₁ , . . . , ϕ _N (h)}, so u _h =

N

P

j =1

u _j ϕ _j Problem can be written: find u = {u _j } s.t. for any i

a X ^N

j =1

u _j ϕ _j , ϕ _i

= F (ϕ _i )

(33)

Finite elements (Galerkin method)

Consider a finite dimensional subspace V h ⊂ V (h refers to a mesh parameter).

Find u _h ∈ V _h such that a(u _h , v _h ) = F (v _h ) ∀v _h ∈ V _h Problem is solvable by Lax–Milgram

Suppose that V _h = span{ϕ ₁ , . . . , ϕ _N (h)}, so u _h =

N

P

j =1

u _j ϕ _j

Problem can be written: find u = {u _j } s.t. for any i

a X ^N

j =1

u _j ϕ _j , ϕ _i

= F (ϕ _i )

(34)

Finite elements (Galerkin method)

Consider a finite dimensional subspace V h ⊂ V (h refers to a mesh parameter).

Find u _h ∈ V _h such that a(u _h , v _h ) = F (v _h ) ∀v _h ∈ V _h Problem is solvable by Lax–Milgram

Suppose that V _h = span{ϕ ₁ , . . . , ϕ _N (h)}, so u _h =

N

P

j =1

u _j ϕ _j Problem can be written: find u = {u _j } s.t. for any i

a X ^N

j =1

u _j ϕ _j , ϕ _i

= F (ϕ _i )

(35)

Galerkin method (cont’ed)

Bilinearity of a gives

N

X

j =1

u _j a(ϕ _j , ϕ _i ) = F (ϕ _i ), i = 1, . . . , N

Let’s denote by A the stiffness matrix A _ij = a(ϕ _j , ϕ _i ) and by b the load vector b i = F (ϕ i ). Then we have the matrix form of discrete problem

Au = b

a symmetric and coercive implies A symmetric positive definite

(36)

Galerkin method (cont’ed)

Bilinearity of a gives

N

X

j =1

u _j a(ϕ _j , ϕ _i ) = F (ϕ _i ), i = 1, . . . , N

Let’s denote by A the stiffness matrix A _ij = a(ϕ _j , ϕ _i ) and by b the load vector b i = F (ϕ i ). Then we have the matrix form of discrete problem

Au = b

a symmetric and coercive implies A symmetric positive definite

(37)

Galerkin method (cont’ed)

Bilinearity of a gives

N

X

j =1

u _j a(ϕ _j , ϕ _i ) = F (ϕ _i ), i = 1, . . . , N

Let’s denote by A the stiffness matrix A _ij = a(ϕ _j , ϕ _i ) and by b the load vector b i = F (ϕ i ). Then we have the matrix form of discrete problem

Au = b

a symmetric and coercive implies A symmetric positive definite

(38)

Galerkin method (cont’ed)

Existence and uniqueness (Lax–Milgram)

Convergence = Consistency + Stability

Stability:

ku _h k _V ≤ 1 α kF k _V

^∗

Strong consistency

a(u − u h , v h ) = 0 ∀v _h ∈ V _h

(39)

Galerkin method (cont’ed)

Existence and uniqueness (Lax–Milgram) Convergence = Consistency + Stability

Stability:

ku _h k _V ≤ 1 α kF k _V

^∗

Strong consistency

a(u − u h , v h ) = 0 ∀v _h ∈ V _h

(40)

Galerkin method (cont’ed)

Existence and uniqueness (Lax–Milgram) Convergence = Consistency + Stability

Stability:

ku _h k _V ≤ 1 α kF k _V

^∗

Strong consistency

a(u − u h , v h ) = 0 ∀v _h ∈ V _h

(41)

Galerkin method (cont’ed)

Existence and uniqueness (Lax–Milgram) Convergence = Consistency + Stability

Stability:

ku _h k _V ≤ 1 α kF k _V

^∗

Strong consistency

a(u − u h , v h ) = 0 ∀v _h ∈ V _h

(42)

Galerkin method (cont’ed)

Error estimate (C´ ea’s Lemma)

αku − u h k ² _V ≤ a(u − u _h , u − u h ) = a(u − u h , u − v h )

≤ Mku − u _h k _V ku − v _h k _V

ku − u _h k _V ≤ M α inf

v ∈V

h

ku − v _h k _V Error bounded by best approximation

Need for good choice of V _h !

(43)

Galerkin method (cont’ed)

Error estimate (C´ ea’s Lemma)

αku − u h k ² _V ≤ a(u − u _h , u − u h ) = a(u − u h , u − v h )

≤ Mku − u _h k _V ku − v _h k _V

ku − u _h k _V ≤ M α inf

v ∈V

h

ku − v _h k _V

Error bounded by best approximation

Need for good choice of V _h !

(44)

Galerkin method (cont’ed)

Error estimate (C´ ea’s Lemma)

αku − u h k ² _V ≤ a(u − u _h , u − u h ) = a(u − u h , u − v h )

≤ Mku − u _h k _V ku − v _h k _V

ku − u _h k _V ≤ M α inf

v ∈V

h

ku − v _h k _V Error bounded by best approximation

Need for good choice of V _h !

(45)

Galerkin method (cont’ed)

Moreover, when a is symmetric, we have the variational property

J(u _h ) = min

v

h

∈V

_h

J(v _h )

Since V _h ⊂ V , in particular, we have

J(u) ≤ J(u _h )

(46)

Galerkin method (cont’ed)

Moreover, when a is symmetric, we have the variational property

J(u _h ) = min

v

h

∈V

_h

J(v _h ) Since V _h ⊂ V , in particular, we have

J(u) ≤ J(u _h )

(47)

Finite elements

One dimensional p/w linear approximation.

Shape (or basis) func- tions: hat functions.

A finite element is defined by:

1 a domain (interval, triangle, tetrahedron,. . . ),

2 a finite dimensional (polynomial) space,

3 a set of degrees of freedom.

(48)

Finite elements

One dimensional p/w linear approximation.

Shape (or basis) func- tions: hat functions.

A finite element is defined by:

1 a domain (interval, triangle, tetrahedron,. . . ),

2 a finite dimensional (polynomial) space,

3 a set of degrees of freedom.

(49)

Finite elements

One dimensional p/w linear approximation.

Shape (or basis) func- tions: hat functions.

A finite element is defined by:

1 a domain (interval, triangle, tetrahedron,. . . ),

2 a finite dimensional (polynomial) space,

3 a set of degrees of freedom.

(50)

Finite elements

One dimensional p/w linear approximation.

Shape (or basis) func- tions: hat functions.

A finite element is defined by:

1 a domain (interval, triangle, tetrahedron,. . . ),

2 a finite dimensional (polynomial) space,

3 a set of degrees of freedom.

(51)

Finite elements (cont’ed)

One dimensional finite elements

1 domain: interval

2 space: P _p

3 d.o.f.’s: depend on polynomial order linear element: endpoints (2)

quadratic element: endpoints + midpoint (3) . . .

Set {a _j } ^N _{j =1} of degrees of freedom is unisolvent, that is, given N numbers α ₁ , . . . , α _N , there exists a unique polynomial ϕ in P _p s. t.

ϕ(a j ) = α j , j = 1, . . . , N

(52)

Finite elements (cont’ed)

One dimensional finite elements

1 domain: interval

2 space: P _p

3 d.o.f.’s: depend on polynomial order linear element: endpoints (2)

quadratic element: endpoints + midpoint (3) . . .

Set {a _j } ^N _{j =1} of degrees of freedom is unisolvent, that is, given N numbers α ₁ , . . . , α _N , there exists a unique polynomial ϕ in P _p s. t.

ϕ(a j ) = α j , j = 1, . . . , N

(53)

Finite elements (cont’ed)

One dimensional finite elements

1 domain: interval

2 space: P _p

3 d.o.f.’s: depend on polynomial order

linear element: endpoints (2)

quadratic element: endpoints + midpoint (3) . . .

Set {a _j } ^N _{j =1} of degrees of freedom is unisolvent, that is, given N numbers α ₁ , . . . , α _N , there exists a unique polynomial ϕ in P _p s. t.

ϕ(a j ) = α j , j = 1, . . . , N

(54)

Finite elements (cont’ed)

One dimensional finite elements

1 domain: interval

2 space: P _p

3 d.o.f.’s: depend on polynomial order linear element: endpoints (2)

quadratic element: endpoints + midpoint (3) . . .

Set {a _j } ^N _{j =1} of degrees of freedom is unisolvent, that is, given N numbers α ₁ , . . . , α _N , there exists a unique polynomial ϕ in P _p s. t.

ϕ(a j ) = α j , j = 1, . . . , N

(55)

Finite elements (cont’ed)

One dimensional finite elements

1 domain: interval

2 space: P _p

3 d.o.f.’s: depend on polynomial order linear element: endpoints (2)

quadratic element: endpoints + midpoint (3) . . .

Set {a _j } ^N _{j =1} of degrees of freedom is unisolvent, that is, given N numbers α ₁ , . . . , α _N , there exists a unique polynomial ϕ in P _p s. t.

ϕ(a j ) = α j , j = 1, . . . , N

(56)

Finite elements (cont’ed)

Approximation properties of one dimensional finite elements

v

h

inf ∈V

_h

ku − v _h k _H

k

≤ Ch ^p+1−k |u| _H

p+1

k = 0, 1

Remark on hp FEM

• Refine in h where solution is singular

• Refine in p where solution is regular

(57)

Finite elements (cont’ed)

Approximation properties of one dimensional finite elements

v

h

inf ∈V

_h

ku − v _h k _H

k

≤ Ch ^p+1−k |u| _H

p+1

k = 0, 1

Remark on hp FEM

• Refine in h where solution is singular

• Refine in p where solution is regular

(58)

Finite elements (cont’ed)

Approximation properties of one dimensional finite elements

v

h

inf ∈V

_h

ku − v _h k _H

k

≤ Ch ^p+1−k |u| _H

p+1

k = 0, 1

Remark on hp FEM

• Refine in h where solution is singular

• Refine in p where solution is regular

(59)

Finite elements (cont’ed)

Generalization to more space dimensions

Example of unisolvent degrees of freedom

(60)

Finite elements (cont’ed)

How to construct stiffness matrix and load vector

In general one considers reference elements and mappings to actual elements

F

Notation: K ˆ reference element; K actual element ˆ

ϕ ₁ , . . . ˆ ϕ _N reference shape functions;

ϕ 1 , . . . ϕ _N actual shape functions

(61)

Finite elements (cont’ed)

How to construct stiffness matrix and load vector

In general one considers reference elements and mappings to actual elements

F

Notation: K ˆ reference element; K actual element ˆ

ϕ ₁ , . . . ˆ ϕ _N reference shape functions;

ϕ 1 , . . . ϕ _N actual shape functions

(62)

Finite elements (cont’ed)

How to construct stiffness matrix and load vector

In general one considers reference elements and mappings to actual elements

F

Notation: K ˆ reference element; K actual element

ˆ

ϕ ₁ , . . . ˆ ϕ _N reference shape functions;

ϕ 1 , . . . ϕ _N actual shape functions

(63)

Finite elements (cont’ed)

How to construct stiffness matrix and load vector

In general one considers reference elements and mappings to actual elements

F

Notation: K ˆ reference element; K actual element ˆ

ϕ ₁ , . . . ˆ ϕ _N reference shape functions;

ϕ 1 , . . . ϕ _N actual shape functions

(64)

Finite elements (cont’ed)

How to map the shape functions

F _K : ˆ K → K , ~ x = F (ˆ ~ x ) ϕ(~ x ) = ˆ ϕ(F ⁻¹ (~ x ))

Example of computation of local stiffness matrix (one dimensional)

A _ji = a(ϕ _i , ϕ _j ) = Z b

a

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx = X

K

Z

K

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx

Z

K

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx = Z

K ˆ

ˆ ϕ ⁰ _i (ˆ x ) F ⁰ (ˆ x )

ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ x ) F ⁰ (ˆ x ) d ˆ x = Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ x ) d ˆ x

(65)

Finite elements (cont’ed)

How to map the shape functions

F _K : ˆ K → K , ~ x = F (ˆ ~ x ) ϕ(~ x ) = ˆ ϕ(F ⁻¹ (~ x ))

Example of computation of local stiffness matrix (one dimensional)

A _ji = a(ϕ _i , ϕ _j ) = Z b

a

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx = X

K

Z

K

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx

Z

K

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx = Z

K ˆ

ˆ ϕ ⁰ _i (ˆ x ) F ⁰ (ˆ x )

ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ x ) F ⁰ (ˆ x ) d ˆ x = Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ x ) d ˆ x

(66)

Finite elements (cont’ed)

How to map the shape functions

F _K : ˆ K → K , ~ x = F (ˆ ~ x ) ϕ(~ x ) = ˆ ϕ(F ⁻¹ (~ x ))

Example of computation of local stiffness matrix (one dimensional)

A _ji = a(ϕ _i , ϕ _j ) = Z b

a

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx = X

K

Z

K

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx

Z

K

ϕ ⁰ _i (x )ϕ ⁰ _j (x ) dx = Z

K ˆ

ˆ ϕ ⁰ _i (ˆ x ) F ⁰ (ˆ x )

ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ x ) F ⁰ (ˆ x ) d ˆ x = Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ x ) d ˆ x

(67)

Finite elements (cont’ed)

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x ) F ⁰ (ˆ x ) d ˆ x

In general, F = α + βˆ x is affine so that F ⁰ = β is constant (and equal to h)

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ ~ x ) dx = 1 h

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x ) dx

In more space dimensions, F is affine for most popular elements. Z

K

grad ϕ _i (~ x ) · grad ϕ _j (~ x ) d~ x =?

(68)

Finite elements (cont’ed)

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x ) F ⁰ (ˆ x ) d ˆ x

In general, F = α + βˆ x is affine so that F ⁰ = β is constant (and equal to h)

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ ~ x ) dx = 1 h

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x ) dx

In more space dimensions, F is affine for most popular elements. Z

K

grad ϕ _i (~ x ) · grad ϕ _j (~ x ) d~ x =?

(69)

Finite elements (cont’ed)

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x ) F ⁰ (ˆ x ) d ˆ x

In general, F = α + βˆ x is affine so that F ⁰ = β is constant (and equal to h)

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ ~ x ) dx = 1 h

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x ) dx

In more space dimensions, F is affine for most popular elements. Z

K

grad ϕ _i (~ x ) · grad ϕ _j (~ x ) d~ x =?

(70)

Finite elements (cont’ed)

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x ) F ⁰ (ˆ x ) d ˆ x

In general, F = α + βˆ x is affine so that F ⁰ = β is constant (and equal to h)

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x )

F ⁰ (ˆ ~ x ) dx = 1 h

Z

K ˆ

ˆ

ϕ ⁰ _i (ˆ x ) ˆ ϕ ⁰ _j (ˆ x ) dx

In more space dimensions, F is affine for most popular elements. Z

K

grad ϕ _i (~ x ) · grad ϕ _j (~ x ) d~ x =?

(71)

Finite elements (cont’ed)

General strategy for assembling stiffness matrix and load vector

• Loop over elements ie = 1, . . . , ne

• Compute local stiffness matrix A ^loc _ji = a(ϕ _i , ϕ _j ), i , j = 1, . . . , ndof and local load vector F _i ^loc = F (ϕ _i ), i = 1, . . . , ndof

• Loop for i , j = 1, . . . , ndof and assembly of global matrix A iglob,jglob = A iglob,jglob + A ^loc _ij

• Account for boundary conditions

(72)

Finite elements (cont’ed)

General strategy for assembling stiffness matrix and load vector

• Loop over elements ie = 1, . . . , ne

• Compute local stiffness matrix A ^loc _ji = a(ϕ _i , ϕ _j ), i , j = 1, . . . , ndof and local load vector F _i ^loc = F (ϕ _i ), i = 1, . . . , ndof

• Loop for i , j = 1, . . . , ndof and assembly of global matrix A iglob,jglob = A iglob,jglob + A ^loc _ij

• Account for boundary conditions

(73)

Finite elements (cont’ed)

Some remarks on the discrete linear system

• matrix is sparse (sparsity pattern, so called skyline, can be determined a priori)

• matrix is SPD (CG can be succesfully applied)

• conditioning of matrix grows as h goes to zero (need for preconditioning)

End of part II

(74)

Finite elements (cont’ed)

Some remarks on the discrete linear system

• matrix is sparse (sparsity pattern, so called skyline, can be determined a priori)

• matrix is SPD (CG can be succesfully applied)

• conditioning of matrix grows as h goes to zero (need for preconditioning)

End of part II

(75)

Finite elements (cont’ed)

Some remarks on the discrete linear system

• matrix is sparse (sparsity pattern, so called skyline, can be determined a priori)

• matrix is SPD (CG can be succesfully applied)

• conditioning of matrix grows as h goes to zero (need for preconditioning)

End of part II

(76)

Finite elements (cont’ed)

Some remarks on the discrete linear system

• matrix is sparse (sparsity pattern, so called skyline, can be determined a priori)

• matrix is SPD (CG can be succesfully applied)

• conditioning of matrix grows as h goes to zero (need for preconditioning)

End of part II

CCM, Part II

CCM, Part II

Daniele Boffi

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

Complexity and its Interdisciplinary Applications

Elliptic PDE’s

One dimensional model problem (Ω =]a, b[)

( − u 00 (x ) = f (x ) in Ω u(a) = u(b) = 0

Boundary value problem (other boundary conditions possible)

Generalization to Ω ∈ R d with boundary ∂Ω ( − ∆u = f in Ω

u = 0 on ∂Ω

Theorem: well-posedness (existence, uniqueness, stability)

Elliptic PDE’s

One dimensional model problem (Ω =]a, b[)

( − u 00 (x ) = f (x ) in Ω u(a) = u(b) = 0

Boundary value problem (other boundary conditions possible) Generalization to Ω ∈ R d with boundary ∂Ω

( − ∆u = f in Ω

u = 0 on ∂Ω

Theorem: well-posedness (existence, uniqueness, stability)

Elliptic PDE’s

One dimensional model problem (Ω =]a, b[)

( − u 00 (x ) = f (x ) in Ω u(a) = u(b) = 0

Boundary value problem (other boundary conditions possible) Generalization to Ω ∈ R d with boundary ∂Ω

( − ∆u = f in Ω

u = 0 on ∂Ω

Theorem: well-posedness (existence, uniqueness, stability)

Finite differences

Summary: easy to design (approximate derivatives with

difference quotients), easy to implement, very hard extension to general domains and boundary conditions

x 0 x 1 x 2 x 3 x 4 x 5

a h 3 b

Here N = 5, x 0 = a, x i = a +

i

P

j =1

h j , i = 1, . . . , N Denoting u i = u(x i ), u i 0 = u 0 (x i ), first finite difference is

u i 0 ' u i +1 − u i −1

h i + h i +1 second order accurate in h (consistent)

Finite differences

Summary: easy to design (approximate derivatives with

difference quotients), easy to implement, very hard extension to general domains and boundary conditions

x 0 x 1 x 2 x 3 x 4 x 5

a h 3 b

Here N = 5, x 0 = a, x i = a +

i

P

j =1

h j , i = 1, . . . , N Denoting u i = u(x i ), u i 0 = u 0 (x i ), first finite difference is

u i 0 ' u i +1 − u i −1

h i + h i +1 second order accurate in h (consistent)

Finite differences

Summary: easy to design (approximate derivatives with

difference quotients), easy to implement, very hard extension to general domains and boundary conditions

x 0 x 1 x 2 x 3 x 4 x 5

a h 3 b

Here N = 5, x 0 = a, x i = a +

i

P

j =1

h j , i = 1, . . . , N

Denoting u i = u(x i ), u i 0 = u 0 (x i ), first finite difference is u i 0 ' u i +1 − u i −1

h i + h i +1 second order accurate in h (consistent)

Finite differences

Summary: easy to design (approximate derivatives with

difference quotients), easy to implement, very hard extension to general domains and boundary conditions

x 0 x 1 x 2 x 3 x 4 x 5

a h 3 b

Here N = 5, x 0 = a, x i = a +

i

P

j =1

h j , i = 1, . . . , N Denoting u i = u(x i ), u i 0 = u 0 (x i ), first finite difference is

u i 0 ' u i +1 − u i −1

h i + h i +1 second order accurate in h (consistent)

Finite differences (cont’ed)

Approximation of second derivative

u i 00 ' u i +1/2 0 − u 0 i −1/2

h

+h

2

( − u ⁰⁰ (x ) = f (x ) in Ω u(a) = u(b) = 0

Generalization to Ω ∈ R ^d with boundary ∂Ω ( − ∆u = f in Ω

( − u ⁰⁰ (x ) = f (x ) in Ω u(a) = u(b) = 0

Boundary value problem (other boundary conditions possible) Generalization to Ω ∈ R ^d with boundary ∂Ω

( − u ⁰⁰ (x ) = f (x ) in Ω u(a) = u(b) = 0

Boundary value problem (other boundary conditions possible) Generalization to Ω ∈ R ^d with boundary ∂Ω

x 0 x ₁ x ₂ x ₃ x ₄ x ₅

a h ₃ b

h j , i = 1, . . . , N Denoting u i = u(x i ), u _i ⁰ = u ⁰ (x i ), first finite difference is

u _i ⁰ ' u _{i +1} − u _{i −1}

h _i + h _{i +1} second order accurate in h (consistent)

x 0 x ₁ x ₂ x ₃ x ₄ x ₅

a h ₃ b

h j , i = 1, . . . , N Denoting u i = u(x i ), u _i ⁰ = u ⁰ (x i ), first finite difference is

u _i ⁰ ' u _{i +1} − u _{i −1}

h _i + h _{i +1} second order accurate in h (consistent)

x 0 x ₁ x ₂ x ₃ x ₄ x ₅

a h ₃ b

Denoting u i = u(x i ), u _i ⁰ = u ⁰ (x i ), first finite difference is u _i ⁰ ' u _{i +1} − u _{i −1}

h _i + h _{i +1} second order accurate in h (consistent)

x 0 x ₁ x ₂ x ₃ x ₄ x ₅

a h ₃ b

h j , i = 1, . . . , N Denoting u i = u(x i ), u _i ⁰ = u ⁰ (x i ), first finite difference is

u _i ⁰ ' u _{i +1} − u _{i −1}

h _i + h _{i +1} second order accurate in h (consistent)

u _i ⁰⁰ ' u _{i +1/2} ⁰ − u ⁰ _{i −1/2}

− ^u

^−u _h

If h i = h (constant mesh size), simpler expression u ⁰⁰ _i ' u _{i −1} − 2u _i + u _{i +1}

h ² second order consistent Our approximate equation at x _i reads

−u _{i −1} + 2u i − u _{i +1}

h ² = f _i , i = 1, . . . , N − 1

u _i ⁰⁰ ' u _{i +1/2} ⁰ − u ⁰ _{i −1/2}

− ^u

^−u _h

If h i = h (constant mesh size), simpler expression u ⁰⁰ _i ' u _{i −1} − 2u _i + u _{i +1}

h ² second order consistent Our approximate equation at x _i reads

−u _{i −1} + 2u i − u _{i +1}

h ² = f _i , i = 1, . . . , N − 1

u _i ⁰⁰ ' u _{i +1/2} ⁰ − u ⁰ _{i −1/2}

− ^u

^−u _h

If h i = h (constant mesh size), simpler expression u ⁰⁰ _i ' u _{i −1} − 2u _i + u _{i +1}

h ² second order consistent

Our approximate equation at x _i reads

−u _{i −1} + 2u i − u _{i +1}

h ² = f _i , i = 1, . . . , N − 1

u _i ⁰⁰ ' u _{i +1/2} ⁰ − u ⁰ _{i −1/2}

− ^u

^−u _h

If h i = h (constant mesh size), simpler expression u ⁰⁰ _i ' u _{i −1} − 2u _i + u _{i +1}

h ² second order consistent Our approximate equation at x _i reads

−u _{i −1} + 2u i − u _{i +1}