Grid-free collocation

The grid-free collocation is a numerical method for solving partial differential equations . It is a special variant of approximations by radial basis functions . In contrast to other methods, such as the finite element method , there is no need for a division into elements or a structured grid.

Overview

The grid-free collocation method is used, for example, to solve elliptical partial differential equations . Only linear systems of equations (LGS) have to be solved, numerical integration and the creation of grids are not necessary (see also comparison with other methods ).

The solution to the problem is approximated by radial basis functions, which only depend on the distances between points. The implementation of the method is therefore largely independent of the dimension of the problem.

Procedure

In the grid-free collocation method, the exact solution is approximated by a linear combination of shape functions (or shape functions to which the differential operator was applied). ${\displaystyle s(x,\gamma )}$

To produce the formulation functions a set of will approach centers in the radial basis function used: , this is a parameter. Depending on the procedure, the approach centers are selected in the area (with a border) or outside the area. ${\displaystyle \{\varphi _{j}(x,\gamma )\}_{j=1}^{N'}}$ ${\displaystyle X_{A}=\{x_{j}'\}_{j=1}^{N'}\subset \mathbb {R} ^{d}}$ ${\displaystyle \varphi (x,\gamma )}$ ${\displaystyle \varphi _{j}(x,\gamma ):=\varphi (\|x-x_{j}'\|,\gamma )}$ ${\displaystyle \gamma \in \mathbb {R} }$

To determine the coefficients, one chooses a set of collocation centers that do not have to coincide with the approach centers. ${\displaystyle X_{K}=\{x_{i}\}_{i=1}^{N}\subset {\overline {\Omega }}}$

Let be a domain with Lipschitz boundary , an elliptic differential operator , a function in and a function on . ${\displaystyle \Omega \subset \mathbb {R} ^{d}}$ ${\displaystyle \partial \Omega }$ ${\displaystyle L}$ ${\displaystyle f\in L^{2}(\Omega )\cap C^{0}(\Omega )}$ ${\displaystyle \Omega }$ ${\displaystyle g_{D}}$ ${\displaystyle \partial \Omega }$

The following Dirchlet problem is given :

${\displaystyle {\begin{cases}u(x)=g_{D}(x)\quad x\in \partial \Omega \\Lu(x)=f(x)\quad x\in \Omega \end{cases}}}$

Direct collocation

To the solution by direct collocation are approach centers and collocation centers from selected. The approach is: . ${\displaystyle N}$ ${\displaystyle X_{A}\subset \mathbb {R} ^{d}}$ ${\displaystyle X_{K}}$ ${\displaystyle \Omega \cup \partial \Omega }$ ${\displaystyle \textstyle s(x,\gamma ):=\sum _{j=1}^{N}\lambda _{j}\varphi _{j}(x,\gamma )}$

There is an equation for each collocation center , depending on the position of the point. Be for on and for in : ${\displaystyle x_{i}\in X_{K}}$ ${\displaystyle x_{i}}$ ${\displaystyle i=1,\ldots ,N_{B}}$ ${\displaystyle \partial \Omega }$ ${\displaystyle i=N_{B}+1,\ldots ,N}$ ${\displaystyle \Omega }$

${\displaystyle {\begin{cases}s(x_{i},\gamma )=\sum _{j=1}^{N}\lambda _{j}\varphi _{j}(x_{i},\gamma )=g_{D}(x_{i})\quad i=1,\ldots ,N_{B}\\Ls(x_{i},\gamma )=\sum _{j=1}^{N}\lambda _{j}L\varphi _{j}(x_{i},\gamma )=f(x_{i})\quad i=N_{B}+1,\ldots ,N\end{cases}}}$

This leads to the LGS :

${\displaystyle \left[{\frac {\varphi _{j}(x_{i})}{L\varphi _{j}(x_{i})}}\right]\cdot \lambda =\left[{\frac {g_{D}(x_{i})}{f(x_{i})}}\right]\qquad {\begin{cases}i=1,\ldots ,N_{B}\\i=N_{B}+1,\ldots ,N\end{cases}}\lambda =(\lambda _{1},\ldots ,\lambda _{N})\quad j=1,\ldots ,N}$

The coefficients we are looking for are obtained as a solution to this system. The choice of Neumann boundary conditions is also possible (also in combination with Dirichlet boundary condition), one only has to consider the position of the collocation centers. The disadvantage of this variant is that the system matrix is ​​often quite singular and not symmetrical. ${\displaystyle \lambda _{j}}$

Symmetrical collocation

Given a Dirichlet problem as above. Choose collocation centers , again for on and for in . ${\displaystyle X_{K}=\{x_{i}\}_{i=1}^{N}}$ ${\displaystyle x_{i}}$ ${\displaystyle i=1,\ldots ,N_{B}}$ ${\displaystyle \partial \Omega }$ ${\displaystyle i=N_{B}+1,\ldots ,N}$ ${\displaystyle \Omega }$

The approach function is: ${\displaystyle s(x,\gamma ):=\sum _{j=1}^{N_{B}}\lambda _{j}\varphi _{j}(x,\gamma )+\sum _{k=N_{B}+1}^{N}\lambda _{k}L\varphi _{k}(x,\gamma )}$

The following equation results for each collocation center:

${\displaystyle {\begin{cases}s(x_{i},\gamma )=\sum _{j=1}^{N_{B}}\lambda _{j}\varphi _{j}(x_{i},\gamma )+\sum _{k=N_{B}+1}^{N}\lambda _{k}L\varphi _{k}(x_{i},\gamma )=g_{D}(x_{i})\quad i=1,\ldots ,N_{B}\\Ls(x_{i},\gamma )=\sum _{j=1}^{N_{B}}\lambda _{j}L\varphi _{j}(x_{i},\gamma )+\sum _{k=N_{B}+1}^{N}\lambda _{k}L^{2}\varphi _{k}(x_{i},\gamma )=f(x_{i})\quad i=N_{B}+1,\ldots ,N\end{cases}}}$

As with direct collocation, an LGS results with the coefficients as solutions: ${\displaystyle \lambda _{j}}$

${\displaystyle \left[{\frac {\varphi _{j}(x_{i})\;|\;L\varphi _{k}(x_{i})}{L\varphi _{j}(x_{i})\;|\;L^{2}\varphi _{k}(x_{i})}}\right]\cdot \lambda =\left[{\frac {g_{D}(x_{i})}{f(x_{i})}}\right]\qquad {\begin{cases}i=1,\ldots ,N_{B}\\i=N_{B}+1,\ldots ,N\end{cases}}j=1,\ldots ,N_{B}\quad k=N_{B}+1,\ldots ,N}$

With this variant, a symmetrical system matrix is ​​obtained , which ensures that the LGS is not singular.

Direct collocation with PDGL on the margin

Since the approximation errors at the edge often become large with such methods, the differential operator at the edge is taken into account in this variant of grid-free collocation. The number of batch functions exceeds that of the collocation centers. Since this increases the number of equations , additional approach centers outside of are added. The approach function is: ${\displaystyle N_{B}}$ ${\displaystyle \{x_{j}\}_{j=N+1}^{N+N_{B}}}$ ${\displaystyle \Omega \cup \partial \Omega }$ ${\displaystyle s(x_{i},\gamma )=\sum _{j=1}^{N+N_{B}}\lambda _{j}\varphi _{j}(x,\gamma )}$

In contrast to direct collocation, there are two equations for collocation centers on the edge (still one inside):

${\displaystyle {\begin{cases}s(x,\gamma )=\sum _{j=1}^{N+N_{B}}\lambda _{j}\varphi _{j}(x_{i},\gamma )=g_{D}(x_{i})\quad i=1,\ldots ,N_{B}\\Ls(x_{i},\gamma )=\sum _{j=1}^{N+N_{B}}\lambda _{j}L\varphi _{j}(x_{i},\gamma )=f(x_{i})\quad i=1,\ldots ,N\end{cases}}}$

Again you get the solutions from: ${\displaystyle \lambda _{j}}$

${\displaystyle \left[{\frac {\varphi _{j}(x_{i})}{L\varphi _{j}(x_{i})}}\right]\cdot \lambda =\left[{\frac {g_{D}(x_{i})}{f(x_{i})}}\right]\qquad {\begin{cases}i=1,\ldots ,N_{B}\\i=N_{B}+1,\ldots ,N+N_{B}\end{cases}}\quad j=1,\ldots ,N+N_{B}}$

Example: direct collocation

Be and like above and . In order to solve the Dirichlet problem by means of direct collocation , the collocation centers , where and , and approach centers are chosen. The following LGS is obtained with the basic function : ${\displaystyle \Omega ,g_{D}}$ ${\displaystyle f}$ ${\displaystyle L=\Delta }$ ${\displaystyle X_{K}=\{x_{1},x_{2},x_{3}\}}$ ${\displaystyle x_{1}\in \partial \Omega }$ ${\displaystyle x_{2},x_{3}\in \Omega }$ ${\displaystyle X_{A}=\{x_{1}',x_{2}',x_{3}'\}\subset \Omega \cup \partial \Omega }$ ${\displaystyle \varphi (x,\gamma )=\exp(-\gamma \|x\|^{2})}$

${\displaystyle {\begin{bmatrix}e^{-\gamma \|x_{1}-x_{1}'\|^{2}}&e^{-\gamma \|x_{1}-x_{2}'\|^{2}}&e^{-\gamma \|x_{1}-x_{3}'\|^{2}}\\\Delta e^{-\gamma \|x_{2}-x_{1}'\|^{2}}&\Delta e^{-\gamma \|x_{2}-x'_{2}\|^{2}}&\Delta e^{-\gamma \|x_{2}-x_{3}'\|^{2}}\\\Delta e^{-\gamma \|x_{3}-x_{1}'\|^{2}}&\Delta e^{-\gamma \|x_{3}-x_{2}'\|^{2}}&\Delta e^{-\gamma \|x_{3}-x_{3}'\|^{2}}\\\end{bmatrix}}\cdot {\begin{bmatrix}\lambda _{1}\\\lambda _{2}\\\lambda _{3}\end{bmatrix}}={\begin{bmatrix}g_{D}(x_{1})\\f(x_{2})\\f(x_{3})\end{bmatrix}}}$

The solution is: ${\displaystyle s(x)=\lambda _{1}e^{-\gamma \|x-x_{1}'\|^{2}}+\lambda _{2}e^{-\gamma \|x-x_{2}'\|^{2}}+\lambda _{3}e^{-\gamma \|x-x_{3}'\|^{2}}}$

Comparison with other methods

Since no grid has to be set up with this method, computing time can be saved. Due to the free choice of the centers, a better adaptation to the geometry of the problem can be achieved. On the other hand, an increase in the number of centers does not necessarily have to lead to an improvement in the result.

To improve the result i. A. Adaptive method used to choose centers. So although the method does not require a grid, the choice of centers is still of crucial importance.

In addition, depending on the procedure and the choice of centers, the condition of the system matrix can be very poor.

swell

• Elisabeth Larsson, Bengt Fornberg: A Numerical Study of some Radial Basis Function based Solution Methods for Elliptic PDEs . In: Computers & Mathematics with Applications , Vol. 46 (2003), ISSN  0097-4943 ( PDF ).
• Holger Wendland: Scattered Data Approximation (Monographs on applied and computational mathematics; Vol. 17). Cambridge University Press, Cambridge 2005, ISBN 0-521-84335-9 .