Slide 1Slide 2Slide 3Finite difference approximation of PDEs: FTCSSlide 5Slide 6ConvergenceLocal truncation errorSlide 9Slide 10Slide 11Slide 12Godunov’s first-order upwind schemeSlide 14Slide 15Slide 16Slide 17The “downwind” schemeSlide 19Slide 20Slide 21Slide 22More SchemesSlide 24Slide 25Slide 261Introduction to Numerical Methods I2Finite difference approximation to derivatives3Consider a smooth function g(x). Taylor’s theorem reads:kkkxgkxxgxxg )(!)()(0)(00In particular:)1( )()()()(20)1(00xOxxgxgxxg (3) )()()()()1.(000)1(xOxxgxxgxgEq )(2)()()()4()3.(2000)1(xOxxxgxxgxgEqs )2( )()()()(20)1(00xOxxgxgxxg (4) )()()()()2.(000)1(xOxxxgxgxgEq Short course on: Numerical methods for hyperbolic equations and applications-Trento, Italia-June 7th to 18th, 20044Finite difference approximation of PDEs: FTCS)()0,(:],0(],0[0)(:0xqxqICTtLxqqqLPDExtaDiscretise the x-t domain into a finite number of M+1 points, I=0,…,Mstep time: ;/ :Mesh ;0,;;),(tMLxnitntxixwithtxnini),( ninitxqq 5Now approximate partial derivatives.(CS) spaceincentred:)(2(FT) timeinforward:)(2111xOxqqqtOtqqqninixninitThen the PDE is replaced by a finite difference approximate operator:02111xqqtqq)(qLnininininia xqqxtqqnininini2 111scheme numericalUse finite differences:6xtcThe Courant-Friedrichs-Lewy numberor CFL number, or Courant numberNote that c is a dimensionless quantity, it is the ratio of two velocities:meshofspeedPDEofspeedtxxtc /)(21111 ninininiqqcqqIntroduce the dimensionless number:Finally, the FTCS scheme reads:This formula allows us to calculate explicitly the evolution in time of discrete approximate values of the solution at every point, except for i=0 and i=M.Stencil7ConvergenceOur ultimate goal is to construct schemes that converge, that is schemesthat approach the true solution of the PDE when the mesh size tends to zero. Lax’s Equivalence theorem says that:the only schemes that are CONVERGENT are those that are CONSISTENT and STABLEWe must therefore work on CONSISTENCY AND STABILITY.8Local truncation error02)(111xqqtqqqLnininininiaThe numerical analogue of the PDE is the approximate operator:We define the local truncation error:xtnxiqtnxiqttnxiqtnxiqET2),)1((),)1((),())1(,(Consider a particular scheme: FTCS.)),(( tnxiqLEaT9Assuming the solution is sufficiently smooth we Taylor expand and obtain:nixxxttnixtTEtOxOqxtqqqL )()(6121)(232nixxxttTEtOxOqxtqL )()(6121232 0)(nixtqq)()(2xOtOLTEThe FTCS is a first-order schemeNoting that:In general, if the local truncation error of a scheme is of the form:)()(lkTExOtOL Then the scheme is said to be k-th order accurate in time and l-th order accurate in space.10ConsistencyA numerical scheme is said to be consistent with the PDE being discretizedif the local truncation error tends to zero as the mesh size tends to zero.0 and 0 as 0  xtLTEFor example, for the FTCS scheme we have)()(2xOtOLTETherefore FTCS is consistent wit the PDE11Stability of a numerical method.If a method is consistent with the PDE, then all we need to bother is stability.One view of stability is that of unbounded growth of errors as the numerical scheme evolves the solution in time.Another view of stability is that of controlling spurious oscillationsStability in the sense on unbounded growth can be analysed by a variety of methodsA popular method is the von Neumann methodOne performs a Fourier decomposition of the error. It is sufficient to consider a single component.12Stability analysis of the FTCS anglefrequencyindexspacialiIeAqIinni::;1solution trial:)(21111 ninininiqqcqqThus FTCS is unstable under all circumstances: UNCONDITIONALLY UNSTABLE (useless).   1sin1sin1sin221121121222)1()1(1cAIcAIceecAeAeAceAeAIIiIniInIinIin13Godunov’s first-order upwind scheme• Approximate derivatives in 0,0 xtqqbyxqqqtqqqninixninit11,then0)(11xqqtqqqLnininininia• The scheme reads)(11 ninininiqqcqqIllustrate the stencil140)(11xqqtqqqLnininininiaThe finite difference operator is:Substitution of the exact solution into the approximate opetaror gives:xtnxiqtnxiqttnxiqtnxiqLTE),)1((),(),())1(,(Assuming sufficient smoothness and Taylor expanding:nixxttTEtOxOxqtqL )()(212122nixxxttnixtTEtOxOqxtqqqL )()(6121)(232Local truncation error:The scheme is first-order accurate in space and time15Stability analysis222cos)1(2)1( ccccA and the stability condition becomes12A10 cGiven wave speed and mesh spacing the time step is determined from the stability condition xtxttxxt  1/010The CFL condition of Courant conditionn.computatio theofnumber CFL the:10 with :SetxtCCxCtcflcflcfl16 The stencil (upwind)n+1True domain of dependencyNumerical domain of dependencynxxtxctpxix1ix0/ dtdxtxdtdx  //o oo-The exact solution is the value on the characteristic ),(nitxq),(),( : isthat ),(at 11 npninitxqtxqtxdtdxwhere is the foot of the characteristic at timepxntt 17• For appropriate choices of the point lies between and • Assume a linear interpolation between and  iiinininixxxxxxqqqxq ,,)()(~1111 • Evaluation of