Skip to content

Integrator

Solving a Differential Equation#Ordinary Differential Equation (ODE) that has no analytical solution requires numerical methods, that allow for the discretization of the ODE. Different methods are available, that trade off computational complexity, accuracy and stability. These methods are called integrators.

Integrators can follow different schemes:

  • Explicit Scheme Integrator is a function that involves only information known at the current time-step.
    • Form: \(y_{n+1}=y_{n}+\Delta t \cdot f(t_{n}, y_{n})\)
    • Pro: These are typically very fast and easy to implement.
    • Con: Not flexible enough for fast-changing ODEs, large time-steps lead to value explosions.
  • Implicit Scheme: Integrator is a function that involves information from the next time-step.
    • Form: \(y_{n+1}=y_{n}+\Delta t \cdot f(t_{n+1}, y_{n+1})\)
    • Pro: Much more stable, allow for large time-steps-
    • Con: Comptationally expensive, requires Root-finding Algorithm at every step.
  • Implicit-Explicit Scheme: Integrator for systems that are separable into two coupled ODEs. The easier sub-system can be solved implicitely, the more complex sub-system explitely based on the approximation of the first system. They offer a trade-off between explitor implicit-only methods.
    • Form: \(\frac{dy}{dt}=f_{EX}(t_{n}, y_{n})+f_{IM}(t_{n+1}, y_{n+1})\)

Explicit Schemes

Forward Euler

Basic iterative scheme for approximating an ODE. It starts with a given value \(y_{0}\) takes small steps of size \(h\) along the slope of the ODE:

\[y_{n+1}=y_{n}+h\cdot f(t_{n}, y_{n})\]

This method is very stiff for large \(h\), making the method cheap to compute per step, but expensive due to the dense discretization required for high accuracy.

Runge-Kutta 4

A four-step discretization scheme: 1. \(k_1\): Slope at the start using \(y_n\). 2. \(k_2\): Slope at the midpoint using \(y_n\) displaced by \(k_1\). 3. \(k_3\): Slope at the midpoint using \(y_n\) displaced by \(k_2\). ("correction" step). 4. \(k_4\): Slope at the end (\(t_n + h\)) using \(y_n\) displaced by \(k_3\).

The next point is estimated using a weighted average of all \(k\):

\[y_{n+1}=y_{n}+\frac{h}{6}(k_{1}+2k_{2}+2k_{3}+k_{4})\]

The slope-estimates at the half-steps are weighted double. This method achieves a much higher accuracy per step. So while the per-step costs are higher, it compensates by allowing for larger step-sizes.

Implicit Schemes

Backward Euler

Similar to the #Forward Euler but using the slope of the next time-step to perform the step:

\[y_{n+1}=y_{n}+h\cdot f(t_{n+1}, y_{n+1})\]

Since \(y_{n+1}\) is unkown and on both sides, this requires solving the equation with a Root-finding Algorithm like Newton's method.

Crank-Nicolson

Combination of #Forward Euler and #Backward Euler, using the arithmetic mean of both estimations for the next step approximation.

\[ y_{n+1}=y_{n}+\frac{h}{2}[f(t_{n},y_{n})+f(t_{n+1},y_{n+1})] \]

Because it is centered in time, this is a 2nd-order integrator and the error drops quadratically with decreasing step-size.

Implicit-Explicit Schemes

Forward-Backward Euler (Symplectic Euler)

This method can be applied to separable systems, i.e. you can split the ODE into two other ODEs, where the second one depends on the first. For example, a second-order system like the acceleration of a particle \(\ddot{x}=a(x)\) can be separated into two first-order systems \(\dot{x}=v,\dot{v}=a(x)\). Now we can solve the second ODE explicitely and the first ODE implicitely:

\[ \begin{align} v_{n+1} &= v_{n}+h\cdot a(x_{n}) \\ x_{n+1} &= x_{n}+h\cdot v_{n+1} \end{align} \]

While the second integrator is implicit, it uses the approximation of the first explicit integrator, so no root-finding algorithm is required.

This integrator is symplectic, meaning it conserves the energy Hamiltonian the system and the magnitude doesn't explode or vanish due to numerical errors over time.