> <\body> > TODO: <\itemize> How did we deduce TVD for the PDE? Lax's entropy condition: > or >? Strange second integral condition in derivation of Godunov. Why the meshing restriction for FD? <\section> Miscellanea <\itemize> An interpolation polynomial is monotone in a jump cell. Example: Degree-five polynomial, six points, degree-four derivative, four derivative zeros in each of the boundary cells>none in the center jump cell. <\itemize> : +f(u)=0>. Initial condition >. : <\equation> |\t>u(x,t)=f(u(b,t))-f(u(a,t)). : Defined by <\equation*> |\t>u(x(t),t)=ux+u0, setting =f>. May cross. : <\itemize> () for almost all For any \C(\)>, 0> <\equation*> ->>u\+f(u)\\x\t->>u(x)\(x,0)\x=0. Both definitions equivalent. : Curve parameterized by separates two smooth regions. <\equation*> s=x(t)=|> Proof: Split () at , carry out time derivative, observe Leibniz rule, apply conservation law. : Conservation law with single-jump (otherwise constant) IC. Rarefaction () is a weak solution, jump is also weak solution>non-uniqueness. If is convex, the general solution \; <\equation*> u(x,t)=>|s*t,>>|>|s*t,>>>>>>|\u,>>|>|f(u)t,>>|)(x/t)>|,>>|>|f(u)t,>>>>>>|\u.>>>>> : add >> to the RHS of the conservation law, letting \0>. : convex (\0>). : (u)=U(u)f(u)>. : an entropy-entropy flux pair. Then is an entropy solution iff <\equation*> U(u)+F(u)\0 weakly. Proof: Multiply c.law by (u>)>, gather derivatives. On RHS, write <\equation*> U(u>)u>=(U(u>)u>)-U(u>)(u>)\(U(u>)u>). Then multiply by smooth \0> and integrate by parts twice. Pass to limit by DCT, RHS vanishes because >> is bounded--maximum principle. The conservation law is <\itemize> : (u)\0> uniformly, : (u)\0> uniformly, : (u)\0> uniformly. : <\itemize> : (t)\> by applying a Rankine-Hugoniot type argument to +F(u)\0>. : For all [u,u]>: <\equation*> )|u-u>\s\)|u-u>, where is the shock speed from Rankine-Hugoniot. : <\equation*> f(u)\s\f(u). Not sufficient for uniqueness, but necessary. Sufficient if (u)\0> uniformly. Simpler if (u)\0>: <\equation*> f(u)\f(u). Since > is >, we can only jump down. Characteristics only go shocks, never out of them because their speed is clamped. > contraction>: For >+f(u>)=\u>> with >(0,t)=u(x)>, we have <\equation*> >(\,t)-v>(\,t)|L|>\-v|L|>, where >> solves the same PDE with IC >. Proof: Chop up <\equation*> |\t>>>\|u>-v>\| at the sign changes. Put in > as a sign function on each interval. Use Leibniz's rule, then the c.law, which can be integrated out to zero, leaving some > terms, which can be deduced to have the right sign. : <\equation*> TV(u)\sup\x : ,t))\TV(u)>. <\itemize> : Discretize =u*u> 255-style, and get a monstrosity that leaves a 1-0 shock just where it is. : <\equation*> u=u-t|\x>-, with <\itemize> > consistent, i.e. (u,\,u)=f(u)>, > locally Lipschitz. : <\equation*> >>a(b-b)=->>(a-a)b-a>b-1>+a>b>. : If }> converges (t,\x\0>) boundedly a.e. to a function > a weak solution. Proof: Summation by parts, DCT, Conservativity. : <\itemize> : Exploit finite propagation speed, solve Riemann problem on each cell, demanding that <\eqnarray*> >(u+f(u))\x\t>||>>> To get >, use the exact Riemann solution at >. <\equation*> =,u]>f(u)>|\u,>>|,u]>f(u)>|\u.>>>>> : <\equation*> =f(u)+f(u)-\\u <\itemize> : =max,u]>\|f(u)\|>, : =max\|f(u)\|>. : <\equation*> =)>|\0>>|)>|\0>>>>>,a=f(u)|\u>. : <\eqnarray*> >||(u)-f(u),>>|(u)>||f(u)\0\u+f(0),>>|(u)>||f(u)\0\u.>>>> : <\itemize> Taylor-expand > in . Replace time derivatives with 2nd-order centered differences to desired order. <\equation*> =f(u)+f(u)-\f(u)(f(u)-f(u)), where <\equation*> u=+u|2>,\=t|\x>. : Predictor-corrector-style <\eqnarray*> >||-\(f(u)-f(u)),>>|>||u+u+\f(u)-f(u).>>>> : Write =G(u,\u)>. Monotone iff ,\,\)>. <\itemize> : \ ,u,u)=u-\[(u,u)-(u,u)]>>,?,\)>. >G=1-\(-)\0!> > >,\>)>. L-F is monotone. Properties: <\itemize> \v> for all >)\G(v)> Proof: by definition. Local maximum principle <\equation*> minstencil>u\G(u)\maxstencil>u Proof: Define to be > on the stencil and otherwise. Then\ <\equation*> min=G(w)\G(u). > contraction>: |>\|>> Proof: Let u\v>. Then G(w)> and (G(u)-G(v))>. Then <\equation*> (G(u)-G(v))\[G(w)-G(v)]>(w-v)=(u-v). . Take =u> in > contraction. : Let and =(c\u)-(c\u)>. <\equation*> )-U(u)|\t>+-|\x>\0 Proof: Show <\equation*> G(c\u)-G(c\u)=\|u-c\|-\(-) by starting with the LHS. Next, u\G(c\u)> and so <\equation*> U(u)=\|u-c\|\G(c\u)-G(c\u). : Montone schemes are at most first-order accurate. Proof: The scheme is second-order accurate for an equation with dissipation, so it can't also be second-order accurate for the original c.law. . : <\equation*> u\u\j\u\u\j. > monotonicity-preserving>. Proof: Suppose it isn't. Then you can make constant outside the relevant stencils. Reversal of order of the two values implies non-TVD. : Linear if applied to a linear PDE. Also ``positive'' because Monotone>positive coefficients. Can be written <\equation*> u=c(\)u. >monotone>. Proof: Consider first differences of a Heaviside jump>all coefficients positive. >at most first order>. Proof: Plug in constant, linear term, quadratic term to obtain <\eqnarray*> ||c,\>>|>||l*c,>>|>||lc.\>>>> Then \(l>)>, \(>)> and Cauchy-Schwarz (equality iff =\\>) to show that not all three can hold. Assume (u)\0> (wind from the left) for the moment. <\itemize> : <\equation*> |\t>>>u\x+f(u(x))-f(u(x))=0, then <\equation*> >\x>>>u\x, so <\equation*> |\t>>=x>- with <\equation*> 1/2>\f(u(x1/2>)). : <\eqnarray*> >>||>+>,>>|)>>||3>->.>>>> Goal is to compute polynomial such that x>>p(x)=>> for some s. Then evaluate at >. : <\equation*> minmod(a,b,c)=|,>>||.>>>>> : <\equation*> >=>+\(C\>-D\>) is TVD if: <\eqnarray*> >|>|>|>|>|>|(C+D)>|>|>>> Proof: Look at \|\>\|>, observe sum-arounds. : <\equation*> =>+u)>->,u)>->|\>\>. Is TVD by Harten's lemma. Proof: Take <\eqnarray*> >>||>-\f(>+)-f(>+)=>-\-D\>],>>>> and <\eqnarray*> >||>+)-f(>+)|>->>=f(\)>->+-|>->>>>|||(\)1+|>->>|\>\\>-|>->>|\>\\>\0>>>> CFL restriction: *max\|f\|\2/3>. Now lift wind-from-left restriction. <\itemize> General form: <\eqnarray*> >>||>-\(u,u)-(u,u),>>>> where (\,\)> is a monotone flux. Now choose <\equation*> u=>+minmod(u->,>->,>->) etc. Prove TVD by <\equation*> >=>-\(u,u)-(u,u>)|\>\>+(u,u>)-(u,u)|\>\> using Harten, monotonicity of the flux. Smooth and montone region>high-order accuracy. Proof: <\eqnarray*> >||x|2>+O(\x)>>|>->>||\x+O(\x)>>|>->>||\x+O(\x)>>>> We have a monotone region, so x)\u>. So the high-accuracy term is half as big as the low-accuracy limiting terms in the minmod. . Consider extremal hump between two grid points. : <\equation*> >(a,b,c)\|M\|\x\|,>>||.>>>>> Scheme maintains high-order accuracy, choosing \|u\|>. TVB: <\equation*> TV(>)\TV(>)+C*M*\x*N\TV(>)+C\t. : <\equation*> U(u)|\t>+x>-=-x>|\>0>. Let (u)\0> and integrate by parts in the definition of the entropy flux . Let <\equation*> =U(u)(u,u)->U(u)f(u)\u. Multiply the c.law by (u)>, yielding a ``junk'' term > that ends up being positive, proving the CEI. <\itemize> : <\eqnarray*> ]>||,>>|,x]>||]-y[x]|x-x>,>>|,x,x]>||,x]-y[x,x]|x-x>,>>>> then <\equation*> p(x)=y[x]+y[x,x](x-x)+y[x,x,x](x-x)(x-x)+\. >Reconstruction>: Thinking about p>, where is the reconstruction polynomial, yields that running sums of cell averages turn reconstruction into interpolation. Since the step p> is first differences, i.e. undoing running sums, the reconstruction polynomial for >> is the same as the interpolation polynomial for >>. : Progressively expand the stencil in the direction with the lowest divided differences. Un-divided differences (for a uniform mesh) may be precomputed. : Start with a linear combination of smaller stencils that gives high-order accuracy. <\equation*> \stencil Now weight them so that =\+O(\x)> in smooth regions and =O(\x)> elsewhere. Then normalize the > so they add up to one. <\itemize> : View )> as cell averages of a function . Then <\equation*> f(u)=x>h(x+\x/2)-h(x-\x/2). So do reconstruction on values of )>. : Required to show stability using Harten. <\equation*> =(u)+(u). Assumptions: <\itemize> |\u>\0>, |\u>\0>. Lax-Friedrichs is a splittable flux. : Focus on > for now. <\equation*> =f(u)+minmod(,\f(u),\f(u)) : <\equation*> u=(+)-(+) . <\itemize> +f(u)+g(u)=0>. Weak solutions, entropy solutions same as 1D. Motone schemes have the same properties (TVD, entropy condition, > contraction. . ``Proof'': Consider a wiggly jump vs. a straight jump. One has high TV, the other low. Saying TVD in D literature amounts to ``TVD in 1D, but straightforwardly generalized to 2D''. : Consider scheme in Harten form. Then > is a convex combination of the values on the stencil. : <\eqnarray*> ||x\y>>>>>f(u)\x*\y>>|||x\y>>>f*(u(x,y,t))-f(u(x,y,t))\y.>>>> One integral is simple reconstruction, which must be carried out in two directions. Then the second integral must be carried out numerically. General procedure: <\eqnarray*> ||}|>{u>}\{f(u>)}|>{}>>|||>>|>|>|~>}>||>|||>>|>|||>}|>{u,j+1/2>}\{f(u,j+1/2>)}|>{}>>>> Only relevant for third and higher order since <\equation*> >|~>=u(x,y)+O(\x,\y), where |~>> and |\>> are cell averaging in and . : Generalizes straightforwardly. <\itemize> : <\equation*> u+A*u=0 If has complete set of eigenvectors and only real eigenvalues, it's called (strongly) hyperbolic. If constant linear system, use change of variables and use upwind/downwind depending on sign of \ eigenvalue. >=R\R\A>. If nonlinear, then find eigenvalues for each new matrix \(\)>, transform to diagonal form, carry out scalar reconstruction, then transform back. Rationale: Separation of shocks--two shocks travelling at different speeds. All results about stability and convergence carry over to linear systems using the characteristic procedure above. Steps for the nonlinear case: <\itemize> At > find a crude ``reference vector'' > as <\itemize> =(>+>)> or : >)-f>)=f()(>->)> Diagonalize ()=R*\R>. Transform all involved cell averages using >=R>>. Carry out 1D reconstruction. Recover =R*v>. For 2D nonlinear system, combine system approach with 2D stuff above. <\itemize> : Multiply PDE by test function , integrate by parts, interpret arising boundary terms by comparing with FV, using >>. Pick a nice monotone flux (\,\)> and give meaning to those meaningless boundary terms. This gives <\equation*> >uv->f(u)v+(u,u)-(u,u)=0. Then pick a basis in the space > and do the Galerkin thing. : Satisfied for /2>, i.e. <\equation*> |\t>u\x+-=-\\0, where <\equation*> =-g(u)+u and <\equation*> g(u)=f(u)\u. In estimating > (note: all terms in > are at ) gather terms and use Mean Value Theorem and consistency of the flux. <\initial> <\collection> <\references> <\collection> > > > > > > > > > > <\auxiliary> <\collection> <\associate|toc> |math-font-series||1Miscellanea> |.>>>>|> |math-font-series||2Theory> |.>>>>|> |math-font-series||3Numerics> |.>>>>|> |3.1Higher Order TVD Schemes |.>>>>|> > |3.2ENO/WENO |.>>>>|> > |3.3Finite Differences |.>>>>|> > |math-font-series||4Numerics in Multiple Space Dimensions> |.>>>>|> |math-font-series||5Systems of Conservation Laws> |.>>>>|> |math-font-series||6Discontinuous Galerkin> |.>>>>|>