{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "f05c6135-6039-4ba8-8728-228a62ddace3",
   "metadata": {},
   "source": [
    "# A Global Error Bound for One Step Methods"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "910acf0e-cd66-459b-9f39-f7be14ad9e30",
   "metadata": {},
   "source": [
    "**References:**\n",
    "\n",
    "- Subection 6.2.1 *Local and global truncation error* in {cite}`Sauer`.\n",
    "- Section 5.2 *Euler's Method* in {cite}`Burden-Faires`.\n",
    "- Section 8.5 of {cite}`Kincaid-Chenney`"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f2da3c6-c341-4f1c-bd2b-d348c9db5698",
   "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": "conditional-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": "fossil-bristol",
   "metadata": {},
   "source": [
    "```{prf:theorem}\n",
    ":label: odeivp-onestep-order-of-global-error\n",
    "\n",
    "When solving the ODE IVP\n",
    "\n",
    "$$ du/dt = f(t, u),\\quad u(a) = u_0 $$\n",
    "\n",
    "on interval $t \\in [a, b]$ by a one step method,\n",
    "one has a bound on the local truncation error\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",
    "and the ODE itself satisfies the *Lipschitz Condition* that for some constant $K$,\n",
    "\n",
    "$$ \\left| \\frac{\\partial F}{\\partial u}(t, u) \\right| \\leq K  $$\n",
    "\n",
    "then there is a bound on the global truncation error:\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",
    "\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": "lesbian-liver",
   "metadata": {},
   "source": [
    "We saw a glimpse of this\n",
    "for Euler's method,\n",
    "in the section [Basic Concepts and Euler's Method](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": "diagnostic-measure",
   "metadata": {},
   "source": [
    "## Order of accuracy for the basic Runge-Kutta type methods\n",
    "\n",
    "- For Euler's method, it was stated in section [Basic Concepts and Euler's Method](ODE-IVP-1-basics-and-Euler-python.ipynb),\n",
    "(and verified for the test case of $du/dt = ku$)\n",
    "that the global truncation error is of first order n step-size $h$:\n",
    "\n",
    "- The Explicit (and Implicit) Trapezoid and Midpoint rules, the local truncation error is $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^5)$ and so its global truncation error is $O(h^4)$ — just as for the composite Simpson's Rule, to which it corresponds for the \"integration\" case $dy/dt = f(t)$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.8.1",
   "language": "julia",
   "name": "julia-1.8"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}