4 - Ordinary differential equations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ordinary differential equations\n",
    "\n",
    "Differential equations are the bread and butter of physics. The purists would say that theoretical modelling (that is, arriving at the differential equations through physical reasoning) is the physicists' raison d'être. Perhaps they were right some decades ago. Today, the bulk of physics (and most of science at that) is application of existing models to ever more complicated systems. This could mean solving non linear partial differential equations in arbitrary geometries. It is clear that the subset of such problems that can be attacked with only pencil and paper is a very narrow one. The world is simply too complicated to be understood analytically. \n",
    "\n",
    "Not all is lost though. We are the happy offsprings of the computer era. Many of the problems that shows us no mercy when armed with only pencil and paper offer little resistance to well coded numerical schemes. Our purpose here is to study some of the simplest and most robust of these. And then hopefully we shall also learn a thing or two about physics as well.\n",
    "\n",
    "## First order differential equations\n",
    "\n",
    "Let us consider first the simplest problem: that of a first order ODE in a n-dimensional space. \n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{d\\mathbf{x}}{dt} = \\mathbf{g}(\\mathbf{x}, t)\n",
    "\\end{equation}\n",
    "where $\\mathbf{x}$ and $\\mathbf{g}$ are written in boldface to highlight their vector nature:   \n",
    "\n",
    "\\begin{equation}\n",
    "\\mathbf{x}(t) = \\big(x^0(t), x^1(t),...,x^{m-1}(t)\\big), \\qquad \\mathbf{g}(\\mathbf{x}(t), t) = \\Big(g^0\\big(\\mathbf{x}(t),t\\big), g^1\\big(\\mathbf{x}(t),t\\big), ...,g^{m-1}\\big(\\mathbf{x}(t),t\\big)\\Big).\n",
    "\\end{equation}\n",
    "\n",
    "Although it might seem at first sight that restricting ourselves to first order differential equations is too strong an impediment, the problem we are tackling here is actually very broad. Just consider how [Hamilton's trick](https://en.wikipedia.org/wiki/Hamiltonian_mechanics) takes us from a system of second order differential equations in spacetime to a doubled system of first order differential equations in [phase space](https://en.wikipedia.org/wiki/Phase_space). Such redefinition of higher derivatives into new dynamical variables is a useful tool that we shall illustrate soon. \n",
    "\n",
    "At first, we shall look at this problem as an initial-value problem, meaning that our first order ODE is complemented by the initial condition\n",
    "\n",
    "\\begin{equation}\n",
    "\\mathbf{x}(t_0) = \\mathbf{x}_0.\n",
    "\\end{equation}\n",
    "\n",
    "## The Euler method\n",
    "\n",
    "Assume we are given an array of instants of time $t$ and another one with the corresponding values of position $x$. We do not bother here to consider $x$ a vector, since the following discussion can be trivially extended to that case. We thus have\n",
    "\n",
    "\\begin{equation}\n",
    "x(t_0) = x_0, \\quad x(t_1) = x_1, \\quad..., \\quad x(t_{l-1}) = x_{l-1}\n",
    "\\end{equation}\n",
    "\n",
    "where the length of both arrays is $l$. Computing discrete approximations of the differential equation is easy peasy:\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{dx}{dt}\\big|_i = g_i \\approx \\frac{x_{i+1} - x_i}{t_{i+1} - t_i}\n",
    "\\end{equation}\n",
    "\n",
    "where we have defined another array that stores the values of $g$\n",
    "\n",
    "\\begin{equation}\n",
    "g(x_0,t_0) = g_0,\\quad g(x_1,t_1) = g_1,\\quad ...,\\quad g(x_{l-1}, t_{l-1}) = g_{l-1}.\n",
    "\\end{equation}\n",
    "\n",
    "Since our goal is to numerically solve the ODE, we use the last equation to retrieve the values of $x_i$ at different times $t_i$. Thus we write \n",
    "\n",
    "\\begin{equation}\n",
    "x_{i+1} \\approx x_i+ g_i(t_{i+1} - t_i).\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Exercise 1. Using the Euler method to solve the harmonic oscillator.\n",
    "\n",
    "Let us implement the Euler method together with Hamilton's trick to solve the harmonic oscillator numerically. The harmonic oscillator ODE is\n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{d^2x}{dt^2} + \\omega^2x = 0\n",
    "\\end{equation}\n",
    "\n",
    "where $\\omega$ is the angular frequency. Here our dynamic variables are the position of the particle $x$ and its momentum $p = \\frac{dx}{dt} = \\dot{x}$. Thus the equation above can be written as a system of two ODES,\n",
    "\n",
    "\\begin{equation}\n",
    "\\dot{x} = p\\\\\n",
    "\\dot{p} = -\\omega^2 x.\n",
    "\\end{equation}\n",
    "\n",
    "We can write the harmonic oscillator ODE as \n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{d}{dt}(x,p) = (p, -\\omega^2 x).\n",
    "\\end{equation}\n",
    "\n",
    "Now applying Euler's method, we get\n",
    "\n",
    "\\begin{equation}\n",
    "x_{i+1} \\approx x_i + p_i(t_{i+1} - t_i)\\\\\n",
    "p_{i+1} \\approx p_i -\\omega^2(t_{i+1} - t_i)\n",
    "\\end{equation}\n",
    "\n",
    "The code written below is incomplete. Fill in the missing steps. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Picard method\n",
    "\n",
    "After solving the exercise above, it should be clear that the Euler method isn't actually the best way to solve and EDO numerically. The reason is that it uses first order approximations to the derivatives. According to [Taylor's theorem](https://en.wikipedia.org/wiki/Taylor%27s_theorem), we can approximate a $k+1$-differentiable function by it's $k$-th order Taylor polynomial,\n",
    "\n",
    "\\begin{equation}\n",
    "f(t) = f(t_0) + f'(t_0)(t-t_0) + \\frac{f''(t_0)}{2!}(t-t_0)^2 + ... + \\frac{f(t_0)^{(k)}}{k!}(t-t_0)^k + \\frac{f^{(k+1)}(\\xi)}{(k+1)!}(\\xi-t_0)^{k+1}\n",
    "\\end{equation}\n",
    "\n",
    "where $\\xi$ lies between $x$ and $t_0$. We thus expect errors of order $O(\\tau^{k+1})$, where $\\tau\\approx t-t_0$. Thus after $n$ steps we can expect an accumulated error of the order $nO(\\tau^{k+1})$. Since $k = 1$ for the Euler method, we might quickly loose track of the real solution unless $\\tau$ is very small. This is why the Euler method is actually almost never used. \n",
    "\n",
    "Let us try to find other computational schemes based on the analytical solution,\n",
    "\n",
    "\\begin{equation}\n",
    "x(t) = x_0 + \\int_{t_0}^tg(x,t')dt'\n",
    "\\end{equation}\n",
    "\n",
    "The idea is clear: since we know $x_0$ and $g(x,t)$, in principle all we need to do is to use a quadrature scheme to compute the integral numericaly. Not so fast though. When we discretize this equation, we get\n",
    "\n",
    "\\begin{equation}\n",
    "x_{i+j} = x_i + \\int_{t_i}^{t_{i+j}}g(x,t)dt\n",
    "\\end{equation}\n",
    "\n",
    "and indeed the Euler method is trivially recovered by taking $j = 1$ and substituting $g(x,t) = g_i$. We thus see where the weakness of Euler's method stems from: it is based on the poorest of all quadrature schemes! But now it is also clear that we have a problem. Suppose we want to use the [trapezoidal rule](https://en.wikipedia.org/wiki/Trapezoidal_rule) to compute the integral above. Although not very sofisticated, it is already an improvement: instead of taking $g(x,t) = g_i$, we now approximate $g$ as $\\frac{g_{i+1} + g_i}{2}$, so we end up with \n",
    "\n",
    "\\begin{equation}\n",
    "x_{i+1} = x_i + \\frac{g_i +g_{i+1}}{2}\\tau.\n",
    "\\end{equation}\n",
    "\n",
    "But $g_{i+1} = g(x_{i+1},t_{i+1})$, and we don't know $x_{i+1}$ yet. One way to bypass this problem is to use a [fixed-point iteration](https://en.wikipedia.org/wiki/Fixed-point_iteration), which goes by the name of Picard method among numerical analysis enthusiasts. It usually works pretty well, and consists in performing the recursion\n",
    "\n",
    "\\begin{equation}\n",
    "x_{i+1,0} = x_i\\\\\n",
    "x_{i+1,j+1} = x_{i,j} + \\frac{g_i + g_{i + 1,j}}{2}\\tau.\n",
    "\\end{equation}\n",
    "\n",
    "a certain number of times."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Exercise 2. The logistic differential equation.\n",
    "\n",
    "The [logistic function](https://en.wikipedia.org/wiki/Logistic_function), also known as the sigmoid curve, is defined as\n",
    "\n",
    "\\begin{equation}\n",
    "x(t) = \\frac{L}{1+\\text{e}^{-\\omega(t-t_0)}}.\n",
    "\\end{equation}\n",
    "\n",
    "It is ubiquitous in applied mathematics, ranging from artificial neural networks to sociology. In physics, it is known as the [Fermi-Dirac statistics](https://en.wikipedia.org/wiki/Fermi%E2%80%93Dirac_statistics). \n",
    "\n",
    "One intuitive way to view this function is to derive it as the solution of the first order non-linear ODE \n",
    "\n",
    "\\begin{equation}\n",
    "\\frac{dx}{dt} = x(1-x)\n",
    "\\end{equation}\n",
    "\n",
    "with boundary condition $x(0) = x_0 = \\frac{1}{2}$. The above ODE can be seen as a model for population growth in which the relative change in population is proportional to both the current population $x$ and the available resources $1-x$ in the environment. \n",
    "\n",
    "The code below uses the Picard method to numerically solve the logistic differential equation. Fill in the remaining steps.   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Runge-Kutta method.\n",
    "\n",
    "We now introduce the industry standard [Runge-Kutta method](https://en.wikipedia.org/wiki/Runge%E2%80%93Kutta_methods). Its advantage is that it uses a clever strategy to improve accuracy through a series of first order approximations of the function $x(t)$. As we shall see, this is accomplished by evaluating $g(x,t)$ at several points, in opposition to evaluating higher order derivatives of $g$ at the same point.  One of the nice things about the Runge-Kutta method is that it doesn't demand extra data to work. This is a big plus, since in most dynamical problems we are only given a single initial condition. \n",
    "\n",
    "Again our starting point will be Taylor's expansion. For the sake of clarity and brevity, let us use the Runge-Kutta method of order 2 as a proxy. It starts from the second order Taylor expansion,\n",
    "\n",
    "\\begin{equation}\n",
    "x(t + \\tau) = x(t) + \\tau x'(t) + \\frac{1}{2}\\tau^2x''(t) + O(\\tau^3).\n",
    "\\end{equation}\n",
    "\n",
    "Now remember that we are given the following data, that actually specify the initial value problem we want to solve:\n",
    "\n",
    "\\begin{equation}\n",
    "x'(t) = g(x,t), \\qquad x(t_0) = x_0.\n",
    "\\end{equation}\n",
    "\n",
    "The idea then is to use a Taylor expansion of $g(x,t)$ to substitute $x'(t)$ and $x''(t)$. This leads us to the followinyg equation.\n",
    "\n",
    "\\begin{equation}\n",
    "x(t + \\tau) = x + \\tau g + \\frac{1}{2}\\tau^2(g_xg + g_t) + O(\\tau^3),\n",
    "\\end{equation}\n",
    "\n",
    "where $g_x(x,t)$ and $g_t(x,t)$ are the partial derivatives of $g$ with respect to $x$ and $t$, respectively.\n",
    "\n",
    "Now observe the following. Instead of using the usual Taylor expansion of $x$ at a given order, we can try to make successive first order approximations. For example, the first order approximation for $x(t + \\tau)$ is simply\n",
    "\n",
    "\\begin{equation}\n",
    "x(t + \\tau) \\approx x(t) + \\alpha_1h_1\n",
    "\\end{equation}\n",
    "\n",
    "with $\\alpha_1 = 1$ and $h_1 = \\tau g = \\tau \\frac{dx}{dt}$. Note that we are using the quantity $\\tau g$ a \"standard\" first order variation in $x$. If we stopped here, we would just recover Euler's method. So let us carry on. To the next order we write\n",
    "\n",
    "\\begin{equation}\n",
    "x(t + \\tau) \\approx x(t) + \\alpha_1h_1 + \\alpha_2h_2\n",
    "\\end{equation}\n",
    "\n",
    "where \n",
    "\n",
    "\\begin{equation}\n",
    "h_1 = \\tau g(x,t) \\qquad\\text{ and}\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "h_2 = \\tau g(x + \\nu_{21}h_1, t + \\nu_{21}\\tau).\n",
    "\\end{equation}\n",
    "\n",
    "If we now Taylor expand $h_2$ we end up with\n",
    "\n",
    "\\begin{equation}\n",
    "x(t+\\tau) \\approx x(t) + (\\alpha_1 + \\alpha_2)g\\tau + \\alpha_2\\nu_{21}(g_xg+g_t)\\tau^2\n",
    "\\end{equation}\n",
    "\n",
    "which must be compared with our original Taylor Expansion in equation (???). Such comparison leads us to the following equations\n",
    "\n",
    "\\begin{equation}\n",
    "\\alpha_1 + \\alpha_2 = 1\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "\\alpha_2\\nu_{21} = \\frac{1}{2}\n",
    "\\end{equation}\n",
    "\n",
    "An interesting feature of the Runge-Kutta method is that the choice of parameters is not unique, since we have more parameters than constraints. \n",
    "A particularly symmetric solution is $\\nu_{21} = 1$, $\\alpha_1 = \\alpha_2 = \\frac{1}{2}$, for which $x(t+\\tau)$ is approximated as \n",
    "\n",
    "\\begin{equation}\n",
    "x(t + \\tau) \\approx x(t) + \\frac{\\tau}{2}\\Big(g\\big(x(t),t\\big) +   g\\big(x(t)+\\tau g(x,t), t + \\tau\\big)\\Big).\n",
    "\\end{equation}\n",
    "\n",
    "As we can see, this choice corresponds to taking the approximated average of $x'(t)$ at $t$ and $t + \\tau$ and using it in the first order Taylor formula. Also note that we have accomplished to substitute the evaluation of partial derivatives of $g$ at the same point by the evaluation of $g$ itself at two different points. This hallmark of the Runge-Kutta method makes its implementation very easy. To illustrate this point, consider the widely used Runge-Kutta method of order 4, which is given by the following set of equations.\n",
    "\n",
    "\\begin{equation}\n",
    "x(t + \\tau) = x(t) + \\frac{1}{6}(c_1 + 2c_2 + 2c_3 + c_4)\n",
    "\\end{equation}\n",
    "\n",
    "where\n",
    "\n",
    "\\begin{equation}\n",
    "c_1 = \\tau g(x,t), \n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "c_2 = \\tau g\\big(x + \\frac{c_1}{2}, t + \\frac{\\tau}{2}\\big),\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "c_3 = \\tau g\\big(x + \\frac{c_2}{2}, t + \\frac{\\tau}{2}\\big)\n",
    "\\end{equation}\n",
    "\n",
    "\\begin{equation}\n",
    "c_4 = \\tau g(x + c_3, t + \\tau).\n",
    "\\end{equation}\n",
    "\n",
    "You can check that this choice of parameters leads to a correct Taylor expansion of $x(t)$ to the fourth order. \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3. The Duffing oscillator."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}