View source for Elliptic partial differential equation, numerical methods

<!--
e0355301.png
$#A+1 = 34 n = 0
$#C+1 = 34 : ~/encyclopedia/old_files/data/E035/E.0305530 Elliptic partial differential equation, numerical methods
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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  $  f \equiv 0 $):

$$ \tag{1 }

\frac{\partial   ^ {2} u }{\partial  x  ^ {2} }
 +

\frac{\partial   ^ {2} u }{\partial  y  ^ {2} }
  =  -
f ( x , y ) .
$$

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  $  ( x , y ) \in \Omega $
and one examines for it the homogeneous Dirichlet problem, that is,

$$ \tag{2 }
\left . u ( x , y ) \right | _ {\partial  \Omega }   =  0 ,
$$

where  $  \partial  \Omega $
is the boundary of  $  \Omega $, 
then a generalized solution of (1)–(2) is defined as a function  $  u \in W _ {2 ,  \mathop{\rm comp}  }  ^ {1} ( \Omega ) = H _ { \mathop{\rm comp}  }  ^ {1} ( \Omega ) $
that for any function  $  v \in H _ { \mathop{\rm comp}  }  ^ {1} ( \Omega ) $
satisfies the integral identity

$$ \tag{3 }
{\int\limits \int\limits } _  \Omega  \left (

\frac{\partial  u }{\partial  x }
 
\frac{\partial  v }{\partial  x }
 +

\frac{\partial  u }{\partial  y }
 
\frac{\partial  v }{\partial  y }
 \right ) \ 
d x  d y  =  - \int\limits _  \Omega  f v  d x  d y .
$$

Here  $  H _ { \mathop{\rm comp}  }  ^ {1} ( \Omega ) $
is the [[Sobolev space|Sobolev space]] of functions that vanish on  $  \partial  \Omega $(
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  $  u _ {h} \in S _ {h} ( \Omega )\subset  H _ { \mathop{\rm comp}  }  ^ {1} ( \Omega ) $
that for any  $  v \in S _ {h} ( \Omega ) $
satisfies the integral identity (3). In a finite element method the subspace  $  S _ {h} ( \Omega ) $
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  $  \Omega $
in which a solution of (1)–(2) is sought is a polygon. Then  $  \Omega $
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  $  H _ { \mathop{\rm comp}  }  ^ {1} ( \Omega ) $
one takes the space  $  S _ {h} ( \Omega ) $
of functions that are piecewise linear, linear on every triangle, continuous, and vanish on  $  \partial  \Omega $. 
The dimension of  $  S _ {h} ( \Omega ) $
is the number of vertices of the triangle (without multiplicities) that do not hit the boundary  $  \partial  \Omega $. 
These vertices are called nodes. As a basis of  $  S _ {h} ( \Omega ) $
one can take the collection of elements  $  \phi _ {i} \in S _ {h} ( \Omega ) $
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  $  \partial  \Omega $). 
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,  $  \Omega $
is the unit square and the partition of  $  \Omega $
into finite elements is effected by the three families of equidistant lines

$$ 
x  =  m h ,\  y  =  n h ,\  y  =  x + p h ,\ \ 
m , n , p \in \mathbf Z ,\  h  ^ {-} 1 = N \in \mathbf N ,
$$

under the condition that the non-zero values of the basis functions are 1, then for the coefficients  $  c _ {mn} $
of the expansion of the approximate solution

$$ 
u _ {h} ( x , y )  =  \sum _ { m,n }
c _ {mn} \phi _ {mn} ( x , y )
$$

one obtains a system of equations that agrees entirely with the system obtained from the finite difference method. Here the  $  c _ {mn} $
are the values of the approximate solution at the nodes.

The accuracy of the finite element method thus described is characterized by the estimate

$$ 
\| u - u _ {n} \| _ {H _ { \mathop{\rm comp}  }  ^ {1} ( \Omega ) }
 =  O ( h) ,
$$

where  $  h $
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  $  O ( h  ^ {k} ) $, 
where  $  k $
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>