05_convergence.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "<table>\n",
    " <tr align=left><td><img align=left src=\"./images/CC-BY.png\">\n",
    " <td>Text provided under a Creative Commons Attribution license, CC-BY. All code is made available under the FSF-approved MIT license. (c) Kyle T. Mandli</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "import numpy\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from clawpack import pyclaw\n",
    "from clawpack import riemann"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Convergence, Accuracy, and Stability"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "For real world problems in science and engineering it is often difficult to find true solutions of any complexity (or at all).  Instead we rely on a process called **Verification and Validation** or **V&V**.  This refers to a two step process rougly described by the following.\n",
    " - **Verification** is the theoretical analysis including convergence and accuracy showing that a chosen numerical method performs as expected.  \n",
    " - **Validation** is the process of comparing the numerical solution obtained from a numerical method on a test problem, either analytical or observed or experimental data.\n",
    " \n",
    "We will concentrate on the former but the entire process V&V is important."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Convergence\n",
    "\n",
    "The first step in our discussion is to establish a form of error.  For finite differences the point-wise values are often used and differenced from the true point-wise values.  For finite volume methods it is much more natural to use cell-wise averages."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let $q(x, t_n)$ be the true solution evaluated at time $t_n$.  Define\n",
    "$$\n",
    "    q^n_i = \\frac{1}{\\Delta x} \\int_{\\mathcal{C}_i} q(x, t_n) dx\n",
    "$$\n",
    "as the exact cell-average then.  Note that for q(x, t_n) sufficiently smooth the point-wise evaluation at cell centers and the cell-averages will will agree to $\\mathcal{O}(\\Delta x^2)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Now define the global error as\n",
    "$$\n",
    "    E^N = Q^N - q^N\n",
    "$$\n",
    "where our finite final time $T$ is defined by $T = N \\Delta t$.  Note that as $\\Delta t \\rightarrow 0$ that $N \\rightarrow \\infty$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Often times we will also assume that there is a fixed relationship between $\\Delta x$ and $\\Delta t$, such as the CFL condition, to simplify our analysis."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Norms\n",
    "\n",
    "Next up is a choice of norms.  We of course can rely on the $p$-norms\n",
    "$$\n",
    "    ||E||_p = \\left(\\Delta x \\sum^\\infty_{i=-\\infty} |E_i|^p \\right )^{1/p}\n",
    "$$\n",
    "for vectors and\n",
    "$$\n",
    "    ||E||_p = \\left( \\int^\\infty_{i=-\\infty} |E(x)|^p dx \\right )^{1/p}\n",
    "$$\n",
    "for functions.\n",
    "\n",
    "The $p=1$ norm is of particular for conservation laws as integrals of the solution itself are often of interest."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Now that we have our basic definitions we can define convergence.\n",
    "\n",
    "A method is **convergent** at time $T$ in the norm $||\\cdot||$ if \n",
    "$$\n",
    "    \\lim_{\\Delta t \\rightarrow 0, N \\Delta t = T} ||E^N|| = 0.\n",
    "$$\n",
    "\n",
    "A method is **accurate of order s** if\n",
    "$$\n",
    "    ||E^N|| = \\mathcal{O}(\\Delta t^s) \\quad \\Delta t \\rightarrow 0.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Note that if $q(x,t)$ is smooth we could also define point-wise convergence.  However we already know that hypernbolic PDEs can contain discontinuities and we cannot expect convergence in the max norm.  There are many other caveats that discontinuities in our solutions will provide and we will talk about them as they arise."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## One-Step and Local Truncation Errors\n",
    "\n",
    "Almost always it is very difficult to directly prove convergence.  Instead we often show two properties of a method:\n",
    "\n",
    "1. The method is **consistent** with the original equation.  This is the same as analysis on error produced in one step of the method or the local error.\n",
    "1. The method is **stable**.  Errors produced in previous time steps do not grow catastrophically and therefore the global error is directly dependent on local errors.\n",
    "\n",
    "The **fundamental theorem of numerical methods** implies that if a method is both consistent and stable that it is convergence.  This is sometimes called the Lax equivalence theorem or Dahlquist's equivalence theorem, for PDEs and ODEs respectively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "An explicit, one-step numerical method can be written as\n",
    "$$\n",
    "    Q^{n+1}_i = \\mathcal{N}(Q^n_i)\n",
    "$$\n",
    "Note that $\\mathcal{N}(\\cdot)$ can be multi-stage or non-linear but fundamentally requires only the currently known time to get the next time step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The **one-step error** can then be defined as\n",
    "$$\n",
    "    \\widetilde{\\tau}^n = \\mathcal{N}(q^n) - q^{n+1}\n",
    "$$\n",
    "Notice that the method is receiving EXACT data to produce the next time step in this case.\n",
    "\n",
    "Instead we can also define the **local truncation error**, or LTE, as\n",
    "$$\n",
    "    \\tau^n = \\frac{1}{\\Delta t} [\\mathcal{N}(q^n) - q^{n+1}).\n",
    "$$\n",
    "Here we have purposefully related the one-step to the local truncation error making explicit the division by $\\Delta t$.  LTE will end up being more useful as it is directly related to the global error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "LTE is also important as it allows us define consistency at this point.  A **consistent** method is one for which\n",
    "$$\n",
    "    \\tau^n \\rightarrow 0 \\text{ as } \\Delta t \\rightarrow 0.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Example: Upwinding\n",
    "\n",
    "Consider the first-order upwinding method\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\frac{u \\Delta t}{\\Delta x}(Q^n_i - Q^n_{i-1})\n",
    "$$\n",
    "with $u > 0$.  Compute the local truncation error, confirming that the method is first-order and therefore consistent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "This can simply be computed by plugging in the method into the equation for LTE.  First we need the following Taylor series expansions:\n",
    "$$\\begin{aligned}\n",
    "    q^n_{i-1} &= q^n_i - \\Delta x (q^n_i)_x + \\frac{\\Delta x^2}{2} (q^n_i)_{xx} + \\mathcal{O}(\\Delta x^3) \\\\\n",
    "    q^{n+1}_{i} &= q^n_i + \\Delta t (q^n_i)_t + \\frac{\\Delta t^2}{2} (q^n_i)_{tt} + \\mathcal{O}(\\Delta t^3)\n",
    "\\end{aligned}$$\n",
    "Now we can finish the LTE computation:\n",
    "$$\\begin{aligned}\n",
    "    \\tau^n &= \\frac{1}{\\Delta t} \\left[q^n_i - \\frac{u \\Delta t}{\\Delta x} (q^n_i - q^n_{i-1}) - q^{n+1}_i \\right ] & & \\\\\n",
    "    &= \\frac{1}{\\Delta t} \\left \\{ q^n_i - \\frac{u \\Delta t}{\\Delta x} \\left[q^n_i - \\left(q^n_i - \\Delta x (q^n_i)_x + \\frac{\\Delta x^2}{2} (q^n_i)_{xx} + \\mathcal{O}(\\Delta x^3) \\right)\\right] \\right . & & \\text{Taylor Series} \\\\\n",
    "    & \\left . \\quad \\quad \\quad - \\left(q^n_i + \\Delta t (q^n_i)_t + \\frac{\\Delta t^2}{2} (q^n_i)_{tt} + \\mathcal{O}(\\Delta t^3) \\right) \\right \\} & & \\\\\n",
    "    &= -[(q^n_i)_t + u (q^n_i)_x] + \\frac{1}{2} \\Delta x u (q^n_i)_{xx} - \\frac{1}{2} \\Delta t (q^n_i)_{tt} + \\mathcal{O}(\\Delta x^2, \\Delta t^2) & & \\text{Simplify}\n",
    "\\end{aligned}$$\n",
    "The first term is identically zero as it is the equation we are solving leading us to the conclusion that $\\tau^n = \\mathcal{O}(\\Delta x, \\Delta t)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Stability Theory\n",
    "\n",
    "Stability theory is concerned with gauranteeing that the local errors made in previous time steps do not catastrophically blow up in future time steps.  Here we will study the general concepts and a number of ways to show stability for methods we have already discussed.}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "First rewrite the global error as\n",
    "$$\n",
    "    Q^n = q^n + E^n.\n",
    "$$\n",
    "Now apply the numerical method $\\mathcal{N}(\\cdot)$ to this data so that we have\n",
    "$$\n",
    "    Q^{n+1} = \\mathcal{N}(Q^n) = \\mathcal{N}(q^n + E^n)\n",
    "$$\n",
    "so that\n",
    "$$\\begin{aligned}\n",
    "    E^{n+1} &= Q^{n+1} - q^{n+1} \\\\\n",
    "    &= \\mathcal{N}(q^n + E^n) - q^{n+1} \\\\\n",
    "    &= \\mathcal{N}(q^n + E^n) - \\mathcal{N}(q^n) + \\mathcal{N}(q^n) - q^{n+1} \\\\\n",
    "    &= [\\mathcal{N}(q^n + E^n) - \\mathcal{N}(q^n)] + \\Delta t \\tau^n.\n",
    "\\end{aligned}$$\n",
    "Note that this has now separated the global error into two pieces, the error that occured locally represented by the LTE and one based on the previous numerical error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Contractive Operators\n",
    "\n",
    "A **contractive operator** is an operator $\\mathcal{N}(\\cdot)$ in some norm that satisfies\n",
    "$$\n",
    "    ||\\mathcal{N}(P) - \\mathcal{N}(Q) || \\leq ||P-Q||\n",
    "$$\n",
    "for any two grid functions $P$ and $Q$.\n",
    "\n",
    "If $\\mathcal{N}$ is contractive then the method represented by $\\mathcal{N}$ is also stable in this norm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let's apply this idea to our case.  Let $P = q^n + E^n$ and $Q = q^n$:\n",
    "$$\\begin{aligned}\n",
    "    ||E^{n+1}|| &\\leq ||\\mathcal{N}(q^n + E^n) - \\mathcal{N}(q^n)|| + \\Delta t ||\\tau^n|| \\\\\n",
    "   & \\leq ||E^n|| + \\Delta t ||\\tau^n||.\n",
    "\\end{aligned}$$\n",
    "\n",
    "Applying this recursively then leads to\n",
    "$$\n",
    "    ||E^n|| \\leq ||E^0|| + \\Delta t \\sum^{N-1}_{n=1} ||\\tau^n||.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Now suppose that \n",
    "$$\n",
    "    ||\\tau|| \\equiv \\max_{0 \\leq n \\leq N} ||\\tau^n||\n",
    "$$\n",
    "so that we can then write\n",
    "$$\\begin{aligned}\n",
    "    ||E^N|| &\\leq ||E^0|| + N \\Delta t ||\\tau|| \\\\\n",
    "    &\\leq ||E^0|| + T ||\\tau||\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Lax-Richtmyer Stability for Linear Methods\n",
    "\n",
    "We actually can require something slighly weaker as a sufficient condition that $\\mathcal{N}$ is stable.  If we have instead\n",
    "$$\n",
    "    ||\\mathcal{N}(P) - \\mathcal{N}(Q) || \\leq (1 + \\alpha \\Delta t) ||P - Q||\n",
    "$$\n",
    "where $\\alpha$ is a constant indepdent of $\\Delta t$ we can still show convergence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We now have\n",
    "$$\n",
    "    ||E^{n+1}|| \\leq (1 + \\alpha \\Delta t) ||E^n|| + \\Delta t ||\\tau||\n",
    "$$\n",
    "implying\n",
    "$$\\begin{aligned}\n",
    "    ||E^n|| &\\leq (1+\\alpha \\Delta t)^N ||E^0|| + \\Delta t \\sum^{N-1}_{n=1} (1 + \\alpha \\Delta t)^{N - 1 - n} ||\\tau|| \\\\\n",
    "    &\\leq e^{\\alpha T} (||E^0|| + T ||\\tau||) \\quad (\\text{for } N\\Delta t = T).\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Generally this type of stability if $\\mathcal{N}$ is linear is **Lax-Richtmyer Stability** that can be expressed as\n",
    "$$\n",
    "    ||\\mathcal{N}|| \\leq 1 + \\alpha \\Delta t.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### 2-Norm Stability and von Neumann Analysis\n",
    "\n",
    "When a method is again linear we can turn to Fourier analysis to provide an easy means to prove stability.  This is the basis of **von Neumann stability**, which we will examine here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Let $Q^n_j$ represent an arbitrary grid function for the Cauchy problem.  Suppose that $||Q^n_j||_2 < \\infty$ so that we can express the grid function as\n",
    "$$\n",
    "    Q^n_j = \\frac{1}{\\sqrt{2 \\pi}} \\int^\\infty_{-\\infty} \\widehat{Q}(\\xi) e^{i \\xi j \\Delta x} d\\xi\n",
    "$$\n",
    "If we apply a LINEAR function $\\mathcal{N}$ to $Q^n_j$ we can find the update\n",
    "$$\n",
    "    Q^{n+1}_j = \\frac{1}{\\sqrt{2 \\pi}} \\int^\\infty_{-\\infty} \\widehat{Q}(\\xi) g(\\xi, \\Delta x, \\Delta t) e^{i \\xi j \\Delta x} d\\xi\n",
    "$$\n",
    "where $g(\\cdot)$ represents the **amplification factor** for wave number $\\xi$ of the method.  We can rewrite this more helpfully as\n",
    "$$\n",
    "    \\widehat{Q}^{n+1}(\\xi) = g(\\xi, \\Delta x, \\Delta t) \\widehat{Q}^n(\\xi).\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Recall that **Parseval's relation** states that\n",
    "$$\n",
    "    ||Q^n||_2 = ||\\widehat{Q}^n||_2\n",
    "$$\n",
    "where\n",
    "$$\n",
    "    ||Q^n||_2 = \\left (\\Delta x \\sum^\\infty_{j=-\\infty} |Q^n_i|^2 \\right )^{1/2} \\quad \\quad ||\\widehat{Q}^n||_2 = \\left (\\int^\\infty_{j=-\\infty} |\\widehat{Q}^n(\\xi)|^2 d\\xi \\right )^{1/2}\n",
    "$$\n",
    "This of course implies that if we can show boundedness of the Fourier transform that we have also shown the boundedness of the original function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Turning back to therefore proving the boundedness of $\\widehat{Q}$ then we consider single wave number data of the form\n",
    "$$\n",
    "    Q^n_j = e^{i \\xi j \\Delta x}.\n",
    "$$\n",
    "As long as $\\xi$ remains arbitrary we can consider the single wave number form of solutions.  Therefore, if we can show that the amplification factor from\n",
    "$$\n",
    "    \\widehat{Q}^{n+1}(\\xi) = g(\\xi, \\Delta x, \\Delta t) \\widehat{Q}^n(\\xi)\n",
    "$$\n",
    "that $|g| \\leq 1$ we have proven what we set out to."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Example:  Upwind\n",
    "\n",
    "Again consider the upwind method, a linear, explicit, one-step method.  Writing the upwind method with $u > 0$ and directly using the Courant number $\\nu$ we have\n",
    "$$\\begin{aligned}\n",
    "    Q^{n+1}_j &= Q^n_j - \\nu (Q^n_j = Q^n_{j - 1}) \\\\\n",
    "    &= (1 - \\nu) Q^n_j + \\nu Q^n_{j - 1} \\\\\n",
    "\\end{aligned}$$\n",
    "Plugging $Q^n_j = e^{i \\xi j \\Delta x}$ into the above expression leads to\n",
    "$$\\begin{aligned}\n",
    "    Q^{n+1}_j &= (1 - \\nu) Q^n_j + \\nu Q^n_{j - 1} \\\\\n",
    "    &= (1 - \\nu) e^{i \\xi j \\Delta x} + \\nu e^{-i \\xi \\Delta x} e^{i \\xi j \\Delta x} \\\\\n",
    "    &= [(1 - \\nu) + \\nu e^{-i \\xi\\Delta x} ] e^{i \\xi j \\Delta x} \\\\\n",
    "    &= g(\\xi, \\Delta x, \\Delta t) Q^n_j.\n",
    "\\end{aligned}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "So we know that we have\n",
    "$$\n",
    "    g(\\xi, \\Delta x, \\Delta t) = (1 - \\nu) + \\nu e^{-i \\xi\\Delta x}.\n",
    "$$\n",
    "Since $-1 \\leq e^{-i \\xi\\Delta x} \\leq 1$ we are not worried about that assuming $-1 \\leq \\nu \\leq 1$.  Of course this also holds for the first term and we see that if the CFL condition is statisfied the method is stable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### 1-Norm Stability of the Upwind Method\n",
    "\n",
    "As mentioned before, the 1-norm is often used for conservation laws, especially in the case of nonlinear PDEs.  Again we will consider the upwind in the form\n",
    "$$\n",
    "    Q^{n+1}_i = (1- \\nu) Q^n_i + \\nu Q^n_{i-1}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Applying the 1-norm we have\n",
    "$$\\begin{aligned}\n",
    "    ||Q^{n+1}||_1 &= \\Delta x \\sum_i |Q^{n+1}_i| & & \\\\\n",
    "    &= \\Delta x \\sum_i |(1-\\nu)Q^n_i + \\nu Q^n_{i-1}| & & \\\\\n",
    "    &\\leq \\Delta x \\sum_i [(1-\\nu) |Q^n_i| + \\nu |Q^n_{i-1}| ] & & \\text{Triangle Inequality} \\\\\n",
    "    ||Q^{n+1}||_1 &\\leq (1-\\nu) ||Q^n||_1 + \\nu ||Q^n||_1 = ||Q^n||_1 & &\n",
    "\\end{aligned}$$\n",
    "This only works if $0 \\leq \\nu \\leq 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Total-Variation Stability for Nonlinear Method\n",
    "\n",
    "Many of the above stability proofs relied on the method being linear.  For non-linear methods we turn to our ideas of total variation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "A numerical methods is **total-variation bounded** (TVB) if, for any data $Q^0$ with $TV(Q^0) < \\infty$ and time $T$, there is a constant $R > 0$ and $\\Delta t_0 > 0$ s.t.\n",
    "$$\n",
    "    \\text{TV}(Q^n) \\leq R \\quad \\forall n \\Delta t \\leq T \\quad \\text{when} \\Delta t < \\Delta t_0\n",
    "$$\n",
    "\n",
    "In other words we require a uniform bound on the total variation up to a time $T$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "We actually require something a bit less strict as we can again use a bound such that\n",
    "$$\n",
    "    \\text{TV}(Q^{n+1}) \\leq (1 + \\alpha \\Delta t) \\text{TV}(Q^n)\n",
    "$$\n",
    "again for an $\\alpha$ constant independent of $\\Delta t$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Accuracy at Extrema\n",
    "\n",
    "The TVD methods we have already discussed are sufficient to show stability but not neccesary.  We would be better off choosing Lax-Wendroff for instance near smooth extrema.  This leads to a number of other methods that attempt to maintain stability but also smooth extrema such as the **esentially nonoscillatory** (ENO) method family."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Order of Accuracy is Not Everything\n",
    "\n",
    "Unfortunately our usual metric of order of accuracy is not always a proper metric for judging a method.  In fact a high-order of accuracy method may not be as accurate on a particular grid as a low order method.  One example of this is a grid that is aligned such that it exactly solves the method but is first-order.  We will now consider other situations where this may also be true."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Consider the error expression\n",
    "$$\n",
    "    ||E^N|| = C(\\Delta x)^2 + \\text{higher-order terms}.\n",
    "$$\n",
    "There's a lot that can go wrong here, for instance $C$ may be large and the higher-order terms may be imporant apart from $\\Delta x \\rightarrow 0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Here the most important piece that may not adhere to order of accuracy are discontinuities in our solution.  We can also show that even given a smooth solution that a limiter method will perform better than a strictly Lax-Wendroff based method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "outputs": [],
   "source": [
    "def run_simulation(dx, limiters=[0]):\n",
    "\n",
    "    solver = pyclaw.ClawSolver1D(riemann.advection_1D)\n",
    "\n",
    "    solver.bc_lower[0] = 2\n",
    "    solver.bc_upper[0] = 2\n",
    "    solver.limiters = limiters\n",
    "    solver.order = 2\n",
    "    solver.cfl_desired = 0.9\n",
    "\n",
    "    mx = 1.0 / dx + 2\n",
    "    x = pyclaw.Dimension(0.0, 1.0, mx, name='x')\n",
    "    domain = pyclaw.Domain(x)\n",
    "    num_eqn = 1\n",
    "    state = pyclaw.State(domain, num_eqn)\n",
    "    state.problem_data['u'] = 1.0\n",
    "\n",
    "    xc = domain.grid.x.centers\n",
    "    beta=100.; x0=0.5; mx=100\n",
    "    state.q[0,:] = numpy.exp(-beta * (xc-x0)**2) * numpy.sin(80.*xc)\n",
    "    # beta=200.; x0=0.3; mx=100\n",
    "    # state.q[0,:] = numpy.exp(-beta * (xc-x0)**2) + (xc>0.6)*(xc<0.8)\n",
    "\n",
    "    claw = pyclaw.Controller()\n",
    "    claw.solution = pyclaw.Solution(state, domain)\n",
    "    claw.solver = solver\n",
    "    claw.tfinal = 2.0\n",
    "    claw.keep_copy = True\n",
    "\n",
    "    claw.run()\n",
    "\n",
    "    return claw.frames[-1].q\n",
    "\n",
    "def compute_lax_wendroff(dx):\n",
    "    return run_simulation(dx, limiters=[0])\n",
    "\n",
    "def compute_limited(dx, limiters=[4]):\n",
    "    return run_simulation(dx, limiters=limiters)\n",
    "\n",
    "def true_solution(dx, t):\n",
    "\n",
    "    mx = 1.0 / dx + 2\n",
    "    xtrue = numpy.linspace(0.0, 1.0, mx)\n",
    "    xshift = numpy.mod(xtrue - t, 1.0)\n",
    "    # x1 = 0.6; x2 = 0.8; beta=200.; x0=0.3\n",
    "    # return numpy.exp(-beta * (xshift-x0)**2) + (xshift>0.6)*(xshift<0.8)\n",
    "\n",
    "    beta=100.; x0=0.5; mx=100\n",
    "    return numpy.exp(-beta * (xshift-x0)**2) * numpy.sin(80.*xshift)\n",
    "    \n",
    "plot_solution = False\n",
    "\n",
    "deltas = numpy.logspace(-1, -4, 8)\n",
    "error_lax_L1 = []\n",
    "error_mc_L1 = []\n",
    "error_lax_max = []\n",
    "error_mc_max = []\n",
    "for dx in deltas:\n",
    "    Q = compute_lax_wendroff(dx)\n",
    "    error_lax_L1.append(numpy.linalg.norm(dx * (Q \n",
    "                                          - true_solution(dx, 2.0)), 1))\n",
    "    error_lax_max.append(numpy.max(Q - true_solution(dx, 2.0)))\n",
    "    Q = compute_limited(dx)\n",
    "    error_mc_L1.append(numpy.linalg.norm(dx * (Q\n",
    "                                         - true_solution(dx, 2.0)), 1))\n",
    "    error_mc_max.append(numpy.max(Q - true_solution(dx, 2.0)))\n",
    "\n",
    "if plot_solution:\n",
    "    fig, axes = plt.subplots(1, 1)\n",
    "    x = numpy.linspace(0, 1, 100)\n",
    "    q = compute_lax_wendroff(x[1]-x[0])[0]\n",
    "    axes.plot(x, compute_lax_wendroff(x[1]-x[0])[0], 'xr')\n",
    "    axes.plot(x, compute_limited(x[1] - x[0])[0], 'ob')\n",
    "    axes.plot(x, true_solution(x[1]-x[0], 2.0), 'k-')\n",
    "\n",
    "order_C = lambda delta_x, error, order: numpy.exp(numpy.log(error) - order * numpy.log(delta_x))\n",
    "\n",
    "fig, axes = plt.subplots(1, 2)\n",
    "fig.set_figwidth(fig.get_figwidth() * 2)\n",
    "\n",
    "axes[0].loglog(deltas, error_lax_L1, 'ko-', label=\"Lax-Wendroff\")\n",
    "axes[0].loglog(deltas, error_mc_L1, 'ko--', label=\"Limited\")\n",
    "axes[0].set_title(\"Error Comparison, $\\ell_1$ Norm\")\n",
    "axes[0].set_xlabel(\"$\\Delta x$\")\n",
    "axes[0].set_ylabel(\"$||Q - q||_1$\")\n",
    "axes[0].loglog(deltas, order_C(deltas[2], error_lax_L1[2], 2.0) * deltas**2.0, 'b', label=\"2nd Order\")\n",
    "axes[0].legend()\n",
    "\n",
    "axes[1].loglog(deltas, error_lax_max, 'ko-', label=\"Lax-Wendroff\")\n",
    "axes[1].loglog(deltas, error_mc_max, 'ko--', label=\"Limited\")\n",
    "axes[1].set_title(\"Error Comparison, Max Norm\")\n",
    "axes[1].set_xlabel(\"$\\Delta x$\")\n",
    "axes[1].set_ylabel(\"$||Q - q||_\\infty$\")\n",
    "axes[1].loglog(deltas, order_C(deltas[3], error_lax_max[3], 2.0) * deltas**2.0, 'b', label=\"2nd Order\")\n",
    "axes[1].legend()\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Modified Equations\n",
    "\n",
    "One way we can start to understand numerical methods is to find the modified equations that equate to the method, i.e. the equation we are actually solving.  This is best shown by example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Example: The Upwind Method\n",
    "\n",
    "Again consider the upwind method with $u > 0$ for the advection equation:\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\frac{u \\Delta t}{\\Delta x} (Q^n_i - Q^n_{i-1}).\n",
    "$$\n",
    "\n",
    "Now replace the numerical solution with a function $v(x,t)$ that is different from the true solution $q(x,t)$ that instead solves the problem the numerical method is sovling but exactly.  Plugging this into our method leads us to\n",
    "$$\n",
    "    v(x, t+ \\Delta t) = v(x,t) - \\frac{u \\Delta t}{\\Delta x} [v(x,t) - v(x - \\Delta x, t)].\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "$$\n",
    "    v(x, t+ \\Delta t) = v(x,t) - \\frac{u \\Delta t}{\\Delta x} [v(x,t) - v(x - \\Delta x, t)].\n",
    "$$\n",
    "Expanding this expression as a Taylor series leads to\n",
    "$$\\begin{aligned}\n",
    "    0 &= \\left( v_t + \\frac{\\Delta t}{2} v_{tt} + \\frac{\\Delta t^2}{6} v_{ttt} + \\mathcal{O}(\\Delta t^3) \\right ) + u \\left( v_x - \\frac{\\Delta x}{2} v_{xx} + \\frac{\\Delta x^2}{6} v_{xxx} + \\mathcal{O}(\\Delta x^3) \\right) \\\\\n",
    "    v_t + u v_x &= \\frac{1}{2} (u \\Delta x v_{xx} - \\Delta t v_{tt} ) - \\frac{1}{6} [u \\Delta x^2 v_{xxx} + \\Delta t^2 v_{ttt} ] + \\mathcal{O}(\\Delta x^3, \\Delta t^3).\n",
    "\\end{aligned}$$\n",
    "This PDE satisfies the original advection equation plus a number of extra terms.  For instance we see that the upwind method seems to solve the advection equation plus another wave equation dependent on $u$ and $\\Delta t$ and $\\Delta x$.  The second order error terms are dispersive in nature."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The true power of modified equation analysis is that we can interpret the error as  the left-over terms as mentioned above.  We can also extend this analysis by replacing the terms in the modified equation we have derived using the original equation:\n",
    "$$\\begin{aligned}\n",
    "    v_t + u v_x &= \\frac{1}{2} (u \\Delta x v_{xx} - \\Delta t v_{tt}) \\Rightarrow \\\\\n",
    "    v_{tt} &= -u v_{xt} + \\frac{1}{2} (u \\Delta x v_{xxt} - \\Delta t v_{ttt}) \\text{ and } \\Rightarrow \\\\\n",
    "    v_{tx} &= -u v_{xx} + \\frac{1}{2}(u \\Delta x v_{xxx} - \\Delta t v_{ttx}),\n",
    "\\end{aligned}$$\n",
    "which combined leads to\n",
    "$$\n",
    "    v_{tt} = u^2 v_{xx} + \\mathcal{O}(\\Delta t)\n",
    "$$\n",
    "which leads to \n",
    "$$\n",
    "    v_t + u v_x = \\frac{u \\Delta x}{2} (1 - \\nu) v_{xx}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "#### Example: Beam-Warming Method\n",
    "\n",
    "Try and calculate this same modified method for Beam-Warming defined by\n",
    "$$\n",
    "    Q^{n+1}_i = Q^n_i - \\nu (3 Q^n_i - 4 Q^n_{i-1} + Q^n_{i-2}) + \\frac{1}{2} \\nu^2 (Q^n_i- 2 Q^n_{i-1} + Q^n_{i-2})\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "The modified equation is\n",
    "$$\n",
    "    v_t + u v_x = \\frac{1}{6} u \\Delta x^2 (2 - 3 \\nu + \\nu^2) v_{xxx}\n",
    "$$"
   ]
  }
 ],
 "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.9.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}