Initial value problems (IVP) for ordinary differential equation (ODE)

In standard form

$u' = f(u,t)$

could represent system of equations (i.e. $u$ vector).

Discretize time in steps of size $k$ (timestep).

See notes from Oxford course here

Numerical methods (finite difference discretization methods, similar to Finite element methods):

• Multi-stage. Runge-Kutta methods: 1 step, i.e. only neighbouring grid points.
  • Euler method
  • Modified Euler method. Accuracy $O(k^2)$
  • Fourth order Runge-Kutta. Accuracy $O(k^4)$
• Multi-step. Adams-Bashforth. Uses points n steps away in grid. Drawback: they are tricky to start up because extra values are needed.
  • 1st order. Called (forward) Euler formula. Accuracy $O(k)$
  • 2nd order. Accuracy $O(k^2)$
  • etc.

All of these methods have explicit and implicit variants

IVP codes in MATLAB

ode23: low-order RK ode45: higher-order RK ode113: variable-order multistep ode23s, ode15s, ode15i, ode23t, ode23tb variants for stiff problems etc.

In Chebfun

N = chebop(a,b) % define the interval [a,b]

N.op = @(x,u) ... % define the ODE, with diff(u,k) = kth derivative of u

N.bc = ... % boundary conditions

Order of accuracy, convergence, stability, etc.

See here for explanation of local truncation error (LTE), used to find order of accuracy (what we call accuracy above, $O(k^2)$, i.e. error decreases with the square of the time step.

Convergence and Stability

Theory of convergence of multistep formulas by Dahlquist (1956). Analogs for RK too.

Key definitions:

consistent: order of accuracy > 1.

stable: if for f(t,u) = 0 all the solutions are bounded.. I.e. does error grow or stay bounded.. See here too.

convergent: $v\rightarrow u$ for each fixed $t$ as $k \rightarrow 0$ (ignoring rounding errors, from computing..).

Dahlquist equivalence theorem:

The Adams formulas are consistent and stable, hence convergent

Adaptive ODE codes adapt step size and other parameters so that estimated errors (using methods above, like LTE) are smaller than a prescribed value.

Chaos and Lyapunov exponents. The Lorenz equations. Sinai billiards is another famous chaotic system.

Stability regions regions of $ka$ space ($a$ is a parameter in the model ode, a=0 corresponds to f=0, as defined above for stability, I guess here we are being more general..) in which solutions remain bounded (this is achieved when characteristic polynomial of the recurrence relation, obtained by the finite difference method, has roots with $|r| \leq 1$ and any root $|r|=1$ is simple). See here too.

Stiffness. A stiff ODE is one with widely varying time scales. One may need very small $k$ because there are modes with $ka$ (i.e. part of equation which create behaviour corresponding to certain $a$ value) outside stability region, even if our solution of interest has effective $ka$ inside it.

This is manifested as our solution changing on a long timescale, but depending on short time-scale terms in equation.

Solution: backward-differentiation formulas, or implicit formulas, that include $f(v_{n+1}, t_{n+1})$, unlike explicit formulas. (Implicit numerical method)

These require solving a (generally) nonlinear equation (or a system of equations for PDEs). And this may need to be solved numerically itself often, for example by Newton's method.

Aside. We've been discussing IVPs here only.

Boundary value problems (BVP) also important. Nonlinear BVP may not have unique solutions! (unlike IVP).

Can use chebfun to solve.

Numerical methods for PDEs

• Finite element methods for complex geometries
• Finite volume methods for Hyperbolic geometry
• Finite difference method for simple geometry.

Books:

Griffiths & Higham, 2010 - introduction to numerical ODE

Iserles, 2009 - includes connection to PDEs

LeVeque, 2007 - likewise

Hairer, Norsett & Wanner I & II - authoritative; full of fun and historical remarks

Ascher & Petzold 1998 - also includes DAEs (differential-algebraic equations, which combine ODEs and nonlinear eqs)

Deuflhard & Bornemann, 2002

Trefethen, old online textbook (http://people.maths.ox.ac.uk/trefethen/pdetext.html)