Third order difference scheme formula. Numerical methods for solving partial differential equations of hyperbolic type (using the example of the transport equation). Formulation of the problem. Method algorithm

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. A 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 goes 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 physics problems lead 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 us consider it using the example of schemes (26.2) and (26.4).

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 at 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 x n , t m Let us expand the solution using the Taylor formula near the node ( X), assuming the existence of continuous fourth derivatives with respect to t

(26.7)

and second in

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

(26.8)

we'll find
And
Thus, the discrepancy (26.8) tends to zero as h 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 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 residual (26.8) only terms of 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.

Courant-Isakson-Ries scheme(KIR), which is sometimes also associated with the name S.K. Godunov, it turns out when , . Its order of approximation is . The KIR scheme is conditionally stable, i.e. when the Courant condition is fulfilled . Let us present the difference equations for the Courant-Isakson-Ries scheme at internal points of the computational domain:

These schemes, also called the scheme with differences upwind (in English literature - upwind) can be written in the form

Their advantage is a more accurate account of the dependency area of ​​the solution. If we introduce the notation

then both schemes can be written in the following forms:

(flow form of difference equation);

(here the term with the second difference is clearly highlighted, which gives stability to the scheme);

(equation in finite increments).

Let's also consider method of uncertain coefficients to construct a difference scheme, the right corner of the first order of accuracy for the transport equation

The scheme can be represented in the form

The Courant-Isakson-Rees scheme is closely related to numerical methods of characteristics. Let us give a brief description of the idea of ​​such methods.

The last two obtained schemes (with different signs of the transfer rate) can be interpreted as follows. Let's construct a characteristic passing through the node (t n + 1, x m), the value at which must be determined, and intersecting the layer t n at the point . For definiteness, we assume that the transfer rate c is positive.

Carrying out linear interpolation between nodes x m - 1 and x m on the bottom layer in time, we obtain

Next, we transfer the value u n (x") along the characteristic without changing to the upper layer t n + 1, i.e. we put . It is natural to consider the last value as an approximate solution homogeneous equation transfer. In this case

or, moving from the Courant number again to grid parameters,

those. using another method we arrived at the already known “left corner” scheme, stable for . When the point of intersection of the characteristic leaving the node (t n + 1, x m, with the n-th layer in time is located to the left of the node (t n, x m - 1). Thus, to find a solution, it is no longer interpolation, but extrapolation, which turns out to be unstable .

The instability of the “right corner” scheme for c > 0 is also obvious. To prove this, one can use either the spectral feature or the Courant, Friedrichs and Levy condition. Similar reasoning can be carried out for the case c< 0 и схемы "правый уголок".

Unstable four-point circuit turns out when , its order of approximation. The grid equations for the difference scheme will have the following form:

Lax-Wendroff scheme occurs when . The order of approximation of the Lax-Wendroff scheme is . The scheme is stable under the Courant condition .

This scheme can be obtained either by the method of undetermined coefficients, or by more accurately taking into account the leading term of the approximation error. Let us consider the process of derivation of the Lax-Wendroff scheme in more detail. Carrying out a study of the previous four-point scheme for approximation (and the study is quite elementary and comes down to expanding the projection function onto the grid of the exact solution of the differential problem in a Taylor series), we obtain for the main term of the error

When deriving the expression for the main term of the approximation error, a consequence of the original differential transport equation was used

Which is obtained by differentiating the original equation (3.3) first with respect to time t, then with respect to the x coordinate and subtracting one of the resulting relations from the other.

Next, replacing second derivative in the second term on the right side with an accuracy of O(h 2), we obtain a new difference scheme that approximates the original differential equation with precision . The grid equations for the Lax-Wendroff scheme at the internal nodes of the computational grids are

Implicit six-point scheme occurs at q = 0; when its order of approximation , at .

Example 1. Difference scheme for the Poisson equation of elliptic type.

Let us consider the construction of a difference scheme for the first boundary value problem for the equation A u = f(x,y) in an area that is a rectangle with sides parallel to the coordinate axes. Let this rectangle be associated with a uniform grid with steps h x And h y .

Boundary value problem

can be written in operator form:

Note that this entry also includes boundary conditions.

Replacing differential operators with difference ones, we obtain the equations

which approximate the original differential equation with the second order 0(h 2 + h 2) accuracy and operate at all internal points of the region.

Difference analogs of boundary conditions will have the form

The difference approximation of the differential equation together with the difference analogues of the boundary conditions form a difference scheme for the Poisson equation.

By analogy with the boundary value problem, the difference scheme can be written in operator form:

where in L/, both the difference equation and the difference boundary condition are included:

The difference equation relates the values ​​of the grid function at five points forming difference pattern for this equation. For this case, this pattern is called cross. We can imagine other patterns for this equation.

We will obtain an approximate solution to the differential boundary value problem if we determine the values ​​of the grid function at all internal nodes of the domain. To do this, it is necessary to jointly solve a system of algebraic linear equations, the dimension of which is equal to the number of internal nodes of the region. In this case, we talk about an implicit difference scheme. Any value we are interested in Uij can be determined only from the solution of the entire difference problem.

Regarding the system of equations, we note two circumstances.

• 1. The system has a very high dimension (M - 1) x (N- 1), and traditional methods of exact solution (for example, the Gauss method) require for solution a number of algebraic operations proportional to the third power of the dimension of the system.
• 2. The system matrix has many zero elements (loose matrix). This circumstance makes it possible to develop economical methods for approximate solutions.

The considered formulation of the difference problem is typical for elliptic equations. In gas dynamics, this is the form of the equation for the stream function or for the velocity potential. In other sections we will look at efficient methods for resolving such difference schemes.

Rice. 2.8.

PRI M 2. Difference scheme for the simplest parabolic equation (non-stationary thermal conductivity in a rod of unit length).

Consider the following problem:

Let us note that in the case of a parabolic equation we have an open region. When constructing a difference scheme, several options arise for the connection between the difference derivatives in space and time.

Let's integrate the equation within one time step:

Depending on which quadrature formula we use to calculate the integral on the right side, we will obtain different difference schemes (Fig. 2.9).

By relating the difference time derivative to the spatial derivative defined on P-th time layer, we get

explicit 'difference scheme'

This is equivalent to an approximate calculation of the integral on the right side of (2.12), but using the method of left rectangles.

Rice. 2.9. Grid and templates for the heat equation: A - area and grid; b- explicit schema template; V- implicit schema template; G- template of a family of six-point circuits; d- diagram template

"leapfrog"

The above formula also contains a method for solving grid equations:

Grid function value at next time layer

is determined through the known values ​​of gf in the previous one. Moving sequentially in layers from the initial condition their, 0) = y(x), the solution can be found in the entire computational domain. The difference pattern for this scheme is shown in Fig. 2.9, b.

Estimating the integral through the value of the integrand on the layer P+ 1, we use a difference template like Fig. 2.9, b, and the difference analogue of the differential equation takes the form

In order to find the values ​​of the grid function at the next time layer, when using this difference scheme, it is necessary to solve jointly as many equations of the form (2.14) as there are internal nodes located on P - 1-1st temporary layer. Taking into account the boundary conditions = / n+1, Mg Г +1 = m n+1, the system allows us to construct a solution on the next time layer with known values ​​of the grid function on the previous one. By moving from the initial values ​​in layers, on each of which it is necessary to solve a system of equations, it is possible to construct an approximate solution in the entire domain.

The considered difference scheme is an example implicit difference scheme, it is called a look-ahead scheme or a purely implicit scheme.

The six-point difference pattern generates a family of difference schemes, of which the previous two are special cases:

At a = 0 we have an explicit scheme, with a = I- implicit with advance, with A> 0 - implicit. At A - 0.5 we obtain the symmetrical one, widely known in computing practice Crank Nicholson's diagram.

The above schemes, of course, do not exhaust the entire variety of difference schemes based on the difference approximation of differential operators. Here is an example of an explicit difference scheme based on time derivative centering, a scheme using a grid function on three time layers:

The difference pattern captures three time layers. The scheme has a second order of approximation both in time and in the spatial variable and is explicit. This scheme has a number of significant disadvantages, most of which can be eliminated by replacing And” in the approximation of the spatial derivative by the average value over two time layers:

The explicit three-layer scheme thus obtained

called Dufortpe-Frankel scheme, and the absence of a grid function value in the central node explains the name “leapfrog”, which is sometimes used for schemes of this kind.

Using examples, it was shown that for the same boundary value problem it is possible to write several different difference schemes, i.e. The researcher has a fairly large selection at his disposal. What conditions must the difference scheme satisfy in order for the difference solution to correspond to the solution of the original differential problem? This issue will be discussed in the next section.

Using a template for each internal node of the solution region, the heat equation is approximated

From here we find:

Using the initial and boundary conditions, the values ​​of the grid function are found at all nodes at the zero time level.

Then using the relations

the values ​​of these functions are found in all internal nodes at the first time level, after which we find the value at the boundary nodes

As a result, we find the value of the features in all nodes at the first time level. After that, using these relations we find all other values, etc.

In the difference scheme under consideration, the value of the desired function at the next time level is found directly, explicitly using the formula

Therefore, the difference scheme under consideration using this pattern is called explicit difference scheme . Its accuracy is of the order of magnitude.

This difference scheme is easy to use, but it has a significant drawback. It turns out that the explicit difference scheme has a stable solution only in case that, if the condition is met :

Explicit difference scheme is conditionally stable . If the condition is not met, then small calculation errors, for example, those associated with rounding computer data, lead to a sharp change in the solution. The solution becomes unusable. This condition imposes very strict restrictions on the time step, which may be unacceptable due to a significant increase in the computation time for solving this problem.

Consider a difference scheme using a different pattern

Method 36

Implicit difference scheme for the heat equation.

Let's substitute into the thermal conductivity equation:

This relation is written for each internal node at the time level and is complemented by two relations that determine the values ​​​​at the boundary nodes. The result is a system of equations for determining the unknown values ​​of the function at the time level.

The scheme for solving the problem is as follows:

Using the initial and boundary conditions, the value of the function is found at the zero time level. Then, using these relations and boundary conditions, a system of linear algebraic equations is constructed to find the value of the function at the first time level, after which the system is built again using these relations, and the values ​​​​are found at the second time level, etc.

Difference from explicit schema- values ​​at the next time level are not calculated directly using a ready-made formula, but are found by solving a system of equations, i.e. the values ​​of the unknowns are found implicitly by solving the SLAE. Therefore, the difference scheme is called implicit. Unlike explicit, implicit is absolutely stable.

Topic No. 9

Optimization problems.

These problems are among the most important problems in applied mathematics. Optimization means choosing the best option from all possible solutions to a given problem. To do this, it is necessary to formulate the problem being solved as a mathematical one, giving a quantitative meaning to the concepts of better or worse. Typically, during the solution process it is necessary to find the optimized parameter values. These parameters are called design And the number of design parameters determines dimension of the problem.

A quantitative assessment of the solution is made using a certain function depending on the design parameters. This function is called target . It is constructed in such a way that the most optimal value corresponds to the maximum (minimum).

- objective function.

The simplest cases are when the objective function depends on one parameter and is specified by an explicit formula. There can be several target functions.

For example, when designing an aircraft, it is necessary to simultaneously ensure maximum reliability, minimum weight and cost, etc. In such cases, enter priority system . Each objective function is assigned a certain target multiplier, resulting in a generalized objective function (trade-off function).

Usually the optimal solution is limited by a number of conditions related to the physical function of the problem. These conditions can be in the form of equalities or inequalities

The theory and methods for solving optimization problems in the presence of restrictions are the subject of research in one of the branches of applied mathematics - mathematical programming.

If the objective function is linear with respect to the design parameters and the restrictions imposed on the parameters are also linear, then linear programming problem . Let's consider methods for solving a one-dimensional optimization problem.

It is required to find the values ​​at which the objective function has a maximum value. If the objective function is specified analytically and an expression for its derivatives can be found, then the optimal solution will be achieved either at the ends of the segment or at the points at which the derivative vanishes. These are the critical points and . It is necessary to find the values ​​of the objective function at all critical points and select the maximum one.

In general, various search methods are used to find a solution. As a result, the segment containing the optimal solution narrows.

Let's look at some of the search methods. Let us assume that the objective function on the interval has one maximum. In this case, dividing with nodal points, the number of which is , the objective function is calculated at these nodal points. Let us assume that the maximum value of the objective function will be at the node , then we can assume that the optimal solution is located on the interval . As a result, the segment containing the optimal solution was narrowed. The resulting new segment is again divided into parts, etc. With each partition, the segment containing the optimal solution is reduced by a factor.

Let us assume that narrowing steps have been performed. Then the original segment is reduced by a factor.

That is, we do it while it’s running (*)

In this case, the objective function is calculated.

It is required to find a value such that the expression (*) is obtained at the smallest

number of calculations.

Method 37

Half division method.

Let's consider the search method for . It is called the halving method, since at each step the segment containing the optimal solution is halved.

The efficiency of the search can be increased by specially selecting the points at which the objective function is calculated at a certain narrowing step.

Method 38

Golden section method.

One effective way is the golden ratio method. The golden section of a segment is the point for which the condition is satisfied

There are two such points: =0.382 +0.618

0,618 +0,382 .

The segment is divided by points and then a point is found at which the objective function is maximum. As a result, a modified segment with a length of 0.618( - ) is found.

One value of the golden section for the narrowed segment is already known, so at each subsequent step it is necessary to calculate the objective function at only one point (the second point of the golden section).

Method 39

Method of coordinate-by-coordinate ascent (descent).

Let's move on to considering the optimization problem in the case where the objective function depends on several parameter values. The simplest search method is the method of coordinate-by-coordinate ascent (descent).

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 the subsequent presentation of the method and algorithm for solving the implicit difference scheme 4. In the section The order of approximation of the difference scheme, it was noted that the 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 chapter ""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 chapter " 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 chapter "The order of approximation of the difference scheme"it was proven that the difference scheme (4.2) hasorder of approximation:

In chapter " 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.