Difference scheme, variational

A difference scheme based on a variational problem corresponding to a boundary value problem for a differential equation. The basic idea behind the construction of a variational difference scheme is to obtain a system of linear algebraic equations with the same structure as a system of difference equations (cf. Difference equation) by choosing special coordinate functions in the Ritz method; usually the unknown parameters are approximate values to the exact solution, and, possibly, to certain of its derivatives at the nodes of a grid. It is possible to use piecewise-linear, semi-linear and other functions as such coordinate functions.

Difference schemes can also be obtained by a special choice of the coordinate functions in the Galerkin method. The method in which difference schemes are obtained via Galerkin's method is called the variational difference method (or projection difference method). The variational difference method is sometimes called the finite-element method, although the latter phrase is used also in a more general sense.

Let the boundary value problem

(1)

(2)

be given, where is a continuous function, is continuously differentiable and .

Multiplying (1) by an arbitrary function satisfying conditions (2) and integrating with respect to ,

leads to the identity

(3)

which is satisfied by the solution to the problem (1), (2). The converse is also true: A function satisfying the boundary conditions (2) and the identity (3) for arbitrary functions , , is a solution to the problem (1), (2). The identity (3) is used to construct an approximate solution by the Galerkin method. The interval is divided into parts by the points , , . The set is called the grid, the points are called the nodes of the grid and is called the step of the grid. The coordinate functions in the Galerkin method are taken to be the functions

where

Clearly outside the interval . This property of coordinate functions is customarily called the property of locality or the property of local support. Let an approximate solution to the problem be sought for in the form

(4)

where the required parameters are the values of the approximate solution at the nodes of the grid:

Let be the set of functions of the form (4). The functions in are linear on the intervals , continuous on and vanish for and . In the Galerkin method a system is obtained by substituting in (3) the function for and the functions for :

(5)

Here

and

only for , so that in each equation there are at most three unknowns.

The system (5) can be written in the form

where

This system is similar in structure to an ordinary difference system. Systems of equations obtained in this way are also called variational difference schemes. In contrast to the usual difference schemes, the coefficients and are not values of the functions and at fixed points but averages of these. This property enables one to use variational difference schemes for equations with "bad" (for example, discontinuous) coefficients.

Let be the matrix of the system (5). Since , the matrix is symmetric. The equation

holds, where is an arbitrary vector in the Euclidean space of dimension , is the scalar product in and

From the inequality

which is valid for an arbitrary differentiable function satisfying , one deduces the estimate

from which one derives the inequality

(6)

The matrix is positive definite; the system (5) has a unique solution.

For small values of the system (5) consists of a large number of equations. The accuracy of the solution of a system of algebraic equations and the amount of work necessary to find it depends to a large extent on the size of the so-called condition number of the matrix of the system. Here and are the largest and the smallest eigen value of . The inequality (6) implies that . The estimate

is also valid.

The condition number , which is the same order in as the known estimates for the matrices of ordinary difference schemes.

The convergence of the approximate solution to the exact solution is proved by the usual scheme for the Galerkin method. For an arbitrary function in equations (3) and (5) imply that

(7)

whence

(8)

where is an arbitrary function in . The right-hand side of (8) is estimated with the help of the inequality

Thus,

The notation

(the number is called the energy norm of the function ) enables one to rewrite the latter inequality in the form

Estimating the error of the variational difference scheme leads to estimating the best approximation to the exact solution by functions in the class . If one takes to be the piecewise-linear function

which coincides with the function at the nodes of the grid, then the estimate

is valid for some constant .

In the example above certain characteristic features of the variational difference method are obvious: the coordinate functions are local, ensuring that the structure of the variational difference scheme is close to that of difference schemes and that one can apply the technique of projection methods to investigate the convergence of the variational difference scheme.

The choice of local coordinate functions having the required approximation properties is basic for the construction of the variational difference scheme. The approximation problem can be posed in various function spaces. For problems in mathematical physics the Sobolev spaces are important, that is, linear sets of functions with finite norm

where is a region in , , is a non-negative integer, is a vector with integer coordinates, , and

Many classes of local coordinate functions can be constructed according to the following scheme. Let functions belonging to and vanishing outside the -dimensional cube , , be given. Let be a fixed vector with positive coordinates, let be an arbitrary integer vector and let

Let denote the set of vectors such that the -dimensional parallelopipedon , , intersects . For the given region as coordinate functions one chooses

that is, functions obtained from the original functions by a change of scale for the variables and a shift by the vector . Such coordinate functions are called regular. Let the class be the set of functions of the form

If any polynomial in of degree can be represented as a linear combination of , then for an arbitrary function it is possible to find a function such that the approximation inequality

(9)

is valid, where and does not depend on and .

The construction of a variational difference scheme for boundary value problems for elliptic equations is based on equivalent problems of finding functions satisfying integral identities. Many of these problems consist of finding functions satisfying, for an arbitrary function , an integral identity

(10)

where is the boundary of and , and are given functions. It is assumed that

and

The application of Galerkin's method to (10) using the coordinate functions gives a variational difference scheme for the problem (10). Let the solution to (10) belong to , , and let the functions satisfy conditions under which inequality (9) is valid. To estimate the error of the variational difference scheme one uses the standard technique for the Galerkin method:

where is the approximate solution.

Problems of the form (10) for which an arbitrary function from can be taken as the function are called problems with natural boundary conditions. There exists another class of boundary value problems in which on the boundary one poses boundary conditions of the form

(11)

In this case the boundary conditions (11) should also be satisfied by the functions in the identity (10). For an approximate solution of such problems by the Galerkin method it is necessary that the coordinate functions satisfy the conditions (11). The coordinate functions , introduced above by the very method of construction, are, generally speaking, not suitable for representing an approximate solution satisfying conditions (11).

A method for constructing a variational difference scheme for problems with boundary conditions of the form (11) uses the penalty method. Suppose, for example, that it is required to solve the Dirichlet problem for the Poisson equation. This problem is equivalent to determining a function with , which, for an arbitrary function with , satisfies the integral equation

In the penalty method one introduces a function which, for an arbitrary function and , satisfies the integral equation

The function is the solution to a problem with a natural boundary condition. It is proved that for small values of the solutions and are close. For an approximate solution to the latter problem it is possible to apply a variational difference scheme using regular coordinate functions.

The general method for constructing coordinate functions is as follows.

For an arbitrary positive number let there be given a set of points in , , called the nodes of the grid, such that the distance of every point of the domain from some node is at most . For each node let a collection of functions in be defined satisfying the given boundary conditions (11), where and does not depend on and . For each and all let the integral

be non-zero only for a number of indices bounded by some number independent of and (the locality condition for coordinate functions). Let be the class of functions of the form

where are numerical parameters.

If the solution to the boundary value problem can be approximated by functions in with accuracy characterized by the inequality

then for a solution obtained via the variational difference scheme the error estimate

is valid.

Irregular grids are sometimes applied to give a more complete calculation of the properties of the problem. For example, for a more accurate reproduction of a function in a neighbourhood of a corner of the boundary it is possible to arrange the nodes on a radial-ring grid.

For numerical computations the matrix of a variational difference scheme should not be too bad conditioned.

For problems of the form (10) the optimal conditioning is considered to be expressed by the relation , where is the condition number of the matrix of the variational difference scheme, is the number of nodes of the grid and is the dimension of the space containing the region . For many practical problems such a conditioning really does hold.

The use of a variational difference scheme combines the merits of the grid method and projection methods. The structure of a variational difference scheme enables one to use economical solution methods of various kinds. The solvability of variational difference schemes is easily established: the matrix of the variational difference scheme is positive definite if the difference operator is positive definite. The question of convergence reduces to the question of the approximation of the exact solution by the coordinate functions of the variational difference scheme and, consequently, the speed of convergence is determined by the differential properties of the exact solution. The variational difference scheme can be applied to problems under very weak restrictions.

Research into variational difference schemes is being carried out in the following basic directions:

1) creating coordinate functions satisfying the boundary conditions, investigating their approximation properties;

2) obtaining estimates for the accuracy in various norms;

3) constructing a variational difference scheme for problems which have some singularities (lines of discontinuity in the coefficients, corners on the boundary, etc.);

4) elaborating methods for solving variational difference schemes and methods for optimizing the methods of solution;

5) solving non-linear equations;

6) applying variational difference schemes to non-stationary equations.

References

[1]	L.A. Oganesyan, V.Ya. Rivkind, L.A. Rukhovets, "Variational-difference methods for solving elliptic equations" , 1–2 , Vilnius (1973–1974) (In Russian)
[2]	G. Fix, "An analyse of the finite element method" , Prentice-Hall (1973)
[3]	J.-P. Aubin, "Approximation of elliptic boundary-value problems" , Wiley (1972) MR0478662 Zbl 0248.65063
[4]	R.G. Varga, "Functional analysis and approximation theory in numerical analysis" , Reg. Conf. Ser. Appl. Math. , 3 , SIAM (1971) (Translated from Russian) MR0310504 Zbl 0226.65064
[5]	S.G. Mikhlin, "Variational-grid approximation" Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. , 48 (1974) pp. 32–188 (In Russian) MR0570097
[6]	G.I. Marchuk, "Methods of numerical mathematics" , Springer (1982) (Translated from Russian) MR0661258 Zbl 0485.65003
[7]	E.G. D'yakonov, "Difference methods for solving boundary value problems" , 1 , Moscow (1971) (In Russian) Zbl 0434.65078 Zbl 0308.65051

References

[a1]	P.G. Ciarlet, "Introduction to the numerical analysis of the finite element method" , North-Holland (1977)
[a2]	P.G. Ciarlet, "The finite element method for elliptic problems" , North-Holland (1978) MR0520174 Zbl 0383.65058
[a3]	A.R. Mitchell, R. Wait, "The finite element method in partial differential equations" , Wiley (1973) MR0615080 MR0483547 MR0488853 MR0383792 Zbl 0344.35001 Zbl 0228.65069