Transcription of Lecture Notes 4 Convergence Theory for Linear Methods
1 Lecture Notes 4 Convergence Theory for Linear MethodsLetqnjbe the numerical approximation of the exact cell average,qnj unj:=1 x xj+1xju(tn, x)dx,tn=n t.(1)We want to check Convergenceqnj unjas x, t 0, Accuracy and Convergence rateqnj=unj+O( xp+ tr),for somep, r consider two cases of the numerical approximation: with and without boundaries. Whenthere are boundaries, we letqnbe the finite length vectorqn= (qn0, .. , qnN) there are no boundaries we letqndenote the infinite sequenceqn= (.. , qn 1, qn0, qn1..),and similarly for the exact solutionun. We write the numerical scheme compactly as an operatorNacting onqn,qn+1=N(qn, t, x).
2 WhenNonly depends on the CFL number = t/ xwe simply writeN(qn, )or justN(qn)when there is no risk for methodsWe assume thatNis a Linear method, if , are scalars,N( q+ u) = N(q) + N(u).A Linear method can always be represented by sequences of numbers,{bj, }, that depend on thetime and spatial step size,qn+1j=M = mbj, ( t, x)qnj+ ,(2)1 (11)DN2255 Numerical Solutions of Differential Equations Spring 2012 Olof Runborgfor some finitemandM, which determines the width of the spatial stencils used. (All methodswe considered so far are of this type. When the equation itself is nonlinear the scheme would ingeneral not be Linear , however.)
3 Example 1 WhenNis the upwind scheme applied tout+a(x)ux= 0,a(x)>0,thenqn+1j=qnj t xa(xj)(qnj qnj 1),so thatbj,0= 1 a(xj) t x,bj, 1=a(xj) t x,and all otherbj, are zero, 1andM= measure errors we need norms. We use the discrete version of theL2norm,||q||22, x=N j=0|qj|2 x,for the case with boundaries. Note that by the scaling withN x=constant, the size of thenorm should not increase as we refine the grid. In the case of noboundaries we similarly use||q||22, x= j= |qj|2 x,which mimics a trapezoidal rule approximation of the continuousL2norm whenqjapproximatesa smooth function again the norm should then be bounded as x can also use the discreteL1norm,||q||1, x=N j=0|qj| x,||q||1, x= j= |qj| we just write|| || xwhen the precise norm type is not Convergence theoryConvergence is usually established using the Lax equivalence theorem which states that a schemeis convergent if and only if it isconsistentandstable.
4 To check Convergence for our schemeNwe must thus verify these two properties and then apply the theorem. We go through the threesteps ConsistencyA scheme is consistent if the exact solution fits the scheme well. More precisely, we define thelocal truncation error nasun+1=N(un) + t (11)DN2255 Numerical Solutions of Differential Equations Spring 2012 Olof RunborgThe local truncation error is thus the residual when the exact solutionun(instead ofqn)isentered into the scheme, scaled by t. One can also think of it as the error performed in onetime step, scaled by Convergence we need a small n.
5 We say that the method isconsistentifmax0 n t T|| n|| x 0as t, x 0, for a fixedT. Moreover, if there is a numberCindependent of tand xsuchthatmax0 n t T|| n|| x C( xp+ tr)we say that the method is of orderpin space andrin time. If we use a constant = t/ x, ormore generally if =O(1), then|| n|| x=O(( x)p+ ( x)r) =O(( x)q)whereq= min(p, r)and we simply say that the method is of and order can usually be checked by simple Taylor expansion of the exact solutionand using the fact that it satisfies the 2 Consider the upwind method forut+aux= 0. The local truncation error njisdefined byun+1j=unj a t x(unj unj 1) + t nj,whereunjis the exact local average defined in (1).
6 We can rewrite this as nj=un+1j unj t+aunj unj 1 x=1 x xj+1xju(tn+1, x) u(tn, x) t+au(tn, x) u(tn, x x) we can Taylor expand the expressions inside the integralu(tn+1, x) u(tn, x) t=ut(tn, x) +12 tutt(tn, x) +O( t2),andau(tn, x) u(tn, x x) x=aux(tn, x) a2 xuxx(tn, x) +O( x2).Then, sinceut+aux= 0, nj=1 x xj+1xjut(tn, x) +12 tutt(tn, x) +aux(tn, x) a2 xuxx(tn, x) +O( x2+ t2)dx=12 x xj+1xj tutt(tn, x) a xuxx(tn, x)dx+O( x2+ t2)= t2 1 x xj+1xjutt(tn, x)dx a x2 1 x xj+1xjuxx(tn, x)dx+O( x2+ t2).Since the integrals are both bounded as t, x 0(they are local averages ofuttanduxx) weconclude that nj=O( x+ t),showing that upwind is a consistent method that is first orderin time and (11)DN2255 Numerical Solutions of Differential Equations Spring 2012 Olof RunborgWe can make a more precise characterization of the local truncation error by differentiatingthe equation once in time and space to getutt+auxt= 0,utx+auxx= this shows thatutt=a2uxx.
7 Therefore nj=a(a t x)21 x xj+1xjuxx(tn, x)dx+O( x2+ t2).This kind of characterization is useful when one derives modified equations (see Leveque ). Italso shows that if one chooses the "magic time step" t= x/athe method is more fact, then the numerical scheme is exact and nj 0. This is, however, very special to theconstant coefficient advection equation, and does not happenin StabilityThe scheme is called (Lax-Richtmyer) stable if||N(q)|| x (1 + t)||q|| xfor allqand with independent ofq, tand x. We will get back later to how this can beshown for a that whenNis nonlinear then we need instead an "almost contraction" property,||N(q) N(q )|| x (1 + t)||q q || xfor allq,q and with independent ofq,q , tand x.
8 See Leveque ConvergenceBy the Lax equivalence theorem"stability + consistency Convergence ".More precisely, the right implication gives both Convergence and an error estimate if themethod is stable and consistent with orderpin space andrin time (in the way defined above)we getmax0 n t T||qn un|| x C( xp+ tr),whereCis independent of xand t, but in general depends onTand the exact solutionu(t, x). This is quite straightforward to prove, as follows:We assume Stability||N(q)|| x (1 + t)||q|| x, q, Consistency such that := max0 n t T|| n|| x C( xp+ tr), Exact initial data,q0j=u0j,||q0 u0|| x= (11)DN2255 Numerical Solutions of Differential Equations Spring 2012 Olof RunborgLet us first define the errorenj=unj qnjand in vector formen=un qn.
9 Thenen+1=un+1 qn+1=N(un) + t n N(qn) =N(en) + t n,where we used the definition of the truncation error and the linearity ofN. Then||en+1|| x ||N(en)|| x+ t|| n|| x {stability and def. of } (1 + t)||en|| x+ t {applying same estimate toen} (1 + t)2||en 1|| x+ (1 + t) t + t {induction} (1 + t)n+1||e0|| x+n j=0(1 + t)j t ={exact initial data}= t n j=0(1 + t) sum is a geometric series,n j=0(1 + t)j=(1 + t)n+1 1(1 + t) 1=(1 + t)n+1 1 ,||en|| x (1 + t)n 1 .Now, using the fact that1 +x exfor allx, we getmax0 n t T||en|| x max0 n t T e n t 1 e T 1 .Hence,max0 n t T||un qn|| x C ( xp+ tr),where the numberC is the numberCin the consistency assumption multiplied by(e T 1)/.
10 This shows the Convergence and error 1In general the boundary conditions can have a significant effect on stability, accuracyand Convergence . The above analysis is not always sharp. Forinstance, the local truncation errorcan, sometimes, be allowed to have lower order at the boundaries without ruining the overallconvergence note that for higher order approximations wider spatial stencils are needed, which meansthat more ghost cells are needed. Then also more boundary conditions for these cells are , the PDE itself has a fixed number of boundary conditions. Hence, the number ofnumerical boundary conditions is often larger than the number of PDE boundary these extra conditions can be a delicate (11)DN2255 Numerical Solutions of Differential Equations Spring 2012 Olof Runborgx0(x,t)x at=x0t(a) Continuous problemxjxj nxj+n(xj,tn)n(b) Numerical approximationFigure CFL Checking stabilityChecking stability of a scheme is usually the most difficult part when proving Convergence .
