Indexed text attachment
partial-differential-equations-in-higher-categories.tex
Source for Partial Differential Equations in Higher Categories
View paper · Download original file
Lines 2561–2660 of 3921. Source text is displayed literally.
2561 2562\section{Squares that almost commute}2563 2564Let $E(t)$ be the solution operator of a well-posed linear evolution problem, $R_h$ the restriction of functions to2565a grid of mesh $h$, and $E_h$ one step of a scheme with time step $\Delta t$ tied to $h$.2566\[ \begin{tikzcd}[column sep=large]2567X\ar[r,"E(\Delta t)"]\ar[d,"R_h"'] & X\ar[d,"R_h"]\\2568X_h\ar[r,"E_h"'] & X_h2569\end{tikzcd} \]2570The scheme is \term{consistent} of order $p$ if the square commutes up to $O(\Delta t\,h^p)$ on smooth functions;2571\term{stable} if the powers $E_h^n$ are bounded uniformly for $n\Delta t\le T$; \term{convergent} if2572$E_h^nR_h-R_hE(n\Delta t)\to0$.2573 2574\begin{theorem}[Lax equivalence]\label{thm:lax}2575\Scl[\cite{LaRi56}] For a consistent scheme, stability is equivalent to convergence.2576\end{theorem}2577\begin{proof}[Idea]2578$E_h^nR_h-R_hE^n=\sum_{j<n}E_h^{n-1-j}(E_hR_h-R_hE)E^j$: the defect of one square, transported by the remaining2579steps. Stability is exactly what keeps the transport from amplifying it.2580\end{proof}2581 2582\noindent The centred three-level scheme for the heat equation is consistent of second order and its amplification2583factor exceeds one for every mesh ratio, $1.48$ at ratio $0.1$: it converges for no data but the trivial. \chk{N10}2584 2585\section{Diffusion}2586 2587For the explicit scheme with $s=k\Delta t/\Delta x^2$ the amplification factor of the mode $e^{ikx}$ is2588$1-2s(1-\cos k\Delta x)$ \src{\S8.2}.2589 2590\begin{theorem}\label{thm:explicit}2591\Scl[source, \S8.2] The explicit scheme is stable if and only if $s\le\tfrac12$, which is also the condition for its2592matrix to have non-negative entries.2593\end{theorem}2594 2595\noindent At $s=0.52$ the computed growth per step equals the predicted $1.0684$; at $s=0.5$ nothing grows.2596\chk{N1} The second clause is \Cref{thm:max}: stability, here, is that the scheme is a morphism of the Markov2597category, and the source's observation that ``none of the coefficients are negative'' predicts the right2598condition for that reason. The error is of second order in $\Delta x$, and of fourth order at the special ratio2599$s=\tfrac16$, where the leading error terms in time and space cancel: halving the mesh divides the error by2600$4.06$ and by $16.1$. \chk{N2} The Crank--Nicolson scheme, the Cayley transform of the generator, has amplification2601factor of modulus at most one for every $s$ and is of second order in time. \chk{N3}2602 2603\begin{center}2604\begin{tikzpicture}2605\begin{scope}[shift={(0,0)}]2606\draw[ink2] (0,3.6)--(0,0)--(6.6,0);2607\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};2608\draw[ink2] (3.3,0)--(3.3,-0.07) node[below,inner sep=1.5pt]{\scriptsize $\pi/2$};2609\draw[ink2] (6.6,0)--(6.6,-0.07) node[below,inner sep=1.5pt]{\scriptsize $\pi$};2610\draw[ink2] (0,0.785)--(-0.07,0.785) node[left,inner sep=1.5pt]{\scriptsize $-1$};2611\draw[ink2] (0,2.095)--(-0.07,2.095) node[left,inner sep=1.5pt]{\scriptsize $0$};2612\draw[ink2] (0,3.404)--(-0.07,3.404) node[left,inner sep=1.5pt]{\scriptsize $1$};2613\node[below] at (3.3,-0.38) {\scriptsize $k\,\Delta x$};2614\node[above,inner sep=1pt] at (0,3.65) {\scriptsize $\xi$};2615\fill[fwd!8] (0,0.785) rectangle (6.6,3.404);2616\draw[ink2,very thin] (0,2.095)--(6.6,2.095);2617\draw[ink2] (0,0.785)--(6.6,0.785);2618\draw[ink2] (0,3.404)--(6.6,3.404);2619\draw[thick,ink2] plot coordinates {(0,3.404) (0.082,3.403) (0.165,3.402) (0.247,3.399) (0.33,3.396) (0.412,3.391) (0.495,3.386) (0.578,3.379) (0.66,3.372) (0.742,3.363) (0.825,3.354) (0.907,3.344) (0.99,3.332) (1.072,3.32) (1.155,3.307) (1.237,3.293) (1.32,3.279) (1.402,3.263) (1.485,3.247) (1.568,3.23) (1.65,3.212) (1.732,3.193) (1.815,3.174) (1.897,3.154) (1.98,3.134) (2.062,3.113) (2.145,3.091) (2.228,3.069) (2.31,3.046) (2.393,3.023) (2.475,3) (2.558,2.976) (2.64,2.951) (2.723,2.927) (2.805,2.902) (2.887,2.877) (2.97,2.851) (3.052,2.826) (3.135,2.8) (3.217,2.775) (3.3,2.749) (3.382,2.723) (3.465,2.698) (3.547,2.672) (3.63,2.647) (3.712,2.621) (3.795,2.596) (3.877,2.571) (3.96,2.547) (4.042,2.523) (4.125,2.499) (4.207,2.475) (4.29,2.452) (4.373,2.429) (4.455,2.407) (4.538,2.385) (4.62,2.364) (4.702,2.344) (4.785,2.324) (4.867,2.305) (4.95,2.286) (5.032,2.268) (5.115,2.251) (5.197,2.235) (5.28,2.22) (5.362,2.205) (5.445,2.191) (5.527,2.178) (5.61,2.166) (5.692,2.155) (5.775,2.144) (5.858,2.135) (5.94,2.127) (6.022,2.119) (6.105,2.113) (6.187,2.107) (6.27,2.103) (6.353,2.099) (6.435,2.097) (6.518,2.095) (6.6,2.095)};2620\draw[thick,fwd] plot coordinates {(0,3.404) (0.082,3.403) (0.165,3.4) (0.247,3.395) (0.33,3.388) (0.412,3.378) (0.495,3.367) (0.578,3.354) (0.66,3.34) (0.742,3.323) (0.825,3.304) (0.907,3.283) (0.99,3.261) (1.072,3.237) (1.155,3.211) (1.237,3.183) (1.32,3.154) (1.402,3.123) (1.485,3.09) (1.568,3.056) (1.65,3.02) (1.732,2.983) (1.815,2.945) (1.897,2.905) (1.98,2.864) (2.062,2.822) (2.145,2.779) (2.228,2.734) (2.31,2.689) (2.393,2.643) (2.475,2.596) (2.558,2.548) (2.64,2.499) (2.723,2.45) (2.805,2.4) (2.887,2.35) (2.97,2.299) (3.052,2.248) (3.135,2.197) (3.217,2.146) (3.3,2.095) (3.382,2.043) (3.465,1.992) (3.547,1.941) (3.63,1.89) (3.712,1.839) (3.795,1.789) (3.877,1.739) (3.96,1.69) (4.042,1.641) (4.125,1.594) (4.207,1.546) (4.29,1.5) (4.373,1.455) (4.455,1.411) (4.538,1.367) (4.62,1.325) (4.702,1.284) (4.785,1.244) (4.867,1.206) (4.95,1.169) (5.032,1.133) (5.115,1.099) (5.197,1.066) (5.28,1.035) (5.362,1.006) (5.445,0.978) (5.527,0.952) (5.61,0.928) (5.692,0.906) (5.775,0.885) (5.858,0.866) (5.94,0.85) (6.022,0.835) (6.105,0.822) (6.187,0.811) (6.27,0.802) (6.353,0.795) (6.435,0.789) (6.518,0.786) (6.6,0.785)};2621\draw[thick,bwd] plot coordinates {(0,3.404) (0.082,3.402) (0.165,3.399) (0.247,3.393) (0.33,3.384) (0.412,3.373) (0.495,3.36) (0.578,3.345) (0.66,3.327) (0.742,3.307) (0.825,3.284) (0.907,3.259) (0.99,3.232) (1.072,3.203) (1.155,3.172) (1.237,3.139) (1.32,3.104) (1.402,3.066) (1.485,3.027) (1.568,2.986) (1.65,2.944) (1.732,2.899) (1.815,2.853) (1.897,2.805) (1.98,2.756) (2.062,2.705) (2.145,2.654) (2.228,2.6) (2.31,2.546) (2.393,2.49) (2.475,2.434) (2.558,2.376) (2.64,2.318) (2.723,2.259) (2.805,2.199) (2.887,2.139) (2.97,2.078) (3.052,2.017) (3.135,1.956) (3.217,1.894) (3.3,1.833) (3.382,1.771) (3.465,1.709) (3.547,1.648) (3.63,1.587) (3.712,1.526) (3.795,1.466) (3.877,1.406) (3.96,1.347) (4.042,1.289) (4.125,1.232) (4.207,1.175) (4.29,1.12) (4.373,1.065) (4.455,1.012) (4.538,0.96) (4.62,0.909) (4.702,0.86) (4.785,0.813) (4.867,0.766) (4.95,0.722) (5.032,0.679) (5.115,0.638) (5.197,0.599) (5.28,0.562) (5.362,0.527) (5.445,0.493) (5.527,0.462) (5.61,0.433) (5.692,0.406) (5.775,0.381) (5.858,0.359) (5.94,0.339) (6.022,0.321) (6.105,0.305) (6.187,0.292) (6.27,0.281) (6.353,0.273) (6.435,0.267) (6.518,0.263) (6.6,0.262)};2622\draw[thick,accent,densely dashed] plot coordinates {(0,3.404) (0.082,3.4) (0.165,3.388) (0.247,3.368) (0.33,3.341) (0.412,3.307) (0.495,3.267) (0.578,3.221) (0.66,3.17) (0.742,3.116) (0.825,3.058) (0.907,2.997) (0.99,2.935) (1.072,2.872) (1.155,2.808) (1.237,2.744) (1.32,2.68) (1.402,2.617) (1.485,2.555) (1.568,2.495) (1.65,2.436) (1.732,2.38) (1.815,2.325) (1.897,2.272) (1.98,2.221) (2.062,2.172) (2.145,2.125) (2.228,2.08) (2.31,2.037) (2.393,1.996) (2.475,1.957) (2.558,1.92) (2.64,1.885) (2.723,1.851) (2.805,1.819) (2.887,1.789) (2.97,1.76) (3.052,1.732) (3.135,1.706) (3.217,1.682) (3.3,1.658) (3.382,1.636) (3.465,1.615) (3.547,1.595) (3.63,1.576) (3.712,1.558) (3.795,1.541) (3.877,1.524) (3.96,1.509) (4.042,1.495) (4.125,1.481) (4.207,1.468) (4.29,1.455) (4.373,1.444) (4.455,1.433) (4.538,1.422) (4.62,1.412) (4.702,1.403) (4.785,1.394) (4.867,1.386) (4.95,1.379) (5.032,1.371) (5.115,1.365) (5.197,1.358) (5.28,1.352) (5.362,1.347) (5.445,1.342) (5.527,1.337) (5.61,1.333) (5.692,1.329) (5.775,1.326) (5.858,1.322) (5.94,1.32) (6.022,1.317) (6.105,1.315) (6.187,1.313) (6.27,1.312) (6.353,1.311) (6.435,1.31) (6.518,1.309) (6.6,1.309)};2623\node[ink2,right] at (6.6,2.095) {\scriptsize $s=0.25$};2624\node[fwd,right] at (6.6,0.785) {\scriptsize $s=0.5$};2625\node[bwd,right] at (6.6,0.262) {\scriptsize $s=0.6$};2626\node[accent,right] at (6.6,1.309) {\scriptsize Crank--Nicolson, $s=2$};2627\end{scope}2628\end{tikzpicture}2629\figcap{The factor by which one step of the explicit scheme multiplies the mode $e^{ikx}$, for three values of $s=k\,\Delta t/\Delta x^2$, and of the Crank--Nicolson scheme at $s=2$. Stability is confinement to the band $|\xi|\le1$; at $s=0.6$ the shortest waves leave it.}2630\end{center}2631 2632\section{Waves}2633 2634\begin{theorem}[Courant--Friedrichs--Lewy]\label{thm:cfl}2635\Scl[source, \S8.3; \cite{CFL28}] The centred scheme for the wave equation is stable if and only if2636$c\,\Delta t\le\Delta x$. If $c\,\Delta t>\Delta x$ the scheme cannot converge, whatever its other properties: its2637domain of dependence is strictly inside the true one.2638\end{theorem}2639 2640\noindent The source writes the condition as $s=c^2\Delta t^2/\Delta x^2\le1$ and gives the same explanation. With2641$c\,\Delta t=2\Delta x$ the scheme returns bit-identical values at $(0,1)$ for two data sets that differ only near2642$x=1$, at every refinement, while the exact solutions differ by $1/2e$. \chk{N5} This is \Cref{thm:causal} read as a2643constraint: a discretization must respect the causal structure of the solution functor, in the sense that the2644discrete domains of dependence contain the continuous ones. At equality the scheme is the parallelogram identity2645of \Cref{cor:par} and reproduces exact solutions to rounding error; at $s=1.1$ the sawtooth grows by the predicted2646factor $1.8633$ per step. \chk{N4} A scheme that preserves the symplectic form of \Cref{prop:symp} is constructed in2647\Cref{ch:fields}.2648 2649\begin{center}2650\begin{tikzpicture}2651\begin{scope}[xshift=0cm]2652\fill[ink2] (-2,0) circle (1pt);2653\fill[ink2] (-1.5,0) circle (1pt);2654\fill[ink2] (-1,0) circle (1pt);2655\fill[ink2] (-0.5,0) circle (1pt);2656\fill[ink2] (0,0) circle (1pt);2657\fill[ink2] (0.5,0) circle (1pt);2658\fill[ink2] (1,0) circle (1pt);2659\fill[ink2] (1.5,0) circle (1pt);2660\fill[ink2] (2,0) circle (1pt);