{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "###### Content under Creative Commons Attribution license CC-BY 4.0, code under MIT license (c)2014 L.A. Barba, C.D. Cooper, G.F. Forsyth." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Riding the wave" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Numerical schemes for hyperbolic PDEs" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Welcome back! This is the second notebook of *Riding the wave: Convection problems*, the third module of [\"Practical Numerical Methods with Python\"](https://openedx.seas.gwu.edu/courses/course-v1:MAE+MAE6286+2017/about). \n", "\n", "The first notebook of this module discussed conservation laws and developed the non-linear traffic equation. We learned about the effect of the wave speed on the stability of the numerical method, and on the CFL number. We also realized that the forward-time/backward-space difference scheme really has many limitations: it cannot deal with wave speeds that move in more than one direction. It is also first-order accurate in space and time, which often is just not good enough. This notebook will introduce some new numerical schemes for conservation laws, continuing with the traffic-flow problem as motivation." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Red light!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's explore the behavior of different numerical schemes for a moving shock wave. In the context of the traffic-flow model of the previous notebook, imagine a very busy road and a red light at $x=4$. Cars accumulate quickly in the front, where we have the maximum allowed density of cars between $x=3$ and $x=4$, and there is an incoming traffic of 50% the maximum allowed density $(\\rho = 0.5\\rho_{\\rm max})$. \n", "\n", "Mathematically, this is:\n", "\n", "$$\n", "\\begin{equation}\n", "\\rho(x,0) = \\left\\{\n", "\\begin{array}{cc}\n", "0.5 \\rho_{\\rm max} & 0 \\leq x < 3 \\\\\n", "\\rho_{\\rm max} & 3 \\leq x \\leq 4 \\\\\n", "\\end{array}\n", "\\right.\n", "\\end{equation}\n", "$$\n", "\n", "Let's find out what the initial condition looks like." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "import numpy\n", "from matplotlib import pyplot\n", "%matplotlib inline" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# Set the font family and size to use for Matplotlib figures.\n", "pyplot.rcParams['font.family'] = 'serif'\n", "pyplot.rcParams['font.size'] = 16" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "def rho_red_light(x, rho_max):\n", " \"\"\"\n", " Computes the \"red light\" initial condition with shock.\n", " \n", " Parameters\n", " ----------\n", " x : numpy.ndaray\n", " Locations on the road as a 1D array of floats.\n", " rho_max : float\n", " The maximum traffic density allowed.\n", " \n", " Returns\n", " -------\n", " rho : numpy.ndarray\n", " The initial car density along the road\n", " as a 1D array of floats.\n", " \"\"\"\n", " rho = rho_max * numpy.ones_like(x)\n", " mask = numpy.where(x < 3.0)\n", " rho[mask] = 0.5 * rho_max\n", " return rho" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "# Set parameters.\n", "nx = 81 # number of locations on the road\n", "L = 4.0 # length of the road\n", "dx = L / (nx - 1) # distance between two consecutive locations\n", "nt = 40 # number of time steps to compute\n", "rho_max = 10.0 # maximum taffic density allowed\n", "u_max = 1.0 # maximum speed traffic\n", "\n", "# Get the road locations.\n", "x = numpy.linspace(0.0, L, num=nx)\n", "\n", "# Compute the initial traffic density.\n", "rho0 = rho_red_light(x, rho_max)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZsAAAELCAYAAAAP/iu7AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAEk1JREFUeJzt3XuM5WV9x/H3d3e4uNyFLeCFi2y7agVRqWm46ChKldZYitVqJU1Nu0lrrdJqtWhBqrQgTW20qF3Qtklt8VLtJREvbT2lrqSwKArKVaB0NVQRC7sszOwM3/5xzsxupnuZmT2/eZ7zzPuVTE72N+ck3zzfzfnMc57nPL/ITCRJ6tKK0gVIktpn2EiSOmfYSJI6Z9hIkjpn2EiSOmfYSJI6Z9hIkjpn2EiSOmfYSJI6N1a6gK4deuihuWbNmtJlNOeRRx7hgAMOKF1GcxzXbjiu3bjxxhsfyMzV83lu82Fz5JFHsnHjxtJlNKfX6zE+Pl66jOY4rt1wXLsREf813+f6MZokqXOGjSSpc4aNJKlzho0kqXOGjSSpc4aNJKlzho0kqXOGjSSpc4aNJKlzho0kqXOGjSSpc4aNJKlzho0kqXOGjSSpc4aNJKlzho0kqXOGjSSpc4aNJKlzho0kqXOGjSSpc4aNJKlzRcMmIo6OiM9HRJasQ5LUrWJhExHnANcBJ+zheftExHsi4raIuCUivhoRpy9NlZKkYSg5s3kH8FJgwx6e90HgNcAZmfks4GPAlyLi5I7rkyQNScmwOS0z79zdEyJiLbAOuDQzfwCQmVcBdwOXdF+iJGkYioVNZk7N42nnAAF8ec71fwPOiogDh16YJGnoxkoXsAcnAY8D9825fg/92p8JXL/URUkaDXf/YAtvvvom7n9wK0+4fu7frFpKtYfNEcDWzJyec/3hwePhO3tRRKyj//Ebq1evptfrdVbgcrVlyxbHtQOO63B98d5t3Pzdyf4/Ht1atphlrvaw2ZXY3S8zcz2wHmDt2rU5Pj6+FDUtK71eD8d1+BzX4bq19x247TbGnzLGxa91E+uwHXfZ/J9be9g8AKyKiJVzZjcHDR5/WKAmSSNiYqr/tnHIfsGxhx9QuJrlrfYTBL5Jv8anzrl+PDAF3LrkFUkaGZNTjwMwVvs73TJQews+CyQwPuf6i4AvZubmJa9I0siYGITNPit2+8m7lkDVYZOZt9Nfe/n9iDgCICLeQP/UgXeWrE1S/ZzZ1KPYmk1EXE7/BIFjBv++afCr52fm5A5PfRNwEbAhIrYBm4GzMvMmJGk3ZtZs9llZuBCVC5vMfNs8n7cNeNfgR5LmbdKP0arh5FJSs7av2RQuRIaNpHa5ZlMPWyCpWe5Gq4dhI6lZk36MVg1bIKlZs7vRfKcrzhZIataEazbVsAWSmuXW53oYNpKa5cymHrZAUrNmd6N5gkBxho2kZm3fIODHaKUZNpKa5dbnetgCSU3KTNdsKmILJDVp23QCsM/KYEX4MVppho2kJs2s1+y70re5GtgFSU2aWa/Zz61oVTBsJDVpZr3GmU0d7IKkJm2f2fg2VwO7IKlJzmzqYhckNcmZTV3sgqQmuRutLnZBUpNmZzZj7kargWEjqUmzazYeH1AFuyCpSROzMxvf5mpgFyQ1aXbNxrCpgl2Q1CTXbOpi2Ehq0oRbn6tiFyQ1adIvdVbFLkhqkjObutgFSU2a2SCwnzObKtgFSU3yFgN1MWwkNcmDOOtiFyQ1yYM462IXJDXJgzjrYhckNcmZTV3sgqQmbV+zcYNADQwbSU2a9CDOqtgFSU3yFgN1sQuSmuTMpi52QVKTvMVAXeyCpCZNeIuBqhg2kpo06ZpNVeyCpCZ5W+i62AVJTTJs6mIXJDVpcuYWA67ZVMGwkdQkv2dTF7sgqTmZyeS0YVOT6rsQEadExDURcWtE3BwR10fEL5auS1K9tk0nmTC2Ili5IkqXIyoPm4g4DvhX4AHgxMw8EfgY8MmIeEXB0iRVbGZW4+aAetTeibOBg4E/zcwpgMz8CPAw8LqShUmq18Q2Tw+oTe2dmBo8js1ciIigX7dbTCTtlKcH1Kf2sLkauA14V0QcGBErgAuA/YCPFK1MUrU8PaA+Y3t+SjmZ+XBEnAn8Jf11my3AQ8BLM/Pfd/W6iFgHrANYvXo1vV5vCapdXrZs2eK4dsBxHY5Nm/thMzX5KL1ez3GtQNVhExFr6W8Q+BzwROAx4NXAZyLi9Zl5zc5el5nrgfUAa9euzfHx8aUpeBnp9Xo4rsPnuA7HzZsegg1f4bCDD2J8/AzHtQK1zzHfAxwKvDkzt2bm45l5NXAt8NcRUXVYSipjYvb0gNrf4paP2jtxIrApMx+dc/0OYDVw/NKXJKl2rtnUp/ZOfB84eiczmGOBBH609CVJqp270epTe9h8kP73bP5wsOWZiHgR8AvAJzLzgZLFSaqTJz7Xp+o1j8z8dES8DHgH8O2ImAYeB94JfKBocZKq5S2h61N12ABk5heAL5SuQ9LomPRjtOoY+5Ka4+0F6mMnJDVn0jWb6tgJSc1xg0B95r1mM7iHzCuBA4F7gM9m5rVdFSZJi+XMpj7z6kREXAR8AngF8DTgPKAXEV8bHCkjSdVwN1p95tuJNwKfAg7PzJMy8wjgDPoHY14fEc/oqkBJWih3o9VnvmFzCPDRmRuYAWTmBuCFwNeA93VQmyQtirvR6jPfTmwCnjr3YmYm/W/5jw+xJknaK67Z1Ge+nfgwcFFEPHkXv39sSPVI0l5zzaY+892N9n7gTOCWiPhz+veX2QScALwXuLKb8iRp4SanXbOpzbxiPzOn6e9Eu4z+HTC/AtxL/8ZmBwD3RsRzvL+MpBpMbHPNpjbz7kRmTmXmpcBRwKnA7wAfp78j7UPARmBzRFzfRaGSNF/bZzaGTS0WPBMZbAr4z8EPABGxCngOcArw3KFVJ0mL4MymPkP52CsztwIbBj+SVJS3ha6PnZDUHL9nUx87Iak5niBQH8NGUnM89bk+dkJScwyb+tgJSc2Z9ASB6tgJSc2ZcM2mOoaNpKZk5uyXOp3Z1MNOSGrKtukkE8ZWBCtXROlyNGDYSGqKs5o62Q1JTZnY5ukBNbIbkprizKZOdkNSU2YO4XQnWl0MG0lN8fYCdbIbkpri7QXqZDckNWVy2g0CNbIbkprizKZOdkNSUyam3SBQI8NGUlOc2dTJbkhqirvR6mQ3JDVl5gQBZzZ1sRuSmuLtBepk2EhqyqR36ayS3ZDUFG8JXSe7IakpMzMb12zqYjckNWViyhMEamQ3JDXFmU2d7IakprgbrU6GjaSmOLOpk92Q1BTXbOpkNyQ1xdtC18luSGqKt4Wuk2EjqSnObOo0Et2IiHMj4tqIuDEi7o6IjRFxXum6JNVn+8xmJN7elo3quxER5wPvBF6Xmc8D1gJ3AGcWLUxSlSac2VRprHQBuxMRxwGXAqdn5iaAzNwWEW8FnlSwNEmVmrnFgDObulQdNsB5wP9m5g07XszM7wHfK1OSpJp587Q61R42pwL3RsS5wFuA1cCDwFWZ+bFdvSgi1gHrAFavXk2v11uCUpeXLVu2OK4dcFz33kObtwLw9Y03sGlVP3Ac1/JqD5unAscBbwXOAb4PnAv8XUQcnZmX7OxFmbkeWA+wdu3aHB8fX5Jil5Ner4fjOnyO695bseFf4LEJXnD6qRx58P6A41qD2ueZ+wMHAG/LzPsz8/HM/BTwj8AFEbGqbHmSauOaTZ1q78bmweNNc65/HVgFPHNpy5FUO79nU6fau3Hb4HFundO7uC5pGcvM2VOf913p20NNau/GPw8eT5pz/VnAo8C3lrYcSTXbNp1kwsoVwZhhU5Xau/EJ4AbgvRFxIEBEnAG8CrgkMx8pWZykurjtuV5V70bLzOmIeBlwGfCtiHgMmAB+KzOvLFudpNq4OaBeVYcNQGY+CPx66Tok1c/NAfWyI5Ka4e0F6mXYSGqGM5t62RFJzfD2AvWyI5KaMTnd3yDgzKY+dkRSM5zZ1MuOSGrG9hunuUGgNoaNpGY4s6mXHZHUDHej1cuOSGqGJwjUy45IaoZno9XLjkhqhicI1MuwkdQM12zqZUckNcPdaPWyI5KaMXuCgDdOq44dkdSM2ZnNPr611caOSGrG7JqNM5vq2BFJzdg+s3E3Wm0MG0nNmJhyzaZWdkRSM2a/1OmaTXXGShfQtYcmkiu+fFfpMppz992TfCsd12FzXPfO7fdvBpzZ1Kj5sPnRRHL5F24vXUab7nRcO+G47rVDV+1bugTN0XzYHLJv8JvjJ5Quozn33XcfxxxzTOkymuO47r2jDtmfU449rHQZmqP5sDls/+D3Xvb00mU0p9e7n/Fxx3XYHFe1yg82JUmdM2wkSZ0zbCRJnTNsJEmdM2wkSZ0zbCRJnTNsJEmdM2wkSZ0zbCRJnTNsJEmdM2wkSZ0zbCRJnTNsJEmdM2wkSZ0zbCRJnTNsJEmdM2wkSZ0zbCRJnTNsJEmdM2wkSZ0zbCRJnRu5sImI/4iIjIjjStciSZqfkQqbiDgXOL10HZKkhRmZsImIfYE/Bj5XuhZJ0sKMTNgAbwQ2AjeULkSStDAjETYR8UTgbcAFpWuRJC3cSIQNcCHwN5l5b+lCJEkLN1a6gD2JiDXAq4FnLOA164B1g39ORMQtXdS2zB0BPFC6iAY5rt1wXLuxdr5PrD5sgPcBl2bmQ/N9QWauB9YDRMTGzDylq+KWK8e1G45rNxzXbkTExvk+t+qwiYgzgGcBryldiyRp8aoOG+ClwErghoiYuXbU4PFzETEJXJCZboeWpIpVHTaZeSH9zQGzIuLdwEXA2fPcMLB++JUJx7Urjms3HNduzHtcIzO7LGTodgib492dJkmjYWTCJiLOBv6I/sdoRwK3ApOZeXLRwiRJezQyYSNJGl2j8qVOVSAijo6Iz0eEf6FIWtAp/E2GTUT8WER8PCJuH/x8OiKeUrquURYR5wDXASeUrqUlEXFyRFwZETdGxDci4tsR8YGIWF26tlEWESdExJ8MxvXGiLhj8Mb4s6Vra8VCT+FvLmwGp0N/CdgX+EngmcAjwJcj4sCStY24d9Dfir6hdCGNuRp4IvCCzHw2/TE+C9gQEU8oWtloeznwS8BrMvN5wNPp/7H0TxHxwqKVNWAxp/A3FzbArwAnAW/PzKnMnAbeDjwN+I2ilY220zLzztJFNOrtmfkIQGZ+F7gc+HHg7KJVjbbvAu/OzLsAMvNx+huMVgCvLFlYIxZ8Cn+LYXMucF9m3j1zITPvB749+J0WITOnStfQqJNm3hB38L3B42FLXUwrMvOzmXnVnMsHDx5/sNT1tGSxp/C3GDYnAffs5Po9wIlLXIu0W5k5uZPLPwEkcO0Sl9OsiHgycAXwtcGjFm9Rp/C3GDZHAJt3cv1hYJWfg6tmEbESeAPw0cy8o3Q9o26wUeAuYBP9o69+PjMfLlzWyNrhFP5LFvraFsNmV2LPT5GK+wNgCji/dCEtyMzvZOYa4BDgDuAbETHvHVT6fxZ8Cv+MFsPmAeCgnVw/CNiamY8ucT3SvETEr9L/q/HlmbmldD0tGcxmzgf+B/hQ4XJG0g6n8H94Ma+v+iDORfom/W2Ocx0P3LzEtUjzEhHnAb8LvDgzv1+6nlE3+Lj8sdzhiJTMzIi4GXhVROyXmRPlKhxJe3UKf4szm88Ax+74jdaIOJL+nT7/vlBN0i5FxOvpb89/yWDnJBHxc4M7zmpxrgF+eifXj6O/fruzjRnajcy8MDNPyMyTZ36Ajwx+ffbg2i6/d9Ni2PwV/RnMZRExFhErgEvp70Zb1PRP6kpE/DJwJf3/ty+JiNcPwucVwJNK1taAiyPicIDoexPwU8AHdpzxaGk0eRDnYCbzfuAU+ltIbwHekpn/XbSwERYRl9OfRh9D//sf3xj86vm72L6reYiIB9n192kuzsx3L2E5zYiI04Bfox8uU8D+wA/pr9f8rWGzdxZzCn+TYSNJqkuLH6NJkipj2EiSOmfYSJI6Z9hIkjpn2EiSOmfYSJI6Z9hIkjpn2EiSOmfYSJI6Z9hIkjpn2EiSOmfYSAVFxJqI2BYRF8+5/uGI2BwRp5SqTRomw0YqKDPvAq4Czo+IIwAi4kLgDcA5mbmxZH3SsHjqs1RYRBwFfIf+8fe3AeuB12bmJ4sWJg1Ri7eFlkZKZt4fEX9G/7bQY8BvGzRqjR+jSXW4E9gPuC4zryhdjDRsho1UWES8GPgL4DrgtIh4duGSpKEzbKSCIuK5wD/Q3yQwDtxH/3a7UlMMG6mQiFgDXAN8EXhTZk4CFwNnR8QLihYnDZm70aQCBjvQvkp/JvMzmTkxuL4SuAX4UWaeWrBEaagMG0lS5/wYTZLUOcNGktQ5w0aS1DnDRpLUOcNGktQ5w0aS1DnDRpLUOcNGktQ5w0aS1Ln/A0wDhLjlQd19AAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Plot the initial traffic density.\n", "fig = pyplot.figure(figsize=(6.0, 4.0))\n", "pyplot.xlabel(r'$x$')\n", "pyplot.ylabel(r'$\\rho$')\n", "pyplot.grid()\n", "line = pyplot.plot(x, rho0,\n", " color='C0', linestyle='-', linewidth=2)[0]\n", "pyplot.xlim(0.0, L)\n", "pyplot.ylim(4.0, 11.0)\n", "pyplot.tight_layout()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The question we would like to answer is: **How will cars accumulate at the red light?** \n", "\n", "We will solve this problem using different numerical schemes, to see how they perform. These schemes are:\n", "\n", " * Lax-Friedrichs\n", " * Lax-Wendroff\n", " * MacCormack" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Before we do any coding, let's think about the equation a little bit. The wave speed $u_{\\rm wave}$ is $-1$ for $\\rho = \\rho_{\\rm max}$ and $\\rho \\leq \\rho_{\\rm max}/2$, making all velocities negative. We should see a solution moving left, maintaining the shock geometry.\n", "\n", "![squarewave](./figures/squarewave.png)\n", "#### Figure 1. The exact solution is a shock wave moving left.\n", "\n", "Now to some coding! First, let's define some useful functions and prepare to make some nice animations later." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "def flux(rho, u_max, rho_max):\n", " \"\"\"\n", " Computes the traffic flux F = V * rho.\n", " \n", " Parameters\n", " ----------\n", " rho : numpy.ndarray\n", " Traffic density along the road as a 1D array of floats.\n", " u_max : float\n", " Maximum speed allowed on the road.\n", " rho_max : float\n", " Maximum car density allowed on the road.\n", " \n", " Returns\n", " -------\n", " F : numpy.ndarray\n", " The traffic flux along the road as a 1D array of floats.\n", " \"\"\"\n", " F = rho * u_max * (1.0 - rho / rho_max)\n", " return F" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Before we investigate different schemes, let's create the function to update the Matplotlib figure during the animation." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "from matplotlib import animation\n", "from IPython.display import HTML" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "def update_plot(n, rho_hist):\n", " \"\"\"\n", " Update the line y-data of the Matplotlib figure.\n", " \n", " Parameters\n", " ----------\n", " n : integer\n", " The time-step index.\n", " rho_hist : list of numpy.ndarray objects\n", " The history of the numerical solution.\n", " \"\"\"\n", " fig.suptitle('Time step {:0>2}'.format(n))\n", " line.set_ydata(rho_hist[n])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Lax-Friedrichs scheme" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recall the conservation law for vehicle traffic, resulting in the following equation for the traffic density:\n", "\n", "$$\n", "\\begin{equation}\n", "\\frac{\\partial \\rho}{\\partial t} + \\frac{\\partial F}{\\partial x} = 0\n", "\\end{equation}\n", "$$\n", "\n", "$F$ is the *traffic flux*, which in the linear traffic-speed model is given by: \n", "\n", "$$\n", "\\begin{equation}\n", "F = \\rho u_{\\rm max} \\left(1-\\frac{\\rho}{\\rho_{\\rm max}}\\right)\n", "\\end{equation}\n", "$$\n", "\n", "In the time variable, the natural choice for discretization is always a forward-difference formula; time invariably moves forward!\n", "\n", "$$\n", "\\begin{equation}\n", "\\frac{\\partial \\rho}{\\partial t}\\approx \\frac{1}{\\Delta t}( \\rho_i^{n+1}-\\rho_i^n )\n", "\\end{equation}\n", "$$\n", "\n", "As is usual, the discrete locations on the 1D spatial grid are denoted by indices $i$ and the discrete time instants are denoted by indices $n$.\n", "\n", "In a convection problem, using first-order discretization in space leads to excessive numerical diffusion (as you probably observed in [Lesson 1 of Module 2](https://nbviewer.jupyter.org/github/numerical-mooc/numerical-mooc/blob/master/lessons/02_spacetime/02_01_1DConvection.ipynb)). The simplest approach to get second-order accuracy in space is to use a central difference:\n", "\n", "$$\n", "\\begin{equation}\n", "\\frac{\\partial F}{\\partial x} \\approx \\frac{1}{2\\Delta x}( F_{i+1}-F_{i-1})\n", "\\end{equation}\n", "$$\n", "\n", "But combining these two choices for time and space discretization in the convection equation has catastrophic results! The \"forward-time, central scheme\" (FTCS) is **unstable**. (Go on: try it; you know you want to!)\n", "\n", "The Lax-Friedrichs scheme was proposed by Lax (1954) as a clever trick to stabilize the forward-time, central scheme. The idea was to replace the solution value at $\\rho^n_i$ by the average of the values at the neighboring grid points. If we do that replacement, we get the following discretized equation: \n", "\n", "$$\n", "\\begin{equation}\n", "\\frac{\\rho_i^{n+1}-\\frac{1}{2}(\\rho^n_{i+1}+\\rho^n_{i-1})}{\\Delta t} = -\\frac{F^n_{i+1}-F^n_{i-1}}{2 \\Delta x}\n", "\\end{equation}\n", "$$\n", "\n", "Take a careful look: the difference formula no longer uses the value at $\\rho^n_i$ to obtain $\\rho^{n+1}_i$. The stencil of the Lax-Friedrichs scheme is slightly different than that for the forward-time, central scheme." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![Stencil of the forward-time central scheme](./figures/FD-stencil_FTCS.png)\n", "#### Figure 2. Stencil of the forward-time/central scheme.\n", "\n", "![Stencil of the Lax-Friedrichs scheme](./figures/FD-stencil_LF.png)\n", "#### Figure 3. Stencil of the Lax-Friedrichs scheme." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This numerical discretization is **stable**. Unfortunately, substituting $\\rho^n_i$ by the average of its neighbors introduces a first-order error. _Nice try, Lax!_\n", "\n", "To implement the scheme in code, we need to isolate the value at the next time step, $\\rho^{n+1}_i$, so we can write a time-stepping loop:\n", "\n", "$$\n", "\\begin{equation}\n", "\\rho_i^{n+1} = \\frac{1}{2}(\\rho^n_{i+1}+\\rho^n_{i-1}) - \\frac{\\Delta t}{2 \\Delta x}(F^n_{i+1}-F^n_{i-1})\n", "\\end{equation}\n", "$$\n", "\n", "The function below implements Lax-Friedrichs for our traffic model. All the schemes in this notebook are wrapped in their own functions to help with displaying animations of the results. This is also good practice for developing modular, reusable code.\n", "\n", "In order to display animations, we're going to hold the results of each time step in the variable `rho`, a 2D array. The resulting array `rho_n` has `nt` rows and `nx` columns." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "def lax_friedrichs(rho0, nt, dt, dx, bc_values, *args):\n", " \"\"\"\n", " Computes the traffic density on the road \n", " at a certain time given the initial traffic density.\n", " Integration using Lax-Friedrichs scheme.\n", " \n", " Parameters\n", " ----------\n", " rho0 : numpy.ndarray\n", " The initial traffic density along the road\n", " as a 1D array of floats.\n", " nt : integer\n", " The number of time steps to compute.\n", " dt : float\n", " The time-step size to integrate.\n", " dx : float\n", " The distance between two consecutive locations.\n", " bc_values : 2-tuple of floats\n", " The value of the density at the first and last locations.\n", " args : list or tuple\n", " Positional arguments to be passed to the flux function.\n", " \n", " Returns\n", " -------\n", " rho_hist : list of numpy.ndarray objects\n", " The history of the car density along the road.\n", " \"\"\"\n", " rho_hist = [rho0.copy()]\n", " rho = rho0.copy()\n", " for n in range(nt):\n", " # Compute the flux.\n", " F = flux(rho, *args)\n", " # Advance in time using Lax-Friedrichs scheme.\n", " rho[1:-1] = (0.5 * (rho[:-2] + rho[2:]) -\n", " dt / (2.0 * dx) * (F[2:] - F[:-2]))\n", " # Set the value at the first location.\n", " rho[0] = bc_values[0]\n", " # Set the value at the last location.\n", " rho[-1] = bc_values[1]\n", " # Record the time-step solution.\n", " rho_hist.append(rho.copy())\n", " return rho_hist" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lax-Friedrichs with $\\frac{\\Delta t}{\\Delta x}=1$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We are now all set to run! First, let's try with CFL=1" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "# Set the time-step size based on CFL limit.\n", "sigma = 1.0\n", "dt = sigma * dx / u_max # time-step size\n", "\n", "# Compute the traffic density at all time steps.\n", "rho_hist = lax_friedrichs(rho0, nt, dt, dx, (rho0[0], rho0[-1]),\n", " u_max, rho_max)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Create an animation of the traffic density.\n", "anim = animation.FuncAnimation(fig, update_plot,\n", " frames=nt, fargs=(rho_hist,),\n", " interval=100)\n", "# Display the video.\n", "HTML(anim.to_html5_video())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Think" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* What do you see in the animation above? How does the numerical solution compare with the exact solution (a left-traveling shock wave)? \n", "* What types of errors do you think we see? \n", "* What do you think of the Lax-Friedrichs scheme, so far?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lax-Friedrichs with $\\frac{\\Delta t}{\\Delta x} = 0.5$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Would the solution improve if we use smaller time steps? Let's check that!" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [], "source": [ "# Set the time-step size based on CFL limit.\n", "sigma = 0.5\n", "dt = sigma * dx / u_max # time-step size\n", "\n", "# Compute the traffic density at all time steps.\n", "rho_hist = lax_friedrichs(rho0, nt, dt, dx, (rho0[0], rho0[-1]),\n", " u_max, rho_max)" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Create an animation of the traffic density.\n", "anim = animation.FuncAnimation(fig, update_plot,\n", " frames=nt, fargs=(rho_hist,),\n", " interval=100)\n", "# Display the video.\n", "HTML(anim.to_html5_video())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Dig deeper" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice the strange \"staircase\" behavior on the leading edge of the wave? You may be interested to learn more about this: a feature typical of what is sometimes called \"odd-even decoupling.\" Last year we published a collection of lessons in Computational Fluid Dynamics, called _CFD Python_, where we discuss [odd-even decoupling](https://nbviewer.jupyter.org/github/barbagroup/CFDPython/blob/14b56718ac1508671de66bab3fe432e93cb59fcb/lessons/19_Odd_Even_Decoupling.ipynb).\n", "\n", "* How does this solution compare with the previous one, where the Courant number was $\\frac{\\Delta t}{\\Delta x}=1$?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Lax-Wendroff scheme" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The Lax-Friedrichs method uses a clever trick to stabilize the central difference in space for convection, but loses an order of accuracy in doing so. First-order methods are just not good enough for convection problems, especially when you have sharp gradients (shocks).\n", "\n", "The Lax-Wendroff (1960) method was the _first_ scheme ever to achieve second-order accuracy in both space and time. It is therefore a landmark in the history of computational fluid dynamics.\n", "\n", "To develop the Lax-Wendroff scheme, we need to do a bit of work. Sit down, grab a notebook and grit your teeth. We want you to follow this derivation in your own hand. It's good for you! Start with the Taylor series expansion (in the time variable) about $\\rho^{n+1}$:\n", "\n", "$$\n", "\\begin{equation}\n", "\\rho^{n+1} = \\rho^n + \\frac{\\partial\\rho^n}{\\partial t} \\Delta t + \\frac{(\\Delta t)^2}{2}\\frac{\\partial^2\\rho^n}{\\partial t^2} + \\ldots\n", "\\end{equation}\n", "$$\n", "\n", "For the conservation law with $F=F(\\rho)$, and using our beloved chain rule, we can write:\n", "\n", "$$\n", "\\begin{equation}\n", "\\frac{\\partial \\rho}{\\partial t} = -\\frac{\\partial F}{\\partial x} = -\\frac{\\partial F}{\\partial \\rho} \\frac{\\partial \\rho}{\\partial x} = -J \\frac{\\partial \\rho}{\\partial x}\n", "\\end{equation}\n", "$$\n", "\n", "where \n", "\n", "$$\n", "\\begin{equation}\n", "J = \\frac{\\partial F}{\\partial \\rho} = u _{\\rm max} \\left(1-2\\frac{\\rho}{\\rho_{\\rm max}} \\right)\n", "\\end{equation}\n", "$$\n", "\n", "is the _Jacobian_ for the traffic model. Next, we can do a little trickery:\n", "\n", "$$\n", "\\begin{equation}\n", "\\frac{\\partial F}{\\partial t} = \\frac{\\partial F}{\\partial \\rho} \\frac{\\partial \\rho}{\\partial t} = J \\frac{\\partial \\rho}{\\partial t} = -J \\frac{\\partial F}{\\partial x}\n", "\\end{equation}\n", "$$\n", "\n", "In the last step above, we used the differential equation of the traffic model to replace the time derivative by a spatial derivative. These equivalences imply that\n", "\n", "$$\n", "\\begin{equation}\n", "\\frac{\\partial^2\\rho}{\\partial t^2} = \\frac{\\partial}{\\partial x} \\left( J \\frac{\\partial F}{\\partial x} \\right)\n", "\\end{equation}\n", "$$\n", "\n", "Let's use all this in the Taylor expansion:\n", "\n", "$$\n", "\\begin{equation}\n", "\\rho^{n+1} = \\rho^n - \\frac{\\partial F^n}{\\partial x} \\Delta t + \\frac{(\\Delta t)^2}{2} \\frac{\\partial}{\\partial x} \\left(J\\frac{\\partial F^n}{\\partial x} \\right)+ \\ldots\n", "\\end{equation}\n", "$$\n", "\n", "We can now reorganize this and discretize the spatial derivatives with central differences to get the following discrete equation:\n", "\n", "$$\n", "\\begin{equation}\n", "\\frac{\\rho_i^{n+1} - \\rho_i^n}{\\Delta t} = -\\frac{F^n_{i+1}-F^n_{i-1}}{2 \\Delta x} + \\frac{\\Delta t}{2} \\left(\\frac{(J \\frac{\\partial F}{\\partial x})^n_{i+\\frac{1}{2}}-(J \\frac{\\partial F}{\\partial x})^n_{i-\\frac{1}{2}}}{\\Delta x}\\right)\n", "\\end{equation}\n", "$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, approximate the rightmost term (inside the parenthesis) in the above equation as follows:\n", "\\begin{equation} \\frac{J^n_{i+\\frac{1}{2}}\\left(\\frac{F^n_{i+1}-F^n_{i}}{\\Delta x}\\right)-J^n_{i-\\frac{1}{2}}\\left(\\frac{F^n_i-F^n_{i-1}}{\\Delta x}\\right)}{\\Delta x}\\end{equation}\n", "\n", "Then evaluate the Jacobian at the midpoints by using averages of the points on either side:\n", "\n", "\\begin{equation}\\frac{\\frac{1}{2 \\Delta x}(J^n_{i+1}+J^n_i)(F^n_{i+1}-F^n_i)-\\frac{1}{2 \\Delta x}(J^n_i+J^n_{i-1})(F^n_i-F^n_{i-1})}{\\Delta x}.\\end{equation}\n", "\n", "Our equation now reads:\n", "\n", "\\begin{align}\n", "&\\frac{\\rho_i^{n+1} - \\rho_i^n}{\\Delta t} = \n", "-\\frac{F^n_{i+1}-F^n_{i-1}}{2 \\Delta x} + \\cdots \\\\ \\nonumber \n", "&+ \\frac{\\Delta t}{4 \\Delta x^2} \\left( (J^n_{i+1}+J^n_i)(F^n_{i+1}-F^n_i)-(J^n_i+J^n_{i-1})(F^n_i-F^n_{i-1})\\right)\n", "\\end{align}\n", "\n", "Solving for $\\rho_i^{n+1}$:\n", "\n", "\\begin{align}\n", "&\\rho_i^{n+1} = \\rho_i^n - \\frac{\\Delta t}{2 \\Delta x} \\left(F^n_{i+1}-F^n_{i-1}\\right) + \\cdots \\\\ \\nonumber \n", "&+ \\frac{(\\Delta t)^2}{4(\\Delta x)^2} \\left[ (J^n_{i+1}+J^n_i)(F^n_{i+1}-F^n_i)-(J^n_i+J^n_{i-1})(F^n_i-F^n_{i-1})\\right]\n", "\\end{align}\n", "\n", "with\n", "\n", "\\begin{equation}J^n_i = \\frac{\\partial F}{\\partial \\rho} = u_{\\rm max} \\left(1-2\\frac{\\rho^n_i}{\\rho_{\\rm max}} \\right).\\end{equation} \n", "\n", "Lax-Wendroff is a little bit long. Remember that you can use \\ slashes to split up a statement across several lines. This can help make code easier to parse (and also easier to debug!). " ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "def jacobian(rho, u_max, rho_max):\n", " \"\"\"\n", " Computes the Jacobian for our traffic model.\n", " \n", " Parameters\n", " ----------\n", " rho : numpy.ndarray\n", " Traffic density along the road as a 1D array of floats.\n", " u_max : float\n", " Maximum speed allowed on the road.\n", " rho_max : float\n", " Maximum car density allowed on the road.\n", " \n", " Returns\n", " -------\n", " J : numpy.ndarray\n", " The Jacobian as a 1D array of floats.\n", " \"\"\"\n", " J = u_max * (1.0 - 2.0 * rho / rho_max)\n", " return J" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "def lax_wendroff(rho0, nt, dt, dx, bc_values, *args):\n", " \"\"\"\n", " Computes the traffic density on the road \n", " at a certain time given the initial traffic density.\n", " Integration using Lax-Wendroff scheme.\n", " \n", " Parameters\n", " ----------\n", " rho0 : numpy.ndarray\n", " The initial traffic density along the road\n", " as a 1D array of floats.\n", " nt : integer\n", " The number of time steps to compute.\n", " dt : float\n", " The time-step size to integrate.\n", " dx : float\n", " The distance between two consecutive locations.\n", " bc_values : 2-tuple of floats\n", " The value of the density at the first and last locations.\n", " args : list or tuple\n", " Positional arguments to be passed to the\n", " flux and Jacobien functions.\n", " \n", " Returns\n", " -------\n", " rho_hist : list of numpy.ndarray objects\n", " The history of the car density along the road.\n", " \"\"\"\n", " rho_hist = [rho0.copy()]\n", " rho = rho0.copy()\n", " for n in range(nt):\n", " # Compute the flux.\n", " F = flux(rho, *args)\n", " # Compute the Jacobian.\n", " J = jacobian(rho, *args)\n", " # Advance in time using Lax-Wendroff scheme.\n", " rho[1:-1] = (rho[1:-1] -\n", " dt / (2.0 * dx) * (F[2:] - F[:-2]) +\n", " dt**2 / (4.0 * dx**2) *\n", " ((J[1:-1] + J[2:]) * (F[2:] - F[1:-1]) -\n", " (J[:-2] + J[1:-1]) * (F[1:-1] - F[:-2])))\n", " # Set the value at the first location.\n", " rho[0] = bc_values[0]\n", " # Set the value at the last location.\n", " rho[-1] = bc_values[1]\n", " # Record the time-step solution.\n", " rho_hist.append(rho.copy())\n", " return rho_hist" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that's we've defined a function for the Lax-Wendroff scheme, we can use the same procedure as above to animate and view our results. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lax-Wendroff with $\\frac{\\Delta t}{\\Delta x}=1$" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "# Set the time-step size based on CFL limit.\n", "sigma = 1.0\n", "dt = sigma * dx / u_max # time-step size\n", "\n", "# Compute the traffic density at all time steps.\n", "rho_hist = lax_wendroff(rho0, nt, dt, dx, (rho0[0], rho0[-1]),\n", " u_max, rho_max)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Create an animation of the traffic density.\n", "anim = animation.FuncAnimation(fig, update_plot,\n", " frames=nt, fargs=(rho_hist,),\n", " interval=100)\n", "# Display the video.\n", "HTML(anim.to_html5_video())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Interesting! The Lax-Wendroff method captures the sharpness of the shock much better than the Lax-Friedrichs scheme, but there is a new problem: a strange wiggle appears right at the tail of the shock. This is typical of many second-order methods: they introduce _numerical oscillations_ where the solution is not smooth. Bummer." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Lax-Wendroff with $\\frac{\\Delta t}{\\Delta x} =0.5$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "How do the oscillations at the shock front vary with changes to the CFL condition? You might think that the solution will improve if you make the time step smaller ... let's see." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "# Set the time-step size based on CFL limit.\n", "sigma = 0.5\n", "dt = sigma * dx / u_max # time-step size\n", "\n", "# Compute the traffic density at all time steps.\n", "rho_hist = lax_wendroff(rho0, nt, dt, dx, (rho0[0], rho0[-1]),\n", " u_max, rho_max)" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Create an animation of the traffic density.\n", "anim = animation.FuncAnimation(fig, update_plot,\n", " frames=nt, fargs=(rho_hist,),\n", " interval=100)\n", "# Display the video.\n", "HTML(anim.to_html5_video())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Eek! The numerical oscillations got worse. Double bummer!\n", "\n", "Why do we observe oscillations with second-order methods? This is a question of fundamental importance!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## MacCormack Scheme" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The numerical oscillations that you observed with the Lax-Wendroff method on the traffic model can become severe in some problems. But actually the main drawback of the Lax-Wendroff method is having to calculate the Jacobian in every time step. With more complicated equations (like the Euler equations), calculating the Jacobian is a large computational expense.\n", "\n", "Robert W. MacCormack introduced the first version of his now-famous method at the 1969 AIAA Hypervelocity Impact Conference, held in Cincinnati, Ohio, but the paper did not at first catch the attention of the aeronautics community. The next year, however, he presented at the 2nd International Conference on Numerical Methods in Fluid Dynamics at Berkeley. His paper there (MacCormack, 1971) was a landslide. MacCormack got a promotion and continued to work on applications of his method to the compressible Navier-Stokes equations. In 1973, NASA gave him the prestigious H. Julian Allen award for his work.\n", "\n", "The MacCormack scheme is a two-step method, in which the first step is called a _predictor_ and the second step is called a _corrector_. It achieves second-order accuracy in both space and time. One version is as follows: \n", "\n", "$$\n", "\\begin{equation}\n", "\\rho^*_i = \\rho^n_i - \\frac{\\Delta t}{\\Delta x} (F^n_{i+1}-F^n_{i}) \\ \\ \\ \\ \\ \\ \\text{(predictor)}\n", "\\end{equation}\n", "$$\n", "\n", "$$\n", "\\begin{equation}\n", "\\rho^{n+1}_i = \\frac{1}{2} (\\rho^n_i + \\rho^*_i - \\frac{\\Delta t}{\\Delta x} (F^*_i - F^{*}_{i-1})) \\ \\ \\ \\ \\ \\ \\text{(corrector)}\n", "\\end{equation}\n", "$$\n", "\n", "If you look closely, it appears like the first step is a forward-time/forward-space scheme, and the second step is like a forward-time/backward-space scheme (these can also be reversed), averaged with the first result. What is so cool about this? You can compute problems with left-running waves and right-running waves, and the MacCormack scheme gives you a stable method (subject to the CFL condition). Nice! Let's try it." ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "def maccormack(rho0, nt, dt, dx, bc_values, *args):\n", " \"\"\"\n", " Computes the traffic density on the road \n", " at a certain time given the initial traffic density.\n", " Integration using MacCormack scheme.\n", " \n", " Parameters\n", " ----------\n", " rho0 : numpy.ndarray\n", " The initial traffic density along the road\n", " as a 1D array of floats.\n", " nt : integer\n", " The number of time steps to compute.\n", " dt : float\n", " The time-step size to integrate.\n", " dx : float\n", " The distance between two consecutive locations.\n", " bc_values : 2-tuple of floats\n", " The value of the density at the first and last locations.\n", " args : list or tuple\n", " Positional arguments to be passed to the flux function.\n", " \n", " Returns\n", " -------\n", " rho_hist : list of numpy.ndarray objects\n", " The history of the car density along the road.\n", " \"\"\"\n", " rho_hist = [rho0.copy()]\n", " rho = rho0.copy()\n", " rho_star = rho.copy()\n", " for n in range(nt):\n", " # Compute the flux.\n", " F = flux(rho, *args)\n", " # Predictor step of the MacCormack scheme.\n", " rho_star[1:-1] = (rho[1:-1] -\n", " dt / dx * (F[2:] - F[1:-1]))\n", " # Compute the flux.\n", " F = flux(rho_star, *args)\n", " # Corrector step of the MacCormack scheme.\n", " rho[1:-1] = 0.5 * (rho[1:-1] + rho_star[1:-1] -\n", " dt / dx * (F[1:-1] - F[:-2]))\n", " # Set the value at the first location.\n", " rho[0] = bc_values[0]\n", " # Set the value at the last location.\n", " rho[-1] = bc_values[1]\n", " # Record the time-step solution.\n", " rho_hist.append(rho.copy())\n", " return rho_hist" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### MacCormack with $\\frac{\\Delta t}{\\Delta x} = 1$" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "# Set the time-step size based on CFL limit.\n", "sigma = 1.0\n", "dt = sigma * dx / u_max # time-step size\n", "\n", "# Compute the traffic density at all time steps.\n", "rho_hist = maccormack(rho0, nt, dt, dx, (rho0[0], rho0[-1]),\n", " u_max, rho_max)" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Create an animation of the traffic density.\n", "anim = animation.FuncAnimation(fig, update_plot,\n", " frames=nt, fargs=(rho_hist,),\n", " interval=100)\n", "# Display the video.\n", "HTML(anim.to_html5_video())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### MacCormack with $\\frac{\\Delta t}{\\Delta x}= 0.5$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Once again, we ask: how does the CFL number affect the errors? Which one gives better results? You just have to try it." ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "# Set the time-step size based on CFL limit.\n", "sigma = 0.5\n", "dt = sigma * dx / u_max # time-step size\n", "\n", "# Compute the traffic density at all time steps.\n", "rho_hist = maccormack(rho0, nt, dt, dx, (rho0[0], rho0[-1]),\n", " u_max, rho_max)" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Create an animation of the traffic density.\n", "anim = animation.FuncAnimation(fig, update_plot,\n", " frames=nt, fargs=(rho_hist,),\n", " interval=100)\n", "# Display the video.\n", "HTML(anim.to_html5_video())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Dig Deeper" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can also obtain a MacCormack scheme by reversing the predictor and corrector steps. For shocks, the best resolution will occur when the difference in the predictor step is in the direction of propagation. Try it out! Was our choice here the ideal one? In which case is the shock better resolved?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "##### Challenge task" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In the *red light* problem, $\\rho \\geq \\rho_{\\rm max}/2$, making the wave speed negative at all points . You might be wondering why we introduced these new methods; couldn't we have just used a forward-time/forward-space scheme? But, what if $\\rho_{\\rm in} < \\rho_{\\rm max}/2$? Now, a whole region has negative wave speeds and forward-time/backward-space is unstable. \n", "\n", "* How do Lax-Friedrichs, Lax-Wendroff and MacCormack behave in this case? Try it out!\n", "\n", "* As you decrease $\\rho_{\\rm in}$, what happens to the velocity of the shock? Why do you think that happens?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## References" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Peter D. Lax (1954), \"Weak solutions of nonlinear hyperbolic equations and their numerical computation,\" _Commun. Pure and Appl. Math._, Vol. 7, pp. 159–193.\n", "\n", "* Peter D. Lax and Burton Wendroff (1960), \"Systems of conservation laws,\" _Commun. Pure and Appl. Math._, Vol. 13, pp. 217–237.\n", "\n", "* R. W. MacCormack (1969), \"The effect of viscosity in hypervelocity impact cratering,\" AIAA paper 69-354. Reprinted on _Journal of Spacecraft and Rockets_, Vol. 40, pp. 757–763 (2003). Also on _Frontiers of Computational Fluid Dynamics_, edited by D. A. Caughey, M. M. Hafez (2002), chapter 2: [read on Google Books](http://books.google.com/books?id=QBsnMOz_8qcC&lpg=PA27&ots=uqCeuH1U6S&lr&pg=PA27#v=onepage&q&f=false).\n", "\n", "* R. W. MacCormack (1971), \"Numerical solution of the interaction of a shock wave with a laminar boundary layer,\" _Proceedings of the 2nd Int. Conf. on Numerical Methods in Fluid Dynamics_, Lecture Notes in Physics, Vol. 8, Springer, Berlin, pp. 151–163. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "\n", "###### The cell below loads the style of the notebook." ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from IPython.core.display import HTML\n", "css_file = '../../styles/numericalmoocstyle.css'\n", "HTML(open(css_file, 'r').read())" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (MOOC)", "language": "python", "name": "py36-mooc" }, "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.6" } }, "nbformat": 4, "nbformat_minor": 1 }