difference scheme

difference scheme is a finite system of algebraic equations associated 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 continuum character, to a finite system of equations, the numerical solution of which is fundamentally possible on computers. Algebraic equations associated 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 the approximate solution of the differential problem.

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

Approximation

It is said 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 grid depending on the step if

An approximation is said to have order if

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

sometimes discrete analogues of integral norms are used.

Example. Approximation of an operator by a finite difference operator

on a bounded interval is second order on the class of smooth functions .

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

Courant condition

The Courant condition (in the English-language literature, Eng. Courant-Friedrichs-Levy condition , CFL) - the propagation velocity of perturbations in the difference problem should not be less than in the 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 circuits whose coefficients do not depend on the solution of the differential equation, the Courant condition follows from stability.

Schemes on biased grids

In these grid schemes, where the result is set and the data is offset from each other. For example, the result points are in the middle between the data points. In some cases, this allows the use of simpler boundary conditions.

Notes

Wikimedia Foundation. 2010 .

See what "Difference Scheme" is in other dictionaries:

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

finite element difference 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, associated 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 Handbook

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

Difference scheme based on a variational problem corresponding to a boundary value problem for a differential equation. The main idea of building R. in. With. is that with a special choice of coordinate functions in the Ritz method ... ... Mathematical Encyclopedia

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

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

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

Methods for solving problems of gas dynamics based on computational algorithms. Let us consider the main aspects of the theory of numerical methods for solving problems of gas dynamics, writing the gas dynamics equations in the form of conservation laws in inertial ... ... Mathematical Encyclopedia eBook

Using a template for each internal node of the solution area, 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 ratios

the values of these functions are found at 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 functions at 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 values of the desired function at the next time level are found directly, explicitly using the formula

Therefore, the considered difference scheme using this template is called explicit difference scheme . Its accuracy is in order.

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, associated with rounding off computer data, lead to a sharp change in the solution. The solution becomes unusable. This condition imposes very severe 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.

Substitute into the heat equation:

This ratio is written for each internal node at the time level and is supplemented by two ratios 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- the 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 the explicit one, the implicit one is absolutely stable.

Theme #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 better or worse. Usually, in the process of solving, it is necessary to find optimized parameter values. These options are called design. And the number of design parameters determines task dimension.

The solution is quantified using some function that depends on the design parameters. This function is called target . It is built 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 given by an explicit formula. There may be several target functions.

For example, when designing an aircraft, it is required to simultaneously ensure maximum reliability, minimum weight and cost, etc. In such cases, enter priority system . Each target function is assigned a certain target multiplier, as a result, a generalized target function (compromise function) is obtained.

Usually the optimal solution is limited by a number of conditions associated with the physical function of the problem. These conditions can take 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 sections of applied mathematics - mathematical programming.

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

It is required to find values for at which the objective function has a maximum value. If the objective function is given 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 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 choose the maximum.

In the general case, 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 has one maximum on the interval. In this case, splitting by nodal points , the number of which is , the objective function is calculated at these nodal points. Suppose that the maximum value of the objective function will be at node , then we can assume that the optimal solution is on the interval . As a result, the segment containing the optimal solution is 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.

Assume that narrowing steps are produced. Then the original segment is reduced by a factor.

That is, do while running (*)

In this case, the objective function is calculated.

It is required to find such a value that the expression (*) is obtained with the least

number of calculations.

Method 37

half division method.

Consider the search method for . It is called the half division method, since at each step the segment containing the optimal solution is halved.

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

Method 38

Golden section method.

One of the effective methods is the golden section method. The golden section of a segment is a 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 after that there is a point where 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, therefore, at each subsequent step, the calculation of the objective function is required only at one point (the second point of the golden section).

Method 39

Coordinate ascent (descent) method.

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

Section 10. Numerical solution of partial differential equations



Difference schemes for equations of elliptic type
Various Boundary Value Problems and Approximation of Boundary Conditions
Construction of a difference scheme in the case of the Dirichlet problem for the Poisson equation
Matrix sweep method
An iterative method for solving a difference scheme for the Dirichlet problem
Equation of parabolic type. Explicit and implicit finite difference methods
Sweep methods for a parabolic type equation
Subject index

Difference schemes. Basic concepts

Let D be some area of change of independent variables x, y, bounded by a contour. It is said that in the region D a second-order linear differential equation is given for the function U(x, y) if for any point from the region D the relation holds

∂2 U		∂2 U	∂2 U
∂x2			∂x2
	G(x, y)U = f(x, y),
	G(x, y)U = f(x, y),

where a(x, y), b(x, y), . . . - coefficients, f(x, y) - free term of the equation. These functions are known and they are usually considered to be defined in a closed region D = D + .

The solution graph is a surface in Oxyz space.

Back First Previous Next Last Skip Index

Denote δ(x, y) = b2 − ac. The equation L(U) = f is called elliptic, parabolic, or

hyperbolic in D if the conditions δ(x, y)< 0, δ(x, y) = 0, δ(x, y) >0 for

all (x, y) D.

Depending on the type of differential equation, boundary initial values are set differently.

(10.1):

Poisson equation (elliptic type equation)

∂2 U ∂2 U

∂x 2 + ∂y 2 = f(x, y)

Back First Previous Next Last Skip Index

Heat equation (parabolic type equation)

∂U = ∂ 2 U + f(x, t) ∂t ∂x2

Wave equation (hyperbolic type equation)

∂2 U ∂2 U

∂x 2 + ∂y 2 = f(x, y)

Convergence, approximation and stability of difference schemes

Let U be the solution of the differential equation

given in D. Consider some set Dh = (Mh ) consisting of isolated points Mh belonging to the closed region D = D + . The number of points in Дh will be characterized by the value h; the smaller h, the greater will be the number of points in Dh. The set Dh is called a grid, and the points Mh Dh are called grid nodes. A function defined in nodes is called a grid function. Denote by U the space of functions V (x, y) continuous in D. We denote by Uh the space formed by the set of grid functions Vh (x, y) defined on Дh . In the grid method, the space U is replaced by the space Uh .

Let U(x, y) be the exact solution of the equation ((10.2 )) and U(x, y) belongs to U. Let us set the problem of finding the values Uh (x, y). These values together form a table in which the number of values

Back First Previous Next Last Skip Index

is equal to the number of points in Dh. It is rarely possible to solve an exact problem. As a rule, one can calculate some grid values U(h) , relative to which one can assume that

U(h) ≈ Uh(x, y).

The quantities U(h) are called approximate grid values of the solution U(x, y). To calculate them, a system of numerical equations is built, which we will write in the form

Lh (U(h) ) = fh ,

there is a difference operator,

corresponding to the operator

is defined by F in the same way as U

was formed according to U. Formula (10.3) will be called the difference

scheme. Let the norms k · kU h and k · kF h , respectively, be introduced in the linear spaces Uh and Fh , which are grid analogs of the norms k · kU and k · kF in the original spaces. We will say that the difference scheme (10.3) is convergent if, as h → 0, the condition

kUh (x, y) − Uh kU h → 0.

If the condition is met

kUh (x, y) − Uh kU h 6 chs ,

where c is a constant independent of h and s > 0, then we say that there is convergence at a rate of order s with respect to h.

The difference scheme (10.3 ) is said to approximate problem (10.2 ) on the solution U(x, y) if

Lh (Uh (x, y)) = f(h) + δf(h) and	δf(h) F h → 0 as h → 0.

Back First Previous Next Last Skip Index

The value δf(h) is called the approximation error or inviscid difference scheme. If

δf (h) F h 6 Mh σ , where M is a constant independent of h and σ > 0, then we say that a difference scheme is given ( 10.3 ) on the solution U(x, y) with an error of the order of σ with respect to h.

Difference scheme (3) is called stable if there exists h0 > 0 such that for all h< h0 и любых f(h) Fh выполняются условия

	The difference scheme (10.3) has a unique solution;
	U (h) Uh			f(h) F h , where M is a constant independent of h and f(h) .

In other words, a difference scheme is stable if its solution depends continuously on the input data. Stability characterizes the sensitivity of the scheme to various kinds of errors, it is an internal property of the difference problem and this property is not directly related to the original differential problem, in contrast to convergence and approximation. There is a connection between the concepts of convergence, approximation and stability. It consists in the fact that convergence follows from approximation and stability.

Theorem 1 Let the difference scheme L h (U h (x, y)) = f (h) approximates the problem L(U) = f on the solution U(x, y) with order s with respect to h and stable. Then this scheme will converge, and the order of its convergence will coincide with the order of approximation, i.e. assessment will be fair

Uh (x, y) − Uh U h 6 khs ,

where k is a constant independent of h.

Proof . By definition of approximation, we have

(h) F h 6 M(Chs ) = Khs ,

where K=MC. Thus, estimate (10.4) is established and the theorem is proved. The usual use of the grid method is as follows:

1. First, the grid selection rule is specified, i.e. the method of replacing the area D and the contour G with some grid area is indicated. Most often, the mesh is chosen to be rectangular and uniform.

2. Then one or more difference schemes are specified and constructed specifically. The approximation condition is checked and its order is established.

3. The stability of the constructed difference schemes is proved. This is one of the most important and difficult questions. If the difference scheme has approximation and stability, then the convergence is judged by the proved theorem.

4. The question of numerical solution of difference schemes is considered.

IN in the case of linear difference schemes, this will be a system of linear algebraic equations. The order of such systems can be large.

Back First Previous Next Last Skip Index

The second part of the book is devoted to the construction and study of difference schemes for ordinary differential equations. At the same time, we 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, obtained in connection with ordinary differential equations, will allow 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 consider 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 question of the convergence of solutions of difference equations when the grid is refined to the solutions of differential equations that they approximate. We restrict ourselves here to the study of two difference schemes for the 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. The division points are numbered from left to right, so that . The value and obtained by the difference scheme at the point will be denoted by Let us set the initial value. Let . Difference equation (2) implies the relation

whence we find the solution of equation (2) under the initial condition :

The exact solution of problem (1) has the form . It takes the value at the point

Let us now find an estimate for the error in the approximate solution (3). This point error will be

We are interested in how it decreases with an increase in the number of partition points, or, what is the same, with a decrease in the step of the difference grid. To find this out, let's put it in the form

Thus, equality (3) takes the form

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

On this basis, we 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).

We 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 two initial conditions to be specified, while the integrable equation (1) is a first-order equation and for it we specify only . It is natural to put in the difference scheme as well.

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

Expansions (9) according to the Taylor formula of the roots of the 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 write out the result immediately:

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 at to the finite limit b, then the first term on the right side of equality (12) tends to the desired solution of problem (1).

configuration of nodes, the values of the grid function in which determine the form of difference equations at internal (not borderline) points of the grid. As a rule, in figures with images of templates, the points involved in the calculation of derivatives are connected by lines.

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

These schemes, which also have the name upwind difference scheme (in the English literature - upwind) can be written as

Their advantage lies in the more accurate consideration of the dependence domain of the solution. If we introduce the notation

then both schemes can be written in the following forms:

(flow form of the difference equation);

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

(equation in finite increments).

Consider also method of indeterminate coefficients to construct a difference scheme, the right corner of the first order of accuracy for the transport equation

The scheme can be represented as

The Courant-Isakson-Ries scheme is closely related to the numerical methods of characteristics. We give a brief description of the idea of such methods.

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

Having carried out a linear interpolation between the nodes x m - 1 and x m on the lower time layer, we obtain

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

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

those. In another way, we arrived at the well-known "left corner" scheme, which is stable at . When the point of intersection of the characteristic coming out of 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, not interpolation is used, 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 criterion or the Courant, Friedrichs, and Levi condition. Similar reasoning can be carried out for the case c< 0 и схемы "правый уголок".

unstable four-point scheme obtained when , its order of approximation is . 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 indeterminate coefficients, or by taking into account the leading term of the approximation error more accurately. Let us consider the process of deriving the Lax-Wendroff scheme in more detail. Carrying out the study of the previous four-point scheme for approximation (and this study is quite elementary and reduces to the decomposition of 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 ratios from the other.

Next, replacing second derivative in the second term on the right side up to O(h 2) , we obtain a new difference scheme approximating 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; with its order of approximation , at .