Numerical Time Integration

(1)

Numerical Time Integration

Wanho Choi

(wanochoi.com)

(2)

가속도

(acceleration)

속도

(velocity)

위치

(position)

시간(t)에 대한 적분 (integration) 시간(t)에 대한 미분 (differentiation) 시간(t)에 대한 적분 (integration) 시간(t)에 대한 미분 (differentiation)

(3)

Mathematics

v(t)

= !p(t)

a(t)

= !v(t) = !!p(t)

시간(t)에 대한 미분 (differentiation)

가속도

(acceleration)

속도

(velocity)

위치

(position)

(4)

가속도

(acceleration)

속도

(velocity)

위치

(position)

Discretization

v(t)

= !p(t)

a(t)

= !v(t) = !!p(t)

시간(t)에 대한 미분 (differentiation)

v(t

+ Δt) = v(t) + Δt ⋅a(t)

p(t

+ Δt) = p(t) + Δt ⋅v(t)

시간(t)에 대한 적분 (integration)

(5)

(6)

Is it difficult?

(7)

What is the answer?

v(t)

= 130

x(t)

= 10

x(t

+1) = ?

t : the current time (hour)

x(t) : the current position (km) v(t) : the current speed (km/h)

assumption) 1. constant speed

(8)

What is the answer?

v(t)

= 130

x(t)

= 10

x(t

+1) = ?

2. rectilinear motion

(9)

What is the answer?

v(t)

= 130

x(t)

= 10

x(t

+1) = ?

(10)

What is the answer?

v(t)

= 130

x(t)

= 10

x(t

+1) = ?

(11)

What is the answer?

v(t)

= 130

x(t)

= 10

x(t

+1) = ?

x(t

+1) = 140 = 10 +1×130

_{from the rate of change of it!}We can get the next position

x(t

+ Δt) = x(t) + Δt ⋅v(t)

_v(t)

=

x(t

+ Δt) − x(t)

(12)

What is the answer?

v(t)

= 130

x(t)

= 10

x(t

+1) = ?

x(t

+1) = 140 = 10 +1×130

_{from the rate of change of it!}We can get the next position

x(t

+ Δt) = x(t) + Δt ⋅v(t)

적분

(integration)

미분

(differentiation)

v(t)

=

x(t

+ Δt) − x(t)

Δt

(13)

(14)

Taylor’s Expansion (Taylor Series)

x(t

+ Δt) = x(t) + Δt ⋅ !x(t) + Δ

t

2

2 ⋅!!x(t) + Δ

t

3

2 ⋅!!!x(t) +!

(15)

What is the meaning of it?

x(t

+ Δt) = x(t) + Δt ⋅ !x(t) + Δ

t

2

2 ⋅!!x(t) + Δ

t

3

2 ⋅!!!x(t) +!

x(t

+ Δt)

x(t)

! path tangent vector:

!x(t)

(16)

Approximation

x(t

+ Δt) = x(t) + Δt ⋅ !x(t) + Δ

t

2

2 ⋅!!x(t) + Δ

t

3

2 ⋅!!!x(t) +!

x(t

+ Δt)

x(t)

_x(t

+ Δt)

path

(17)

Numerical Integration: Euler Method

x(t

+ Δt) = x(t) + Δt ⋅ !x(t) + Δ

t

2

2 ⋅!!x(t) + Δ

t

3

2 ⋅!!!x(t) +!

x(t

+ Δt)

x(t)

x(t

+ Δt) = x(t) + Δt ⋅ !x(t)

= x(t) + Δt ⋅v(t)

numerical error

x(t

+ Δt)

path

(18)

It differs from the analytic solutions.

v(t)

= v(0) + t ⋅a

p(t)

= p(0) + t ⋅v(0) +

t

2

2 ⋅a

(19)

Mass-Spring-Damper System

(20)

(21)

01_FreeFall

m

⋅g

m

⋅!!x(t)

v(t + Δt) = v(t) + Δt ⋅g x(t + Δt) = x(t) + Δt ⋅v(t) m⋅ v(t + Δt) − v(t) Δt = m ⋅g

(22)

01_FreeFall

The velocity increases more gradually as it falls downward. So, the every interval of time is increasing.

(23)

02_MassSpring_ForwardEuler

m

⋅g

m

⋅!!x(t)

k

⋅x(t)

v(t + Δt) = v(t) + Δt ⋅g − Δt ⋅ k m ⋅x(t) x(t + Δt) = x(t) + Δt ⋅v(t) m⋅ v(t + Δt) − v(t) Δt = m ⋅g − k ⋅x(t)

(24)

02_MassSpring_ForwardEuler

(25)

03_MassSpringDamper_ForwardEuler

m

⋅g

m

⋅!!x(t)

k

⋅x(t)

c

⋅v(t)

v(t + Δt) = v(t) + Δt ⋅g − Δt ⋅ k m ⋅x(t) − Δ t ⋅c m ⋅v(t) x(t + Δt) = x(t) + Δt ⋅v(t) m⋅ v(t + Δt) − v(t) Δt = m ⋅g − k ⋅x(t) − c⋅v(t)

(26)

03_MassSpringDamper_ForwardEuler

It oscillates stably.

(27)

Backward Euler Time Integration

(28)

Backward Euler Time Integration

(29)

Backward Euler Time Integration

(30)

Backward Euler Time Integration

m!!x(t) = f (t) = f (x(t),v(t)) = mg − kx(t) − cv(t) Δx ≡ x(t + Δt) − x(t)

(31)

Backward Euler Time Integration

m!!x(t) = f (t) = f (x(t),v(t)) = mg − kx(t) − cv(t) Δx = Δt ⋅v(t) Δv = Δt m ⋅ f(t) Δx = Δt ⋅v(t + Δt) Δv = Δt m ⋅ f(t + Δt) explicit Euler (forward Euler) implicit Euler (backward Euler)

conditionally stable unconditionally stable but, unknowns: f(t + Δt) vs

Δx ≡ x(t + Δt) − x(t) Δv ≡ v(t + Δt) − v(t)

(32)

Explicit vs Implicit

To generate an animation of an object, it needs to

compute the location of it for a series of time steps.

• Explicit time integration: The positions of the nodes

in the next time step are computed only using past

information.

• Implicit time integration: The positions, velocities,

and accelerations in the next time step are computed

simultaneously. This requires predicting the internal

forces at the next time step.

(33)

Backward Euler Time Integration

Δv = Δt

(34)

Backward Euler Time Integration

Δv = Δt

m ⋅ f(t + Δt) = Δ t

(35)

Backward Euler Time Integration

Δv = Δt m ⋅ f(t + Δt) = Δt m ⋅ f(t) + Δx ⋅ ∂ f(t) ∂x + Δv ⋅ ∂ f(t) ∂v ⎛ ⎝⎜ ⎞⎠⎟

(

∵Taylor's expansion

)

= Δt m ⋅ f x(t + Δt),v(t + Δt)

(

)

(36)

Backward Euler Time Integration

Δv = Δt m ⋅ f(t + Δt) = Δt m ⋅ f(t) + Δx ⋅ ∂ f(t) ∂x + Δv ⋅ ∂ f(t) ∂v ⎛ ⎝⎜ ⎞⎠⎟ = Δt m ⋅ m ⋅g − cv(t) − kx(t) − Δx ⋅ k − Δv ⋅c

(

)

(

)

∵∂f / ∂x = −k,∂f / ∂v = −c

(

)

= Δt m ⋅ f x(t + Δt),v(t + Δt)

(

)

∵f = mg − cv − kx

(

)

(37)

Backward Euler Time Integration

Δv = Δt m ⋅ f(t + Δt) ∵Δx = Δt ⋅v(t + Δt) = Δt ⋅ v(t) + Δv

(

)

(

)

= Δt m ⋅ f(t) + Δx ⋅ ∂ f(t) ∂x + Δv ⋅ ∂ f(t) ∂v ⎛ ⎝⎜ ⎞⎠⎟ = Δt m ⋅ m ⋅g − cv(t) − kx(t) − Δx ⋅ k − Δv ⋅c

(

)

(

)

∵∂f / ∂x = −k,∂f / ∂v = −c

(

)

= Δt m ⋅ f x(t + Δt),v(t + Δt)

(

)

∵f = mg − cv − kx

(

)

= Δt m ⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ v(t) + Δv

(

)

⋅ k − Δv ⋅c

)

(38)

Backward Euler Time Integration

(

)

(

)

(

)

(

)

∵∂f / ∂x = −k,∂f / ∂v = −c

(

)

= Δt m ⋅ f x(t + Δt),v(t + Δt)

(

)

∵f = mg − cv − kx

(

)

(

)

⋅ k − Δv ⋅c

)

= Δt m ⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t) − Δt ⋅ k ⋅ Δv − Δv ⋅c

(

)

(39)

Backward Euler Time Integration

(

)

(

)

(

)

(

)

∵∂f / ∂x = −k,∂f / ∂v = −c

(

)

= Δt m ⋅ f x(t + Δt),v(t + Δt)

(

)

∵f = mg − cv − kx

(

)

(

)

⋅ k − Δv ⋅c

)

= Δt m ⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t) − Δt ⋅ k ⋅ Δv − Δv ⋅c

(

)

∴Δv = Δt m + Δt2 ⋅ k + Δt ⋅c ⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t)

(

)

(40)

Backward Euler Time Integration

v(t

+ Δt) = v(t) +

Δt

m

+ Δt

2

⋅ k + Δt ⋅c

⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t)

(

)

x(t

+ Δt) = x(t) + Δt ⋅v(t + Δt)

energy loss artificial damping

(41)

05_MassSpringDamper_BackwardEuler

v(t

+ Δt) = v(t) +

Δt

m

+ Δt

2

⋅ k + Δt ⋅c

⋅ m ⋅g − cv(t) − kx(t) − Δt ⋅ k ⋅v(t)

(

)

x(t

+ Δt) = x(t) + Δt ⋅v(t + Δt)

energy loss artificial damping

(42)

(43)

04_MassSpring_BackwardEuler

v(t

+ Δt) = v(t) +

Δt

m

+ Δt

2

⋅ k

⋅ m ⋅g − kx(t) − Δt ⋅ k ⋅v(t)

(

)

(44)

(45)

Comparison: 02 vs 04

We can use a large time step because it is unconditionally stable. However, it has some artificial damping.

(46)

Ground Truth

x(t

+ Δt)

x(t)

!

(47)

Explicit Time Integration

x(t

+ Δt)

x(t)

_x(t

+ Δt)

(48)

More Stiff, Larger Error

x(t

+ Δt)

x(t)

x(t

+ Δt)

x(t)

_x(t

+ Δt)

_x(t

+ Δt)

numerical error numerical error

path

(49)

Implicit Time Integration

x(t

+ Δt)

x(t)

(50)

Implicit Time Integration

x(t

+ Δt)

x(t)

x(t

+ Δt)

numerical error path

(51)

Explicit vs Implicit

Both schemes have some numerical errors, but explicit diverges and implicit converges!