Examples of difference schemes. Explicit and implicit difference schemes

Part two of the book is devoted to the construction and study of difference schemes for ordinary differential equations. At the same time, we will introduce the basic concepts of convergence, approximation and stability in the theory of difference schemes, which are of a general nature. Familiarity with these concepts, gained in connection with ordinary differential equations, will make it possible in the future, when studying difference schemes for partial differential equations, to focus on the numerous features and difficulties characteristic of this very diverse class of problems.

CHAPTER 4. ELEMENTARY EXAMPLES OF DIFFERENCE SCHEMES

In this chapter we will look at introductory examples of difference schemes, intended only for a preliminary acquaintance with the basic concepts of the theory.

§ 8. The concept of the order of accuracy and approximation

1. Order of accuracy of the difference scheme.

This section is devoted to the issue of convergence of solutions of difference equations when refining the mesh to solutions of differential equations that they approximate. We will limit ourselves here to studying two difference schemes for numerical solution of the problem

Let's start with the simplest difference scheme based on the use of the difference equation

Let us divide the segment into steps of length h. It is convenient to choose where N is an integer. We number the division points from left to right, so . The value and obtained from the difference scheme at a point will be denoted by Set the initial value. Let's put it. The difference equation (2) implies the relation

from where we find the solution to equation (2) under the initial condition:

The exact solution to problem (1) has the form . It takes on the value

Let us now find an estimate of the error value of the approximate solution (3). This error at the point will be

We are interested in how it decreases as the number of partition points increases, or, what is the same, as the step of the difference grid decreases. In order to find out this, let us represent it in the form

Thus, equality (3) will take the form

i.e. error (5) tends to zero at and the magnitude of the error is of the order of the first power of the step.

On this basis, they say that the difference scheme has the first order of accuracy (not to be confused with the order of the difference equation defined in § 1).

Let us now solve problem (1) using the difference equation

This is not as simple as it might seem at first glance. The fact is that the scheme under consideration is a second-order difference equation, i.e., it requires specifying two initial conditions, while the integrable equation (1) is a first-order equation and for it we specify only . It is natural to put .

It's not clear how to set them. To understand this, we will use the explicit form of solving equation (7) (see § 3 formulas):

Expansion (9) according to the Taylor roots formula characteristic equation allow us to give approximate representations for Let us carry out in detail the derivation of such a representation -

Since then

We will not carry out a completely similar calculation for , but will immediately write out the result:

Substituting approximate expressions for into formula (8), we obtain

We will obtain all further conclusions by studying this formula.

Note that if the coefficient tends to the finite limit b, then the first term on the right side of equality (12) tends to the desired solution to problem (1).

Grid and template. For most difference schemes, the grid nodes lie at the intersection of some straight lines (in multidimensional problems - hyperplanes), drawn either in a natural coordinate system or in a region specially selected in shape G.

If one of the variables has a physical meaning of time t, then the grid is usually constructed so that among its lines (or hyperplanes) there are lines t = t m. The set of grid nodes lying on such a line or hyperplane is called a layer.

On each layer, directions are identified along which only one spatial coordinate changes. For example, for variables x, y, t there are directions x (t = const, y = const) and direction y (t = const, X = const).

When compiling difference schemes (26.2) and (26.4), we used the same type of difference approximation of derivatives at all internal nodes of the region. In other words, when writing each difference equation around a certain grid node, the same number of nodes was taken, forming a strictly defined configuration, which we called the template of this difference scheme (see Fig. 26.2).

Definition. The nodes in which the difference scheme is written on the template are called regular, and the rest are called irregular.

Irregular are usually the boundary nodes, and sometimes also the nodes lying near the boundary (such that the pattern taken near this node extends beyond the boundary of the region).

Drawing up a difference scheme begins with choosing a template. The template does not always define the difference scheme unambiguously, but it significantly influences its properties; for example, later we will see that in the template Fig. 26.2 b it is impossible to create a good difference scheme for the heat conduction problem (26.1). Each type of equations and boundary value problems requires its own template.

Explicit and implicit difference schemes

Let us discuss the issue of actually calculating the difference solution. Most physical problems leads to equations containing time as one of the variables. For such equations, a mixed boundary value problem is usually posed, a typical case of which is the heat conduction problem (26.1).

A layer-by-layer calculation algorithm is used for such problems. Let's consider it using schemes (26.2) and (26.4) as an example.

In scheme (26.4) on the original layer m= 0 the solution is known due to the initial condition. Let's put m= 0 in equations (26.4). Then for each index value n the equation contains one unknown ; from here we can determine at
Values And are determined by boundary conditions (26.3). Thus, the values ​​in the first layer are calculated. Using them, the solution on the second layer is calculated in a similar way, etc.

Scheme (26.4) in each equation contains only one value of the function on the next layer; this value is easy to express explicitly through the known values ​​of the function on the original layer, which is why such schemes are called explicit.

Scheme (26.2) contains in each equation several unknown values ​​of the function on a new layer; Such schemes are called implicit. To actually calculate the solution, we rewrite scheme (26.2) taking into account the boundary condition (26.3) in the following form

(26.5)

At each layer, scheme (26.5) is a system of linear equations for determining the quantities
; the right-hand sides of these equations are known because they contain the solution values ​​from the previous layer. The matrix of the linear system is tridiagonal, and the solution can be calculated by algebraic sweep.

The algorithm considered now is quite typical. It is used in many implicit difference schemes for one-dimensional and multidimensional problems. Next, instead of an index, we will m use abbreviations frequently

In this notation, the explicit and implicit difference schemes take the following form, respectively:

Residual. Let us consider an operator differential equation of general form (not necessarily linear)

Au = f, or Au – f = 0.

Replacing operator A difference operator A h, right side f– some grid function , and the exact solution u– difference solution y, let's write the difference scheme

or
. (26.6)

If we substitute the exact solution u into relation (26.6), then the solution, generally speaking, will not satisfy this relation
. Size

called the residual.

The residual is usually estimated using a Taylor series expansion. For example, let's find the residual of the explicit difference scheme (26.4) for the heat equation (26.1a). Let us write this equation in canonical form

Because in this case
That

Let us expand the solution using the Taylor formula near the node ( x n , t m), assuming the existence of continuous fourth derivatives with respect to X and second in t

(26.7)

Where

Substituting these expansions into the expression of the residual and neglecting, due to the continuity of derivatives, the difference in quantities
from ( x n , t m) we'll find

(26.8)

Thus, the discrepancy (26.8) tends to zero as
And
The proximity of the difference scheme to the original problem is determined by the magnitude of the residual. If the discrepancy tends to zero at h And tending to zero, then we say that such a difference scheme approximates a differential problem. The approximation has r th order if
.

Expression (26.8) gives the discrepancy only at regular grid nodes. Comparing (26.3) and (26.1b), we can easily find the discrepancy in irregular nodes

Note 1. The solution of the heat conduction problem with a constant coefficient (26.1) in the region is continuously differentiable an infinite number of times. However, taking fifth or more derivatives into account in the Taylor series expansion (26.7) will add to the discrepancy (26.8) only terms of a higher order of smallness in And h, i.e. essentially will not change the type of residual.

Note 2. Let, for some reason, the solution to the original problem be differentiable a small number of times; for example, in problems with a variable thermal conductivity coefficient that is smooth but does not have a second derivative, the solution has only third continuous derivatives. Then in the Taylor series expansion (26.7) the last terms will be
not exactly compensating each other. This will lead to the appearance in the residual (26.8) of a term of the type
those. the discrepancy will be of a lower order of smallness than for four times continuously differentiable solutions.

Note 3. Having transformed the residual expression taking into account the fact that the function included in it u(x,t) is an exact solution of the original equation and the relations are satisfied for it

Substituting this expression into (26.8), we get

If we choose steps in space and time so that
then the leading term of the residual will vanish and only terms of a higher order of smallness will remain And h(which we omitted). This technique is used when constructing difference schemes of increased accuracy.

Difference scheme

Difference scheme- this is a finite system of algebraic equations, put in correspondence with some differential problem containing a differential equation and additional conditions (for example, boundary conditions and/or initial distribution). Thus, difference schemes are used to reduce a differential problem, which has a continual nature, to a finite system of equations, the numerical solution of which is in principle possible on computers. Algebraic equations put into correspondence with a differential equation are obtained using the difference method, which distinguishes the theory of difference schemes from other numerical methods for solving differential problems (for example, projection methods, such as the Galerkin method).

The solution of the difference scheme is called an approximate solution of the differential problem.

Although the formal definition does not impose significant restrictions on the type of algebraic equations, in practice it makes sense to consider only those schemes that in some way correspond to the differential problem. Important concepts in the theory of difference schemes are the concepts of convergence, approximation, stability, and conservatism.

Approximation

They say that a differential operator defined on functions defined in the domain is approximated on a certain class of functions by a finite-difference operator defined on functions defined on a mesh depending on the step if

An approximation is said to be of order if

where is a constant that depends on a specific function, but does not depend on the step. The norm used above may be different, and the concept of approximation depends on its choice. The discrete analogue of the norm of uniform continuity is often used:

sometimes discrete analogues of integral norms are used.

Example. Approximation of the operator by a finite-difference operator

on a limited interval has second order on the class of smooth functions.

A finite-difference problem approximates a differential problem, and the approximation has order , if both the differential equation itself and the boundary (and initial) conditions are approximated by the corresponding finite-difference operators, and the approximations have order .

Courant condition

Courant condition (in English-language literature English. Courant-Friedrichs-Levy condition , CFL) - the speed of propagation of disturbances in a difference problem should not be less than in a differential one. If this condition is not met, then the result of the difference scheme may not tend to solve the differential equation. In other words, in one time step the particle should not “run through” more than one cell.

In the case of schemes whose coefficients do not depend on the solution of the differential equation, the Courant condition follows from stability.

Schemes on offset grids

In these schemes, the grids on which the result is given and the data are offset relative to each other. For example, result points are midway between data points. In some cases, this allows the use of simpler boundary conditions.

See also

Links

• “Difference schemes” - Chapter in wikibooks on the topic “Difference schemes for hyperbolic equations”
• Demyanov A. Yu., Chizhikov D. V. Implicit hybrid monotonic difference scheme of second order of accuracy
• V. S. Ryabenkiy, A. F. Filippov. On the stability of difference equations. - M.: Gostekhizdat, 1956.
• S. K. Godunov, V. S. Ryabenky. Introduction to the theory of difference schemes. - M.: Fizmatgiz, 1962.
• K. I. Babenko. Basics numerical analysis. - M.: Science, 1986.
• Berezin I.S., Zhidkov N.P. Calculation methods, - Any edition.
• Bakhvalov N.S., Zhidkov N.P., Kobelkov G.M. Numerical methods, - Any edition.
• G. I. Marchuk. Methods of computational mathematics. - M.: Science, 1977.

Notes

Wikimedia Foundation. 2010.

See what a “Difference scheme” is in other dictionaries:

A system of difference equations that approximate the differential equation and additional (initial, boundary, etc.) conditions. Approximation of the original differential problem R. s. this is one of the ways to approximate discretization of the original problem... Mathematical Encyclopedia

difference finite element scheme- finite element method - [A.S. Goldberg. English-Russian energy dictionary. 2006] Topics energy in general Synonyms finite element method EN finite volume difference schedule ...

A difference scheme is a finite system of algebraic equations, put in correspondence with any differential problem containing a differential equation and additional conditions (for example, boundary conditions and/or initial ... ... Wikipedia

finite-difference calculation scheme based on control volumes- (eg heat and mass transfer, thermal conductivity) [A.S. Goldberg. English-Russian energy dictionary. 2006] Energy topics in general EN control volume based finite difference schedule … Technical Translator's Guide

Outline: graphic document; presentation, image, presentation of something in the most general terms, simplified (for example, a diagram of a report); electronic device, containing many components (integrated circuit). Graphic document... ...Wikipedia

A difference scheme constructed on the basis of a variational problem corresponding to a boundary value problem for a differential equation. The main idea of ​​​​constructing R. v. With. is that with a special choice of coordinate functions in the Ritz method... ... Mathematical Encyclopedia

Numerical methods for solving methods for solving equations giierbolpch. type based on computational algorithms. Various mathematical models in many cases lead to hyperbolic differential equations. type. Such equations have exact aialit... ... Mathematical Encyclopedia

A branch of computational mathematics that studies methods for approximate solution of differential equations by replacing them with finite difference equations (difference schemes). R.s. t. studies methods for constructing difference schemes,... ... Mathematical Encyclopedia

Numerical methods for solving partial differential equations are approximate solution methods, as a result of which the solution to the problem is represented by a table of numbers. Exact solutions (in the form of explicit formulas, series, etc.) K. z. can only be built in rare... Mathematical Encyclopedia

Methods for solving gas dynamics problems based on computational algorithms. Let's consider the main aspects of the theory numerical methods solving gas dynamics problems by writing gas dynamics equations in the form of conservation laws in inertial... ... Mathematical Encyclopedia e-book

1. In the coordinate system xOt build a rectangular grid with steps h along the axis Oh and with step τ along the axis Ot:

a) x i =ih, i= l, n , n=L/h;

b) t k =kτ, k= l,m , m=T/τ;

V) And i , k = u(x i ,t k) = u(ih,kτ).

2. Calculate the function values u(x i , t k) at nodes lying on straight lines x= 0 and x=L:

3. Calculate u i ,0 =f(ih),i= 1, n .

4. Using (1.16) or (1.23), we find a solution for all internal nodes: u i , k + n , i= l,n -l, k= 0, m -l.

1.3. Solving a mixed problem for the wave equation using the grid method

1.3.1. Statement of the problem. Method algorithm

Let us consider a mixed problem (i.e., initial and boundary conditions are given) for the wave equation

in the area D=(0≤x≤ L, 0≤t≤T) with initial conditions

and boundary conditions

We will assume that f(x),g(x) are fairly smooth functions, and the matching conditions are satisfied in two corners of the region D(x=0, t=0), (x=L, t=0), ensuring the existence and uniqueness of the solution u(x, t).

To discretize the original problem, we construct in the domain

rectangular grid

Where h – grid step in direction X, τ – grid step in direction t,

Using second-order central differences (1.10) to approximate partial derivatives, for each internal grid node we obtain a system of difference equations

which approximate the wave equation (1.24) at the node ( X i , t k) with error O(h 2 + τ 2).

Here u i , k– approximate value of the function And(X,t) at node ( x i ,t k).

Assuming λ = aτ/ h, we obtain a three-layer difference scheme:

Scheme (1.28) is called three-layer because it connects the values u i , k functions And(X,t) on three time layers with numbers ( k-l), k, (k+1).

The difference scheme (1.28) corresponds to a five-point three-layer “cross” pattern (Fig. 1.2).

Scheme (1.28) connects the values u i , k =u(ih, kτ) on three layers in time, and to go to the level ( k+1), you need to know how u i , k, so u i , k-1, which is a consequence of the fact that the differential equation (1.24) contains a second derivative with respect to time. The numerical solution of problem (1.24) – (1.26) consists in calculating approximate values u i , k solutions u(X, t) in nodes ( X i ,t) at i = 1, n , k=1, m . The calculation scheme according to (1.28) is explicit; it allows one to approximately calculate the values ​​of the function at the nodes ( k+1)-th layer based on its known values ​​on the two previous layers. On the first two layers, the function values ​​are determined from the initial conditions (1.25). We believe

For the time derivative we use approximation (1.5)

The order of approximation (1.30) is equal to ABOUT(τ).

Note that (1.29), (1.31) give solutions for the first two lines: k=0, k=1. Substituting k= 1 in (1.28), we get:

All terms on the right side of equation (1.32) include the values And i , k only from the first two rows of the grid; but all these values ​​are known from the initial conditions.

After that, knowing the solutions And i ,1 ,And i,2, we can use (1.28) to calculate the values ​​of the function And i , k on the third time layer, fourth, etc.

The calculation scheme (1.28) – (1.31) described above approximates problem (1.24) – (1.26) with an accuracy ABOUT(τ+ h 2). The low order of approximation with respect to τ is explained by the use of too rough an approximation for the derivative with respect to t in formula (1.30).

Let us now consider the issues of convergence and stability. Without presenting evidence here, we will limit ourselves to formulating the final results. The calculation scheme will be stable if the Courant condition is satisfied

This means that when (1.33) is satisfied, small errors that arise, for example, during calculations on the first layer, will not increase indefinitely when moving to each new time layer. When the Courant condition is satisfied, the difference scheme (1.28) has uniform convergence, i.e., when h→0 and τ→0 the solution of the difference problem (1.28) – (1.31) uniformly tends to the solution of the original problem (1.24) – (1.26).

Condition (1.33) is sufficient for convergence, but is not necessary. In other words, there are equations and interval values ​​for which (1.33) does not hold, but the correct result is still obtained. The whole point is that then convergence cannot be guaranteed. In the general case, of course, it is desirable to ensure convergence for sure, and therefore the requirement to satisfy condition (1.33) is mandatory.

Thus, once the step size is selected h in the direction X, then there is a limitation on the size of the time step τ. A distinctive feature of all explicit methods is that when using them, some condition like (1.33) must be observed, ensuring the convergence and stability of the method.

Mathematics and mathematical analysis

The solution of the difference scheme is called an approximate solution of the differential problem. Characteristics of the implicit difference scheme Consider a one-dimensional differential equation of parabolic type with initial and boundary conditions: 4.7 is written at the n 1st time step for the convenience of subsequent presentation of the method and algorithm for solving the implicit difference scheme 4. In the section Order of approximation of the difference scheme, it was noted that difference scheme 4.

Question 8: Difference schemes: explicit and implicit schemes:

Difference schemethis is a finite system of algebraic equations, put in correspondence with some differential problem containingdifferential equationand additional conditions (for exampleboundary conditions and/or initial distribution). Thus, difference schemes are used to reduce a differential problem, which has a continual nature, to a finite system of equations, the numerical solution of which is in principle possible on computers. Algebraic equations put into correspondencedifferential equationare obtained by applyingdifference method, what distinguishes the theory of difference schemes from othersnumerical methodssolving differential problems (for example, projection methods, such as Galerkin method).

The solution of the difference scheme is called an approximate solution of the differential problem.

Characteristics of implicit difference scheme

Consider a one-dimensional differential equationparabolic type With :

Let us write for the equation (4.5) implicit difference scheme:

Let's write:

The approximation of boundary conditions (4.7) is written as ( n method and algorithm solutions to the implicit difference scheme (4.6).
In the section ""it was noted that the difference scheme (4.6) has the sameorder of approximation, as well as the corresponding explicit difference scheme(4.2) , namely:

In the section " Proof of absolute stability of the implicit difference scheme"it was proven that the implicit difference scheme (4.6) is absolutely stable, i.e., regardless of the choice of the division interval bydifference grid(or, in other words, choosing a calculation step based on independent variables)solution errorthe implicit difference scheme will not increase during the calculation process. Note that this is certainly an advantage of the implicit difference scheme (4.6) compared to the explicit difference scheme(4.2) , which is stable only if the condition is satisfied(3.12) . At the same time, the explicit difference scheme has a fairly simple solution method , and the method for solving the implicit difference scheme (4.6), calledsweep method, more complex. Before you goto the presentation of the sweep method, necessary derive a series of relationships, used by this method.

Characteristics of explicit difference scheme.

Consider a one-dimensional differential equationparabolic type With initial and boundary conditions:

Let us write for the equation(4.1) explicit difference scheme:

Let's write it down approximation of initial and boundary conditions:

The approximation of boundary conditions (4.3) is written as ( n + 1)th time step for convenience of subsequent presentation method and algorithm solutions to the explicit difference scheme (4.2).
In the section "The order of approximation of the difference scheme"it was proven that the difference scheme (4.2) hasorder of approximation:

In the section " Proof of the conditional stability of an explicit difference scheme"condition was received sustainability given difference scheme, which imposes restrictions on the choice of division interval when creatingdifference grid(or, in other words, a restriction on the choice of calculation step for one of the independent variables):

Note that this, of course, is a drawback of the explicit difference scheme (4.2). At the same time, it has a fairly simple solution method