01_02_higher_order_methods.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Higher order: Taylor’s series\n",
    "-----------------------------\n",
    "\n",
    "We can go a step beyond Euler’s method keeping up to second order terms\n",
    "in the expansion around $x_0$. Doing so we obtain\n",
    "$$y(x+\\Delta x)=y(x)+y'(x)\\Delta x+\\frac{1}{2}y''(x)(\\Delta x)^2+O(\\Delta \n",
    "x^3)\n",
    "$$ from the ODE we get $$\\begin{eqnarray}\n",
    "y'(x)&=&f(x,y), \\\\\n",
    "y''(x)&=&\\frac{df}{dx}=\\frac{\\partial f}{\\partial x}+\\frac{\\partial \n",
    "f}{\\partial y}\\frac{dy}{dx}=\\frac{\\partial f}{\\partial \n",
    "x}+\\frac{\\partial f}{\\partial y} f \\end{eqnarray}$$\n",
    "\n",
    "Substituting in the Taylor expansion we obtain\n",
    "\n",
    "$$y_{n+1}=y_n+f\\Delta x+\\frac{1}{2}(\\Delta x)^2[\\frac{\\partial \n",
    "f}{\\partial x}+f\\frac{\\partial f}{\\partial y}]+O(\\Delta x^3),$$\n",
    "\n",
    "where all the functions and derivatives are evaluated in $(x_n,y_n)$.\n",
    "\n",
    "Multistep or Predictor-Corrector methods\n",
    "----------------------------------------\n",
    "\n",
    "We can achieve higher accuracy by relating $y_{n+1}$ not only to $y_n$,\n",
    "but also to points further in the past $y_{n-1},y_{n-2},...$ To derive\n",
    "such formulas we can formally integrate exactly the equation of motion to obtain:\n",
    "$$y_{n+1}=y_n+\\int_{x_n}^{x_{n+1}}f(x,y)dx$$\n",
    "\n",
    "The problem is that we don’t know $f(x,y)$ over the interval\n",
    "$(x_n,x_{n+1})$. However, we can use the values of $y$ at $x_n$ and\n",
    "$x_{n-1}$ to provide a linear extrapolation:\n",
    "$$f=\\frac{(x-x_{n-1})}{\\Delta x}f_n-\\frac{(x-x_n)}{\\Delta x} \n",
    "f_{n-1}+O(\\Delta x^2),$$ with $f_n=f(x_n,y_n)$. Inserting into\n",
    "the integral we obtain\n",
    "$$y_{n+1}=y_n+\\Delta x(\\frac{3}{2}f_n-\\frac{1}{2}f_{n-1})+O(\\Delta x^3)$$\n",
    "Note that the value of $y_0$ is not sufficient information to get this\n",
    "algorithm started. The value of $y_1$ has to be obtained first by some\n",
    "other procedure, like the ones described previously. This means that the\n",
    "method is not **\"self starting\"**.\n",
    "\n",
    "Runge-Kutta methods\n",
    "-------------------\n",
    "\n",
    "### 2nd order Runge-Kutta\n",
    "\n",
    "Euler’s method rests on the idea that the slope at one point can be used\n",
    "to extrapolate to the next. A plausible idea to make a better estimate\n",
    "of the slope is to extrapolate to a point halfway across the interval,\n",
    "and then to use the derivative at this point to extrapolate across the\n",
    "whole interval. Thus,\n",
    "\n",
    "$$\\begin{eqnarray}\n",
    "k&=&\\Delta x f(x_n,y_x), \\\\\n",
    "y_{n+1}&=&y_n+\\Delta x f(x+\\Delta x/2, y_n+k/2) + O(\\Delta \n",
    "x^3).\\end{eqnarray}$$\n",
    "\n",
    "It has the same accuracy as the Taylor series. It requires\n",
    "the evaluation of $f$ twice for each step.\n",
    "\n",
    "### 4th order Runge-Kutta\n",
    "\n",
    "Similar ideas can be used to derive a 3rd or 4th order Runge-Kutta\n",
    "method. It has been found by experience that the best balance between\n",
    "accuracy and computational effort is given by a fourth-order algorithm.\n",
    "Such a method would require evaluating $f$ four times at each step, with\n",
    "a local accuracy of $O(\\Delta x^5)$. It can be written as follows:\n",
    "$$\\begin{eqnarray}\n",
    " k_1&=&\\Delta x f(x_n,y_n), \\\\\n",
    " k_2&=&\\Delta x f(x_n+\\Delta x/2,y_n+k_1/2), \\\\\n",
    " k_3&=&\\Delta x f(x_n+\\Delta x/2,y_n+k_2/2), \\\\\n",
    " k_4&=&\\Delta x f(x_n+\\Delta x,y_n+k_3), \\\\\n",
    " y_{n+1}&=&y_n+\\frac{1}{6}(k_1+2k_2+2k_3+k_4)+O(\\Delta x^5).\\end{eqnarray}$$\n",
    "\n",
    "Runge-Kutta method are self-starting, meaning that they can be used to\n",
    "obtain the first few iterations for a non self-starting algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Challenge 1.2\n",
    "\n",
    "Repeat the calculation in Challenge 1.1 using 4th order Runge-Kutta"
   ]
  }
 ],
 "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.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}