View source for Elliptic partial differential equation, numerical methods

Methods for the approximate determination of solutions of elliptic partial differential equations. Among the various classes of problems that are raised for elliptic equations, boundary value problems and problems with Cauchy data have been most thoroughly studied. The latter are ill-posed and require for their solution special methods [[#References|[1]]]. More typical for elliptic equations are boundary value problems, and for their approximate solution many different numerical methods have been worked out (see [[#References|[2]]], [[#References|[3]]]). In computational practice grid methods are the most widespread, and among them the method of finite differences (see [[Difference methods|Difference methods]]; [[Difference schemes, theory of|Difference schemes, theory of]], [[#References|[4]]], [[#References|[5]]]) and the method of finite elements (see [[#References|[6]]]–[[#References|[9]]]). Although these methods differ in their approach to the construction of an approximate solution — in the first one approximates the equation and the boundary conditions (see [[Approximation of a differential boundary value problem by difference boundary value problems|Approximation of a differential boundary value problem by difference boundary value problems]]) and in the second one approximates the required solution itself — nevertheless the resulting algebraic systems for determining an approximate solution are often based on similar ideas and in a number of cases coincide completely.

The essence of the method of finite differences consists of the following. The domain of continuous variation of the arguments of the original problem is replaced by a discrete set of points (nodes), which is called a grid; derivatives occurring in the differential equation and the boundary conditions are approximated by difference relations; here boundary value problems for the differential equations are replaced by a system of algebraic equations (a difference scheme). If the resulting difference boundary value problem is solvable (possibly on a sufficiently fine grid) and if its solution for a sufficiently refined grid approximates (converges to) a solution of the original problem for the differential equation, then a solution of the difference problem obtained on any fixed grid is accepted as an approximate solution of the original problem.

The simplest example of an elliptic partial differential equation is the Poisson equation (the Laplace equation when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e0355301.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/e/e035/e035530/e0355302.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

Examples of difference schemes for the Poisson equation are given in the articles [[Boundary value problem, numerical methods for partial differential equations|Boundary value problem, numerical methods for partial differential equations]] and [[Difference equation|Difference equation]].

In a finite element method a generalized solution of a boundary value problem is approximated. If, for example, (1) is given for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e0355303.png" /> and one examines for it the homogeneous Dirichlet problem, that is,

<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/e/e035/e035530/e0355304.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e0355305.png" /> is the boundary of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e0355306.png" />, then a generalized solution of (1)–(2) is defined as a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e0355307.png" /> that for any function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e0355308.png" /> satisfies the 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/e/e035/e035530/e0355309.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553010.png" /> is the [[Sobolev space|Sobolev space]] of functions that vanish on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553011.png" /> (as generalized functions). The most important finite element methods are those of Galerkin type (conformal finite element methods). In the [[Galerkin method|Galerkin method]] an approximate solution is sought in a finite-dimensional subspace of the space on which the integral identity that defines a generalized solution is given. Applied to the problem (3) a Galerkin-approximate solution is a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553012.png" /> that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553013.png" /> satisfies the integral identity (3). In a finite element method the subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553014.png" /> must have certain special properties (see [[Difference scheme, variational|Difference scheme, variational]]).

The specific nature of the finite-dimensional subspace that distinguishes the finite element method from other realizations of the Galerkin method is illustrated by the following examples. Suppose that the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553015.png" /> in which a solution of (1)–(2) is sought is a polygon. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553016.png" /> is partitioned into small triangles (the finite elements) so that any two do not have common points at all, or just one common vertex, or one common side. As a finite-dimensional subspace of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553017.png" /> one takes the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553018.png" /> of functions that are piecewise linear, linear on every triangle, continuous, and vanish on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553019.png" />. The dimension of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553020.png" /> is the number of vertices of the triangle (without multiplicities) that do not hit the boundary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553021.png" />. These vertices are called nodes. As a basis of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553022.png" /> one can take the collection of elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553023.png" /> that differ from zero only at one node. A characteristic feature of this basis is the fact that for every element its support is minimal and is formed by the union of all triangles with a common vertex at that node where the given basis element is non-zero. Thanks to this property, on every finite element there are at most three non-zero basis functions (among the vertices that do not hit <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553024.png" />). This allows one to use the restrictions of these basis functions to finite elements as a basis on the finite elements and to perform all calculations on finite elements without bringing in information on other finite elements. This property makes the finite element method very effective from the point of view of its implementation [[#References|[10]]].

If, for example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553025.png" /> is the unit square and the partition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553026.png" /> into finite elements is effected by the three families of equidistant lines

<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/e/e035/e035530/e03553027.png" /></td> </tr></table>

under the condition that the non-zero values of the basis functions are 1, then for the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553028.png" /> of the expansion of the approximate solution

<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/e/e035/e035530/e03553029.png" /></td> </tr></table>

one obtains a system of equations that agrees entirely with the system obtained from the finite difference method. Here the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553030.png" /> are the values of the approximate solution at the nodes.

The accuracy of the finite element method thus described is characterized by 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/e/e035/e035530/e03553031.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553032.png" /> is the largest linear dimension of the finite elements. To achieve higher accuracy one has to look for an approximate solution not in the space of piecewise-linear functions but in that of piecewise-quadratic or, more generally, piecewise-polynomial functions. In this case the accuracy for a suitable smoothness of the required solution is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553033.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035530/e03553034.png" /> is the degree of the polynomials used.

Apart from triangular finite elements one also uses quadrilateral finite elements. However, when the sides of the quadrilaterals are not parallel to the coordinate axes, one has to employ the isoparametric technique, that is, begin by mapping the finite elements in question into canonical form (in the present case into rectangles with sides parallel to the coordinate axes) by means of a non-degenerate transformation whose inverse is given by the same functions as the approximate solution on canonical finite elements. One can use triangle and quadrilaterals with curvilinear sides (again applying the isoparametric technique), which is necessary to solve problems in domains with smooth boundaries by methods of higher order of accuracy than the first.

Apart from the finite element methods of Galerkin type there are also other so-called non-conformal finite element methods, in which the solution is sought in spaces other than subspaces of the original ones. Most frequently such methods are used for problems with elliptic partial differential equations of an order higher than the second.

The methods of finite differences and of finite elements lead to systems of linear algebraic equations of large order with sparse matrices; one can suppress the majority of the zero elements of these matrices (see [[#References|[11]]], [[#References|[12]]]). Yet another method of approximate solution of boundary value problems for elliptic partial differential equations has been significantly developed: the method of boundary elements [[#References|[13]]].

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Lattès,   "Méthode de quasi-réversibilité et applications" , Dunod  (1967)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L.V. Kantorovich,   V.I. Krylov,   "Approximate methods of higher analysis" , Noordhoff  (1958)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  S.G. Mikhlin,   Kh.L. Smolitskii,   "Approximate methods of solution of differential and integral equations" , American Elsevier  (1967)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  A.A. Samarskii,   V.B. Andreev,   "Méthodes aux différences pour équations elliptiques" , MIR  (1978)  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  G. Birkhoff,   "Solving elliptic problems: 1930–1980"  M.H. Schultz (ed.) , ''Elliptic problem solvers'' , Acad. Press  (1981)  pp. 17–38</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  O.C. Zienkiewicz,   "The finite element method in engineering science" , McGraw-Hill  (1977)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  G.J. Fix,   "An analyse of the finite element method" , Prentice-Hall  (1973)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  P.G. Ciarlet,   "The finite element method for elliptic problems" , North-Holland  (1978)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  A.R. Mitchell,   R. Wait,   "The finite element method in partial differential equations" , Wiley  (1977)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  E. Hinton,   D.R.J. Owen,   "Finite element programming" , Acad. Press  (1977)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  A.A. Samarskii,   E.S. Nikolaev,   "Numerical methods for grid equations" , '''1–2''' , Birkhäuser  (1989)  (Translated from Russian)</TD></TR><TR><TD valign="top">[12]</TD> <TD valign="top">  A. George,   J.W.-H. Liu,   "Computer solutions of large sparse positive definite systems" , Prentice-Hall  (1981)</TD></TR><TR><TD valign="top">[13]</TD> <TD valign="top">  C.A. Brebbia,   S. Walker,   "Boundary element techniques in engineering" , Butterworths  (1980)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  O. Axelson,   V.A. Barker,   "Finite element solution of boundary value problems. Theory and computation" , Acad. Press  (1984)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  C. Johnson,   "Numerical solution of partial differential equations by the finite element method" , Cambridge Univ. Press  (1987)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G. Birkhoff,   R.E. Lynch,   "Numerical solution of elliptic problems" , SIAM  (1984)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  W.F. Ames,   "Numerical methods for partial differential equations" , Acad. Press  (1977)</TD></TR><TR><TD valign="top">[a5]</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">[a6]</TD> <TD valign="top">  G. Fairweather,   "Finite element Galerkin methods for differential equations" , M. Dekker  (1978)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  G.E. Forsythe,   W.R. Wasow,   "Finite difference methods for partial differential equations" , Wiley  (1960)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  I. Gladwell (ed.)  R. Wait (ed.) , ''A survey of numerical methods for partial differential equations'' , Clarendon Press  (1979)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  A.R. Mitchell,   D.F. Griffiths,   "The finite difference method in partial differential equations" , Wiley  (1980)</TD></TR></table>