View source for Laplace equation, numerical methods

<!--
l0574801.png
$#A+1 = 49 n = 0
$#C+1 = 49 : ~/encyclopedia/old_files/data/L057/L.0507480 Laplace 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 that replace the original boundary value problem by a discrete problem containing a finite number  $  N $
of unknows, such that if one finds a solution of the latter with suitable accuracy, this enables one to determine the solution of the original problem with given accuracy  $  \epsilon $; 
$  N $
depends on  $  \epsilon $
and tends to infinity as  $  \epsilon \rightarrow 0 $.

In the case of  $  d $
spatial variables  $  x \equiv ( x _ {1} \dots x _ {d} ) $, 
the [[Laplace equation|Laplace equation]] has the form

$$ 
\Delta u ( x) \equiv \sum_{r=1}^ { d } 

\frac{\partial   ^ {2} u ( x) }{\partial  x _ {r}  ^ {2} }
  =  0
$$

and is the homogeneous [[Poisson equation|Poisson equation]]. Boundary value problems for the Laplace equation are special cases of boundary value problems for the Poisson equation and more general equations of elliptic type (see [[#References|[1]]]), and numerical methods for solving boundary value problems for equations of elliptic type (see [[#References|[1]]], [[#References|[2]]]) comprise many numerical methods for the Laplace equation. The specific character of the Laplace equation makes it possible to construct and use methods that have essentially better characteristics than methods for more general equations, although in practice one often prefers the simplicity of using general methods on a computer, rather than these possibilities.

The main numerical methods for equations of elliptic type are: projection-grid methods (finite-element methods) and difference methods. Both classes of methods are connected with the approximation of the original domain  $  \Omega $
by a grid domain  $  \Omega _ {N} $
containing  $  N $
nodes of the grid and the construction of a system of algebraic equations

$$ \tag{* }
L _ {N} u _ {N}  =  f _ {N}  $$

for the values of the function defined at these nodes. In projection-grid methods, which are special cases of variational and projection methods, one uses the idea of approximation of the space of functions under consideration that contains the solution of the original problem by certain special finite-dimensional subspaces with given basis functions, and in the system (*) the vector  $  u _ {N} $
consists of the coefficients of the expansion of the resulting approximation of the required solution with respect to the chosen basis. On the assumption that the solution of the original problem in a bounded domain  $  \Omega $
of the plane has the form

$$ 
u ( x)  =  \sum_{r=1}^ { k } 
c _ {r} \chi _ {r} ( x) + u _ {0} ( x) ,
$$

where  $  u _ {0} ( x) \in W _ {2}  ^ {1+m} ( \Omega ) $, 
$  m > 0 $, 
where  $  W _ {2}  ^ {1+m} ( \Omega ) $
denotes a Sobolev space, and the functions  $  \chi _ {k} ( x) \in W _ {2}  ^ {1} ( \Omega ) $
are specified and reflect the asymptotic behaviour of  $  u ( x) $
close to singular points (corner points of the boundary and points where the type of boundary condition changes), for many types of domains  $  \Omega $
and mixed boundary value problems these methods make it possible, for example, to find the solution  $  u ( x) $
to within  $  \epsilon $
in  $  W _ {2}  ^ {1} ( \Omega ) $
in  $  O ( \epsilon  ^ {-2/m}  \mathop{\rm ln}  ^ {2}  \epsilon ) $
arithmetic operations (see [[#References|[3]]]), and in a number of more special cases the estimates of the computational work are lowered to  $  O ( \epsilon  ^ {-2/m} |  \mathop{\rm ln}  \epsilon | ) $
and  $  O ( \epsilon  ^ {-2/m} ) $.

In difference methods one commonly uses in one form or another an approximation of the derivatives by differences, and in the system (*) the vector consists of components that approximate the values of the solution at the nodes of the grid  $  \Omega _ {N} $. 
The characteristics of the methods mentioned have been extensively studied for boundary value problems in bounded domains  $  \Omega $
of the plane. For example, for the Dirichlet condition  $  U \mid  _  \Gamma  = \phi ( s) $, 
where  $  \Gamma $
is the boundary of  $  \Omega $
and the  $  \phi ( s) $
are sufficiently smooth, on the basis of an improvement of the differentiability properties of the solution of the Laplace equation as one moves away from  $  \Gamma $
one can construct the system (*) in such a way that the number  $  N $
has equal order as the number  $  N _  \Gamma  $
of points on  $  \Gamma $
used to specify  $  \phi ( s) $
to within  $  \epsilon $, 
and  $  u _ {N} $
can be found to within  $  \epsilon $
in  $  O ( N _  \Gamma   \mathop{\rm ln}  ^ {2}  N _  \Gamma  ) $
arithmetic operations, and this makes it possible to find a solution of the original problem to within  $  \epsilon $
at any fixed point of a strictly interior subdomain in a finite number of operations (see [[#References|[4]]]). Methods of this type are asymptotically optimal; in the case when one uses, for example, simpler methods with a rectangular grid that have accuracy  $  O ( N  ^ {-1} ) $, 
the number of operations required to find  $  u _ {N} $
to within  $  \epsilon $
is  $  O ( N  |  \mathop{\rm ln}  N \epsilon | ) $; 
$  N \approx N _  \Gamma   ^ {2} $(
see [[#References|[4]]]). Estimates of the error in the grid method for the Laplace equation have been studied in more detail (see [[#References|[4]]], [[#References|[5]]]); if there are singular points on  $  \Gamma $
it is advisable to use the special structure of the grid close to these points (see [[#References|[5]]]). One often uses difference methods based on the approximation of certain integral characteristics for the Laplace equation (see [[#References|[6]]]).

Fairly infrequently one uses collocation methods, in which the system (*) is obtained as a consequence of the original equation being satisfied at nodes of the grid and the assumption that an approximation to a solution of the original problem is sought in some finite-dimensional subspace. A special class of numerical methods for solving boundary value problems for the Laplace equation is based on the reduction of these problems to singular integral equations and the subsequent solution of the resulting integral equations by numerical methods (see [[#References|[7]]], [[#References|[8]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  J.P. Aubin,   "Approximation of elliptic boundary-value problems" , Wiley  (1972)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  P.G. Ciarlet,   "The finite element method for elliptic problems" , North-Holland  (1978)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  E.G. Dyakonov,   "Minimization of computational work. Asymptotically optimal algorithms for elliptic problems" , Moscow  (1989)  (In Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  N.S. Bakhvalov,   "About optimization of numerical methods" , ''Proc. Internat. Congress Mathematicians Nice, 1970'' , '''3''' , Gauthier-Villars  (1971)  pp. 289–295</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  E.A. Volkov,   "On the smoothness of solutions of the Dirichlet problem and the composite mesh method on polyhedra"  ''Proc. Steklov Inst. Math.'' , '''150'''  (1979)  pp. 71–104  ''Trudy Mat. Inst. Steklov.'' , '''150'''  (1979)  pp. 67–98</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  A.A. Samarskii,   I.V. Fryazinov,   "Difference approximation methods for problems of mathematical physics"  ''Russian Math. Surveys'' , '''31''' :  6  (1976)  pp. 179–213  ''Uspekhi Mat. Nauk'' , '''31''' :  6  (1976)  pp. 167–197</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  P.K. Banerjee,   R. Butterfield,   "Boundary element methods in engineering science" , McGraw-Hill  (1981)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  S.L. Grouch,   A.M. Starfield,   "Boundary element methods in solid mechanics" , Allen &amp; Unwin  (1983)</TD></TR></table>

====Comments====

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.R. Rices,   R.F. Boisvert,   "Solving elliptic problems using ELLPACK" , Springer  (1984)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Birkhoff,   R.E. Lynch,   "Numerical solution of elliptic problems" , SIAM  (1984)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  R.S. Varga,   "Matrix iterative analysis" , Prentice-Hall  (1962)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  E.L. Wachspress,   "Iterative solution of elliptic systems, and applications to the neutron diffusion equations of nuclear physics" , Prentice-Hall  (1966)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  D.M. Young,   "Iterative solutions of large linear system" , Acad. Press  (1971)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  G.J. Fix,   "An analyse of the finite element method" , Prentice-Hall  (1973)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A.R. Mitchell,   D.F. Griffiths,   "The finite difference method in partial differential equations" , Wiley  (1980)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  C. Johnson,   "Numerical solutions of partial differential equations by the finite element method" , Cambridge Univ. Press  (1987)</TD></TR></table>