View source for 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|Difference equation]]) by choosing special coordinate functions in the [[Ritz method|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|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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317301.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317302.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

be given, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317303.png" /> is a continuous function, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317304.png" /> is continuously differentiable and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317305.png" />.

Multiplying (1) by an arbitrary function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317306.png" /> satisfying conditions (2) and integrating with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317307.png" />,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317308.png" /></td> </tr></table>

leads to the identity

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d0317309.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

which is satisfied by the solution to the problem (1), (2). The converse is also true: A function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173010.png" /> satisfying the boundary conditions (2) and the identity (3) for arbitrary functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173011.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173012.png" />, is a solution to the problem (1), (2). The identity (3) is used to construct an approximate solution by the Galerkin method. The interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173013.png" /> is divided into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173014.png" /> parts by the points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173015.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173017.png" />. The set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173018.png" /> is called the grid, the points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173019.png" /> are called the nodes of the grid and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173020.png" /> is called the step of the grid. The coordinate functions in the Galerkin method are taken to be the functions

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173021.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173022.png" /></td> </tr></table>

Clearly <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173023.png" /> outside the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173024.png" />. 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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173025.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>

where the required parameters <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173026.png" /> are the values of the approximate solution at the nodes of the grid:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173027.png" /></td> </tr></table>

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173028.png" /> be the set of functions of the form (4). The functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173029.png" /> are linear on the intervals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173030.png" />, continuous on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173031.png" /> and vanish for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173032.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173033.png" />. In the Galerkin method a system is obtained by substituting in (3) the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173034.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173035.png" /> and the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173036.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173037.png" />:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173038.png" /></td> <td valign="top" style="width:5%;text-align:right;">(5)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173039.png" /></td> </tr></table>

Here

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173040.png" /></td> </tr></table>

and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173041.png" /></td> </tr></table>

only for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173042.png" />, so that in each equation there are at most three unknowns.

The system (5) can be written in the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173043.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173044.png" /></td> </tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173045.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173046.png" /></td> </tr></table>

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173047.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173048.png" /> are not values of the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173049.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173050.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173051.png" /> be the matrix of the system (5). Since <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173052.png" />, the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173053.png" /> is symmetric. The equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173054.png" /></td> </tr></table>

holds, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173055.png" /> is an arbitrary vector in the Euclidean space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173056.png" /> of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173057.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173058.png" /> is the scalar product in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173059.png" /> and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173060.png" /></td> </tr></table>

From the inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173061.png" /></td> </tr></table>

which is valid for an arbitrary differentiable function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173062.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173063.png" />, one deduces the estimate

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173064.png" /></td> </tr></table>

from which one derives the inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173065.png" /></td> <td valign="top" style="width:5%;text-align:right;">(6)</td></tr></table>

The matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173066.png" /> is positive definite; the system (5) has a unique solution.

For small values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173067.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173068.png" /> of the matrix of the system. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173069.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173070.png" /> are the largest and the smallest eigen value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173071.png" />. The inequality (6) implies that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173072.png" />. The estimate

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173073.png" /></td> </tr></table>

is also valid.

The condition number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173074.png" />, which is the same order in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173075.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173076.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173077.png" /> equations (3) and (5) imply that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173078.png" /></td> <td valign="top" style="width:5%;text-align:right;">(7)</td></tr></table>

whence

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173079.png" /></td> <td valign="top" style="width:5%;text-align:right;">(8)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173080.png" /> is an arbitrary function in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173081.png" />. The right-hand side of (8) is estimated with the help of the inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173082.png" /></td> </tr></table>

Thus,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173083.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173084.png" /></td> </tr></table>

The notation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173085.png" /></td> </tr></table>

(the number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173086.png" /> is called the energy norm of the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173087.png" />) enables one to rewrite the latter inequality in the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173088.png" /></td> </tr></table>

Estimating the error of the variational difference scheme leads to estimating the best approximation to the exact solution by functions in the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173089.png" />. If one takes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173090.png" /> to be the piecewise-linear function

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173091.png" /></td> </tr></table>

which coincides with the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173092.png" /> at the nodes of the grid, then the estimate

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173093.png" /></td> </tr></table>

is valid for some constant <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173094.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173095.png" /> are important, that is, linear sets of functions with finite norm

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173096.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173097.png" /> is a region in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173098.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d03173099.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730100.png" /> is a non-negative integer, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730101.png" /> is a vector with integer coordinates, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730102.png" />, and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730103.png" /></td> </tr></table>

Many classes of local coordinate functions can be constructed according to the following scheme. Let functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730104.png" /> belonging to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730105.png" /> and vanishing outside the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730106.png" />-dimensional cube <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730107.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730108.png" />, be given. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730109.png" /> be a fixed vector with positive coordinates, let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730110.png" /> be an arbitrary integer vector and let

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730111.png" /></td> </tr></table>

Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730112.png" /> denote the set of vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730113.png" /> such that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730114.png" />-dimensional parallelopipedon <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730115.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730116.png" />, intersects <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730117.png" />. For the given region <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730118.png" /> as coordinate functions one chooses

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730119.png" /></td> </tr></table>

that is, functions obtained from the original functions by a change of scale for the variables and a shift by the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730120.png" />. Such coordinate functions are called regular. Let the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730121.png" /> be the set of functions of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730122.png" /></td> </tr></table>

If any polynomial <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730123.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730124.png" /> of degree <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730125.png" /> can be represented as a linear combination of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730126.png" />, then for an arbitrary function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730127.png" /> it is possible to find a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730128.png" /> such that the approximation inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730129.png" /></td> <td valign="top" style="width:5%;text-align:right;">(9)</td></tr></table>

is valid, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730130.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730131.png" /> does not depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730132.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730133.png" />.

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730134.png" /> satisfying, for an arbitrary function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730135.png" />, an integral identity

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730136.png" /></td> <td valign="top" style="width:5%;text-align:right;">(10)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730137.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730138.png" /> is the boundary of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730139.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730140.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730141.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730142.png" /> are given functions. It is assumed that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730143.png" /></td> </tr></table>

and

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730144.png" /></td> </tr></table>

The application of Galerkin's method to (10) using the coordinate functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730145.png" /> gives a variational difference scheme for the problem (10). Let the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730146.png" /> to (10) belong to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730147.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730148.png" />, and let the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730149.png" /> 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:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730150.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730151.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730152.png" /> is the approximate solution.

Problems of the form (10) for which an arbitrary function from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730153.png" /> can be taken as the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730154.png" /> are called problems with natural boundary conditions. There exists another class of boundary value problems in which on the boundary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730155.png" /> one poses boundary conditions of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730156.png" /></td> <td valign="top" style="width:5%;text-align:right;">(11)</td></tr></table>

In this case the boundary conditions (11) should also be satisfied by the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730157.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730158.png" />, 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730159.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730160.png" />, which, for an arbitrary function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730161.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730162.png" />, satisfies the integral equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730163.png" /></td> </tr></table>

In the penalty method one introduces a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730164.png" /> which, for an arbitrary function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730165.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730166.png" />, satisfies the integral equation

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730167.png" /></td> </tr></table>

The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730168.png" /> is the solution to a problem with a natural boundary condition. It is proved that for small values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730169.png" /> the solutions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730170.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730171.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730172.png" /> let there be given a set of points <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730173.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730174.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730175.png" />, called the nodes of the grid, such that the distance of every point of the domain from some node is at most <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730176.png" />. For each node <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730177.png" /> let a collection of functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730178.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730179.png" /> be defined satisfying the given boundary conditions (11), where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730180.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730181.png" /> does not depend on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730182.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730183.png" />. For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730184.png" /> and all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730185.png" /> let the integral

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730186.png" /></td> </tr></table>

be non-zero only for a number of indices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730187.png" /> bounded by some number independent of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730188.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730189.png" /> (the locality condition for coordinate functions). Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730190.png" /> be the class of functions of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730191.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730192.png" /> are numerical parameters.

If the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730193.png" /> to the boundary value problem can be approximated by functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730194.png" /> with accuracy characterized by the inequality

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730195.png" /></td> </tr></table>

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

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730196.png" /></td> </tr></table>

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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730197.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730198.png" /> is the condition number of the matrix of the variational difference scheme, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730199.png" /> is the number of nodes of the grid and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730200.png" /> is the dimension of the space containing the region <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d031/d031730/d031730201.png" />. 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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  L.A. Oganesyan,   V.Ya. Rivkind,   L.A. Rukhovets,   "Variational-difference methods for solving elliptic equations" , '''1–2''' , Vilnius  (1973–1974)  (In Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  G. Fix,   "An analyse of the finite element method" , Prentice-Hall  (1973)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  J.-P. Aubin,   "Approximation of elliptic boundary-value problems" , Wiley  (1972)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  R.G. Varga,   "Functional analysis and approximation theory in numerical analysis" , ''Reg. Conf. Ser. Appl. Math.'' , '''3''' , SIAM  (1971)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  S.G. Mikhlin,   "Variational-grid approximation"  ''Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst.'' , '''48'''  (1974)  pp. 32–188  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  G.I. Marchuk,   "Methods of numerical mathematics" , Springer  (1982)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  E.G. D'yakonov,   "Difference methods for solving boundary value problems" , '''1''' , Moscow  (1971)  (In Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P.G. Ciarlet,   "Introduction to the numerical analysis of the finite element method" , North-Holland  (1977)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  P.G. Ciarlet,   "The finite element method for elliptic problems" , North-Holland  (1978)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A.R. Mitchell,   R. Wait,   "The finite element method in partial differential equations" , Wiley  (1973)</TD></TR></table>