Heath - Scientific Computing (523150), страница 88

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 88)

. , n.The boundary conditions give us uk0 = α and ukn+1 = β for all k, and the initial conditionsprovide the starting values u0j = f (xj ) for all j, so that we can march the numericalsolution forward in time using the difference scheme. In Fig. 11.2a, the pattern of meshpoints involved in this scheme is indicated by the lines, with the arrow indicating the meshpoint at which the solution is being computed. Such a pattern is called the stencil of thegiven finite difference scheme.The local truncation error of this scheme is O(∆t)+O((∆x)2 ), so we say that the schemeis first-order accurate in time and second-order accurate in space. The local error goes tozero as ∆t and ∆x go to zero, so the scheme is consistent. To investigate its stability, wenote that this fully discrete explicit scheme is simply Euler’s method applied to the systemof ODEs resulting from the semidiscrete finite difference method for the heat equation givenin Section 11.2.1.

There we saw that the Jacobian matrix of the semidiscrete system haseigenvalues between −4c/(∆x)2 and 0, and hence the stability region for Euler’s methodrequires that the time step satisfy(∆x)2∆t ≤.2c11.2. TIME-DEPENDENT PROBLEMS331(a) Explicit method forthe heat equation•.............•k+1 •(b) Explicit method forthe wave equation•.............•k+1 •..................................................................................................................................................................................................k•••k•••k−1•j−1•j•j+1k−1•j−1•j•j+1(c) Implicit method forthe heat equationk + 1 •................................•.............................................•......................k•k−1•j−1(d ) Crank-Nicolson methodfor the heat equationk + 1 •................................•.............................................•..........................................................................................••k••••j•j+1k−1•j−1•j•j+1Figure 11.2: Stencils of finite difference methods for time-dependent problems.This restriction on the time step is rather severe and makes this explicit method relativelyinefficient compared with implicit methods that we will see shortly.Example 11.2 Wave Equation.

As a further illustration of the finite difference approachto full discretization, we now consider the wave equationutt = cuxx ,0 ≤ x ≤ 1,t ≥ 0,with initial and boundary conditionsu(0, x) = f (x),ut (0, x) = g(x),u(t, 0) = α,u(t, 1) = β.Using centered difference formulas for both utt and uxx gives the finite difference schemeuk+1− 2ukj + uk−1jj(∆t)2=cukj+1 − 2ukj + ukj−1,(∆x)2or(∆t)2 k(u− 2ukj + ukj−1 ).(∆x)2 j+1The stencil for this scheme is shown in Fig.

11.2b. We note that this scheme requires dataat two levels in time, which requires additional storage and also means that we need bothu0j and u1j to get started. These values can be obtained from the initial conditionsuk+1= 2ukj − uk−1+cjju0j = f (xj ),u1j = f (xj ) + (∆t)g(xj ),332CHAPTER 11. PARTIAL DIFFERENTIAL EQUATIONSwhere in the latter we have used a forward difference approximation to the initial conditionut = g(x). This scheme is second-order accurate in both space and time, and the stabilityrestriction on the time step is∆x∆t ≤ √ ,cwhich is much less stringent than that for the scheme we considered for the heat equation.11.2.4Implicit Finite Difference MethodsIn the finite difference schemes we have considered thus far the values of the approximatesolution at the next time level have been given by explicit formulas involving solution valuesonly at previous levels.

For ODEs we saw that implicit methods are stable for a much greaterrange of stepsizes, and the same is true of implicit methods for PDEs.The explicit method that we considered for the heat equation results from applyingEuler’s method to the semidiscrete system of ODEs in Section 11.2.1. If instead we apply thebackward Euler method to the semidiscrete system, we obtain the implicit finite differencescheme∆t(uk+1 − 2uk+1+ uk+1uk+1= ukj + cjjj−1 ),(∆x)2 j+1whose stencil is shown in Fig. 11.2c.

This scheme inherits the unconditional stability of thebackward Euler method, which means that there is no stability restriction on the relativesizes of ∆t and ∆x. Accuracy is still a consideration, however, and the fact that thisparticular method is only first-order accurate in time still limits the time step severely. Thesimplest unconditionally stable implicit method for the heat equation that is second-orderaccurate in time is the Crank-Nicolson method∆tkkkuk+1= ukj + c(uk+1 − 2uk+1+ uk+1jjj−1 + uj+1 − 2uj + uj−1 ),2(∆x)2 j+1which results from applying the trapezoid rule to the semidiscrete system of ODEs (oralternatively, by averaging the previous explicit and implicit methods). The stencil for theCrank-Nicolson scheme is shown in Fig. 11.2d.The much greater stability of implicit finite difference methods enables them to takemuch larger time steps than are permissible with explicit methods, but they require morework per step because we must solve a system of equations at each step to determine thesolution values at the next step.

For both the backward Euler and Crank-Nicolson methodsfor the heat equation in one space dimension, the linear system to be solved at each stepis tridiagonal, and thus both the work and the storage required are modest. In higherdimensions the matrix of the linear system does not have such a simple form, but it is stillvery sparse, with nonzeros in a very regular pattern.

We will discuss methods for solvingsuch linear systems in Sections 11.4 and 11.5.Obviously, many additional finite difference schemes are possible, depending on the particular PDE being solved, the order of accuracy sought, etc. Such schemes are usuallycustom-tailored to take advantage of the specific features of a given problem. Finite difference schemes are relatively easy to derive; but analyzing their accuracy, stability, andefficiency can be much more challenging, and consequently they should not be used blindly.11.2.

TIME-DEPENDENT PROBLEMS11.2.5333Hyperbolic versus Parabolic ProblemsThus far we have treated all time-dependent problems alike: we simply replaced partialderivatives by finite difference approximations and then considered the accuracy and stability of the resulting scheme for stepping the approximate solution forward in time. A detailedstudy of the theory of partial differential equations is beyond the scope of this book, but weconsider briefly a basic theoretical difference between hyperbolic and parabolic PDEs thathas significant implications for practical numerical solution methods.Consider the following first-order hyperbolic PDE, known as the one-way wave equationor advection equation:ut = −cux , t ≥ 0,with initial conditionu(0, x) = u0 (x),x ≥ 0.It is obvious from the chain rule that a solution is given byu(t, x) = u0 (x − ct).Thus, the initial function u0 is simply propagated to the right (or to the left if c < 0) withvelocity c, as depicted in Fig.

11.3.u...................................... ................................................................................................................................... ........... ............ ............ ...........................................................................................................................................................................................................................................−→t=0xt>0Figure 11.3: A solution of the one-way wave equation.Note that u0 need not be smooth or even continuous. This behavior is typical of hyperbolic equations: they propagate steep fronts or shocks (or anything else, including numericalerrors) undiminished—for this reason, they are said to be conservative.

Such behavior canpotentially cause difficulties for numerical methods that are predicated on a certain degreeof smoothness. In particular, centered finite difference schemes, though desirable for theirhigher accuracy, often induce unwanted oscillations in the numerical solution to a hyperbolicequation near a sharp front. A useful alternative for the spatial derivatives in such casesis to use one-sided differences whose sample points are on the side from which the frontis coming.

Характеристики

Список файлов книги