Robert Schaback

Davoud Mirzaei, Robert Schaback

The Meshless Local Petrov{Galerkin (MLPG) method is one of the popular meshless methods that has been used very successfully to solve several types of boundary value problems since the late nineties. In this paper, using a generalized moving least squares (GMLS) approximation, a new direct MLPG technique, called DMLPG, is presented. Following the principle of meshless methods to express everything "entirely in terms of nodes", the generalized MLS recovers test functionals directly from values at nodes, without any detour via shape functions. This leads to a cheaper and even more accurate scheme. In particular, the complete absence of shape functions allows numerical integrations in the weak forms of the problem to be done over low{degree polynomials instead of complicated shape functions. Hence, the standard MLS shape function subroutines are not called at all. Numerical examples illustrate the superiority of the new technique over the classical MLPG. On the theoretical side, this paper discusses stability and convergence for the new discretizations that replace those of the standard MLPG. However, it does not treat stability, convergence, or error estimation for the MLPG as a whole. This should be taken from the literature on MLPG.

Gabriele Santin, Robert Schaback

Kernel-based methods in Numerical Analysis have the advantage of yielding optimal recovery processes in the "native" Hilbert space $\calh$ in which they are reproducing. Continuous kernels on compact domains have an expansion into eigenfunctions that are both $L_2$-orthonormal and orthogonal in $\calh$ (Mercer expansion). This paper examines the corresponding eigenspaces and proves that they have optimality properties among all other subspaces of $\calh$. These results have strong connections to $n$-widths in Approximation Theory, and they establish that errors of optimal approximations are closely related to the decay of the eigenvalues. Though the eigenspaces and eigenvalues are not readily available, they can be well approximated using the standard $n$-dimensional subspaces spanned by translates of the kernel with respect to $n$ nodes or centers. We give error bounds for the numerical approximation of the eigensystem via such subspaces. A series of examples shows that our numerical technique via a greedy point selection strategy allows to calculate the eigensystems with good accuracy.

Ka-Chun Cheung, Leevan Ling, Robert Schaback

The strong-form asymmetric kernel-based collocation method, commonly referred to as the Kansa method, is easy to implement and hence is widely used for solving engineering problems and partial differential equations despite the lack of theoretical support. The simple least-squares (LS) formulation, on the other hand, makes the study of its solvability and convergence rather nontrivial. In this paper, we focus on general second order linear elliptic differential equations in $Ω\subset R^d$ under Dirichlet boundary conditions. With kernels that reproduce $H^m(Ω)$ and some smoothness assumptions on the solution, we provide denseness conditions for a constrained least-squares method and a class of weighted least-squares algorithms to be convergent. Theoretically, we identify some $H^2(Ω)$ convergent LS formulations that have an optimal error behavior like $h^{m-2}$. We also demonstrate the effects of various collocation settings on the respective convergence rates, as well as how these formulations perform with high order kernels and when coupled with the stable evaluation technique for the Gaussian kernel.

Oleg Davydov, Robert Schaback

This paper proves that the approximation of pointwise derivatives of order $s$ of functions in Sobolev space $W_2^m(\R^d)$ by linear combinations of function values cannot have a convergence rate better than $m-s-d/2$, no matter how many nodes are used for approximation and where they are placed. These convergence rates are attained by {\em scalable} approximations that are exact on polynomials of order at least $\lfloor m-d/2\rfloor +1$, proving that the rates are optimal for given $m,\,s,$ and $d$. And, for a fixed node set $X\subset\R^d$, the convergence rate in any Sobolev space $W_2^m(Ω)$ cannot be better than $q-s$ where $q$ is the maximal possible order of polynomial exactness of approximations based on $X$, no matter how large $m$ is. In particular,scalable stencil constructions via polyharmonic kernels are shown to realize the optimal convergence rates, and good approximations of their error in Sobolev space can be calculated via their error in Beppo-Levi spaces. This allows to construct near-optimal stencils in Sobolev spaces stably and efficiently, for use in meshless methods to solve partial differential equations via generalized finite differences (RBF-FD). Numerical examples are included for illustration.

Oleg Davydov, Robert Schaback

We investigate numerical differentiation formulas on irregular centers in two or more variables that are exact for polynomials of a given order and minimize an absolute seminorm of the weight vector. Error bounds are given in terms of a growth function that carries the information about the geometry of the centers. Specific forms of weighted $\ell_1$ and weighted least squares minimization are proposed that produce numerical differentiation formulas with particularly good performance in numerical experiments.

Robert Schaback

It is well-known that univariate cubic spline interpolation, if carried out on point sets with fill distance $h$, converges only like ${\cal O}(h^2)$ in $L_2[a,b]$ for functions in $W_2^2[a,b]$ if no additional assumptions are made. But superconvergence up to order $h^4$ occurs if more smoothness is assumed and if certain additional boundary conditions are satisfied. This phenomenon was generalized in 1999 to multivariate interpolation in Reproducing Kernel Hilbert Spaces on domains $Ω\subset R^d$ for continuous positive definite Fourier-transformable shift-invariant kernels on $R^d$. But the sufficient condition for superconvergence given in 1999 still needs further analysis, because the interplay between smoothness and boundary conditions is not clear at all. Furthermore, if only additional smoothness is assumed, superconvergence is numerically observed in the interior of the domain, but without explanation, so far. This paper first generalizes the "improved error bounds" of 1999 by an abstract theory that includes the Aubin-Nitsche trick and the known superconvergence results for univariate polynomial splines. Then the paper analyzes what is behind the sufficient conditions for superconvergence. They split into conditions on smoothness and localization, and these are investigated independently. If sufficient smoothness is present, but no additional localization conditions are assumed, it is proven that superconvergence always occurs in the interior of the domain. If smoothness and localization interact in the kernel-based case on $R^d$, weak and strong boundary conditions in terms of pseudodifferential operators occur. A special section on Mercer expansions is added, because Mercer eigenfunctions always satisfy the sufficient conditions for superconvergence. Numerical examples illustrate the theoretical findings.

Robert Schaback

There are many application papers that solve elliptic boundary value problems by meshless methods, and they use various forms of generalized stiffness matrices that approximate derivatives of functions from values at scattered nodes $x_1,\ldots,x_M\in Ω\subset\R^d$. If $u^*$ is the true solution in some Sobolev space $S$ allowing enough smoothness for the problem in question, and if the calculated approximate values at the nodes are denoted by $\tilde u_1,\ldots,\tilde u_M$, the canonical form of error bounds is $$ \max_{1\leq j\leq M}|u^*(x_j)-\tilde u_j|\leq ε\|u^*\|_S $$ where $ε$ depends crucially on the problem and the discretization, but not on the solution. This contribution shows how to calculate such $ε$ {\em numerically and explicitly}, for any sort of discretization of strong problems via nodal values, may the discretization use Moving Least Squares, unsymmetric or symmetric RBF collocation, or localized RBF or polynomial stencils. This allows users to compare different discretizations with respect to error bounds of the above form, without knowing exact solutions, and admitting all possible ways to set up generalized stiffness matrices. The error analysis is proven to be sharp under mild additional assumptions. As a byproduct, it allows to construct worst cases that push discretizations to their limits. All of this is illustrated by numerical examples.

Klaus Böhmer, Robert Schaback

This paper solves the two-dimensional Dirichlet problem for the Monge-Ampère equation by a strong meshless collocation technique that uses a polynomial trial space and collocation in the domain and on the boundary. Convergence rates may be up to exponential, depending on the smoothness of the true solution, and this is demonstrated numerically and proven theoretically, applying a sufficiently fine collocation discretization. A much more thorough investigation of meshless methods for fully nonlinear problems is in preparation.

Maryam Mohammadi, Robert Schaback

The paper provides the fractional integrals and derivatives of the Rie\-mann-Liouville and Caputo type for the five kinds of radial basis functions (RBFs), including the powers, Gaussian, multiquadric, Matern and thin-plate splines, in one dimension. It allows to use high order numerical methods for solving fractional differential equations. The results are tested by solving two fractional differential equations. The first one is a fractional ODE which is solved by the RBF collocation method and the second one is a fractional PDE which is solved by the method of lines based on the spatial trial spaces spanned by the Lagrange basis associated to the RBFs.

Klaus Böhmer, Robert Schaback

We generalize our earlier results concerning meshfree collocation methods for semilinear elliptic second order problems to the quasilinear case. The stability question, however, is treated differently, namely by extending a paper on uniformly stable discretizations of well-posd linear problems to the nonlinear case. These two ingredients allow a proof that all well-posed quasilinear elliptic second-order problems can be discretized in a uniformly stable way by using sufficient oversampling, and then the error of the numerical solution behaves like the error obtainable by direct approximation of the true solution by functions from the chosen trial space, up to a factor induced by being forced to use a Hölder-type theory for the nonlinear PDE. We apply our general technique to prove convergence of meshfree methods for quasilinear elliptic equations with Dirichlet and non-Dirichlet boundary conditions. This is achieved for bifurcation and center manifolds of elliptic partial differential equations and their numerical methods as well.

Robert Schaback

Motivated by the successful use of greedy algorithms for Reduced Basis Methods, a greedy method is proposed that selects N input data in an asymptotically optimal way to solve well-posed operator equations using these N data. The operator equations are defined as infinitely many equations given via a compact set of functionals in the dual of an underlying Hilbert space, and then the greedy algorithm, defined directly in the dual Hilbert space, selects N functionals step by step. When N functionals are selected, the operator equation is numerically solved by projection onto the span of the Riesz representers of the functionals. Orthonormalizing these yields useful Reduced Basis functions. By recent results on greedy methods in Hilbert spaces, the convergence rate is asymptotically given by Kolmogoroff N-widths and therefore optimal in that sense. However, these N-widths seem to be unknown in PDE applications. Numerical experiments show that for solving elliptic second-order Dirichlet problems, the greedy method of this paper behaves like the known P-greedy method for interpolation, applied to second derivatives. Since the latter technique is known to realize Kolmogoroff N-widths for interpolation, it is hypothesized that the Kolmogoroff N-widths for solving second-order PDEs behave like the Kolmogoroff N-widths for second derivatives, but this is an open theoretical problem.

Robert Schaback

When an Approximation Theorist looks at well-posed PDE problems or operator equations, and standard solution algorithms like Finite Elements, Rayleigh-Ritz or Trefftz techniques, methods of fundamental or particular solutions and their combinations, they boil down to approximation problems and stability issues. These two can be handled by Approximation Theory, and this paper shows how, with special applications to the aforementioned algorithms. The intention is that the Approximation Theorists viewpoint is helpful for readers who are somewhat away from that subject.

Robert Schaback

The paper starts out with a computational technique that allows to compare all linear methods for PDE solving that use the same input data. This is done by writing them as linear recovery formulas for solution values as linear combinations of the input data. Calculating the norm of these reproduction formulas on a fixed Sobolev space will then serve as a quality criterion that allows a fair comparison of all linear methods with the same inputs, including finite-element, finite-difference and meshless local Petrov-Galerkin techniques. A number of illustrative examples will be provided. As a byproduct, it turns out that a unique error--optimal method exists. It necessarily outperforms any other competing technique using the same data, e.g. those just mentioned, and it is necessarily meshless, if solutions are written "entirely in terms of nodes" (Belytschko et. al. 1996). On closer inspection, it turns out that it coincides with {\em symmetric meshless collocation} carried out with the kernel of the Hilbert space used for error evaluation, e.g. with the kernel of the Sobolev space used. This technique is around since at least 1998, but its optimality properties went unnoticed, so far.

Licia Lenarduzzi, Robert Schaback

One of the basic principles of Approximation Theory is that the quality of approximations increase with the smoothness of the function to be approximated. Functions that are smooth in certain subdomains will have good approximations in those subdomains, and these {\em sub-approximations} can possibly be calculated efficiently in parallel, as long as the subdomains do not overlap. This paper proposes a class of algorithms that first calculate sub-approximations on non-overlapping subdomains, then extend the subdomains as much as possible and finally produce a global solution on the given domain by letting the subdomains fill the whole domain. Consequently, there will be no Gibbs phenomenon along the boundaries of the subdomains. Throughout, the algorithm works for fixed scattered input data of the function itself, not on spectral data, and it does not resample.

Davoud Mirzaei, Robert Schaback

As an improvement of the Meshless Local Petrov-Galerkin (MLPG), the Direct Meshless Local Petrov-Galerkin (DMLPG) method is applied here to the numerical solution of transient heat conduction problem. The new technique is based on direct recoveries of test functionals (local weak forms) from values at nodes without any detour via classical moving least squares (MLS) shape functions. This leads to an absolutely cheaper scheme where the numerical integrations will be done over low-degree polynomials rather than complicated MLS shape functions. This eliminates the main disadvantage of MLS based methods in comparison with finite element methods (FEM), namely the costs of numerical integration.