Ordinary Differential Equations, Applications and Discretizations
Chris Rackauckas
October 1st, 2020
Youtube Video Link Part 1
Youtube Video Link Part 2
Now that we have a sense of parallelism, let's return back to our thread on scientific machine learning to start constructing parallel algorithms for integration of scientific models. We previously introduced discrete dynamical systems and their asymptotic behavior. However, many physical systems are not discrete and are in fact continuous. In this discussion we will understand how to numerically compute ordinary differential equations by transforming them into discrete dynamical systems, and use this to come up with simulation techniques for physical systems.
What is an Ordinary Differential Equation?
An ordinary differential equation is an equation defined by a relationship on the derivative. In its general form we have that
\[ u' = f(u,p,t) \]
describes the evolution of some variable $u(t)$ which we would like to solve for. In its simplest sense, the solution to the ordinary differential equation is just the integral, since by taking the integral of both sides and applying the Fundamental Theorem of Calculus we have that
\[ u = \int_{t_0}^{t_f} f(u,p,t)dt \]
The difficulty of this equation is that the variable $u(t)$ is unknown and dependent on $t$, meaning that the integral cannot readily be solved by simple calculus. In fact, in almost all cases there exists no analytical solution for $u$ which is readily available. However, we can understand the behavior by looking at some simple cases.
Solving Ordinary Differential Equations in Julia
To solve an ordinary differential equation in Julia, one can use the DifferentialEquations.jl package to define the differential equation you'd like to solve. Let's say we want to solve the Lorenz equations:
\[ \begin{align} \frac{dx}{dt} &= σ(y-x) \\ \frac{dy}{dt} &= x(ρ-z) - y \\ \frac{dz}{dt} &= xy - βz \\ \end{align} \]
which was the system used in our investigation of discrete dynamics. The first thing we need to do is give it this differential equation. We can either write it in an in-place form f(du,u,p,t) or an out-of-place form f(u,p,t). Let's write it in the in-place form:
function lorenz(du,u,p,t) du[1] = p[1]*(u[2]-u[1]) du[2] = u[1]*(p[2]-u[3]) - u[2] du[3] = u[1]*u[2] - p[3]*u[3] end
lorenz (generic function with 3 methods)
Question: How could I maybe speed this up a little?
Next we give an initial condition. Here, this is a vector of equations, so our initial condition has to be a vector. Let's choose the following initial condition:
u0 = [1.0,0.0,0.0]
3-element Vector{Float64}:
1.0
0.0
0.0
Notice that I made sure to use Float64 values in the initial condition. The Julia library's functions are generic and internally use the corresponding types that you give it. Integer types do not bode well for continuous problems.
Next, we have to tell it the timespan to solve on. Here, let's some from time 0 to 100. This means that we would use:
tspan = (0.0,100.0)
(0.0, 100.0)
Now we need to define our parameters. We will use the same ones as from our discrete dynamical system investigation.
p = (10.0,28.0,8/3)
(10.0, 28.0, 2.6666666666666665)
These describe an ODEProblem. Let's bring in DifferentialEquations.jl and define the ODE:
using DifferentialEquations prob = ODEProblem(lorenz,u0,tspan,p)
ODEProblem with uType Vector{Float64} and tType Float64. In-place: true
Non-trivial mass matrix: false
timespan: (0.0, 100.0)
u0: 3-element Vector{Float64}:
1.0
0.0
0.0
Now we can solve it by calling solve:
sol = solve(prob)
retcode: Success
Interpolation: 3rd order Hermite
t: 1292-element Vector{Float64}:
0.0
3.5678604836301404e-5
0.0003924646531993154
0.003262408731175873
0.009058076622686189
0.01695647090176743
0.027689960116420883
0.041856352219618344
0.060240411865493296
0.08368541210909924
⋮
99.43545175575305
99.50217600300971
99.56297541572351
99.62622492183432
99.69561088424294
99.77387244562912
99.86354266863755
99.93826978918452
100.0
u: 1292-element Vector{Vector{Float64}}:
[1.0, 0.0, 0.0]
[0.9996434557625105, 0.0009988049817849058, 1.781434788799189e-8]
[0.9961045497425811, 0.010965399721242457, 2.1469553658389193e-6]
[0.9693591548287857, 0.0897706331002921, 0.00014380191884671585]
[0.9242043547708632, 0.24228915014052968, 0.0010461625485930237]
[0.8800455783133068, 0.43873649717821195, 0.003424260078582332]
[0.8483309823046307, 0.6915629680633586, 0.008487625469885364]
[0.8495036699348377, 1.0145426764822272, 0.01821209108471829]
[0.9139069585506618, 1.442559985646147, 0.03669382222358562]
[1.0888638225734468, 2.0523265829961646, 0.07402573595703686]
⋮
[1.2013409155396158, -2.429012698730855, 25.83593282347909]
[-0.4985909866565941, -2.2431908075030083, 21.591758421186338]
[-1.3554328352527145, -2.5773570617802326, 18.48962628032902]
[-2.1618698772305467, -3.5957801801676297, 15.934724265473792]
[-3.433783468673715, -5.786446127166032, 14.065327938066913]
[-5.971873646288483, -10.261846004477597, 14.060290896024572]
[-10.941900618598972, -17.312154206417734, 20.65905960858999]
[-14.71738043327772, -16.96871551014668, 33.06627229408802]
[-13.714517151605754, -8.323306384833089, 38.798231477265624]
To see what the solution looks like, we can call plot:
using Plots plot(sol)
We can also plot phase space diagrams by telling it which vars to compare on which axis. Let's plot this in the (x,y,z) plane:
plot(sol,vars=(1,2,3))
Note that the sentinal to time is 0, so we can also do (t,y,z) with:
plot(sol,vars=(0,2,3))
The equation is continuous and therefore the solution is continuous. We can see this by checking how it is at any random time value:
sol(0.5)
3-element Vector{Float64}:
6.503654869601841
-8.508354698106574
38.09199725979106
which gives the current evolution at that time point.
Differential Equations from Scientific Contexts
N-Body Problems and Astronomy
There are many different contexts in which differential equations show up. In fact, it's not a stretch to say that the laws in all fields of science are encoded in differential equations. The starting point for physics is Newton's laws of gravity, which define an N-body ordinary differential equation system by describing the force between two particles as:
\[ F = G \frac{m_1m_2}{r^2} \]
where $r^2$ is the Euclidean distance between the two particles. From here, we use the fact that
\[ F = ma \]
to receive differential equations in terms of the accelerations of each particle. The differential equation is a system, where we know the change in position is due to the current velocity:
\[ x' = v \]
and the change in velocity is the acceleration:
\[ v' = F/m = G \frac{m_i}{r_i^2} \]
where $i$ runs over the other particles. Thus we have a vector of position derivatives and a vector of velocity derivatives that evolve over time to give the evolving positions and velocity.
An example of this is the Pleiades problem, which is an approximation to a 7-star chaotic system. It can be written as:
using OrdinaryDiffEq function pleiades(du,u,p,t) @inbounds begin x = view(u,1:7) # x y = view(u,8:14) # y v = view(u,15:21) # x′ w = view(u,22:28) # y′ du[1:7] .= v du[8:14].= w for i in 15:28 du[i] = zero(u[1]) end for i=1:7,j=1:7 if i != j r = ((x[i]-x[j])^2 + (y[i] - y[j])^2)^(3/2) du[14+i] += j*(x[j] - x[i])/r du[21+i] += j*(y[j] - y[i])/r end end end end tspan = (0.0,3.0) prob = ODEProblem(pleiades,[3.0,3.0,-1.0,-3.0,2.0,-2.0,2.0,3.0,-3.0,2.0,0,0,-4.0,4.0,0,0,0,0,0,1.75,-1.5,0,0,0,-1.25,1,0,0],tspan)
ODEProblem with uType Vector{Float64} and tType Float64. In-place: true
Non-trivial mass matrix: false
timespan: (0.0, 3.0)
u0: 28-element Vector{Float64}:
3.0
3.0
-1.0
-3.0
2.0
-2.0
2.0
3.0
-3.0
2.0
⋮
1.75
-1.5
0.0
0.0
0.0
-1.25
1.0
0.0
0.0
where we assume $m_i = i$. When we solve this equation we receive the following:
sol = solve(prob,Vern8(),abstol=1e-10,reltol=1e-10) plot(sol)
tspan = (0.0,200.0) prob = ODEProblem(pleiades,[3.0,3.0,-1.0,-3.0,2.0,-2.0,2.0,3.0,-3.0,2.0,0,0,-4.0,4.0,0,0,0,0,0,1.75,-1.5,0,0,0,-1.25,1,0,0],tspan) sol = solve(prob,Vern8(),abstol=1e-10,reltol=1e-10) plot(sol,vars=((1:7),(8:14)))
Population Ecology: Lotka-Volterra
Population ecology's starting point is the Lotka-Volterra equations which describes the interactions between a predator and a prey. In this case, the prey grows at an exponential rate but has a term that reduces its population by being eaten by the predator. The predator's growth is dependent on the available food (the amount of prey) and has a decay rate due to old age. This model is then written as follows:
function lotka(du,u,p,t) du[1] = p[1]*u[1] - p[2]*u[1]*u[2] du[2] = -p[3]*u[2] + p[4]*u[1]*u[2] end p = [1.5,1.0,3.0,1.0] prob = ODEProblem(lotka,[1.0,1.0],(0.0,10.0),p) sol = solve(prob) plot(sol)
Biochemistry: Robertson Equations
Biochemical equations commonly display large separation of timescales which lead to a stiffness phenomena that will be investigated later. The classic "hard" equations for ODE integration thus tend to come from biology (not physics!) due to this property. One of the standard models is the Robertson model, which can be described as:
using Sundials, ParameterizedFunctions function rober(du,u,p,t) y₁,y₂,y₃ = u k₁,k₂,k₃ = p du[1] = -k₁*y₁+k₃*y₂*y₃ du[2] = k₁*y₁-k₂*y₂^2-k₃*y₂*y₃ du[3] = k₂*y₂^2 end prob = ODEProblem(rober,[1.0,0.0,0.0],(0.0,1e5),(0.04,3e7,1e4)) sol = solve(prob,Rosenbrock23()) plot(sol)
plot(sol, xscale=:log10, tspan=(1e-6, 1e5), layout=(3,1))
Chemical Physics: Pollution Models
Chemical reactions in physical models are also described as differential equation systems. The following is a classic model of dynamics between different species of pollutants:
k1=.35e0 k2=.266e2 k3=.123e5 k4=.86e-3 k5=.82e-3 k6=.15e5 k7=.13e-3 k8=.24e5 k9=.165e5 k10=.9e4 k11=.22e-1 k12=.12e5 k13=.188e1 k14=.163e5 k15=.48e7 k16=.35e-3 k17=.175e-1 k18=.1e9 k19=.444e12 k20=.124e4 k21=.21e1 k22=.578e1 k23=.474e-1 k24=.178e4 k25=.312e1 p = (k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12,k13,k14,k15,k16,k17,k18,k19,k20,k21,k22,k23,k24,k25) function f(dy,y,p,t) k1,k2,k3,k4,k5,k6,k7,k8,k9,k10,k11,k12,k13,k14,k15,k16,k17,k18,k19,k20,k21,k22,k23,k24,k25 = p r1 = k1 *y[1] r2 = k2 *y[2]*y[4] r3 = k3 *y[5]*y[2] r4 = k4 *y[7] r5 = k5 *y[7] r6 = k6 *y[7]*y[6] r7 = k7 *y[9] r8 = k8 *y[9]*y[6] r9 = k9 *y[11]*y[2] r10 = k10*y[11]*y[1] r11 = k11*y[13] r12 = k12*y[10]*y[2] r13 = k13*y[14] r14 = k14*y[1]*y[6] r15 = k15*y[3] r16 = k16*y[4] r17 = k17*y[4] r18 = k18*y[16] r19 = k19*y[16] r20 = k20*y[17]*y[6] r21 = k21*y[19] r22 = k22*y[19] r23 = k23*y[1]*y[4] r24 = k24*y[19]*y[1] r25 = k25*y[20] dy[1] = -r1-r10-r14-r23-r24+ r2+r3+r9+r11+r12+r22+r25 dy[2] = -r2-r3-r9-r12+r1+r21 dy[3] = -r15+r1+r17+r19+r22 dy[4] = -r2-r16-r17-r23+r15 dy[5] = -r3+r4+r4+r6+r7+r13+r20 dy[6] = -r6-r8-r14-r20+r3+r18+r18 dy[7] = -r4-r5-r6+r13 dy[8] = r4+r5+r6+r7 dy[9] = -r7-r8 dy[10] = -r12+r7+r9 dy[11] = -r9-r10+r8+r11 dy[12] = r9 dy[13] = -r11+r10 dy[14] = -r13+r12 dy[15] = r14 dy[16] = -r18-r19+r16 dy[17] = -r20 dy[18] = r20 dy[19] = -r21-r22-r24+r23+r25 dy[20] = -r25+r24 end
f (generic function with 2 methods)
u0 = zeros(20) u0[2] = 0.2 u0[4] = 0.04 u0[7] = 0.1 u0[8] = 0.3 u0[9] = 0.01 u0[17] = 0.007 prob = ODEProblem(f,u0,(0.0,60.0),p) sol = solve(prob,Rodas5())
retcode: Success
Interpolation: specialized 4rd order "free" stiffness-aware interpolation
t: 29-element Vector{Float64}:
0.0
0.0013845590497824308
0.0032425408555978065
0.007901605186238558
0.016011573128447715
0.02740615782667033
0.04461209489084016
0.07720629860953748
0.11607399520754574
0.17630637866968027
⋮
3.676321760674584
5.344946006050843
7.985770156053235
11.981253004863657
17.45250678979442
24.88225038649404
34.664626562428
47.2776368703344
60.0
u: 29-element Vector{Vector{Float64}}:
[0.0, 0.2, 0.0, 0.04, 0.0, 0.0, 0.1, 0.3, 0.01, 0.0, 0.0, 0.0, 0.0, 0.0, 0
.0, 0.0, 0.007, 0.0, 0.0, 0.0]
[0.00029350836769160676, 0.19970649101355778, 1.6938359129632629e-10, 0.03
970673366392417, 1.1424841091201046e-7, 1.0937647553427752e-7, 0.0999996667
6440009, 0.3000003350396963, 0.00999998209858389, 5.603772477404191e-9, 6.0
479383374015165e-9, 1.0047570803311956e-8, 5.981228120551784e-12, 6.2395533
94674911e-9, 2.3022538431539708e-10, 3.1293305822799984e-17, 0.006999999417
662247, 5.823377531818466e-10, 3.8240538930007013e-10, 6.930819262664874e-1
4]
[0.0006836584210606728, 0.19931633630217105, 1.9606016528699768e-10, 0.039
31745223172094, 2.0821314250665419e-7, 2.5242637532813185e-7, 0.09999884087
663291, 0.30000116344747263, 0.009999897466495843, 2.0605144943050522e-8, 1
.684478883093366e-8, 8.136618111448752e-8, 1.0724538626933362e-10, 6.486750
821281317e-8, 3.101041569326282e-9, 3.0986508176686375e-17, 0.0069999964441
40287, 3.555859713411784e-9, 2.0643860560505372e-9, 2.04762753632627e-12]
[0.001642817973784757, 0.1983571312432743, 2.6245924356629333e-10, 0.03836
2310983454995, 3.515273101615516e-7, 4.6645725111944667e-7, 0.0999954492136
874, 0.30000456320511154, 0.009999473651020205, 4.496438391129492e-8, 3.335
02845049581e-8, 4.812858406908092e-7, 1.4409606151241901e-9, 4.444464457652
569e-7, 3.7457516938538236e-8, 3.023375105689781e-17, 0.006999981334742858,
1.8665257142397453e-8, 1.174674259521366e-8, 6.886039137106916e-11]
[0.0032462850225591445, 0.19675344573879994, 3.734915520585143e-10, 0.0367
6859814520768, 4.320335387184177e-7, 5.784969053293274e-7, 0.09998753646912
427, 0.30001250073288577, 0.009998412790451154, 5.8477927152284906e-8, 4.22
8373027866144e-8, 1.5155870812728752e-6, 8.524980703156782e-9, 1.4615346572
047066e-6, 2.1422147530567468e-7, 2.897772877949438e-17, 0.0069999433444060
12, 5.665559398821745e-8, 4.43684984962106e-8, 1.0618431973890099e-9]
[0.005361393190485352, 0.19463777385295444, 5.199898982181124e-10, 0.03466
7922896299615, 4.301350092281597e-7, 5.629734261088105e-7, 0.09997580962788
367, 0.30002429018904825, 0.009996820354680816, 5.777644507236682e-8, 4.151
1457721949835e-8, 3.0752434554602552e-6, 2.7267226071503796e-8, 2.988896438
241699e-6, 6.762050044137204e-7, 2.7322163958218528e-17, 0.0069998862740145
64, 1.1372598543664712e-7, 1.1359725976682261e-7, 7.943534967386e-9]
[0.008274965318269555, 0.19172294809854468, 7.218269825111368e-10, 0.03177
417954845203, 3.982608406112008e-7, 5.005231391036288e-7, 0.099959353941917
14, 0.300040899020958, 0.009994606735209868, 5.1781453122059335e-8, 3.71499
24313099417e-8, 5.229419300841296e-6, 6.871430336440403e-8, 5.0406374956490
56e-6, 1.6909616337911896e-6, 2.5041573614239238e-17, 0.006999806991149951,
1.9300885005015165e-7, 2.3808905244058542e-7, 4.4409098072607686e-8]
[0.013002671318851926, 0.18699194482599224, 1.049323561876941e-9, 0.027078
334037616423, 3.5965739410667507e-7, 4.2306208864328683e-7, 0.0999319171894
685, 0.3000687867967008, 0.009990985411945132, 4.426632274947438e-8, 3.1717
46958404593e-8, 8.707148755333385e-6, 1.7539884106882868e-7, 8.159542240883
362e-6, 4.282355437394482e-6, 2.1340727118370458e-17, 0.006999677462765769,
3.2253723423264374e-7, 4.2925315065526384e-7, 2.484238633415188e-7]
[0.01754950729519731, 0.18244010884103498, 1.3641806654225862e-9, 0.022563
569798023868, 3.3611627665219436e-7, 3.7150092691942174e-7, 0.0999030946222
7086, 0.30009836545416396, 0.00998725529901846, 3.9316873511644326e-8, 2.81
30812292559504e-8, 1.2231150670661027e-5, 3.3462367843417047e-7, 1.10333490
02446733e-5, 8.113770458853323e-6, 1.7782592725489358e-17, 0.00699954424491
0211, 4.5575508978909645e-7, 5.171121459997653e-7, 7.091787421818916e-7]
[0.022860661613490273, 0.17711993299100587, 1.73184571091162e-9, 0.0172953
18555603175, 3.1879075364204e-7, 3.2801759382055173e-7, 0.09986309177047625
, 0.300139895951179, 0.00998216370470338, 3.519652671198561e-8, 2.513676786
0138182e-8, 1.6956873147943384e-5, 6.25307597452982e-7, 1.4391910532463165e
-5, 1.5036821435384024e-5, 1.3630627098669301e-17, 0.0069993626630001395, 6
.373369998607806e-7, 5.03963397597307e-7, 1.6196515366685374e-6]
⋮
[0.03892999735437117, 0.1604402368867814, 2.85114929728684e-9, 0.003179560
08911747, 3.0972897811641606e-7, 2.602522819195009e-7, 0.0980811459179412,
0.30211293767372266, 0.009756427861203763, 2.885705465295251e-8, 2.05076506
54844796e-8, 0.00021451972631080356, 2.4313112175691176e-5, 2.9844862910201
526e-5, 0.0005806907027467829, 2.505845600520316e-18, 0.006991260058496229,
8.739941503769193e-6, 5.644795632194947e-7, 1.2098732180840256e-5]
[0.039731796537023946, 0.15934875795654752, 2.9100311254712643e-9, 0.00326
7839752137841, 3.0340454395221574e-7, 2.5336826978046205e-7, 0.097271594953
56082, 0.30301666850124537, 0.00965451237688205, 2.8039000119328963e-8, 1.9
914463412878598e-8, 0.0003034867246036114, 3.515693743956708e-5, 2.88433240
19763882e-5, 0.0008554038029440712, 2.575419755118674e-18, 0.00698754630755
90415, 1.2453692440956403e-5, 6.384025807352443e-7, 1.4123181732045657e-5]
[0.040943187208598346, 0.1576850912950308, 2.9989715185596e-9, 0.003403815
830366668, 2.939882096709909e-7, 2.432059982770996e-7, 0.09603188669900084,
0.3043989914914678, 0.009500566487829796, 2.6846369078838243e-8, 1.9049769
62281522e-8, 0.00043799313574801105, 5.130948964158783e-5, 2.73117729320062
4e-5, 0.0012863760972174228, 2.6825839689896286e-18, 0.0069818694756024514,
1.8130524397547305e-5, 7.249056240671434e-7, 1.6655501943851133e-5]
[0.042654561696058295, 0.15530170623580716, 3.1246155572333914e-9, 0.00360
15753045073383, 2.8144779338211706e-7, 2.2972054413184106e-7, 0.09424346935
894977, 0.30638970384396974, 0.009282897755892716, 2.528730281874828e-8, 1.
7919684520147888e-8, 0.0006285310077796074, 7.356403773398156e-5, 2.5311075
3753331e-5, 0.0019296593193905075, 2.838440343565706e-18, 0.006973700746157
927, 2.6299253842069584e-5, 8.253072617857802e-7, 1.984170187409533e-5]
[0.04479393246135517, 0.15226289464206202, 3.2817111936182302e-9, 0.003858
92228187977, 2.6689443440311687e-7, 2.1414675303509895e-7, 0.09194251648748
625, 0.3089455017411972, 0.009010154312479313, 2.352093061465373e-8, 1.6639
788243957748e-8, 0.0008681121754211703, 0.00010022359753405744, 2.305697536
117501e-5, 0.0027942306422822226, 3.0412582721411475e-18, 0.006963219960954
567, 3.678003904543005e-5, 9.43933666671727e-7, 2.388736154988901e-5]
[0.04738795813338107, 0.1484819667059184, 3.472264728946916e-9, 0.00418771
1251881557, 2.5064147986763696e-7, 1.9688141062144886e-7, 0.089048104276790
82, 0.3121528541632084, 0.00867804711899695, 2.160557990823513e-8, 1.525257
8917241284e-8, 0.0011615459187110737, 0.00013035940506834825, 2.06304824209
4911e-5, 0.003939836777778162, 3.300380405671045e-18, 0.006950068610221137,
4.9931389778860094e-5, 1.0960312398722418e-6, 2.9391473307054347e-5]
[0.05036882172710196, 0.1439934027383323, 3.691354585976077e-9, 0.00459132
2628879476, 2.3347509478876398e-7, 1.7884243007156847e-7, 0.085567492825857
56, 0.31600005342350956, 0.00829377445138549, 1.9649651821888793e-8, 1.3836
777316009929e-8, 0.0015041060231603585, 0.00016128742167467142, 1.817665814
529518e-5, 0.005401518761016489, 3.61847088517853e-18, 0.00693427969378984,
6.572030621015856e-5, 1.290602412510906e-6, 3.683937473103346e-5]
[0.053649129090393384, 0.13885256460201417, 3.932627820296831e-9, 0.005072
852559184232, 2.1601058410371068e-7, 1.6077416149742535e-7, 0.0815216555371
0297, 0.32046057172837844, 0.007866251839641075, 1.7728583902698214e-8, 1.2
447109856080338e-8, 0.0018899287966242708, 0.00018974903887604067, 1.579955
8056071188e-5, 0.007213606467836548, 3.997969816965666e-18, 0.0069159305102
837465, 8.406948971625122e-5, 1.5343174722649974e-6, 4.670824170376513e-5]
[0.05646254720110646, 0.1342484201017113, 4.139733781936766e-9, 0.00552313
9725453313, 2.0189808613188215e-7, 1.4645450805820833e-7, 0.077842495121283
02, 0.3245075304667332, 0.007494014171885701, 1.622296660463107e-8, 1.13586
63790512162e-8, 0.0022305051646554423, 0.00020871630726230074, 1.3969348737
70099e-5, 0.008964884997558832, 4.352845989436236e-18, 0.00689921972266994,
0.00010078027733005697, 1.7721521050276581e-6, 5.682962012795103e-5]
plot(sol)
plot(sol, xscale=:log10, tspan=(1e-6, 60), layout=(3,1))
Geometric Properties
Linear Ordinary Differential Equations
The simplest ordinary differential equation is the scalar linear ODE, which is given in the form
\[ u' = \alpha u \]
We can solve this by noticing that $(e^{\alpha t})^\prime = \alpha e^{\alpha t}$ satisfies the differential equation and thus the general solution is:
\[ u(t) = u(0)e^{\alpha t} \]
From the analytical solution we have that:
If $Re(\alpha) > 0$ then $u(t) \rightarrow \infty$ as $t \rightarrow \infty$
If $Re(\alpha) < 0$ then $u(t) \rightarrow 0$ as $t \rightarrow \infty$
If $Re(\alpha) = 0$ then $u(t)$ has a constant or periodic solution.
This theory can then be extended to multivariable systems in the same way as the discrete dynamics case. Let $u$ be a vector and have
\[ u' = Au \]
be a linear ordinary differential equation. Assuming $A$ is diagonalizable, we diagonalize $A = P^{-1}DP$ to get
\[ Pu' = DPu \]
and change coordinates $z = Pu$ so that we have
\[ z' = Dz \]
which decouples the equation into a system of linear ordinary differential equations which we solve individually. Thus we see that, similarly to the discrete dynamical system, we have that:
If all of the eigenvalues negative, then $u(t) \rightarrow 0$ as $t \rightarrow \infty$
If any eigenvalue is positive, then $u(t) \rightarrow \infty$ as $t \rightarrow \infty$
Nonlinear Ordinary Differential Equations
As with discrete dynamical systems, the geometric properties extend locally to the linearization of the continuous dynamical system as defined by:
\[ u' = \frac{df}{du} u \]
where $\frac{df}{du}$ is the Jacobian of the system. This is a consequence of the Hartman-Grubman Theorem.
Numerically Solving Ordinary Differential Equations
Euler's Method
To numerically solve an ordinary differential equation, one turns the continuous equation into a discrete equation by discretizing it. The simplest discretization is the Euler method. The Euler method can be thought of as a simple approximation replacing $dt$ with a small non-infinitesimal $\Delta t$. Thus we can approximate
\[ f(u,p,t) = u' = \frac{du}{dt} \approx \frac{\Delta u}{\Delta t} \]
and now since $\Delta u = u_{n+1} - u_n$ we have that
\[ \Delta t f(u,p,t) = u_{n+1} - u_n \]
We need to make a choice as to where we evaluate $f$ at. The simplest approximation is to evaluate it at $t_n$ with $u_n$ where we already have the data, and thus we re-arrange to get
\[ u_{n+1} = u_n + \Delta t f(u_n,p,t_n) \]
This is the Euler method.
We can interpret it more rigorously by looking at the Taylor series expansion. First write out the Taylor series for the ODE's solution in the near future:
\[ u(t+\Delta t) = u(t) + \Delta t u'(t) + \frac{\Delta t^2}{2} u''(t) + \ldots \]
Recall that $u' = f(u,p,t)$ by the definition of the ODE system, and thus we have that
\[ u(t+\Delta t) = u(t) + \Delta t f(u,p,t) + \mathcal{O}(\Delta t^2) \]
This is a first order approximation because the error in our step can be expressed as an error in the derivative, i.e.
\[ \frac{u(t + \Delta t) - u(t)}{\Delta t} = f(u,p,t) + \mathcal{O}(\Delta t) \]
Higher Order Methods
We can use this analysis to extend our methods to higher order approximation by simply matching the Taylor series to a higher order. Intuitively, when we developed the Euler method we had to make a choice:
\[ u_{n+1} = u_n + \Delta t f(u,p,t) \]
where do we evaluate $f$? One may think that the best derivative approximation my come from the middle of the interval, in which case we might want to evaluate it at $t + \frac{\Delta t}{2}$. To do so, we can use the Euler method to approximate the value at $t + \frac{\Delta t}{2}$ and then use that value to approximate the derivative at $t + \frac{\Delta t}{2}$. This looks like:
\[ k_1 = f(u_n,p,t)\\ k_2 = f(u_n + \frac{\Delta t}{2} k_1,p,t + \frac{\Delta t}{2})\\ u_{n+1} = u_n + \Delta t k_2 \]
which we can also write as:
\[ u_{n+1} = u_n + \Delta t f(u_n + \frac{\Delta t}{2} f_n,p,t + \frac{\Delta t}{2}) \]
where $f_n = f(u_n,p,t)$. If we do the two-dimensional Taylor expansion we get:
\[ u_{n+1} = u_n + \Delta t f_n + \frac{\Delta t^2}{2}(f_t + f_u f)(u_n,p,t)\\ + \frac{\Delta t^3}{6} (f_{tt} + 2f_{tu}f + f_{uu}f^2)(u_n,p,t) \]
which when we compare against the true Taylor series:
\[ u(t+\Delta t) = u_n + \Delta t f(u_n,p,t) + \frac{\Delta t^2}{2}(f_t + f_u f)(u_n,p,t) + \frac{\Delta t^3}{6}(f_{tt} + 2f_{tu} + f_{uu}f^2 + f_t f_u + f_u^2 f)(u_n,p,t) \]
and thus we see that
\[ u(t + \Delta t) - u_n = \mathcal{O}(\Delta t^3) \]
Runge-Kutta Methods
More generally, Runge-Kutta methods are of the form:
\[ k_1 = f(u_n,p,t)\\ k_2 = f(u_n + \Delta t (a_{21} k_1),p,t + \Delta t c_2)\\ k_3 = f(u_n + \Delta t (a_{31} k_1 + a_{32} k_2),p,t + \Delta t c_3)\\ \vdots \\ u_{n+1} = u_n + \Delta t (b_1 k_1 + \ldots + b_s k_s) \]
where $s$ is the number of stages. These can be expressed as a tableau:
The order of the Runge-Kutta method is simply the number of terms in the Taylor series that ends up being matched by the resulting expansion. For example, for the 4th order you can expand out and see that the following equations need to be satisfied:
The classic Runge-Kutta method is also known as RK4 and is the following 4th order method:
\[ k_1 = f(u_n,p,t)\\ k_2 = f(u_n + \frac{\Delta t}{2} k_1,p,t + \frac{\Delta t}{2})\\ k_3 = f(u_n + \frac{\Delta t}{2} k_2,p,t + \frac{\Delta t}{2})\\ k_4 = f(u_n + \Delta t k_3,p,t + \Delta t)\\ u_{n+1} = u_n + \frac{\Delta t}{6}(k_1 + 2 k_2 + 2 k_3 + k_4)\\ \]
While it's widely known and simple to remember, it's not necessarily good. The way to judge a Runge-Kutta method is by looking at the size of the coefficient of the next term in the Taylor series: if it's large then the true error can be larger, even if it matches another one asymptotically.
What Makes a Good Method?
Leading Truncation Coefficients
For given orders of explicit Runge-Kutta methods, lower bounds for the number of f evaluations (stages) required to receive a given order are known:
While unintuitive, using the method is not necessarily the one that reduces the coefficient the most. The reason is because what is attempted in ODE solving is precisely the opposite of the analysis. In the ODE analysis, we're looking at behavior as $\Delta t \rightarrow 0$. However, when efficiently solving ODEs, we want to use the largest $\Delta t$ which satisfies error tolerances.
The most widely used method is the Dormand-Prince 5th order Runge-Kutta method, whose tableau is represented as:
Notice that this method takes 7 calls to f for 5th order. The key to this method is that it has optimized leading truncation error coefficients, under some extra assumptions which allow for the analysis to be simplified.
Looking at the Effects of RK Method Choices and Code Optimizations
Pulling from the SciML Benchmarks, we can see the general effect of these different properties on a given set of Runge-Kutta methods:
Here, the order of the method is given in the name. We can see one immediate factor is that, as the requested error in the calculation decreases, the higher order methods become more efficient. This is because to decrease error, you decrease $\Delta t$, and thus the exponent difference with respect to $\Delta t$ has more of a chance to pay off for the extra calls to f. Additionally, we can see that order is not the only determining factor for efficiency: the Vern8 method seems to have a clear approximate 2.5x performance advantage over the whole span of the benchmark compared to the DP8 method, even though both are 8th order methods. This is because of the leading truncation terms: with a small enough $\Delta t$, the more optimized method (Vern8) will generally have low error in a step for the same $\Delta t$ because the coefficients in the expansion are generally smaller.
This is a factor which is generally ignored in high level discussions of numerical differential equations, but can lead to orders of magnitude differences! This is highlighted in the following plot:
Here we see ODEInterface.jl's ODEInterfaceDiffEq.jl wrapper into the SciML common interface for the standard dopri method from Fortran, and ODE.jl, the original ODE solvers in Julia, have a performance disadvantage compared to the DifferentialEquations.jl methods due in part to some of the coding performance pieces that we discussed in the first few lectures.
Specifically, a large part of this can be attributed to inlining of the higher order functions, i.e. ODEs are defined by a user function and then have to be called from the solver. If the solver code is compiled as a shared library ahead of time, like is commonly done in C++ or Fortran, then there can be a function call overhead that is eliminated by JIT compilation optimizing across the function call barriers (known as interprocedural optimization). This is one way which a JIT system can outperform an AOT (ahead of time) compiled system in real-world code (for completeness, two other ways are by doing full function specialization, which is something that is not generally possible in AOT languages given that you cannot know all types ahead of time for a fully generic function, and calling C itself, i.e. c-ffi (foreign function interface), can be optimized using the runtime information of the JIT compiler to outperform C!).
The other performance difference being shown here is due to optimization of the method. While a slightly different order, we can see a clear difference in the performance of RK4 vs the coefficient optimized methods. It's about the same order of magnitude as "highly optimized code differences", showing that both the Runge-Kutta coefficients and the code implementation can have a significant impact on performance.
Taking a look at what happens when interpreted languages get involved highlights some of the code challenges in this domain. Let's take a look at for example the results when simulating 3 ODE systems with the various RK methods:
We see that using interpreted languages introduces around a 50x-100x performance penalty. If you recall in your previous lecture, the discrete dynamical system that was being simulated was the 3-dimensional Lorenz equation discretized by Euler's method, meaning that the performance of that implementation is a good proxy for understanding the performance differences in this graph. Recall that in previous lectures we saw an approximately 5x performance advantage when specializing on the system function and size and around 10x by reducing allocations: these features account for the performance differences noticed between library implementations, which are then compounded by the use of different RK methods (note that R uses "call by copy" which even further increases the memory usages and makes standard usage of the language incompatible with mutating function calls!).
Stability of a Method
Simply having an order on the truncation error does not imply convergence of the method. The disconnect is that the errors at a given time point may not dissipate. What also needs to be checked is the asymptotic behavior of a disturbance. To see this, one can utilize the linear test problem:
\[ u' = \alpha u \]
and ask the question, does the discrete dynamical system defined by the discretized ODE end up going to zero? You would hope that the discretized dynamical system and the continuous dynamical system have the same properties in this simple case, and this is known as linear stability analysis of the method.
As an example, take a look at the Euler method. Recall that the Euler method was given by:
\[ u_{n+1} = u_n + \Delta t f(u_n,p,t) \]
When we plug in the linear test equation, we get that
\[ u_{n+1} = u_n + \Delta t \alpha u_n \]
If we let $z = \Delta t \alpha$, then we get the following:
\[ u_{n+1} = u_n + z u_n = (1+z)u_n \]
which is stable when $z$ is in the shifted unit circle. This means that, as a necessary condition, the step size $\Delta t$ needs to be small enough that $z$ satisfies this condition, placing a stepsize limit on the method.
If $\Delta t$ is ever too large, it will cause the equation to overshoot zero, which then causes oscillations that spiral out to infinity.
Thus the stability condition places a hard constraint on the allowed $\Delta t$ which will result in a realistic simulation.
For reference, the stability regions of the 2nd and 4th order Runge-Kutta methods that we discussed are as follows:
Interpretation of the Linear Stability Condition
To interpret the linear stability condition, recall that the linearization of a system interprets the dynamics as locally being due to the Jacobian of the system. Thus
\[ u' = f(u,p,t) \]
is locally equivalent to
\[ u' = \frac{df}{du}u \]
You can understand the local behavior through diagonalizing this matrix. Therefore, the scalar for the linear stability analysis is performing an analysis on the eigenvalues of the Jacobian. The method will be stable if the largest eigenvalues of df/du are all within the stability limit. This means that stability effects are different throughout the solution of a nonlinear equation and are generally understood locally (though different more comprehensive stability conditions exist!).
Implicit Methods
If instead of the Euler method we defined $f$ to be evaluated at the future point, we would receive a method like:
\[ u_{n+1} = u_n + \Delta t f(u_{n+1},p,t+\Delta t) \]
in which case, for the stability calculation we would have that
\[ u_{n+1} = u_n + \Delta t \alpha u_n \]
or
\[ (1-z) u_{n+1} = u_n \]
which means that
\[ u_{n+1} = \frac{1}{1-z} u_n \]
which is stable for all $Re(z) < 0$ a property which is known as A-stability. It is also stable as $z \rightarrow \infty$, a property known as L-stability. This means that for equations with very ill-conditioned Jacobians, this method is still able to be use reasonably large stepsizes and can thus be efficient.
Stiffness and Timescale Separation
From this we see that there is a maximal stepsize whenever the eigenvalues of the Jacobian are sufficiently large. It turns out that's not an issue if the phenomena we see are fast, since then the total integration time tends to be small. However, if we have some equations with both fast modes and slow modes, like the Robertson equation, then it is very difficult because in order to resolve the slow dynamics over a long timespan, one needs to ensure that the fast dynamics do not diverge. This is a property known as stiffness. Stiffness can thus be approximated in some sense by the condition number of the Jacobian. The condition number of a matrix is its maximal eigenvalue divided by its minimal eigenvalue and gives a rough measure of the local timescale separations. If this value is large and one wants to resolve the slow dynamics, then explicit integrators, like the explicit Runge-Kutta methods described before, have issues with stability. In this case implicit integrators (or other forms of stabilized stepping) are required in order to efficiently reach the end time step.
Exploiting Continuity
So far, we have looked at ordinary differential equations as a $\Delta t \rightarrow 0$ formulation of a discrete dynamical system. However, continuous dynamics and discrete dynamics have very different characteristics which can be utilized in order to arrive at simpler models and faster computations.
Geometric Properties: No Jumping and the Poincaré–Bendixson theorem
In terms of geometric properties, continuity places a large constraint on the possible dynamics. This is because of the physical constraint on "jumping", i.e. flows of differential equations cannot jump over each other. If you are ever at some point in phase space and $f$ is not explicitly time-dependent, then the direction of $u'$ is uniquely determined (given reasonable assumptions on $f$), meaning that flow lines (solutions to the differential equation) can never cross.
A result from this is the Poincaré–Bendixson theorem, which states that, with any arbitrary (but nice) two dimensional continuous system, you can only have 3 behaviors:
Steady state behavior
Divergence
Periodic orbits
A simple proof by picture shows this.