Discretization of Differential Equations

Abstract

The simplest approach to discretize a differential equation replaces differential quotients by quotients of finite differences. For the space variables this method works best on a regular grid. Finite volume methods, which are very popular in computational fluid dynamics, take averages over small control volumes and can be easily used with irregular grids. Finite elements and finite volumes belong to the general class of finite element methods which are prominent in the engineering sciences and use an expansion in piecewise polynomials with small support. Spectral methods, on the other hand, expand the solution as a linear combination of global basis functions. A general concept is the method of weighted residuals. Most popular is Galerkin’s method. The simpler point collocation and sub-domain collocation methods fulfill the differential equation only at certain points or averaged over certain control volumes. The more demanding least-squares method has become popular in computational fluid dynamics and computational electrodynamics.

If the Green’s function is available for a problem, the method of boundary elements is an interesting alternative. It reduces the dimensionality and is, for instance, very popular in chemical physics to solve the Poisson-Boltzmann equation.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Many processes in science and technology can be described by differential equations involving the rate of changes in time or space of a continuous variable, the unknown function. While the simplest differential equations can be solved exactly, a numerical treatment is necessary in most cases and the equations have to be discretized to turn them into a finite system of equations which can be solved by computers [6, 155, 200]. In this chapter we discuss different methods to discretize differential equations. The simplest approach is the method of finite differences, which replaces the differential quotients by difference quotients (Chap. 3). It is often used for the discretization of time. Finite difference methods for the space variables work best on a regular grid. Finite volume methods are very popular in computational fluid dynamics. They take averages over small control volumes and can be easily used with irregular grids. Finite differences and finite volumes belong to the general class of finite element methods which are prominent in the engineering sciences and use an expansion in piecewise polynomials with small support. Spectral methods, on the other hand, expand the solution as a linear combination of global basis functions like polynomials or trigonometric functions. A general concept for the discretization of differential equations is the method of weighted residuals which minimizes the weighted residual of a numerical solution. Most popular is Galerkin’s method which uses the expansion functions also as weight functions. Simpler are the point collocation and sub-domain collocation methods which fulfill the differential equation only at certain points or averaged over certain control volumes. More demanding is the least-squares method which has become popular in computational fluid dynamics and computational electrodynamics. The least-square integral provides a measure for the quality of the solution which can be used for adaptive grid size control.

If the Green’s function is available for a problem, the method of boundary elements is an interesting alternative. It reduces the dimensionality and is, for instance, very popular in chemical physics to solve the Poisson-Boltzmann equation.

1 Classification of Differential Equations

An ordinary differential equation (ODE) is a differential equation for a function of one single variable, like Newton’s law for the motion of a body under the influence of a force field

$$\begin{aligned} m\frac{\mathrm {d}^{2}}{\mathrm {d}t^{2}}\mathbf {x}(t)=\mathbf {F}(\mathbf {x},t), \end{aligned}$$

(11.1)

a typical initial value problem where the solution in the domain t ₀≤t≤T is determined by position and velocity at the initial time

$$\begin{aligned} \mathbf {x}(t=t_{0})=\mathbf {x}_{0} \quad \frac{\mathrm {d}}{\mathrm {d}t}\mathbf {x}(t=t_{0})=\mathbf {v}_{0}. \end{aligned}$$

(11.2)

Such equations of motion are discussed in Chap. 12. They also appear if the spatial derivatives of a partial differential equation have been discretized. Usually this kind of equation is solved by numerical integration over finite time steps Δt=t _n+1−t _n . Boundary value problems, on the other hand, require certain boundary conditions¹ to be fulfilled, for instance the linearized Poisson-Boltzmann equation in one dimension (Chap. 17)

$$\begin{aligned} \frac{\mathrm {d}^{2}}{\mathrm {d}x^{2}}\varPhi-\kappa^{2}\varPhi=-\frac{1}{\varepsilon}\rho(x) \end{aligned}$$

(11.3)

where the value of the potential is prescribed on the boundary of the domain x ₀≤x≤x ₁

$$\begin{aligned} \varPhi(x_{0})=\varPhi_{0}\quad\varPhi(x_{1})= \varPhi_{1}. \end{aligned}$$

(11.4)

Partial differential equations (PDE) finally involve partial derivatives with respect to at least two different variables, in many cases time and spatial coordinates.

1.1 Linear Second Order PDE

A very important class are second order linear partial differential equations of the general form

$$\begin{aligned} \Biggl[\sum_{i=1}^{N}\sum _{j=1}^{N}a_{ij}\frac{\partial^{2}}{\partial x_{i}\partial x_{j}}+\sum _{i=1}^{N}b_{i}\frac{\partial}{\partial x_{i}}+c \Biggr]f(x_{1}\dots x_{N})+d=0 \end{aligned}$$

(11.5)

where the coefficients a _ij ,b _i ,c,d are functions of the variables x ₁…x _N but do not depend on the function f itself. The equation is classified according to the eigenvalues of the coefficient matrix a _ij as [141]

• elliptical if all eigenvalues are positive or all eigenvalues are negative, like for the Poisson equation (Chap. 17)

  $$\begin{aligned} \biggl(\frac{\partial^{2}}{\partial x^{2}}+\frac{\partial^{2}}{\partial y^{2}}+\frac{\partial^{2}}{\partial z^{2}} \biggr) \varPhi(x,y,z)=-\frac{1}{\varepsilon}\rho(x,y,z) \end{aligned}$$

  (11.6)

• hyperbolic if one eigenvalue is negative and all the other eigenvalues are positive or vice versa, for example the wave equation in one spatial dimension (Chap. 18)

  $$\begin{aligned} \frac{\partial^{2}}{\partial t^{2}}f-c^{2}\frac{\partial^{2}}{\partial x^{2}}f=0 \end{aligned}$$

  (11.7)

• parabolic if at least one eigenvalue is zero, like for the diffusion equation (Chap. 19)

  $$\begin{aligned} \frac{\partial}{\partial t}f(x,y,z,t)-D \biggl(\frac{\partial ^{2}}{\partial x^{2}}+\frac{\partial^{2}}{\partial y^{2}}+ \frac{\partial^{2}}{\partial z^{2}} \biggr)f(x,y,z,t)=S(x,y,z,t) \end{aligned}$$

  (11.8)

• ultra-hyperbolic if there is no zero eigenvalue and more than one positive as well as more than one negative eigenvalue. Obviously the dimension then must be 4 at least.

1.2 Conservation Laws

One of the simplest first order partial differential equations is the advection equation

$$\begin{aligned} \frac{\partial}{\partial t}f(x,t)+u\frac{\partial}{\partial x}f(x,t)=0 \end{aligned}$$

(11.9)

which describes transport of a conserved quantity with density f (for instance mass, number of particles, charge etc.) in a medium streaming with velocity u. This is a special case of the class of conservation laws (also called continuity equations)

$$\begin{aligned} \frac{\partial}{\partial t}f(\mathbf {x},t)+ \operatorname{div} \mathbf {J}(\mathbf {x},t)=g(\mathbf {x},t) \end{aligned}$$

(11.10)

which are very common in physics. Here J describes the corresponding flux and g is an additional source (or sink) term. For instance the advection-diffusion equation (also known as convection equation) has this form which describes quite general transport processes:

$$\begin{aligned} \frac{\partial}{\partial t}C= \operatorname{div} (D\operatorname{grad}C-\mathbf {u}C)+S(\mathbf {x},t)=- \operatorname{div} \mathbf {J}+S(\mathbf {x},t) \end{aligned}$$

(11.11)

where one contribution to the flux

$$\begin{aligned} \mathbf {J}=-D \operatorname{grad} C+\mathbf {u}C \end{aligned}$$

(11.12)

is proportional to the gradient of the concentration C (Fick’s first law) and the second part depends on the velocity field u of a streaming medium. The source term S represents the effect of chemical reactions. Equation (11.11) is also similar to the drift-diffusion equation in semiconductor physics and closely related to the Navier Stokes equations which are based on the Cauchy momentum equation [1]

$$\begin{aligned} \rho\frac{d\mathbf {u}}{dt}=\rho\biggl(\frac{\partial \mathbf {u}}{\partial t}+\mathbf {u} \operatorname{grad} \mathbf {u} \biggr)=\operatorname{div}\sigma+\mathbf {f} \end{aligned}$$

(11.13)

where σ denotes the stress tensor. Equation (11.10) is the strong or differential form of the conservation law. The requirements on the smoothness of the solution are reduced by using the integral form which is obtained with the help of Gauss’ theorem

$$\begin{aligned} \int_{V} \biggl(\frac{\partial}{\partial t}f(\mathbf {x},t)-g(\mathbf {x},t) \biggr)\,dV+\oint_{\partial V}\mathbf {J}(\mathbf {x},t)\,d\mathbf {A}=0. \end{aligned}$$

(11.14)

An alternative integral form results from Galerkin’s [98] method of weighted residuals which introduces a weight function w(x) and considers the equation

$$\begin{aligned} \int_{V} \biggl(\frac{\partial}{\partial t}f(\mathbf {x},t)+\operatorname{div} \mathbf {J}(\mathbf {x},t)-g(\mathbf {x},t) \biggr)w(\mathbf {x})\, dV=0 \end{aligned}$$

(11.15)

or after applying Gauss’ theorem

$$\begin{aligned} \begin{aligned}[b] &\int_{V} \biggl\{ \biggl(\frac{\partial}{\partial t}f(\mathbf {x},t)-g( \mathbf {x},t) \biggr)w(\mathbf {x})-\mathbf {J}(\mathbf {x},t) \operatorname{grad}w(\mathbf {x}) \biggr\} \,dV \\ & \quad {}+\oint_{\partial V}w(\mathbf {x})\mathbf {J}(\mathbf {x},t)\,d\mathbf {A}=0. \end{aligned} \end{aligned}$$

(11.16)

The so called weak form of the conservation law states that this equation holds for arbitrary weight functions w.

2 Finite Differences

The simplest method to discretize a differential equation is to introduce a grid of equidistant points and to discretize the differential operators by finite differences (FDM) as described in Chap. 3. For instance, in one dimension the first and second derivatives can be discretized by

$$\begin{aligned} x\rightarrow x_{m}=m\Delta x\quad m=1\dots M& \end{aligned}$$

(11.17)

$$\begin{aligned} f(x)\rightarrow f_{m}=f(x_{m})\quad m=1\dots M& \end{aligned}$$

(11.18)

$$\begin{aligned} \frac{\partial f}{\partial x}\rightarrow\biggl(\frac{\partial}{\partial x}f\biggr)_{m}= \frac{f_{m+1}-f_{m}}{\Delta x} \quad \mbox{or} \quad \biggl(\frac{\partial }{\partial x}f\biggr)_{m}= \frac{f_{m+1}-f_{m-1}}{2\Delta x}& \\ & \end{aligned}$$

(11.19)

$$\begin{aligned} \frac{\partial^{2}f}{\partial x^{2}}\rightarrow\biggl(\frac{\partial ^{2}}{\partial x^{2}}f\biggr)_{m}= \frac{f_{m+1}+f_{m-1}-2f_{m}}{\Delta x^{2}}.& \end{aligned}$$

(11.20)

These expressions are not well defined at the boundaries of the grid m=1,M unless the boundary conditions are taken into account. For instance, in case of a Dirichlet problem f ₀ and f _M+1 are given boundary values and

$$\begin{aligned} \biggl(\frac{\partial}{\partial x}f\biggr)_{1}=\frac {f_{2}-f_{0}}{2\Delta x}\quad\biggl( \frac{\partial^{2}}{\partial x^{2}}f\biggr)_{1}=\frac {f_{2}-2f_{1}+f_{0}}{\Delta x^{2}}& \end{aligned}$$

(11.21)

$$\begin{aligned} \begin{aligned}[b] &\biggl(\frac{\partial}{\partial x}f\biggr)_{M} = \frac{f_{M+1}-f_{M}}{\Delta x}\mbox{ or } \frac{f_{M+1}-f_{M-1}}{2\Delta x} \\ &\biggl(\frac{\partial ^{2}}{\partial x^{2}}f\biggr)_{M}= \frac{f_{M-1}-2f_{M}+f_{M+1}}{\Delta x^{2}}. \end{aligned}& \end{aligned}$$

(11.22)

Other kinds of boundary conditions can be treated in a similar way.

2.1 Finite Differences in Time

Time derivatives can be treated similarly using an independent time grid

$$\begin{aligned} t\rightarrow t_{n}=n\Delta t\quad n=1\dots N& \end{aligned}$$

(11.23)

$$\begin{aligned} f(t,x)\rightarrow f_{m}^{n}=f(t_{n},x_{m})& \end{aligned}$$

(11.24)

and finite differences like the first order forward difference quotient

$$\begin{aligned} \frac{\partial f}{\partial t}\rightarrow\frac {f_{m}^{n+1}-f_{m}^{n}}{\Delta t} \end{aligned}$$

(11.25)

or the symmetric difference quotient

$$\begin{aligned} \frac{\partial f}{\partial t}\rightarrow\frac {f_{m}^{n+1}-f_{m}^{n-1}}{2\Delta t} \end{aligned}$$

(11.26)

to obtain a system of equations for the function values at the grid points $f_{m}^{n}$. For instance for the diffusion equation in one spatial dimension

$$\begin{aligned} \frac{\partial f(x,t)}{\partial t}=D\frac{\partial^{2}}{\partial x^{2}}f(x,t)+S(x,t) \end{aligned}$$

(11.27)

the simplest discretization is the FTCS (forward in time, centered in space) scheme

$$\begin{aligned} \bigl(f_{m}^{n+1}-f_{m}^{n}\bigr)=D \frac{\Delta t}{\Delta x{}^{2}}\bigl(f_{m+1}^{n}+f_{m-1}^{n}-2f_{m}^{n} \bigr)+S_{m}^{n}\Delta t \end{aligned}$$

(11.28)

which can be written in matrix notation as

$$\begin{aligned} \mathbf {f}_{n+1}-\mathbf {f}_{n}=D\frac{\Delta t}{\Delta x^{2}}M \mathbf {f}_{n}+\mathbf {S}_{n}\Delta t \end{aligned}$$

(11.29)

with

$$\begin{aligned} \mathbf {f}_{n}=\left ( \begin{array}{c} f_{1}^{n}\\ f_{2}^{n}\\ f_{3}^{n}\\ \vdots\\ f_{M}^{n} \end{array} \right ) \quad \mbox{and} \quad M= \left ( \begin{array}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c} -2 & 1\\ 1 & -2 & 1\\ & 1 & -2 & 1\\ & & \ddots& \ddots& \ddots\\ & & & 1 & -2 \end{array} \right ). \end{aligned}$$

(11.30)

2.2 Stability Analysis

Fully discretized linear differential equations provide an iterative algorithm of the type²

$$\begin{aligned} \mathbf {f}_{n+1}=A\mathbf {f}_{n}+\mathbf {S}_{n}\Delta t \end{aligned}$$

(11.31)

which propagates numerical errors according to

$$\begin{aligned} \mathbf {f}_{n+1}+\mathbf {\varepsilon}_{n+1}=A(\mathbf {f}_{n}+\mathbf { \varepsilon}_{n})+\mathbf {S}_{n}\Delta t& \end{aligned}$$

(11.32)

$$\begin{aligned} \mathbf {\varepsilon}_{j+1}=A\mathbf {\varepsilon}_{j}.& \end{aligned}$$

(11.33)

Errors are amplified exponentially if the absolute value of at least one eigenvalue of A is larger than one. The algorithm is stable if all eigenvalues of A are smaller than one in absolute value (Sect. 1.4). If the eigenvalue problem is difficult to solve, the von Neumann analysis is helpful which decomposes the errors into a Fourier series and considers the Fourier components individually by setting

$$\begin{aligned} \mathbf {f}_{n}=g^{n}(k)\left ( \begin{array}{c} \mathrm {e}^{\mathrm {i}k}\\ \vdots\\ \mathrm {e}^{\mathrm {i}kM} \end{array} \right ) \end{aligned}$$

(11.34)

and calculating the amplification factor

$$\begin{aligned} \biggl \vert \frac{f_{m}^{n+1}}{f_{m}^{n}}\biggr \vert =\bigl \vert g(k)\bigr \vert . \end{aligned}$$

(11.35)

The algorithm is stable if |g(k)|≤1 for all k.

Example

For the discretized diffusion equation (11.28) we find

$$\begin{aligned} g^{n+1}(k)=g^{n}(k)+2D\frac{\Delta t}{\Delta x^{2}}g^{n}(k) ( \cos k-1 )& \end{aligned}$$

(11.36)

$$\begin{aligned} g(k)=1+2D\frac{\Delta t}{\Delta x^{2}}(\cos k-1)=1-4D\frac{\Delta t}{\Delta x{}^{2}}\sin^{2} \biggl(\frac{k}{2} \biggr)& \end{aligned}$$

(11.37)

$$\begin{aligned} 1-4D\frac{\Delta t}{\Delta x^{2}}\le g(k)\le1& \end{aligned}$$

(11.38)

hence stability requires

$$\begin{aligned} D\frac{\Delta t}{\Delta x^{2}}\le\frac{1}{2}. \end{aligned}$$

(11.39)

2.3 Method of Lines

Alternatively time can be considered as a continuous variable. The discrete values of the function then are functions of time (so called lines)

$$\begin{aligned} f_{m}(t) \end{aligned}$$

(11.40)

and a set of ordinary differential equations has to be solved. For instance for diffusion in one dimension (11.27) the equations

$$\begin{aligned} \frac{\mathrm {d}f_{m}}{\mathrm {d}t}=\frac{D}{h^{2}} (f_{m+1}+f_{m-1}-2f_{m})+S_{m}(t) \end{aligned}$$

(11.41)

which can be written in matrix notation as

$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {d}t}\left ( \begin{array}{c} f_{1}\\ f_{1}\\ f_{2}\\ \vdots\\ f_{M} \end{array} \right )=\frac{D}{\Delta x^{2}} \left ( \begin{array}{c@{\quad}c@{\quad}c@{\quad}c@{\quad}c} -2 & 1\\ 1 & -2 & 1\\ & 1 & -2 & 1\\ & & \ddots& \ddots& \ddots\\ & & & 1 & -2 \end{array} \right )\left ( \begin{array}{c} f_{1}\\ f_{2}\\ f_{3}\\ \vdots\\ f_{M} \end{array} \right )+\left ( \begin{array}{c} S_{1}+\frac{D}{h^{2}}f_{0}\\ S_{2}\\ S_{3}\\ \vdots\\ S_{M}+\frac{D}{h^{2}}f_{M+1} \end{array} \right ) \end{aligned}$$

(11.42)

or briefly

$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {d}t}\mathbf {f}(t)=A\mathbf {f}(t)+\mathbf {S}(t). \end{aligned}$$

(11.43)

Several methods to integrate such a semi-discretized equation will be discussed in Chap. 12. If eigenvectors and eigenvalues of A are easy available, an eigenvector expansion can be used.

2.4 Eigenvector Expansion

A homogeneous system

$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {d}t}\mathbf {f}(t)=A\mathbf {f}(t) \end{aligned}$$

(11.44)

where the matrix A is obtained from discretizing the spatial derivatives, can be solved by an eigenvector expansion. From the eigenvalue problem

$$\begin{aligned} A\mathbf {f}=\lambda \mathbf {f} \end{aligned}$$

(11.45)

we obtain the eigenvalues λ and eigenvectors f _λ which provide the particular solutions:

$$\begin{aligned} \mathbf {f}(t)=\mathrm{e}^{\lambda t} \mathbf {f}_{\lambda}& \end{aligned}$$

(11.46)

$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {d}t}\bigl(\mathrm{e}^{\lambda t} \mathbf {f}_{\lambda}\bigr)=\lambda \bigl(\mathrm{e}^{\lambda t}\mathbf {f}_{\lambda}\bigr)=A\bigl(\mathrm{e}^{\lambda t} \mathbf {f}_{\lambda}\bigr). & \end{aligned}$$

(11.47)

These can be used to expand the general solution

$$\begin{aligned} \mathbf {f}(t)=\sum_{\lambda}C_{\lambda}\mathrm{e}^{\lambda t} \mathbf {f}_{\lambda}. \end{aligned}$$

(11.48)

The coefficients C _λ follow from the initial values by solving the linear equations

$$\begin{aligned} \mathbf {f}(t=0)=\sum_{\lambda}C_{\lambda} \mathbf {f}_{\lambda}. \end{aligned}$$

(11.49)

If the differential equation is second order in time

$$\begin{aligned} \frac{\mathrm {d}^{2}}{\mathrm {d}t^{2}}\mathbf {f}(t)=A\mathbf {f}(t) \end{aligned}$$

(11.50)

the particular solutions are

$$\begin{aligned} \mathbf {f}(t)=\mathrm{e}^{\pm t\sqrt{\lambda}} \mathbf {f}_{\lambda}& \end{aligned}$$

(11.51)

$$\begin{aligned} \frac{\mathrm {d}^{2}}{\mathrm {d}t^{2}}\bigl(\mathrm{e}^{\pm t\sqrt{\lambda}} \mathbf {f}_{\lambda }\bigr)=\lambda \bigl(\mathrm{e}^{\pm t\sqrt{\lambda}} \mathbf {f}_{\lambda}\bigr)=A\bigl(\mathrm{e}^{\pm t\sqrt{\lambda}} \mathbf {f}_{\lambda}\bigr)& \end{aligned}$$

(11.52)

and the eigenvector expansion is

$$\begin{aligned} \mathbf {f}(t)=\sum_{\lambda} \bigl(C_{\lambda+}\mathrm{e}^{t\sqrt{\lambda}} +C_{\lambda-}\mathrm{e}^{-t\sqrt{\lambda}}\bigr)\mathbf {f}_{\lambda}. \end{aligned}$$

(11.53)

The coefficients C _λ± follow from the initial amplitudes and velocities

$$\begin{aligned} \begin{aligned}[c] \mathbf {f}(t=0) & = \sum_{\lambda}(C_{\lambda+}+C_{\lambda-}) \mathbf {f}_{\lambda} \\ \frac{\mathrm {d}}{\mathrm {d}t}\mathbf {f}(t=0) & = \sum_{\lambda}\sqrt{ \lambda}(C_{\lambda+}-C_{\lambda-})\mathbf {f}_{\lambda}. \end{aligned} \end{aligned}$$

(11.54)

For a first order inhomogeneous system

$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {d}t}\mathbf {f}(t)=A\mathbf {f}(t)+\mathbf {S}(t) \end{aligned}$$

(11.55)

the expansion coefficients have to be time dependent

$$\begin{aligned} \mathbf {f}(t)=\sum_{\lambda}C_{\lambda}(t)\mathrm{e}^{\lambda t} \mathbf {f}_{\lambda} \end{aligned}$$

(11.56)

and satisfy

$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {d}t}\mathbf {f}(t)-A\mathbf {f}(t)=\sum_{\lambda} \frac{\mathrm {d}C_{\lambda}}{ \mathrm {d}t}\mathrm {e}^{\lambda t}\mathbf {f}_{\lambda}=\mathbf {S}(t). \end{aligned}$$

(11.57)

After taking the scalar product with f _μ ³

$$\begin{aligned} \frac{\mathrm {d}C_{\mu}}{ \mathrm {d}t}=\mathrm {e}^{-\mu t} \bigl(\mathbf {f}_{\mu} \mathbf {S}(t) \bigr) \end{aligned}$$

(11.58)

can be solved by a simple time integration. For a second order system

$$\begin{aligned} \frac{\mathrm {d}^{2}}{\mathrm {d}t^{2}}\mathbf {f}(t)=A\mathbf {f}(t)+\mathbf {S}(t) \end{aligned}$$

(11.59)

we introduce the first time derivative as a new variable

$$\begin{aligned} \mathbf {g}=\frac{\mathrm {d}}{\mathrm {d}t}\mathbf {f} \end{aligned}$$

(11.60)

to obtain a first order system of double dimension

$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {d}t}\left ( \begin{array}{c} \mathbf {f}\\ \mathbf {g} \end{array} \right )=\left ( \begin{array}{cc} 0 & 1\\ A & 0 \end{array} \right ) \left ( \begin{array}{c} \mathbf {f}\\ \mathbf {g} \end{array} \right )+\left ( \begin{array}{c} \mathbf {S}\\ 0 \end{array} \right ) \end{aligned}$$

(11.61)

where eigenvectors and eigenvalues can be found from those of A (11.45)

$$\begin{aligned} \left ( \begin{array}{cc} 0 & 1\\ A & 0 \end{array} \right )\left ( \begin{array}{c} \mathbf {f}_{\lambda}\\ \pm\sqrt{\lambda} \mathbf {f}_{\lambda} \end{array} \right )=\left ( \begin{array}{c} \pm\sqrt{\lambda} \mathbf {f}_{\lambda}\\ \lambda \mathbf {f}_{\lambda} \end{array} \right )=\pm\sqrt{\lambda} \left ( \begin{array}{c} \mathbf {f}_{\lambda}\\ \pm\sqrt{\lambda} \mathbf {f}_{\lambda} \end{array} \right ) & \end{aligned}$$

(11.62)

$$\begin{aligned} \left (\pm\sqrt{\lambda} \begin{array}{cc} \mathbf {f}_{\lambda}^{T} & \mathbf {f}_{\lambda}^{T} \end{array} \right )\left ( \begin{array}{cc} 0 & 1\\ A & 0 \end{array} \right )=\left ( \lambda \begin{array}{cc} \mathbf {f}_{\lambda}^{T} & \pm\sqrt{\lambda} \mathbf {f}_{\lambda}^{T} \end{array} \right )=\pm\sqrt{\lambda}\left(\pm\sqrt{\lambda} \begin{array}{cc} \mathbf {f}_{\lambda}^{T} & \mathbf {f}_{\lambda}^{T} \end{array} \right).& \end{aligned}$$

(11.63)

Insertion of

$$\begin{aligned} \sum_{\lambda}C_{\lambda+}\mathrm {e}^{\sqrt{\lambda}t} \left ( \begin{array}{c} \mathbf {f}_{\lambda}\\ \sqrt{\lambda} \mathbf {f}_{\lambda} \end{array} \right )+C_{\lambda-}\mathrm {e}^{-\sqrt{\lambda}t} \left ( \begin{array}{c} \mathbf {f}_{\lambda}\\ -\sqrt{\lambda} \mathbf {f}_{\lambda} \end{array} \right ) \end{aligned}$$

gives

$$\begin{aligned} \sum_{\lambda}\frac{\mathrm {d}C_{\lambda+}}{\mathrm {d}t}\mathrm {e}^{\sqrt{\lambda}t} \left ( \begin{array}{c} \mathbf {f}_{\lambda}\\ \sqrt{\lambda} \mathbf {f}_{\lambda} \end{array} \right )+\frac{\mathrm {d}C_{\lambda-}}{\mathrm {d}t}\mathrm {e}^{\sqrt{\lambda}t} \left ( \begin{array}{c} \mathbf {f}_{\lambda}\\ -\sqrt{\lambda} \mathbf {f}_{\lambda} \end{array} \right )=\left ( \begin{array}{c} \mathbf {S}(t)\\ 0 \end{array} \right ) \end{aligned}$$

(11.64)

and taking the scalar product with one of the left-eigenvectors we end up with

$$\begin{aligned} \frac{\mathrm {d}C_{\lambda+}}{\mathrm {d}t}=\frac{1}{2} \bigl(\mathbf {f}_{\lambda }\mathbf {S}(t) \bigr) \mathrm {e}^{-\sqrt{\lambda}t}& \end{aligned}$$

(11.65)

$$\begin{aligned} \frac{\mathrm {d}C_{\lambda-}}{\mathrm {d}t}=-\frac{1}{2} \bigl(\mathbf {f}_{\lambda }\mathbf {S}(t) \bigr) \mathrm {e}^{\sqrt{\lambda}t}.& \end{aligned}$$

(11.66)

3 Finite Volumes

Whereas the finite differences method uses function values

$$\begin{aligned} f_{i,j,k}=f(x_{i},y_{j},z_{k}) \end{aligned}$$

(11.67)

at the grid points

$$\begin{aligned} \mathbf {r}_{ijk}=(x_{i},y_{j},z_{k}), \end{aligned}$$

(11.68)

the finite volume method (FVM) [79] averages function values and derivatives over small control volumes V _r which are disjoint and span the domain V (Fig. 11.1)

(11.69)

The averages are

$$\begin{aligned} \overline{f}_{r}=\frac{1}{V_{r}}\int_{V_{r}}dV\,f(\mathbf {r}) \end{aligned}$$

(11.70)

or in the simple case of cubic control volumes of equal size h ³

$$\begin{aligned} \overline{f}_{ijk}=\frac{1}{h^{3}}\int_{x_{i}-h/2}^{x_{i}+h/2}dx \int_{y_{j}-h/2}^{y_{j}+h/2}dy\int_{z_{k}-h/2}^{z_{k}+h/2}dz\, f(x,y,z). \end{aligned}$$

(11.71)

Fig. 11.1

(Finite volume method)  The domain V is divided into small control volumes V _r , in the simplest case cubes around the grid points r _ijk

Such average values have to be related to discrete function values by numerical integration (Chap. 4). The midpoint rule (4.17), for instance replaces the average by the central value

$$\begin{aligned} \overline{f}_{ijk}=f(x_{i},y_{j},z_{k})+O \bigl(h^{2}\bigr) \end{aligned}$$

(11.72)

whereas the trapezoidal rule (4.13) implies the average over the eight corners of the cube

$$\begin{aligned} \overline{f}_{ijk}=\frac{1}{8}\sum_{m,n,p=\pm 1}f(x_{i+m/2},y_{j+n/2},z_{k+p/2})+O \bigl(h^{2}\bigr). \end{aligned}$$

(11.73)

In (11.73) the function values refer to a dual grid [79] centered around the vertices of the original grid (11.68) (Fig. 11.2),

$$\begin{aligned} \mathbf {r}_{i+1/2,j+1/2,k+1/2}=\biggl (x_{i}+\frac{h}{2},y_{j}+ \frac{h}{2},z_{k}+\frac{h}{2}\biggr). \end{aligned}$$

(11.74)

Fig. 11.2

(Dual grid)  The dual grid (black) is centered around the vertices of the original grid (red)

The average gradient can be rewritten using the generalized Stokes’ theorem as

$$\begin{aligned} \overline{\operatorname{grad} f_{ijk}}=\frac{1}{V} \int_{V_{ijk}}dV\,\operatorname{grad} f(\mathbf {r})=\oint_{\partial V_{ijk}}f(\mathbf {r})\, d\mathbf {A}. \end{aligned}$$

(11.75)

For a cubic grid we have to integrate over the six faces of the control volume

$$\begin{aligned} \overline{\operatorname{grad} f_{ijk}}=\frac{1}{h^{3}}\left ( \begin{array}{c} \int_{z_{k}-h/2}^{z_{k}+h/2}dz\int_{y_{j}-h/2}^{y_{j}+h/2}dy (f(x_{i}+\frac{h}{2},y,z)-f(x_{i}-\frac{h}{2},y,z) )\\ \int_{z_{k}-h/2}^{z_{k}+h/2}dz\int_{x_{i}-h/2}^{x_{i}+h/2}dx (f(x_{i},y+\frac{h}{2},z)-f(x_{i},y-\frac{h}{2},z) )\\ \int_{x_{i}-h/2}^{x_{i}+h/2}dx\int_{y_{j}-h/2}^{y_{j}+h/2}dy (f(x_{i},y,z+\frac{h}{2})-f(x_{i},y,z-\frac{h}{2}) ) \end{array} \right ). \end{aligned}$$

(11.76)

The integrals have to be evaluated numerically. Applying as the simplest approximation the midpoint rule (4.17)

$$\begin{aligned} \int_{x_{i}-h/2}^{x_{i}+h/2}dx\int_{y_{j}-h/2}^{y_{j}+h/2}dy\,f(x,y)=h^{2} \bigl(f(x_{i},y_{j})+O \bigl(h^{2}\bigr) \bigr) \end{aligned}$$

(11.77)

this becomes

$$\begin{aligned} \overline{\operatorname{grad} f_{ijk}}=\frac{1}{h}\left ( \begin{array}{c} f(x_{i}+\frac{h}{2},y_{j},z_{k})-f(x_{i}-\frac{h}{2},y_{j},z_{k})\\ f(x_{i},y_{j}+\frac{h}{2},z_{k})-f(x_{i},y_{j}-\frac{h}{2},z_{k})\\ f(x_{i},y_{j},z_{k}+\frac{h}{2})-f(x_{i},y_{j},z_{k}-\frac{h}{2}) \end{array} \right ) \end{aligned}$$

(11.78)

which involves symmetric difference quotients. However, the function values in (11.78) refer neither to the original nor to the dual grid. Therefore we interpolate (Fig. 11.3)

$$\begin{aligned} f\biggl(x_{i}\pm\frac{h}{2},y_{j},z_{k} \biggr)\approx\frac{1}{2} \bigl(f(x_{i},y_{j},z_{k})+f(x_{i\pm 1},y_{j},z_{k}) \bigr)& \end{aligned}$$

(11.79)

$$\begin{aligned} \begin{aligned}[b] &\frac{1}{h}\biggl(f\biggl(x_{i}+\frac{h}{2},y_{j},z_{k} \biggr)-f\biggl(x_{i}-\frac{h}{2},y_{j},z_{k} \biggr)\biggr) \\ & \quad \approx\frac{1}{2h}\bigl(f(x_{i+1},y_{j},z_{k})-f(x_{i-1},y_{j},z_{k})\bigr) \end{aligned}& \end{aligned}$$

(11.80)

or

$$\begin{aligned} f\biggl(x_{i}\pm\frac{h}{2},y_{j},z_{k} \biggr)\approx\frac{1}{4}\sum_{m,n=\pm 1}f \biggl(x_{i}\pm\frac{h}{2},y_{j}+m \frac{h}{2},z_{k}+n\frac{h}{2}\biggr). \end{aligned}$$

(11.81)

Fig. 11.3

(Interpolation between grid points)  Interpolation is necessary to relate the averaged gradient (11.78) to the original or dual grid

The finite volume method is capable of treating discontinuities and is very flexible concerning the size and shape of the control volumes.

3.1 Discretization of fluxes

Integration of (11.10) over a control volume and application of Gauss’ theorem gives the integral form of the conservation law

$$\begin{aligned} \frac{1}{V}\oint \mathbf {J}\,d\mathbf {A}+\frac{\partial}{\partial t}\frac {1}{V}\int f\, dV=\frac{1}{V}\int g\, dV \end{aligned}$$

(11.82)

which involves the flux J of some property like particle concentration, mass, energy or momentum density or the flux of an electromagnetic field. The total flux through a control volume is given by the surface integral

$$\begin{aligned} \varPhi=\oint_{\partial V}\mathbf {J}\,d\mathbf {A} \end{aligned}$$

(11.83)

which in the special case of a cubic volume element of size h ³ becomes the sum over the six faces of the cube (Fig. 11.4)

$$\begin{aligned} \varPhi =&\sum_{r=1}^{6}\int _{A_{r}}\mathbf {J}\,d\mathbf {A} \\ =&\int_{x_{i}-h/2}^{x_{i}+h/2}dx\int_{y_{j}-h/2}^{y_{j}+h/2}dy \biggl(J_{z}\biggl(x,y,z_{k}+\frac{h}{2}\biggr)-J_{z}\biggl(x,y,z_{k}-\frac{h}{2} \biggr)\biggr) \\ &{} +\int_{x_{i}-h/2}^{x_{i}+h/2}dx\int_{z_{k}-h/2}^{z{}_{k}+h/2}dz \biggl(J_{y}\biggl(x,y_{j}+\frac{h}{2},z \biggr)-J_{z}\biggl(x,y_{j}-\frac{h}{2},z \biggr)\biggr) \\ &{} +\int_{z_{k}-h/2}^{z{}_{k}+h/2}dz\int_{y_{j}-h/2}^{y_{j}+h/2}dy \biggl(J_{x}\biggl(x_{i}+\frac{h}{2},y,z \biggr)-J_{z}\biggl(x_{i}-\frac{h}{2},y,z \biggr)\biggr). \end{aligned}$$

(11.84)

Fig. 11.4

Flux through a control volume

The surface integral can be evaluated numerically (Chap. 4). Using the midpoint approximation (11.77) we obtain

$$\begin{aligned} \frac{1}{V}\varPhi(x_{i},y_{j},z_{k}) =& \frac{1}{h} \bigl(J_{z}(x_{i},y_{j},z_{k+1/2})-J_{z}(x_{i},y_{j},z_{k-1/2}) \\ &{} +J_{y}(x_{i},y_{j+1/2},z_{k})-J_{y}(x_{i},y_{j-1/2},z_{k}) \\ &{} +J_{x}(x_{i+1/2},y_{j},z_{k})-J_{x}(x_{i-1/2},y_{j},z_{k})\bigr). \end{aligned}$$

(11.85)

The trapezoidal rule (4.13) introduces an average over the four corners (Fig. 11.3)

$$\begin{aligned} &\int_{x_{i}-h/2}^{x_{i}+h/2}dx\int_{y_{j}-h/2}^{y_{j}+h/2}dy\, f(x,y) \\ &\quad =h^{2} \biggl(\frac{1}{4}\sum_{m,n=\pm 1}f(x_{i+m/2},y_{j+n/2})+O \bigl(h^{2}\bigr) \biggr) \end{aligned}$$

(11.86)

which replaces the flux values in (11.85) by the averages

$$\begin{aligned} J_{x}(x_{i\pm 1/2},y_{j},z_{k})= \frac{1}{4}\sum_{m=\pm1,n=\pm1}J_{z}(x_{i\pm 1/2},y_{j+m/2},z_{k+n/2})& \end{aligned}$$

(11.87)

$$\begin{aligned} J_{y}(x_{i},y_{j\pm 1/2},z_{k})= \frac{1}{4}\sum_{m=\pm1,n=\pm1}J_{z}(x_{i+m/2},y_{j\pm 1/2},z_{k+n/2})& \end{aligned}$$

(11.88)

$$\begin{aligned} J_{z}(x_{i},y_{j},z_{k\pm 1/2})= \frac{1}{4}\sum_{m=\pm1,n=\pm1}J_{z}(x_{i+m/2},y_{j+n/2},z_{k\pm 1/2}).& \end{aligned}$$

(11.89)

One advantage of the finite volume method is that the flux is strictly conserved.

4 Weighted Residual Based Methods

A general method to discretize partial differential equations is to approximate the solution within a finite dimensional space of trial functions.⁴ The partial differential equation is turned into a finite system of equations or a finite system of ordinary differential equations if time is treated as a continuous variable. This is the basis of spectral methods which make use of polynomials or Fourier series but also of the very successful finite element methods. Even finite difference methods and finite volume methods can be formulated as weighted residual based methods.

Consider a differential equation⁵ on the domain V which is written symbolically with the differential operator $\mathcal{T}$

$$\begin{aligned} \mathcal{T} \bigl[u(\mathbf {r}) \bigr]=f(\mathbf {r})\quad \mathbf {r}\in V \end{aligned}$$

(11.90)

and corresponding boundary conditions which are expressed with a boundary operator $\mathcal{B}$ ⁶

$$\begin{aligned} \mathcal{B}\bigl[u(\mathbf {r})\bigr]=g(\mathbf {r})\quad \mathbf {r}\in\partial V. \end{aligned}$$

(11.91)

The basic principle to obtain an approximate solution $\tilde{u}(\mathbf {r})$ is to choose a linear combination of expansion functions N _i (r) i=1…r as a trial function which fulfills the boundary conditions⁷

$$\begin{aligned} \tilde{u}=\sum_{i=1}^{r}u_{i}N_{i}( \mathbf {r})& \end{aligned}$$

(11.92)

$$\begin{aligned} \mathcal{B}\bigl[\tilde{u}(\mathbf {r})\bigr]=g(\mathbf {r}).& \end{aligned}$$

(11.93)

In general (11.92) is not an exact solution and the residual

$$\begin{aligned} R(\mathbf {r})=\mathcal{T} [\tilde{u} ](\mathbf {r})-f(\mathbf {r}) \end{aligned}$$

(11.94)

will not be zero throughout the whole domain V. The function $\tilde{u}$ has to be determined such that the residual becomes “small” in a certain sense. To that end weight functions⁸ w _j j=1…r are chosen to define the weighted residuals

$$\begin{aligned} R_{j} (u_{1}\dots u_{r} )=\int dV\,w_{j}(\mathbf {r}) \bigl(\mathcal{T} [\tilde{u} ](\mathbf {r})-f(\mathbf {r}) \bigr). \end{aligned}$$

(11.95)

The optimal parameters u _i are then obtained from the solution of the equations

$$\begin{aligned} R_{j}(u_{1}\dots u_{r})=0\quad j=1\dots r. \end{aligned}$$

(11.96)

In the special case of a linear differential operator these equations are linear

$$\begin{aligned} \sum_{i=1}^{r}u_{i}\int dV\,w_{j}(\mathbf {r})\mathcal{T} \bigl[N_{i}(\mathbf {r}) \bigr]-\int dV\, w_{j}(\mathbf {r})f(\mathbf {r})=0. \end{aligned}$$

(11.97)

Several strategies are available to choose suitable weight functions.

4.1 Point Collocation Method

The collocation method uses the weight functions w _j (r)=δ(r−r _j ), with certain collocation points r _j ∈V. The approximation $\tilde{u}$ obeys the differential equation at the collocation points

$$\begin{aligned} 0=R_{j}=\mathcal{T}[\tilde{u}](\mathbf {r}_{j})-f( \mathbf {r}_{j}) \end{aligned}$$

(11.98)

and for a linear differential operator

$$\begin{aligned} 0=\sum_{i=1}^{r}u_{i} \mathcal{T}[N_{i}](\mathbf {r}_{j})-f(\mathbf {r}_{j}). \end{aligned}$$

(11.99)

The point collocation method is simple to use, especially for nonlinear problems. Instead of using trial functions satisfying the boundary conditions, extra collocation points on the boundary can be added (mixed collocation method).

4.2 Sub-domain Method

This approach uses weight functions which are the characteristic functions of a set of control volumes V _i which are disjoint and span the whole domain similar as for the finite volume method

(11.100)

$$\begin{aligned} w_{j}(\mathbf {r)}= \left\{ \begin{array}{l@{\quad}l} 1&\mathbf {r}\in V_{j} \\ 0& \mbox{else}. \end{array} \right.& \end{aligned}$$

(11.101)

The residuals then are integrals over the control volumes and

$$\begin{aligned} 0=R_{j}=\int_{V_{j}}dV\, \bigl(\mathcal{T} [\tilde{u} ](\mathbf {r})-f(\mathbf {r}) \bigr) \end{aligned}$$

(11.102)

respectively

$$\begin{aligned} 0=\sum_{i}u_{i}\int _{V_{j}}dV\,\mathcal{T} [N_{i} ](\mathbf {r})-\int _{V_{j}}dV\, f(\mathbf {r}). \end{aligned}$$

(11.103)

4.3 Least Squares Method

Least squares methods have become popular for first order systems of differential equations in computational fluid dynamics and computational electrodynamics [30, 140].

The L2-norm of the residual (11.94) is given by the integral

$$\begin{aligned} S=\int_{V}dV\, R(\mathbf {r})^{2}. \end{aligned}$$

(11.104)

It is minimized by solving the equations

$$\begin{aligned} 0=\frac{\partial S}{\partial u_{j}}=2\int_{V}dV\,\frac{\partial R}{\partial u_{j}} R(\mathbf {r}) \end{aligned}$$

(11.105)

which is equivalent to choosing the weight functions

$$\begin{aligned} w_{j}(\mathbf {r})=\frac{\partial R}{\partial u_{j}}R(\mathbf {r})=\frac {\partial}{\partial u_{j}} \mathcal{T} \biggl[\sum_{i}u_{i}N_{i}( \mathbf {r}) \biggr] \end{aligned}$$

(11.106)

or for a linear differential operator simply

$$\begin{aligned} w_{j}(\mathbf {r})=\mathcal{T} \bigl[N_{j}(\mathbf {r}) \bigr]. \end{aligned}$$

(11.107)

Advantages of the least squares method are that boundary conditions can be incorporated into the residual and that S provides a measure for the quality of the solution which can be used for adaptive grid size control. On the other hand S involves a differential operator of higher order and therefore much smoother trial functions are necessary.

4.4 Galerkin Method

Galerkin’s widely used method [87, 98] chooses the basis functions as weight functions

$$\begin{aligned} w_{j}(\mathbf {r})=N_{j}(\mathbf {r}) \end{aligned}$$

(11.108)

and solves the following system of equations

$$\begin{aligned} \int dV\, N_{j}(\mathbf {r})\mathcal{T} \biggl[\sum _{i}u_{i}N_{i}(\mathbf {r}) \biggr]-\int dV\, N_{j}(\mathbf {r})f(\mathbf {r})=0 \end{aligned}$$

(11.109)

or in the simpler linear case

$$\begin{aligned} \sum u_{i}\int_{V}dV\,N_{j}(\mathbf {r})\mathcal{T}\bigl(N_{i}(\mathbf {r})\bigr)=\int _{V}dV\,N_{j}(\mathbf {r})f(\mathbf {r},t). \end{aligned}$$

(11.110)

5 Spectral and Pseudo-spectral Methods

Spectral methods use basis functions which are nonzero over the whole domain, the trial functions being mostly polynomials or Fourier sums [35]. They can be used to solve ordinary as well as partial differential equations. The combination of a spectral method with the point collocation method is also known as pseudo-spectral method.

5.1 Fourier Pseudo-spectral Methods

Linear differential operators become diagonal in Fourier space. Combination of Fourier series expansion and point collocation leads to equations involving a discrete Fourier transformation, which can be performed very efficiently with the Fast Fourier Transform methods.

For simplicity we consider only the one-dimensional case. We choose equidistant collocation points

$$\begin{aligned} x_{m}=m\Delta x\quad m=0,1\dots M-1 \end{aligned}$$

(11.111)

and expansion functions

$$\begin{aligned} N_{j}(x)=\mathrm {e}^{\mathrm {i}k_{j}x}\quad k_{j}=\frac{2\pi}{M\Delta x}j \quad j=0,1\dots M-1. \end{aligned}$$

(11.112)

For a linear differential operator

$$\begin{aligned} \mathcal{L}\bigl[\mathrm {e}^{\mathrm {i}k_{j}x}\bigr]=l(k_{j})\mathrm {e}^{\mathrm {i}k_{j}x} \end{aligned}$$

(11.113)

and the condition on the residual becomes

$$\begin{aligned} 0=R_{m}=\sum_{j=0}^{M-1}u_{j}l(k_{j})\mathrm {e}^{\mathrm {i}k_{j}x_{m}}-f(x_{m}) \end{aligned}$$

(11.114)

or

$$\begin{aligned} f(x_{m})=\sum_{j=0}^{M-1}u_{j}l(k_{j})\mathrm {e}^{\mathrm {i}2\pi mj/M} \end{aligned}$$

(11.115)

which is nothing but a discrete Fourier back transformation (Sect. 7.2, (7.19)) which can be inverted to give

$$\begin{aligned} u_{j} l(k_{j})=\frac{1}{N}\sum _{m=0}^{M-1}f(x_{m})\mathrm {e}^{-\mathrm {i}2\pi mj/M}. \end{aligned}$$

(11.116)

Instead of exponential expansion functions, sine and cosine functions can be used to satisfy certain boundary conditions, for instance to solve the Poisson equation within a cube (Sect. 17.1.2).

5.2 Example: Polynomial Approximation

Let us consider the initial value problem (Fig. 11.5)

$$\begin{aligned} \frac{\mathrm {d}}{\mathrm {d}x}u(x)-u(x)=0\quad u(0)=1\quad\mbox{for }0\le x\le1 \end{aligned}$$

(11.117)

with the well known solution

$$\begin{aligned} u(x)=\mathrm {e}^{x}. \end{aligned}$$

(11.118)

We choose a polynomial trial function with the proper initial value

$$\begin{aligned} \tilde{u}(x)=1+u_{1}x+u_{2}x^{2}. \end{aligned}$$

(11.119)

The residual is

$$\begin{aligned} R(x) =&u_{1}+2u_{2}x- \bigl(1+u_{1}x+u_{2}x^{2} \bigr) \\ =&(u_{1}-1)+(2u_{2}-u_{1})x-u_{2}x^{2}. \end{aligned}$$

(11.120)

Fig. 11.5

(Approximate solution of a simple differential equation)  The initial value problem $\frac{\mathrm {d}}{\mathrm {d}x}u(x)-u(x)=0$ u(0)=1 for 0≤x≤1 is approximately solved with a polynomial trial function $\tilde {u}(x)=1+u_{1}x+u_{2}x^{2}$. The parameters u _1,2 are optimized with the method of weighted residuals using point collocation (full curve), sub-domain collocation (dotted curve), Galerkin’s method (dashed curve) and least squares (dash-dotted curve). The absolute error $\tilde{u}(x)-\mathrm {e}^{x}$ (top) and the residual $R(x)=\frac{\mathrm {d}}{\mathrm {d}x}\tilde{u}(x)- \tilde {u}(x)= (u_{1}-1)+(2u_{2}-u_{1})x -u_{2}x^{2}$ both are smallest for the least squares and sub-domain collocation methods

5.2.1 Point Collocation Method

For our example we need two collocation points to obtain two equations for the two unknowns u _1,2. We choose $x_{1}=0,x_{2}=\frac{1}{2}$. Then we have to solve the equations

$$\begin{aligned} R(x_{1})=u_{1}-1=0& \end{aligned}$$

(11.121)

$$\begin{aligned} R(x_{2})=\frac{1}{2}u_{1}+\frac{3}{4}u_{2}-1=0& \end{aligned}$$

(11.122)

which gives

$$\begin{aligned} u_{1}=1\quad u_{2}=\frac{2}{3}& \end{aligned}$$

(11.123)

$$\begin{aligned} u_{c}=1+x+\frac{2}{3}x^{2}.& \end{aligned}$$

(11.124)

5.2.2 Sub-domain Method

We need two sub-domains to obtain two equations for the two unknowns u _1,2. We choose $V_{1}=\{x,0<x<\frac{1}{2}\}$, $V_{2}=\{x,\frac{1}{2}<x<1\}$. Integration gives

$$\begin{aligned} R_{1}=\frac{3}{8}u_{1}+\frac{5}{24}u_{2}- \frac{1}{2}=0& \end{aligned}$$

(11.125)

$$\begin{aligned} R_{2}=\frac{1}{8}u_{1}+\frac{11}{24}u_{2}- \frac{1}{2}=0& \end{aligned}$$

(11.126)

$$\begin{aligned} u_{1}=u_{2}=\frac{6}{7}& \end{aligned}$$

(11.127)

$$\begin{aligned} u_{sdc}=1+\frac{6}{7}x+\frac{6}{7}x^{2}.& \end{aligned}$$

(11.128)

5.2.3 Galerkin Method

Galerkin’s method uses the weight functions w ₁(x)=x,w ₂(x)=x ². The equations

$$\begin{aligned} \int_{0}^{1}dx\, w_{1}(x)R(x)= \frac{1}{6}u_{1}+\frac{5}{12}u_{2}- \frac{1}{2}=0& \end{aligned}$$

(11.129)

$$\begin{aligned} \int_{0}^{1}dx\, w_{2}(x)R(x)= \frac{1}{12}u_{1}+\frac{3}{10}u_{2}- \frac{1}{3}=0& \end{aligned}$$

(11.130)

have the solution

$$\begin{aligned} u_{1}=\frac{8}{11}\quad u_{2}=\frac{10}{11}& \end{aligned}$$

(11.131)

$$\begin{aligned} u_{G}=1+\frac{8}{11}x+\frac{10}{11}x^{2}.& \end{aligned}$$

(11.132)

5.2.4 Least Squares Method

The integral of the squared residual

$$\begin{aligned} S=\int_{0}^{1}dx\, R(x)^{2}=1-u_{1}- \frac{4}{3}u_{2}+\frac{1}{3}u_{1}^{2}+ \frac{1}{2}u_{1}u_{2}+\frac{8}{15}u_{2}^{2} \end{aligned}$$

(11.133)

is minimized by solving

$$\begin{aligned} \frac{\partial S}{\partial u_{1}}=\frac{2}{3}u_{1}+\frac{1}{2}u_{2}-1=0& \end{aligned}$$

(11.134)

$$\begin{aligned} \frac{\partial S}{\partial u_{2}}=\frac{1}{2}u_{1}+\frac{16}{15}u_{2}- \frac{4}{3}=0& \end{aligned}$$

(11.135)

which gives

$$\begin{aligned} u_{1}=\frac{72}{83}\quad u_{2}=\frac{70}{83}& \end{aligned}$$

(11.136)

$$\begin{aligned} u_{LS}=1+\frac{72}{83}x+\frac{70}{83}x^{2}.& \end{aligned}$$

(11.137)

6 Finite Elements

The method of finite elements (FEM) is a very flexible method to discretize partial differential equations [84, 210]. It is rather dominant in a variety of engineering sciences. Usually the expansion functions N _i are chosen to have compact support. The integration volume is divided into disjoint sub-volumes

(11.138)

The N _i (x) are piecewise continuous polynomials which are nonzero only inside V _i and a few neighbor cells.

6.1 One-Dimensional Elements

In one dimension the domain is an interval V={x;a≤x≤b} and the sub-volumes are small sub-intervals V _i ={x;x _i ≤x≤x _i+1}. The one-dimensional mesh is the set of nodes {a=x ₀,x ₁…x _r =b}. Piecewise linear basis functions (Fig. 11.6) are in the 1-dimensional case given by

$$\begin{aligned} N_{i}(x)= \left\{ \begin{array}{l@{\quad}l} \frac{x_{i+1}-x}{x_{i+1}-x_{i}}&\mbox{for }x_{i}<x<x_{i+1}\\ \frac{x-x_{i-1}}{x_{i}-x_{i-1}}&\mbox{for }x_{i-1}<x<x_{i}\\ 0&\mbox{else} \end{array} \right . \end{aligned}$$

(11.139)

and the derivatives are (except at the nodes x _i )

$$\begin{aligned} N_{i}'(x)= \left\{ \begin{array}{l@{\quad}l} -\frac{1}{x_{i+1}-x_{i}}&\mbox{for }x_{i}<x<x_{i+1}\\ \frac{1}{x_{i}-x_{i-1}}&\mbox{for }x_{i-1}<x<x_{i}\\ 0&\mbox{else}. \end{array} \right . \end{aligned}$$

(11.140)

Fig. 11.6

(Finite elements in one dimension)  The basis functions N _i are piecewise continuous polynomials and have compact support. In the simplest case they are composed of two linear functions over the sub-intervals x _i−1≤x≤x _i and x _i ≤x≤x _i+1

6.2 Two- and Three-Dimensional Elements

In two dimensions the mesh is defined by a finite number of points (x _i ,y _i )∈V (the nodes of the mesh). There is considerable freedom in the choice of these points and they need not be equally spaced.

6.2.1 Triangulation

The nodes can be regarded as forming the vertices of a triangulation⁹ of the domain V (Fig. 11.7).

Fig. 11.7

(Triangulation of a two-dimensional domain)  A two-dimensional mesh is defined by a set of node points which can be regarded to form the vertices of a triangulation

The piecewise linear basis function in one dimension (11.139) can be generalized to the two-dimensional case by constructing functions N _i (x,y) which are zero at all nodes except (x _i ,y _i )

$$\begin{aligned} N_{i}(x_{j},y_{j})=\delta_{i,j}. \end{aligned}$$

(11.141)

These functions are linear over each triangle which contains the vertex i and can be combined as the sum of small pyramids (Fig. 11.8). Let one of the triangles be denoted by its three vertices as T _ijk .¹⁰ The corresponding linear function then is

$$\begin{aligned} n_{ijk}(x,y)=\alpha+\beta_{x}(x-x_{i})+ \beta_{y}(y-y_{i}) \end{aligned}$$

(11.142)

where the coefficients follow from the conditions

$$\begin{aligned} n_{ijk}(x_{i},y_{i})=1\quad n_{ijk}(x_{j},y_{j})=n_{ijk}(x_{k},y_{k})=0 \end{aligned}$$

(11.143)

as

$$\begin{aligned} \alpha=1\quad\beta_{x}=\frac{y_{j}-y_{k}}{2A_{ijk}}\quad\beta_{y}= \frac{x_{k}-x_{j}}{2A_{ijk}} \end{aligned}$$

(11.144)

with

$$\begin{aligned} A_{ijk}=\frac{1}{2} \det \left| \begin{array}{c@{\quad}c} x_{j}-x_{i} & x_{k}-x_{i}\\ y_{j}-y_{i} & y_{k}-y_{i} \end{array} \right| \end{aligned}$$

(11.145)

which, apart from sign, is the area of the triangle T _ijk . The basis function N _i now is given by

$$\begin{aligned} N_{i}(x,y)= \left\{ \begin{array}{l@{\quad}l} n_{ijk}(x,y)&(x,y)\in T_{ijk}\\ 0&\mbox{else}. \end{array} \right. \end{aligned}$$

Fig. 11.8

(Finite elements in two dimensions)  The simplest finite elements in two dimensions are piecewise linear functions N _i (x,y) which are non-vanishing only at one node (x _i ,y _i ) (right side). They can be constructed from small pyramids built upon one of the triangles that contains this node (left side)

In three dimensions we consider tetrahedrons (Fig. 11.9) instead of triangles. The corresponding linear function of three arguments has the form

$$\begin{aligned} n_{i,j,k,l}(x,y,z)=\alpha+\beta_{x}(x-x_{i})+ \beta_{y}(y-y_{i})+\beta_{z}(z-z_{i}) \end{aligned}$$

(11.146)

and from the conditions n _i,j,k,l (x _i ,y _i ,z _i )=1 and n _i,j,k,l =0 on all other nodes we find (an algebra program is helpful at that point)

$$\begin{aligned} \alpha =&1 \\ \beta_{x} =&\frac{1}{6V_{ijkl}}\det\left\vert \begin{array}{c@{\quad}c} y_{k}-y_{j} & y_{l}-y_{j}\\ z_{k}-z_{j} & z_{l}-z_{j} \end{array} \right\vert \\ \beta_{y} =&\frac{1}{6V_{ijkl}}\det \left\vert \begin{array}{c@{\quad}c} z_{k}-z_{j} & z_{l}-z_{j}\\ x_{k}-x_{j} & x_{l}-x_{j} \end{array} \right\vert \\ \beta_{z} =&\frac{1}{6V_{ijkl}}\det\left\vert \begin{array}{c@{\quad}c} x_{k}-x_{j} & x_{l}-x_{j}\\ y_{k}-y_{j} & y_{l}-y_{j} \end{array} \right\vert \end{aligned}$$

(11.147)

where V _ijkl is, apart from sign, the volume of the tetrahedron

$$\begin{aligned} V_{ijkl}=\frac{1}{6}\det\left \vert \begin{array}{c@{\quad}c@{\quad}c} x_{j}-x_{i} & x_{k}-x_{i} & x_{l}-x_{i}\\ y_{j}-y_{i} & y_{k}-y_{i} & y_{l}-y_{i}\\ z_{j}-z_{i} & z_{k}-z_{i} & z_{l}-z_{i} \end{array} \right \vert . \end{aligned}$$

(11.148)

Fig. 11.9

(Tetrahedron)  The tetrahedron is the three-dimensional case of a Euclidean simplex, i.e. the simplest polytope

6.2.2 Rectangular Elements

For a rectangular grid rectangular elements offer a practical alternative to triangles. Since equations for four nodes have to be fulfilled, the basic element needs four parameters, which is the case for a bilinear expression. Let us denote one of the rectangles which contains the vertex i as R _i,j,k,l . The other three edges are

$$\begin{aligned} (x_{j},y_{j})=(x_{i}+b_{x},y_{i}) \quad(x_{k},y_{k})=(x_{i},y_{i}+b_{y}) \quad(x_{l},y_{l})=(x_{i}+b_{x},y_{i}+b_{y}) \end{aligned}$$

(11.149)

where b _x =±h _x ,b _y =±h _y corresponding to the four rectangles with the common vertex i (Fig. 11.10).

Fig. 11.10

(Rectangular elements around one vertex)  The basis function N _i is a bilinear function on each of the four rectangles containing the vertex (x _i ,y _i )

The bilinear function (Fig. 11.11) corresponding to R _ijkl is

$$\begin{aligned} n_{i,j,k,l}(x,y)=\alpha+\beta(x-x_{i})+\gamma(y-y_{i})+ \eta(x-x_{i}) (y-y_{i}). \end{aligned}$$

(11.150)

It has to fulfill

$$\begin{aligned} n_{i,j,k,l}(x_{i},y_{i})=1\quad n_{i,j,k,l}(x_{j},y_{j})=n_{i,j,k,l}(x_{k},y_{k})=n_{i,j,k,l}(x_{l},y_{l})=0 \end{aligned}$$

(11.151)

from which we find

$$\begin{aligned} \alpha=1\quad\beta=-\frac{1}{b_{x}}\quad\gamma=-\frac{1}{b_{y}}\quad\eta= \frac{1}{b_{x}b_{y}}& \end{aligned}$$

(11.152)

$$\begin{aligned} n_{i,j,k,l}(x,y)=1-\frac{x-x_{i}}{b_{x}}-\frac{y-y_{i}}{b_{y}}+ \frac{(x-x_{i})}{b_{x}}\frac{(y-y_{i})}{b_{y}}.& \end{aligned}$$

(11.153)

The basis function centered at node i then is

$$\begin{aligned} N_{i}(x,y)= \left\{ \begin{array}{l@{\quad}l} n_{i,j,k,l}(x,y)&(x,y)\in R_{i,j,k,l} \\ 0&\mbox{else}. \end{array} \right . \end{aligned}$$

(11.154)

Fig. 11.11

(Bilinear elements on a rectangular grid)  The basis functions N _i (x,y) on a rectangular grid (right side) are piecewise bilinear functions (left side), which vanish at all nodes except (x _i ,y _i ) (right side)

Generalization to a three-dimensional grid is straightforward (Fig. 11.12). We denote one of the eight cuboids containing the node (x _i ,y _i ,z _i ) as $C_{i,j_{1}\dots j_{7}}$ with $(x_{j_{1}},y_{j_{1}},z_{j_{1}})=(x_{i}+b_{x},y_{i},z_{i})\dots (x_{j_{7}},y_{j_{7}},z_{j_{7}})=(x_{i}+b_{x},y_{i}+b_{y},z_{i}+b_{z})$. The corresponding trilinear function is

$$\begin{aligned} n_{i,j_{1}\dots j_{7}} =& 1-\frac{x-x_{i}}{b_{x}}-\frac {y-y_{i}}{b_{y}}-\frac{z-z_{i}}{b_{z}} \\ &{} +\frac{(x-x_{i})}{b_{x}}\frac{(y-y_{i})}{b_{y}}+\frac {(x-x_{i})}{b_{x}}\frac{(z-z_{i})}{b_{z}}+ \frac{(z-z_{i})}{b_{z}}\frac{(y-y_{i})}{b_{y}} \\ &{} -\frac{(x-x_{i})}{b_{x}}\frac{(y-y_{i})}{b_{y}}\frac{(z-z_{i})}{b_{z}}. \end{aligned}$$

(11.155)

Fig. 11.12

(Three-dimensional rectangular grid)  The basis function N _i is trilinear on each of the eight cuboids containing the vertex i. It vanishes on all nodes except (x _i ,y _i ,z _i )

6.3 One-Dimensional Galerkin FEM

As an example we consider the one-dimensional linear differential equation (11.5)

$$\begin{aligned} \biggl(a\frac{\partial^{2}}{\partial x^{2}}+b\frac{\partial}{\partial x}+c \biggr)u(x)=f(x) \end{aligned}$$

(11.156)

in the domain 0≤x≤1 with boundary conditions

$$\begin{aligned} u(0)=u(1)=0. \end{aligned}$$

(11.157)

We use the basis functions from (11.139) on a one-dimensional grid with

$$\begin{aligned} x_{i+1}-x_{i}=h_{i} \end{aligned}$$

(11.158)

and apply the Galerkin method [88]. The boundary conditions require

$$\begin{aligned} u_{0}=u_{N-1}=0. \end{aligned}$$

(11.159)

The weighted residual is

$$\begin{aligned} 0=R_{j}=\sum_{i}u_{i}\int _{0}^{1}dx\, N_{j}(x) \biggl(a \frac{\partial^{2}}{\partial x^{2}}+b\frac{\partial}{\partial x}+c \biggr)N_{i}(x)-\int_{0}^{1}dx\, N_{j}(x)f(x). \end{aligned}$$

(11.160)

First we integrate

$$\begin{aligned} \int_{0}^{1}N_{j}(x)N_{i}(x)\, dx=\int_{x_{i-1}}^{x_{i+1}}N_{j}(x)N_{i}(x)\,dx= \left\{ \begin{array}{l@{\quad}l} \frac{h_{i}+h_{i-1}}{3}& j=i\\ \frac{h_{i}}{6}& j=i+1\\ \frac{h_{i-1}}{6}& j=i-1\\ 0&|i-j|>1. \end{array} \right. \end{aligned}$$

(11.161)

Integration of the first derivative gives

$$\begin{aligned} \int_{0}^{1}dx\, N_{j}(x)N_{i}'(x)= \left\{ \begin{array}{l@{\quad}l} 0& j=i\\ \frac{1}{2}& j=i-1\\ -\frac{1}{2}& j=i\mbox{+1}\\ 0&\mbox{else}. \end{array} \right . \end{aligned}$$

(11.162)

For the second derivative partial integration gives

$$\begin{aligned} &\int_{0}^{1}dx\, N_{j}(x)\frac{\partial^{2}}{\partial x^{2}}N_{i}(x) \\ &\quad =N_{j}(1)N_{i}'(1-\varepsilon)-N_{j}(0)N_{i}'(0+ \varepsilon)-\int_{0}^{1}dx\, N_{j}'(x)N_{i}'(x) \end{aligned}$$

(11.163)

where the first two summands are zero due to the boundary conditions. Since $N_{i}\mbox{ and }N_{i}'$ are nonzero only for x _i−1<x<x _i+1 we find

$$\begin{aligned} \int_{0}^{1}dx\, N_{j}(x)\frac{\partial^{2}}{\partial x^{2}}N_{i}(x) =& -\int_{x_{i-1}}^{x_{i+1}}dx\, N'_{j}(x) N'_{i}(x) \\ = &\left\{ \begin{array}{l@{\quad}l} \frac{1}{h_{i-1}}& j=i-1\\ -\frac{1}{h_{i}}-\frac{1}{h_{i-1}}& i=j\\ \frac{1}{h_{i}}& j=i+1\\ 0&\mbox{else}. \end{array} \right. \end{aligned}$$

(11.164)

Integration of the last term in (11.160) gives

$$\begin{aligned} \int_{0}^{1}dx\, N_{j}(x)f(x) =& \int_{x_{i-1}}^{x_{i+1}}dx\, N_{j}(x)f(x) \\ =&\int_{x_{j-1}}^{x_{j}}dx\,\frac{x-x_{j-1}}{x_{j}-x_{j-1}}f(x) \\ &{} +\int_{x_{j}}^{x_{j+1}}dx\,\frac{x_{j+1}-x}{x_{j+1}-x_{j}}f(x). \end{aligned}$$

(11.165)

Applying the trapezoidal rule¹¹ for both integrals we find

$$\begin{aligned} \int_{x_{j-1}}^{x_{j+1}}dx\, N_{j}(x)f(x)\approx f(x_{j})\frac{h_{j}+h_{j-1}}{2}. \end{aligned}$$

(11.166)

The discretized equation finally reads

$$\begin{aligned} &a \biggl\{ \frac{1}{h_{j-1}}u_{j-1}- \biggl(\frac{1}{h_{j}}+ \frac{1}{h_{j-1}} \biggr)u_{j}+\frac{1}{h_{j}}u_{j+1} \biggr\} \\ &\qquad {} +b \biggl\{ -\frac{1}{2}u_{j-1}+\frac{1}{2}u_{j+1} \biggr\} \\ &\qquad {} +c \biggl\{ \frac{h_{j-1}}{6}u_{j-1}+\frac{h_{j}+h_{j-1}}{3}u_{j}+ \frac{h_{j}}{6}u_{j+1} \biggr\} \\ &\quad =f(x_{j})\frac{h_{j}+h_{j-1}}{2} \end{aligned}$$

(11.167)

which can be written in matrix notation as

$$\begin{aligned} A\mathbf {u}=B\mathbf {f} \end{aligned}$$

(11.168)

where the matrix A is tridiagonal as a consequence of the compact support of the basis functions

$$\begin{aligned} A =&a\left ( \begin{array}{ccccc} -\frac{1}{h_{1}}-\frac{1}{h_{0}}, & \frac{1}{h_{1}}\\ & \ddots\\ & \frac{1}{h_{j-1}}, & -\frac{1}{h_{j}}-\frac{1}{h_{j-1}}, & \frac {1}{h_{j}}\\ & & & \ddots\\ & & & \frac{1}{h_{N-3}}, & -\frac{1}{h_{N-2}}-\frac{1}{h_{N-3}} \end{array} \right ) \\ &{} +b\left ( \begin{array}{ccccc} 0, & \frac{1}{2}\\ & \ddots\\ & -\frac{1}{2}, & 0, & \frac{1}{2}\\ & & & \ddots\\ & & & -\frac{1}{2}, & 0 \end{array} \right ) \\ &{} +c\left ( \begin{array}{ccccc} \frac{(h_{1}+h_{0})}{3}, & \frac{h_{1}}{6}\\ & \ddots\\ & \frac{h_{j-1}}{6}, & \frac{(h_{j}+h_{j-1})}{3}, & \frac{h_{j}}{6}\\ & & & \ddots\\ & & & \frac{h_{N-3}}{6}, & \frac{(h_{N-2}+h_{N-3})}{3} \end{array} \right ) \\ B =&\left ( \begin{array}{ccccc} \frac{h_{0}+h_{1}}{2}\\ & \ddots\\ & & \frac{h_{j-1}+h_{j}}{2}\\ & & & \ddots\\ & & & & \frac{h_{N-2}+h_{N-3}}{2} \end{array} \right ). \end{aligned}$$

For equally spaced nodes h _i =h _i−1=h and after division by h (11.167) reduces to a system of equations where the derivatives are replaced by finite differences (11.20)

$$\begin{aligned} &a \biggl\{ \frac{1}{h^{2}}u_{j-1}-\frac{2}{h^{2}}u_{j}+ \frac{1}{h^{2}}u_{j+1} \biggr\} \\ &\qquad {} +b \biggl\{ -\frac{1}{2h}u_{j-1}+\frac{1}{2h}u_{j+1} \biggr\} \\ &\qquad {} +c \biggl\{ \frac{1}{6}u_{j-1}+\frac{2}{3}u_{j}+ \frac{1}{6}u_{j+1} \biggr\} \\ &\quad =f(x_{j}) \end{aligned}$$

(11.169)

and the function u is replaced by a certain average

$$\begin{aligned} \frac{1}{6}u_{j-1}+\frac{2}{3}u_{j}+ \frac{1}{6}u_{j+1}=u_{j}+\frac{1}{6} (u_{j-1}-2u_{j}+u_{j+1} ). \end{aligned}$$

(11.170)

The corresponding matrix in (11.169) is the so called mass matrix. Within the framework of the finite differences method the last expression equals

$$\begin{aligned} u_{j}+\frac{1}{6} (u_{j-1}-2u_{j}+u_{j+1} )=u_{j}+\frac{h^{2}}{6} \biggl(\frac{d^{2}u}{dx^{2}} \biggr)_{j}+O\bigl(h^{4}\bigr) \end{aligned}$$

(11.171)

hence replacing it by u _j (this is called mass lumping) introduces an error of the order O(h ²).

7 Boundary Element Method

The boundary element method (BEM) [18, 276] is a method for linear partial differential equations which can be brought into boundary integral form¹² like Laplace’s equation (Chap. 17)¹³

$$\begin{aligned} -\Delta\varPhi(\mathbf{r})=0 \end{aligned}$$

(11.172)

for which the fundamental solution

$$\begin{aligned} \Delta G\bigl(\mathbf {r},\mathbf {r}'\bigr)=-\delta\bigl(\mathbf {r}- \mathbf {r}'\bigr) \end{aligned}$$

is given by

$$\begin{aligned} G\bigl(\mathbf {r}-\mathbf {r}'\bigr)=\frac{1}{4\pi|\mathbf {r}-\mathbf {r}'|} \quad \mbox{in three dimensions}& \end{aligned}$$

(11.173)

$$\begin{aligned} G\bigl(\mathbf {r}-\mathbf {r}'\bigr)=\frac{1}{2\pi}\ln \frac{1}{|\mathbf {r}-\mathbf {r}'|}\quad\mbox{in two dimensions}.& \end{aligned}$$

(11.174)

We apply Gauss’s theorem to the expression [277]

$$\begin{aligned} \begin{aligned}[b] &\operatorname{div} \bigl[G\bigl(\mathbf{r}-\mathbf{r}'\bigr)\operatorname{grad} \bigl(\varPhi(\mathbf{r})\bigr)-\varPhi(\mathbf{r})\operatorname{grad}\bigl (G\bigl( \mathbf{r}-\mathbf{r}'\bigr)\bigr) \bigr] \\ & \quad =-\varPhi(\mathbf{r})\Delta\bigl(G\bigl(\mathbf{r}-\mathbf{r}' \bigr)\bigr). \end{aligned} \end{aligned}$$

(11.175)

Integration over a volume V gives

$$\begin{aligned} &\oint_{\partial V}dA \biggl(G\bigl(\mathbf{r}-\mathbf{r}'\bigr) \frac{\partial}{\partial n}\bigl(\varPhi(\mathbf{r})\bigr)-\varPhi (\mathbf{r}) \frac{\partial}{\partial n}\bigl(G\bigl(\mathbf{r}-\mathbf{r}'\bigr )\bigr) \biggr) \\ &\quad =-\int_{V}dV\, \bigl(\varPhi(\mathbf{r})\Delta\bigl(G\bigl( \mathbf{r}-\mathbf{r}'\bigr)\bigr)\bigr)=\varPhi\bigl( \mathbf {r}'\bigr). \end{aligned}$$

(11.176)

This integral equation determines the potential self-consistently by its value and normal derivative on the surface of the cavity. It can be solved numerically by dividing the surface into a finite number of boundary elements. The resulting system of linear equations often has smaller dimension than corresponding finite element approaches. However, the coefficient matrix is in general full and not necessarily symmetric.