View source for Poisson equation, numerical methods

Methods replacing the original boundary value problem for the [[Poisson equation|Poisson 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/p/p073/p073300/p0733001.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

by a system of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p0733002.png" /> linear algebraic equations

<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/p/p073/p073300/p0733003.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

with a solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p0733004.png" /> which makes it possible to construct a certain approximation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p0733005.png" /> to the solution of the original problem as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p0733006.png" />.

One defines such extremely important concepts as the error of the numerical method and bounds for the error (the accuracy) depending on the way one compares the solutions of the original problem (1) and the discrete problem (2). The algebraic properties of the system (2) (discrete analogues of boundary value problems) connected with the stability of solutions (the well-posedness of the discrete problems), the possibility of finding exact or approximate solutions of (2) by some direct or iterative method when carrying out the corresponding computation and corresponding demands on the computer memory (see [[Minimization of the labour of calculation|Minimization of the labour of calculation]]) give other characteristics of the numerical methods.

Numerical solutions of boundary value problems for the Poisson equation are important not only because these problems often arise in diverse branches of science and technology, but because they frequently are a means for solving more general boundary value problems for both equations and systems of equations of elliptic type as well as for various non-stationary systems. The basic numerical methods for solving the boundary value problems under discussion are projection methods and difference methods (see [[#References|[1]]]–[[#References|[13]]]).

==Projection methods.==
These encompass a number of methods: variational, least squares, Galerkin, projection-difference, projection-grid, and finite elements methods. In all of these one characteristically reduces the original boundary value problem to an operator 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/p/p073/p073300/p0733007.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

(the operator <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p0733008.png" /> acts, for example, from a Hilbert space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p0733009.png" /> into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330010.png" />) with subsequent choice of finite-dimensional subspaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330012.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330013.png" />): the problem (3) itself is replaced in these methods by the problem of finding a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330014.png" /> such that for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330015.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/p/p073/p073300/p07330016.png" /></td> </tr></table>

Then, given bases in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330017.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330018.png" />, the system (2) is a system for the coefficients in the expansion of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330019.png" /> with respect to the basis of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330021.png" /> can be taken as the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330022.png" /> itself; it is natural to define the error in the method as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330023.png" />. In the most important cases <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330024.png" /> is a certain subspace of the Sobolev space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330026.png" /> and, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330027.png" /> is a basis of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330028.png" />, then the system (2) takes 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/p/p073/p073300/p07330029.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</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/p/p073/p073300/p07330030.png" /></td> </tr></table>

The error in the method is estimated by the distance in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330031.png" /> from the solution of the original problem to the subspace <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330032.png" /> (see [[#References|[1]]], [[#References|[5]]]–[[#References|[11]]]). In modern variants of projection methods the subspaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330033.png" /> tend to be chosen so that the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330034.png" /> have local supports and in each equation (4) only a finite number of coefficients are non-zero. Methods of this type are also called projection-grid methods (projection-difference, variational-difference, finite element methods) (see [[#References|[1]]], [[#References|[4]]], [[#References|[7]]]–[[#References|[11]]]). The great merit of these methods is that they can be applied when the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330035.png" /> of the boundary value problem under consideration is geometrically fairly complicated. Methods which are also close to projection methods but relatively rarely applied are the [[Collocation method|collocation method]], spectral methods and boundary element methods (see [[#References|[13]]]–[[#References|[15]]]).

==Difference (finite-difference) methods.==
These use a certain grid domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330036.png" /> containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330037.png" /> nodes of a grid to approximate the original domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330038.png" /> and usually lead to a system (2) by approximating the Poisson equation and the corresponding boundary conditions by their difference (grid) analogues, using only the values of the function at the chosen nodes (see [[#References|[1]]]). The error of the method is usually obtained by comparing the vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330039.png" /> and the vector obtained by restricting the required solution to the set of nodes under consideration. The well-posedness and approximation can be studied for various choices of norms; it is, in particular, possible to use the maximum principle; convergence is obtained as a corollary of well-posedness and approximation (see [[#References|[1]]]–[[#References|[4]]]).

Systems (2) can be derived both by basing them on certain discrete analogues of the corresponding variational problems and by basing them on an approximation to certain integral relations (see [[#References|[1]]], [[#References|[2]]], [[#References|[4]]], [[#References|[11]]]); such approaches bring these variants of difference methods somewhat closer to projection-difference methods.

The most intensively studied methods for solving systems of grid equations (2) are the simplest difference analogues on a parallelepiped grid (see [[#References|[1]]], [[#References|[10]]]). In the case of two variables and when the domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330040.png" /> in the plane is rectangular, direct methods are often applied for a number of boundary conditions; these direct methods enable one to find the solution of (2) at the cost of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330041.png" /> arithmetic operations. Such a method is that of separation of variables, which uses the discrete Fourier transform and the reduction method (cf. [[Separation of variables, method of|Separation of variables, method of]]); methods are also known with a bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330042.png" /> on the numbers of operations (see [[#References|[11]]]–[[#References|[13]]]). When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330043.png" /> and one may use separation of variables (in this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330044.png" /> is a parallelepiped), the solution of (2) can be found with accuracy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330045.png" /> at the cost of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330046.png" /> operations by an iterative alternating-directions method (see [[#References|[1]]], [[#References|[11]]]); iterative methods with factorizable operators (methods of successive overrelaxation with symmetrization, incomplete matrix factorization, alternating-triangular methods) enable one to find the solution of (2) with accuracy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330047.png" /> at a cost of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330048.png" /> operations (see [[#References|[11]]], [[#References|[12]]]) in fairly general situations.

In the case of simply-connected and multiply-connected domains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330049.png" /> in the plane which are composed of a finite number of rectangles, the solution of the system (2) with accuracy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330050.png" /> can be found at the cost of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330051.png" /> operations by cutting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330052.png" /> up into rectangles (see [[#References|[11]]], [[#References|[13]]]). Similar asymptotic solutions for discrete analogues of the Dirichlet problem can be obtained for certain domains using the methods of capacity and of fictitious unknowns (see [[#References|[11]]], [[#References|[13]]]). For a number of systems (2) which are projection-difference analogues of the original problem, computation lengths of the order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330053.png" /> and sometimes also <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330054.png" /> (when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330055.png" /> is of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330056.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330057.png" />) can be achieved by iterative methods using the spectral equivalence of operators (see [[#References|[11]]], [[#References|[13]]]). In a number of cases the use of a sequence of grids enables one to obtain methods which give the solution to (2) with an accuracy of order <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330058.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330059.png" />, and with asymptotically-minimal computational work (the number of operations is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330060.png" />) (see for example [[#References|[1]]], [[#References|[10]]], [[#References|[11]]]).

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  S.K. Godunov,   V.S. Ryaben'kii,   "The theory of difference schemes" , North-Holland  (1964)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  O.A. Ladyzhenskaya,   "The boundary value problems of mathematical physics" , Springer  (1986)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  G.I. Marchuk,   V.V. Shaidurov,   "Difference methods and their extrapolations" , Springer  (1983)  (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">  S.G. Mikhlin,   "The numerical performance of variational methods" , Wolters-Noordhoff  (1971)  (Translated from Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  M.A. Krasnosel'skii,   G.M. Vainikko,   P.P. Zabreiko,   et al.,   "Approximate solution of operator equations" , Wolters-Noordhoff  (1972)  (Translated from Russian)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  J.P. Aubin,   "Approximation of elliptic boundary value problems" , Wiley  (1972)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  G. Strang,   J. Fix,   "An analyse of the finite element method" , Prentice-Hall  (1973)</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  P.G. Ciarlet,   "The finite element method for elliptic problems" , North-Holland  (1978)</TD></TR><TR><TD valign="top">[10]</TD> <TD valign="top">  W. Hackbush,   "Multigrid methods and applications" , Springer  (1985)</TD></TR><TR><TD valign="top">[11]</TD> <TD valign="top">  E.G. D'yakonov,   "Minimization of computational work. Asymptotically-optimal algorithms" , Moscow  (1989)  (In Russian)</TD></TR><TR><TD valign="top">[12]</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">[13]</TD> <TD valign="top">  R. Glowinski (ed.)  G.H. Golub (ed.)  G.A. Meurant (ed.)  J. Periaux (ed.) , ''First Internat. Symp. Domain Decomposition Methods For Partial Diff. Eqs.'' , SIAM  (1988)</TD></TR><TR><TD valign="top">[14]</TD> <TD valign="top">  C. Canuto,   M.Y. Hussaini,   A. Quarteroni,   T.A. Zang,   "Spectral methods in fluid dynamics" , Springer  (1988)</TD></TR><TR><TD valign="top">[15]</TD> <TD valign="top">  P.K. Banerjee,   R. Butterfield,   "Boundary element methods in engineering science" , McGraw-Hill  (1981)</TD></TR></table>



====Comments====
During the last few years a new and very powerful class of methods has come up which have essentially an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/p/p073/p073300/p07330061.png" /> complexity. These so-called multigrid methods are based on employing smoothing effects of higher frequencies on courser grids and damping of lower frequencies on finer grids. They must be considered to be among the most powerful tools available today (1990) and can be used for finite-difference and finite-element discretization alike.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  U. Trottenberg (ed.) , ''Multigrid Methods. Proc. Köln-Porz, 1981'' , ''Lect. notes in math.'' , '''960''' , Springer  (1982)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  S.F. McCormick,   "Multigrid methods" , SIAM  (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">  C. Johnson,   "Numerical solution of partial differential equations by the finite element method" , Cambridge Univ. Press  (1987)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  G.D. Smith,   "Numerical solution of partial differential equations: finite difference method" , Clarendon Press  (1978)</TD></TR><TR><TD valign="top">[a6]</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">[a7]</TD> <TD valign="top">  A.R. Mitchell,   R. Wait,   "Finite element analysis and applications" , Wiley  (1985)</TD></TR></table>