{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "virtual-vision",
   "metadata": {},
   "source": [
    "# Initial Value Problems for Ordinary Differential Equations, Part 3: Global Error Bounds for One Step Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fewer-shelter",
   "metadata": {},
   "source": [
    "**Updated on March 31** (with some references added on April 14)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "exempt-throw",
   "metadata": {},
   "source": [
    "**References:**\n",
    "\n",
    "- Section 6.2.1 *Local and global truncation error* of [Sauer](../references.html#Sauer)\n",
    "- Section 5.2 *Euler's Method* of [Burden&Faires](../references.html#Burden-Faires),\n",
    "the subsection *Error Bounds for Euler’s Method* .\n",
    "- Sections 7.1 and 7.2 of [Chenney&Kincaid](../references.html#Chenney-Kincaid)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "reverse-custom",
   "metadata": {},
   "source": [
    "All the methods seen so far for solving ODE IVP's are *one-step methods*:\n",
    "they fit the general form\n",
    "\n",
    "$$\n",
    "U_{i+1} = F(t_i, U_i, h)\n",
    "$$\n",
    "\n",
    "For example, Euler's Method has\n",
    "\n",
    "$$\n",
    "F(t, U, h) = U + h f(t, U),\n",
    "$$\n",
    "\n",
    "the Explicit Midpoint Method (Modified Euler) has\n",
    "\n",
    "$$\n",
    "F(t, U, h) = U + h f(t+h/2, U + hf(t, U)/2)\n",
    "$$\n",
    "\n",
    "and even the Runge-Kutta method has a similar form, but it is long and ugly."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dated-bracelet",
   "metadata": {},
   "source": [
    "For these, there is a general result that gives a bound on the globl truncation error (\"GTE\") once one has a suitable bound on the local truncation error (\"LTE\").\n",
    "This is very useful, because bounds on the LTE are usually far easier to derive."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "declared-motel",
   "metadata": {},
   "source": [
    "**Theorem**\n",
    "\n",
    "**IF**, when solving the ODE IVP\n",
    "\n",
    "$$\n",
    "\\frac{d u}{d t} = f(t, u),\\quad u(a) = u_0\n",
    "$$\n",
    "\n",
    "on interval $t \\in [a, b]$ by a one step method\n",
    "\n",
    "one has a bound on the local truncation error\n",
    "\n",
    "$$\n",
    "|e_i| = |U_{i+1} - u(t_i+h; t_i, U_i) = |F(t_i, U_i, h) - u(t_i + h; t_i, U_i)| \\leq Ch^{p+1} = O(h^{p+1})\n",
    "$$\n",
    "\n",
    "and the ODE itself satisfies the *Lipschitz Condition* that for some constant $K$,\n",
    "\n",
    "$$\n",
    "\\left| \\frac{\\partial F}{\\partial u}(t, u) \\right| \\leq K \n",
    "$$\n",
    "\n",
    "**THEN**\n",
    "there is a bound on the global truncation error:\n",
    "\n",
    "$$\n",
    "| E_i | = |U_i - u(t_i; a, u_0)| \\leq C \\frac{e^{K (t_i - a)} - 1}{k} h^p, = O(h^p)\n",
    "$$\n",
    "\n",
    "So yet again, there is a loss of one factor of $h$ in going from local to global error,\n",
    "as first seen with the composite rules for definite integrals."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "adjusted-nature",
   "metadata": {},
   "source": [
    "We saw a glimpse of this\n",
    "for Euler's method,\n",
    "in the section\n",
    "[Solving Initial Value Problems for Ordinary Differential Equations, Part 1](ODE-IVP-1-basics-and-Euler-python.ipynb),\n",
    "where the Taylor's Theorem error formula canbe used to get the LTE bound\n",
    "\n",
    "$$ |e_i| \\leq C h^2 \\text{ where } C = \\frac{|u_0 e^{K(b - a)}|}{2} $$\n",
    "\n",
    "and this leads to to GTE bound\n",
    "\n",
    "$$\n",
    "| E_i | \\leq \\frac{|u_0 e^{K(b - a)}|}{2} \\frac{e^{K (t_i - a)} - 1}{k} h.\n",
    "$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "alike-spectrum",
   "metadata": {},
   "source": [
    "The essence of why it is true is that the Lipshitz condition limits the growth rate of solutions to be no faster than for $du/dt = KU$,\n",
    "and then the \"compounding of errors\" is no fast than for that equation, so the argument in\n",
    "[Solving Initial Value Problems for Ordinary Differential Equations, Part 1](ODE-IVP-1-basics-and-Euler-python.ipynb)\n",
    "for getting from a bound on the local trunctation error to a bound on the global truncation error works again with just sight modification."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "hawaiian-indiana",
   "metadata": {},
   "source": [
    "## Order of accuracy for the basic Runge-Kutta type mehods\n",
    "\n",
    "- For Euler's method, it was stated in section\n",
    "[Solving Initial Value Problems for Ordinary Differential Equations, Part 1](ODE-IVP-1-basics-and-Euler-python.ipynb),\n",
    "(and verified for the test case of $du/dt = ku$)\n",
    "that the local truncation error is second order, $O(h^2)$, and (thus)\n",
    "the global truncation error isfirst order: $O(h)$:\n",
    "\n",
    "- The Explicit (and Implicit) Trapezoid and Midpoint methods, have local truncation error $O(h^3)$\n",
    "and so their global truncation error is $O(h^2)$ — they are second order accurate, just as for the corresponding approximate integration rules.\n",
    "\n",
    "- The classical Runge-Kutta method, has local truncation error $O(h^4)$\n",
    "and so its global truncation error is $O(h^4)$ — just as for the composie Simpson's Rule."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "gothic-retention",
   "metadata": {},
   "source": [
    "---\n",
    "This work is licensed under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/)"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}