drnxxx

Z. Liu and Q. Xu

# Convergence of one-level and multilevel unsymmetric collocation for second
order elliptic boundary value problems

Zhiyong Liu, and Qiuyan Xu
School of Mathematics and statistics  Email<EMAIL_ADDRESS>author. Email<EMAIL_ADDRESS>
Ningxia University  Yinchuan 750021  Ningxia  China

###### Abstract

The paper proves convergence of one-level and multilevel unsymmetric
collocation for second order elliptic boundary value problems on the bounded
domains. By using Schaback’s linear discretization theory, $L^{2}$ errors are
obtained based on the kernel-based trial spaces generated by the compactly
supported radial basis functions. For the one-level unsymmetric collocation
case, we obtain convergence when the testing discretization is finer than the
trial discretization. The convergence rates depend on the regularity of the
solution, the smoothness of the computing domain, and the approximation of
scaled kernel-based spaces. The multilevel process is implemented by employing
successive refinement scattered data sets and scaled compactly supported
radial basis functions with varying support radii. Convergence of multilevel
collocation is further proved based on the theoretical results of one-level
unsymmetric collocation. In addition to having the same dependencies as the
one-level collocation, the convergence rates of multilevel unsymmetric
collocation especially depends on the increasing rules of scattered data and
the selection of scaling parameters. elliptic boundary value problems; radial
basis functions; one-level collocation; multilevel collocation; convergence
rates.

##  1 Introduction

Since the first kernel-based collocation method was introduced by Kansa (see
Kansa, 1986), radial basis functions have been successfully applied to solving
various partial differential equations numerically. But unfortunately, we are
obtaining highly accurate solutions from severely ill-conditioned linear
systems and high computational cost when using radial basis functions
collocation methods with global supports. To a certain extent, the utilization
of compactly supported radial basis functions (such as well-known Wendland’s
functions (see Wendland, 1995) and Wu’s functions (see Wu, 1995)) improves the
condition of collocation matrices. Then a multilevel interpolation algorithm
for the approximation of functions is developed, right after the popularity of
compactly supported radial basis functions (see Floater& Iske, 1996). With a
multilevel algorithm, the condition number of the discrete matrix can be
relatively small, and computation can be performed in $O(N)$ operations. In
this algorithm, the interpolation problem is solved first on the coarsest
level by one of the compactly supported radial basis functions with a larger
support (usually scaling the size of the support with the fill distance). Then
the residual can be formed, and be computed on the next finer level by the
same compactly supported radial basis function but with a smaller support.
This process can be repeated and stopped on the finest level. And the final
approximation is the sum of all of interpolants. The sophisticated proofs of
convergence of multilevel interpolation algorithm were given for the first
time on the sphere (see Le Gia _et al._ , 2010), and on bounded domains (see
Wendland, 2010). In fact, all one-level collocation methods can be used for
constructing multilevel collocation algorithms, such as multilevel symmetric
collocation (see Farrell & Wendland, 2013; Fasshauer, 1999), multilevel
Galerkin collocation (see Chernih & Le Gia, 2014; Wendland, 2018), and
multilevel unsymmetric collocation (in this paper). However, the situation
becomes more complicated when using multilevel algorithm to solve partial
differential equations numerically.

One-level symmetric collocation method was developed by Fasshauer (1997),
based on the generalized Hermite interpolation method (see Wu, 1992). The
collocation matrices produced by symmetric method are symmetric and positive
definite when the trial data (centers) and the testing data (collocation
points) are the same. Its convergence has been proved in Franke & Schaback
(1998) for generate radial basis functions trial spaces and in Farrell &
Wendland (2013) for some scaled kernel-based spaces. Fasshauer (1999) suggests
using multilevel symmetric collocation to solve partial differential
equations, and carries out a large number of numerical observations.
Convergence of the multilevel symmetric collocation for elliptic boundary
value problems was given in Farrell & Wendland (2013). Different from the
multilevel interpolation algorithm, the scaling parameter is no longer
proportional to the fill distance in the multilevel symmetric collocation
method. This leads to a non-stationary multilevel approximation space. In
fact, the other two multilevel collocation methods also lead to the same
phenomenon. The multilevel symmetric collocation has been used for other
scientific and engineering calculations successfully (see Chen _et al._ ,
2002; Chernih & Le Gia, 2012, 2013; Le Gia _et al._ , 2012; Farrell _et al._ ,
2017; Townsend & Wendland, 2013; Wendland, 2017).

One-level Galerkin collocation method was proposed by Wendland (1998). The
method is constructed by combining Ritz-Galerkin approximation with radial
basis functions. Wendland (1998) proves that the Galerkin collocation method
leads to the same error bounds as the classical finite element methods under
$W^{1,2}(\Omega)$ norm. By using the Aubin-Nische technology, Wendland (2018)
gives $L^{2}(\Omega)$ error of one-level Galerkin collocation method. The idea
of combing a multilevel interpolation algorithm with the Galerkin
approximation was suggested in Wendland (1998) first. Then convergence of
multilevel Galerkin collocation method was given in Chernih & Le Gia (2014)
and further refined in Wendland (2018).

One-level unsymmetric collocation method was proposed by Kansa (1986), which
has a little earlier history than symmetric collocation and Galerkin
collocation methods. Compared with the other two collocation methods, one-
level unsymmetric collocation method is more flexible and concise. It avoids
constructing the trial space based on complicated differential operator or
implementing the numerical integration. However, Hon & Schaback (2001) shows
that this method may be failure for some scattered data sites with the special
distribution. Schaback (2007, 2010) prove that one-level unsymmetric
collocation method is convergent once the testing discretization has been
selected to have more degrees of freedom than the trial discretization. By
using Schaback’s linear discretization theory, we will prove the $L^{2}$ error
of one-level unsymmetric collocation method. Further, we will construct
multilevel unsymmetric collocation method and prove its convergence in the
paper.

The paper is organized as follows. Section 2 is devoted to some notation and
the second order elliptic partial differential equation model. Section 3 is an
introduction of kernel-based trial spaces generated by compactly supported
radial basis functions. A Bernstein inequality for functions from scaled
kernel-based trial spaces will be given in this section. Section 4 and Section
5 are convergence of one-level unsymmetric collocation method and multilevel
unsymmetric collocation method. Section 6 closes the paper with a concise
conclusion.

##  2  Preliminaries

We assume $\Omega\subseteq\mathbb{R}^{d}$ is a bounded domain. We will provide
the $L^{2}(\Omega)$ convergence analysis of one-level and multilevel
unsymmetric collocation for elliptic boundary value problems in the paper. So
we start by introducing some notation about integer order and fractional order
Sobolev spaces.

###  2.1 Sobolev norms

With a nonnegative integer $k$ and $1\leq p<\infty$, Sobolev space
$W^{k,p}(\Omega)$ contains all functions which have weak differentiability
order $k$ and integrability power $p$. $W^{k,p}(\Omega)$ has been assembled
with the (semi-) norms

$|u|_{W^{k,p}(\Omega)}=(\sum_{|\alpha|=k}\|D^{\alpha}u\|_{L^{p}(\Omega)}^{p})^{1/p},\quad\|u\|_{W^{k,p}(\Omega)}=(\sum_{|\alpha|\leq
k}\|D^{\alpha}u\|_{L^{p}(\Omega)}^{p})^{1/p}.$

When $p=\infty$, the (semi-) norms are defined as

$|u|_{W^{k,\infty}(\Omega)}=\sup_{|\alpha|=k}\|D^{\alpha}u\|_{L^{\infty}(\Omega)},\quad\|u\|_{W^{k,\infty}(\Omega)}=\sup_{|\alpha|\leq
k}\|D^{\alpha}u\|_{L^{\infty}(\Omega)}.$

When $p=2$ and noninteger values $0<\sigma<\infty$, the fractional order
Sobolev space $W^{\sigma,2}(\mathbb{R}^{d})$ is characterized by Fourier
transform

$\widehat{u}(\bm{\omega})=(2\pi)^{-d/2}\int_{\mathbb{R}^{d}}u(\textbf{x})e^{-i\textbf{x}^{T}\bm{\omega}}d\textbf{x}.$
(1)

At this time the norm of $W^{\sigma,2}(\mathbb{R}^{d})$ is given by

$\|u\|_{W^{\sigma,2}(\mathbb{R}^{d})}^{2}=\int_{\mathbb{R}^{d}}|\widehat{u}(\bm{\omega})|^{2}(1+\|\bm{\omega}\|_{2}^{2})^{-\sigma}d\bm{\omega}.$
(2)

$W^{\sigma,2}(\Omega)$ is a subspace of $W^{\sigma,2}(\mathbb{R}^{d})$, which
can be simply defined by

$W^{\sigma,2}(\Omega)=\\{u|_{\Omega}:u\in W^{\sigma,2}(\mathbb{R}^{d})\\}.$

We always assume $\Omega$ has a $C^{k,s}-$boundary with $s\in[0,1)$, thus we
can define the Sobolev norm on $\partial\Omega$ by a number of
$C^{k,s}-$diffeomorphisms

$\psi_{j}:B\rightarrow V_{j},\quad 1\leq j\leq K,$

where $B=B(\textbf{0},1)$ is the unit ball in $\mathbb{R}^{d-1}$ and
$V_{j}\subseteq\mathbb{R}^{d}$ are open sets such that
$\partial\Omega=\bigcup_{j=1}^{K}V_{j}$. Hence the Sobolev norm on the
boundary can be defined by

$\|u\|_{W^{\sigma,p}(\partial\Omega)}^{2}=\sum_{j=1}^{K}\|(u\omega_{j})\circ\psi_{j}\|_{W^{\sigma,p}(B)}^{p},$

where $\\{\omega_{j}\\}$ is a partition of unity with respect to $V_{j}$.

The connection between $W^{\sigma,2}(\Omega)$ and
$W^{\sigma,2}(\mathbb{R}^{d})$ can be characterized by Sobolev extension (see
Adams & Fournier, 2003).

######  Lemma 2.1.

(Sobolev extension) Let $\Omega\subseteq\mathbb{R}^{d}$ be open and have a
Lipschitz boundary. Let $\sigma\geq 0$. Then there exists a linear operator
$E:W^{\sigma,2}(\Omega)\rightarrow W^{\sigma,2}(\mathbb{R}^{d})$ such that for
all $f\in W^{\sigma,2}(\Omega)$ the following results hold:

(1) $Ef|_{\Omega}=f$,

(2)$\|Ef\|_{W^{\sigma,2}(\mathbb{R}^{d})}\leq C\|f\|_{W^{\sigma,2}(\Omega)}$.

To establish a relation between Sobolev norm for the domain $\Omega$ and
Sobolev norm for the boundary $\partial\Omega$, we need to cite the trace
theorem and inverse trace theorem.

######  Lemma 2.2.

(trace theorem)Suppose $\Omega\subseteq\mathbb{R}^{d}$ is a bounded domain
with $C^{k,s}-$boundary. Let $1/2<\sigma<k+s$. Then, there exists a continuous
linear operator

$T:W^{\sigma,2}(\Omega)\rightarrow W^{\sigma-1/2,2}(\partial\Omega)$

such that $Tu=u|_{\partial\Omega}$ for all $u\in W^{\sigma,2}(\Omega)$ and

$\|u\|_{W^{\sigma-1/2,2}(\partial\Omega)}\leq
C\|u\|_{W^{\sigma,2}(\partial\Omega)}$

for some positive constant $C$ which is independent of $u$.

The proof of trace theorem can be found in Wloka (1987). The following inverse
trace theorem depicts the opposite situation, namely, the linear mapping from
$W^{\sigma-1/2,2}(\partial\Omega)$ to $W^{\sigma,2}(\Omega)$.

######  Lemma 2.3.

(inverse trace theorem)Suppose $\Omega\subseteq\mathbb{R}^{d}$ is a bounded
region with $C^{k,s}-$boundary. Let $1/2<\sigma<k+s$. Then, there exists a
continuous linear operator

$Z:W^{\sigma-1/2,2}(\partial\Omega)\rightarrow W^{\sigma,2}(\Omega)$

such that $T\circ Zu=u$ for all $u\in W^{\sigma-1/2,2}(\partial\Omega)$.

###  2.2 Elliptic boundary value problems and regularity

We consider a second order elliptic boundary value problem with the form

$\displaystyle Lu$ $\displaystyle=f\quad\hbox{in}\ \Omega,$ (3) $\displaystyle
u$ $\displaystyle=g\quad\hbox{on}\ \partial\Omega.$ (4)

where $L$ is strictly elliptic on $\Omega$ with the form

$Lu(\textbf{x})=\sum_{i,j=1}^{d}a_{ij}(\textbf{x})\frac{\partial^{2}}{\partial
x_{i}\partial
x_{j}}u(\textbf{x})+\sum_{i=1}^{d}b_{i}(\textbf{x})\frac{\partial}{\partial
x_{i}}u(\textbf{x})+c(\textbf{x})u(\textbf{x}).$ (5)

We assume that the solution of (3)-(4) has the regularity $u\in
W^{\sigma,2}(\Omega)$ with $\sigma>d/2+2$. When making appropriate assumptions
about the coefficients of (5), we can obtain Lemma 2.4 which describes the
continuity of linear operator $L$. The proof can be found in Giesl & Wendland
(2007).

######  Lemma 2.4.

(continuity of $L$)Let $\sigma\in\mathbb{R}$, and
$k=\lfloor\sigma\rfloor>d/2+2$. Let the coefficients of (5) satisfy
$a_{ij},b_{i},c\in W^{k-1,\infty}(\Omega)$. Then $L$ is a bounded operator
from $W^{\sigma,2}(\Omega)$ to $W^{\sigma-2,2}(\Omega)$ which satisfies

$\|Lu\|_{W^{\sigma-2,2}(\Omega)}\leq C\|u\|_{W^{\sigma,2}(\Omega)},\quad u\in
W^{\sigma,2}(\Omega).$

Another important theoretical result about the equations (3)-(4) is priori
inequality, which describes the continuously dependent properties of the
solution on the data.

######  Lemma 2.5.

(priori inequality) Let $u\in W^{1,2}(\Omega)$ satisfy the equations (3)-(4)
in the weak sense. Then $g\in W^{1/2,2}(\partial\Omega)$, and there exists a
constant $C$ such that

$\|u\|_{L^{2}(\Omega)}\leq
C\\{\|f\|_{L^{2}(\Omega)}+\|g\|_{W^{1/2,2}(\partial\Omega)}\\}.$ (6)

######  Proof 2.6.

With the help of the inverse trace operator $Z$, we know $Zg\in
W^{1,2}(\Omega)$. Using the $L^{2}-$analogue of the maximum principle taken
from Gilbarg & Trudinger (2001), then there exists a constant $C_{1}$ such
that

$\|u\|_{W^{1,2}(\Omega)}\leq
C_{1}\\{\|f\|_{L^{2}(\Omega)}+\|Zg\|_{W^{1,2}(\Omega)}\\}.$ (7)

From the continuity of the inverse trace operator (Lemma 2.3), we have

$\|Zg\|_{W^{1,2}(\Omega)}\leq C_{2}\|g\|_{W^{1/2,2}(\partial\Omega)}.$

Using the trivial estimate $\|u\|_{L^{2}(\Omega)}\leq\|u\|_{W^{1,2}(\Omega)}$
yields the inequality (6).

##  3 Kernel-based trial spaces

We want to use the trial spaces produced by radial basis functions as finite
dimensional approximation of the equations (3)-(4). In fact, such trial spaces
are the subspaces of the reproducing kernel Hilbert spaces (or native spaces).
The reproducing kernel plays an important role in our later analysis.

######  Definition 3.1.

Let $H$ be a real Hilbert space of functions
$f:\Omega(\subseteq\mathbb{R}^{d})\rightarrow\mathbb{R}$ with inner product
$\langle\cdot,\cdot\rangle_{H}$. A function
$\Phi:\Omega\times\Omega\rightarrow\mathbb{R}$ is called reproducing kernel
for $H$ if

(1)$\Phi(\cdot,\textbf{x})\in H$ for all $\textbf{x}\in\Omega$,

(2)$f(\textbf{x})=\langle f,\Phi(\cdot,\textbf{x})\rangle_{H}$ for all $f\in
H$ and all $\textbf{x}\in\Omega$.

A translation-invariant kernel such as the strictly positive definite radial
function $\Phi(\textbf{x},\textbf{y})=\Phi(\textbf{x}-\textbf{y})$ will
generate a reproducing kernel Hilbert space, the so-called native space
$\mathcal{N}_{\Phi}(\Omega)$. But we will make use of the native space
$\mathcal{N}_{\Phi}(\mathbb{R}^{d})$ which defined in $\mathbb{R}^{d}$ and
described by Fourier transform (1). $\mathcal{N}_{\Phi}(\mathbb{R}^{d})$
consists of all functions $f\in L^{2}(\mathbb{R}^{d})$ with

$\|f\|_{\Phi}^{2}=\int_{\mathbb{R}^{d}}\frac{|\widehat{f}(\bm{\omega})|^{2}}{\widehat{\Phi}(\bm{\omega})}d\bm{\omega}<\infty.$
(8)

Hence, if the Fourier transform of $\Phi:\mathbb{R}^{d}\rightarrow\mathbb{R}$
has the algebraic decay condition

$c_{1}(1+\|\bm{\omega}\|_{2}^{2})^{-\sigma}\leq\widehat{\Phi}\leq
c_{2}(1+\|\bm{\omega}\|_{2}^{2})^{-\sigma}$ (9)

for two fixed constants $0<c_{1}<c_{2}$, then the native space
$\mathcal{N}_{\Phi}(\mathbb{R}^{d})$ will be norm equivalent to the Sobolev
space $W^{\sigma,2}(\mathbb{R}^{d})$. In the paper, we always use $\Phi$ to
represent the radial functions which satisfy the condition (9). Thus, with a
radial function $\Phi$ satisfied (9) and a scaling parameter $\delta\in(0,1]$
we can construct a scaled radial function

$\Phi_{\delta}:=\delta^{-d}\Phi((\textbf{x}-\textbf{y})/\delta),\quad\textbf{x},\textbf{y}\in\mathbb{R}^{d}.$
(10)

The following Lemma establishes a relation between the native space
$\mathcal{N}_{\Phi_{\delta}}(\mathbb{R}^{d})$ and the Sobolev space
$W^{\sigma,2}(\mathbb{R}^{d})$. Its proof can be found in Wendland (2010).

######  Lemma 3.2.

(norm equivalence) For every $\delta\in(0,1]$ we have
$\mathcal{N}_{\Phi_{\delta}}(\mathbb{R}^{d})=W^{\sigma,2}(\mathbb{R}^{d})$.
And we have for every $f\in W^{\sigma,2}(\mathbb{R}^{d})$ the norm equivalence

$c_{1}\|f\|_{\Phi_{\delta}}\leq\|f\|_{W^{\sigma,2}(\mathbb{R}^{d})}\leq
c_{2}\delta^{-\sigma}\|f\|_{\Phi_{\delta}}$ (11)

with $c_{1},c_{2}>0$.

Now we can consider the finite dimensional kernel-based trial space generated
by $\Phi_{\delta}$. Let
$Y^{I}=\\{\textbf{y}_{1},\textbf{y}_{2},\ldots,\textbf{y}_{N_{I}}\\}\subseteq\Omega$
and
$Y^{B}=\\{\textbf{y}_{N_{I}+1},\textbf{y}_{N_{I}+2},\ldots,\textbf{y}_{N}\\}\subseteq\partial\Omega$
be some data sites which are arranged on the domain and its boundary
respectively. Hence the whole of centers are $Y=Y^{I}\bigcup Y^{B}$, which can
used to construct a trial space and determine its degrees of freedom. Some
measures are defined as follows:

$h_{I}:=\sup_{\textbf{y}\in\Omega}\min_{\textbf{y}_{j}\in
Y^{I}}\|\textbf{y}-\textbf{y}_{j}\|_{2},\quad\textrm{for interior centers}\
Y^{I},$ $h_{B}:=\max_{1\leq j\leq K}h_{Bj}=\max_{1\leq j\leq
K}\left\\{\sup_{\textbf{y}\in
B=B(\textbf{0},1)}\min_{\textbf{y}_{j}\in\psi_{j}^{-1}\left(Y^{B}\bigcap
V_{j}\right)}\|\textbf{y}-\textbf{y}_{j}\|_{2}\right\\},\quad\textrm{for
boundary centers}\ Y^{B},$
$q_{I}:=\frac{1}{2}\min_{\textbf{y}_{i},\textbf{y}_{k}\in Y^{I},i\neq
k}\|\textbf{y}_{i}-\textbf{y}_{k}\|_{2},\quad\textrm{for interior centers}\
Y^{I},$ $q_{B}:=\min_{1\leq j\leq K}q_{Bj}=\min_{1\leq j\leq
K}\left\\{\frac{1}{2}\min_{\textbf{y}_{i},\textbf{y}_{k}\in\psi_{j}^{-1}\left(Y^{B}\bigcap
V_{j}\right),i\neq
k}\|\textbf{y}_{i}-\textbf{y}_{k}\|_{2}\right\\},\quad\textrm{for boundary
centers}\ Y^{B},$ $h_{Y}:=\max\\{h_{I},h_{B}\\},\quad
q_{Y}:=\min\\{q_{I},q_{B}\\}.$

Using the scaled radial function $\Phi_{\delta}$ as basis functions, then the
kernel-based trial space is

$W_{\delta}=\textrm{span}\\{\Phi_{\delta}(\cdot-\textbf{y})|\textbf{y}\in
Y\\}.$ (12)

To establish the Bernstein-type inequality in the kernel-based trial space
$W_{\delta}$, we need a class of band-limited functions. Let $\rho>0$, we
define $\mathcal{B}_{\rho}$ to be

$\mathcal{B}_{\rho}:=\\{f\in L^{2}(\mathbb{R}^{d}):\textrm{supp}\
\widehat{f}\subseteq B(\textbf{0},\rho)\\},$

where $B(\textbf{0},\rho)$ is the ball in $\mathbb{R}^{d}$ having center 0 and
radius $\rho$. We denote the reproducing kernel of
$W^{\beta,2}(\mathbb{R}^{d})$ by $\Psi:\mathbb{R}^{d}\rightarrow\mathbb{R}$
which has a Fourier transform that satisfies

$\widehat{\Psi}=(1+\|\bm{\omega}\|_{2}^{2})^{-\beta},\quad\bm{\omega}\in\mathbb{R}^{d},$
(13)

where we take $\sigma\geq\beta>d/2$. At this time, the scaled kernel is

$\Psi_{\delta}:=\delta^{-d}\Psi((\textbf{x}-\textbf{y})/\delta),\quad\textbf{x},\textbf{y}\in\mathbb{R}^{d}.$
(14)

We first need an auxiliary result from Narcowich _et al._ (2006).

######  Lemma 3.3.

Let $f=\sum_{j=1}^{N}c_{j}\Psi(\cdot-\textbf{x}_{j}),\ \textbf{x}_{j}\in Y$.
Define $\widehat{f_{\rho}}=\widehat{f}_{YB(0,\rho)}$, where $YB(0,\rho)$ is
the characteristic function of the ball $B(0,\rho)$. Then, there exists a
constant $k>0$, which is dindependent of $Y$ and the $\\{c_{j}\\}$, such that
for $\rho=k/q_{Y}$ the following inequality holds

$\|f-f_{\rho}\|_{W^{\beta,2}(\mathbb{R}^{d})}\leq\frac{1}{2}\|f\|_{W^{\beta,2}(\mathbb{R}^{d})}.$
(15)

This Lemma can be used to prove a version of scaled trial spaces generated by
$\Psi_{\delta}$.

######  Lemma 3.4.

Let $f=\sum_{j=1}^{N}c_{j}\Psi_{\delta}(\cdot-\textbf{x}_{j}),\
\textbf{x}_{j}\in Y$. Define
$\widehat{f_{\rho/\delta}}=\widehat{f}_{YB(0,\rho/\delta)}$, where
$YB(0,\rho/\delta)$ is the characteristic function of the ball
$B(0,\rho/\delta)$. Then there exists a constant $k>0$, which is dindependent
of $Y$ and the $\\{c_{j}\\}$, such that for $\rho=k\delta/q_{Y}$ the following
inequality holds

$\|f-f_{\rho/\delta}\|_{\Psi_{\delta}}\leq\frac{1}{2}\|f\|_{\Psi_{\delta}},$
(16)

and

$\|f\|_{\Psi_{\delta}}\leq 2\|f_{\rho/\delta}\|_{\Psi_{\delta}}.$ (17)

######  Proof 3.5.

The proof is very similar to the technical process of Lemma 4 of Wendland
(2010). Define $g(\textbf{x})=\delta^{d/2}f(\delta\textbf{x})$, then $g\in
W^{\beta,2}(\mathbb{R}^{d})$ and
$\|g\|_{W^{\beta,2}(\mathbb{R}^{d})}=\|f\|_{\Psi_{\delta}}$. Define a new
scattered data set $X=Y/\delta=\\{\textbf{y}/\delta:\textbf{y}\in Y\\}$ which
has separation distance $q_{X}=q_{Y}/\delta$. Then we can define a $g_{\rho}$
with $\rho=k\delta/q_{Y}$ and
$\widehat{g_{\rho}}=\widehat{g}_{XB(\textbf{0},\rho)}$. By using Lemma 3.3 we
have

$\|g-g_{\rho}\|_{W^{\beta,2}(\mathbb{R}^{d})}\leq\frac{1}{2}\|g\|_{W^{\beta,2}(\mathbb{R}^{d})}.$

We then define
$f_{\rho/\delta}(\textbf{x})=\delta^{-d/2}g_{\rho}(\textbf{x}/\delta)$, and
for $\bm{\omega}\in B(0,\rho/\delta)\subset\mathbb{R}^{d}$

$\widehat{f_{\rho/\delta}}(\bm{\omega})=\delta^{d/2}\widehat{g_{\rho}}(\delta\bm{\omega})=\delta^{d/2}\widehat{g}_{XB(\textbf{0},\rho)}(\delta\bm{\omega})=\widehat{f}_{YB(0,\rho/\delta)}(\bm{\omega}).$

Since
$\|f_{\rho/\delta}\|_{\Psi_{\delta}}=\|g_{\rho}\|_{W^{\beta,2}(\mathbb{R}^{d})}$,
so

$\displaystyle\|f-f_{\rho/\delta}\|_{\Psi_{\delta}}$
$\displaystyle=\|g-g_{\rho}\|_{W^{\beta,2}(\mathbb{R}^{d})}$
$\displaystyle\leq\frac{1}{2}\|g\|_{W^{\beta,2}(\mathbb{R}^{d})}\leq\frac{1}{2}\|f\|_{\Psi_{\delta}}.$

(17) is a direct result from (16).

We can now combine Lemma 3.4 with Lemma 3.2 to arrive at the following inverse
inequality.

######  Lemma 3.6.

(inverse inequality) Let $\sigma\geq\beta>d/2$. Let
$f=\sum_{j=1}^{N}c_{j}\Psi_{\delta}(\cdot-\textbf{x}_{j}),\ \textbf{x}_{j}\in
Y$. Let $\rho=k\delta/q_{Y}$ with $k>0$. Then there exists a constant $C$ such
that

$\|f\|_{W^{\beta,2}(\mathbb{R}^{d})}\leq
Cq_{Y}^{-\beta}\|f\|_{L^{2}(\mathbb{R}^{d})}.$ (18)

######  Proof 3.7.

Using Lemma 3.4, Lemma 3.2, (13) and Parseval’s identity,

$\displaystyle\|f\|_{W^{\beta,2}(\mathbb{R}^{d})}^{2}$ $\displaystyle\leq
c\delta^{-2\beta}\|f\|_{\Psi_{\delta}}^{2}$ $\displaystyle\leq
4c\delta^{-2\beta}\int_{\|\bm{\omega}\|_{2}\leq\rho/\delta}\frac{|\widehat{f}(\bm{\omega})|^{2}}{\widehat{\Psi_{\delta}}(\bm{\omega})}d\bm{\omega}$
$\displaystyle=4c\delta^{-2\beta}\int_{\|\bm{\omega}\|_{2}\leq\rho/\delta}|\widehat{f}(\bm{\omega})|^{2}(1+\delta^{2}\|\bm{\omega}\|_{2}^{2})^{\beta}d\bm{\omega}$
$\displaystyle\leq
4c\delta^{-2\beta}(1+\rho^{2})^{\beta}\int_{\|\bm{\omega}\|_{2}\leq\rho/\delta}|\widehat{f}(\bm{\omega})|^{2}d\bm{\omega}$
$\displaystyle\leq
4c\delta^{-2\beta}2^{\beta}\rho^{2\beta}\int_{\mathbb{R}^{d}}|\widehat{f}(\bm{\omega})|^{2}d\bm{\omega}$
$\displaystyle=4c2^{\beta}k^{2\beta}q_{Y}^{-2\beta}\|f\|_{L^{2}(\mathbb{R}^{d})}^{2}.$

We also need another auxiliary result comes from Wendland (2018), which is a
scaled version of Theorem 3.4 in Narcowich _et al._ (2006).

######  Lemma 3.8.

Let $f\in W^{\beta,2}(\mathbb{R}^{d})$, $\beta>d/2$. Then there exists a
constant $k>0$, which is dindependent of $Y$ and $\delta$ such that to each
$f$ there is a band-limited function $f_{k/q_{Y}}\in\mathcal{B}_{k/q_{Y}}$
with $f_{k/q_{Y}}|Y=f|Y$ and

$\|f-f_{k/q_{Y}}\|_{\Psi_{\delta}}\leq 5\|f\|_{\Psi_{\delta}}.$

The last auxiliary result in this section is the well-known sampling
inequality (see Narcowich _et al._ , 2006; Rieger _et al._ , 2010; Schaback,
2007; Wendland & Rieger, 2005).

######  Lemma 3.9.

(sampling inequality) Suppose $\Omega\subseteq\mathbb{R}^{d}$ is a bounded
domain with an interior cone condition. Let $q\in[1,\infty]$ and constants
$0\leq\mu<\mu+d/2<\lfloor m\rfloor$. Then there are positive constant $C$,
$h_{0}$ such that

$\|f\|_{W^{\mu,q}(\Omega)}\leq
C\left(h_{Y}^{m-\mu-d(1/2-1/q)_{+}}\|f\|_{W^{m,2}(\Omega)}+h_{Y}^{-\mu}\|\Pi_{Y}f\|_{\infty,Y}\right)$
(19)

holds for every discrete set $Y\subset\Omega$ with fill distance at most
$h_{Y}\leq h_{0}$ and every $f\in W^{m,2}(\Omega)$. Here $\Pi_{Y}$ is the
function evaluation operator at the data sites $Y$.

##  4 One-level unsymmetric collocation

We are now ready to consider the unsymmetric collocation for the equations
(3)-(4). According to Schaback (2007), it should be implemented by a nonsquare
testing at another data sites with many more degrees of freedom than the
centers $Y=Y^{I}\bigcup Y^{B}$. On the testing side, we use a set
$X=X^{I}\bigcup X^{B}$ with
$X^{I}=\\{\textbf{x}_{1},\textbf{x}_{2},\ldots,\textbf{x}_{M_{I}}\\}\subseteq\Omega$
and
$X^{B}=\\{\textbf{x}_{M_{I}+1},\textbf{x}_{M_{I}+2},\ldots,\textbf{y}_{M}\\}\subseteq\partial\Omega$.
We use

$s_{I}:=\sup_{\textbf{x}\in\Omega}\min_{\textbf{x}_{j}\in
X^{I}}\|\textbf{x}-\textbf{x}_{j}\|_{2},$ $s_{B}:=\max_{1\leq j\leq
K}s_{Bj}=\max_{1\leq j\leq K}\left\\{\sup_{\textbf{x}\in
B=B(\textbf{0},1)}\min_{\textbf{x}_{j}\in\psi_{j}^{-1}\left(X^{B}\bigcap
V_{j}\right)}\|\textbf{x}-\textbf{x}_{j}\|_{2}\right\\}$

to represent the fill distance of the data sites $X^{I}$ and $X^{B}$
respectively. Obviously, they have the parallel definitions with $h_{I}$ and
$h_{B}$ on trial side. Hence choose $s_{X}=\max\\{s_{I},s_{B}\\}$. Then we can
construct a trial function with the form

$s_{u}(\textbf{x})=\sum_{j=1}^{N}c_{j}\Phi_{\delta}(\textbf{x}-\textbf{y}_{j}),\quad\textbf{y}_{j}\in
Y,$

which satisfies

$\displaystyle Ls_{u}(\textbf{x})$
$\displaystyle=f(\textbf{x}),\quad\textbf{x}\in X^{I},$ (20) $\displaystyle
s_{u}(\textbf{x})$ $\displaystyle=g(\textbf{x}),\quad\textbf{x}\in X^{B}.$
(21)

(20)-(21) is a one-level unsymmetric collocation for the equations (3)-(4),
but with a nonsquare linear systems. We now want to bound the $L^{2}-$error
between the solution $u$ and its approximation $s_{u}$.

First we define a map $I_{h}:u\rightarrow I_{h}u\in W_{\delta}$ via
interpolation

$I_{h}u(\textbf{y}_{k})=\sum_{j=1}^{N}c_{j}\Phi_{\delta}(\textbf{y}_{k}-\textbf{y}_{j})=u(\textbf{y}_{k}),\quad\textbf{y}_{k}\in
Y,k=1,2,\ldots,N,$ (22)

for the unknown coefficients $c_{1},c_{2},\ldots,c_{N}$ are determined by
solving the above linear system. Because $I_{h}u$ is a interpolant to $u$ from
the trial $W_{\delta}$ at the centers $Y$, so its stability can be obtained by
using Lemma 3.8.

######  Lemma 4.1.

Let $\Omega\subseteq\mathbb{R}^{d}$ be a bounded domain with Lipschitz
boundary. Let $Y$ be quasi-uniform in the sense that $h_{Y}\leq cq_{Y}$.
Denote the interpolant of $u\in W^{\sigma,2}(\Omega)$ with $\sigma>d/2+2$ on
$Y$ by $I_{h}u$. Then there exists a constant $C>0$ such that

$\|u-I_{h}u\|_{W^{\sigma,2}(\Omega)}\leq
C\delta^{-\sigma}\|u\|_{W^{\sigma,2}(\Omega)}.$

######  Proof 4.2.

From Lemma 3.8 combined with Lemma 2.1, for $u\in W^{\sigma,2}(\Omega)$ there
exists a band-limited function
$\widetilde{u}:=(Eu)_{k/q_{Y}}\in\mathcal{B}_{k/q_{Y}}$ such that
$u|Y=Eu|Y=\widetilde{u}|Y$. Then

$\displaystyle\|u-I_{h}u\|_{W^{\sigma,2}(\Omega)}$ $\displaystyle=\|Eu-
I_{h}(Eu)\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq\|Eu-\widetilde{u}\|_{W^{\sigma,2}(\Omega)}+\|\widetilde{u}-I_{h}u\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq\|Eu-\widetilde{u}\|_{W^{\sigma,2}(\Omega)}+\|\widetilde{u}-I_{h}\widetilde{u}\|_{W^{\sigma,2}(\Omega)}.$

The first term on the right can be bounded by

$\displaystyle\|Eu-\widetilde{u}\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq\|Eu-\widetilde{u}\|_{W^{\sigma,2}(\mathbb{R}^{d})}$
$\displaystyle\leq C\delta^{-\sigma}\|Eu-\widetilde{u}\|_{\Phi_{\delta}}\leq
5C\delta^{-\sigma}\|Eu\|_{\Phi_{\delta}}$ $\displaystyle\leq
5C\delta^{-\sigma}\|Eu\|_{W^{\sigma,2}(\mathbb{R}^{d})}\leq
C\delta^{-\sigma}\|u\|_{W^{\sigma,2}(\Omega)}.$

Using Lemma 2.1, Lemma 3.2 and Lemma 3.8, the upper bound of the second term
simply follows from

$\displaystyle\|\widetilde{u}-I_{h}\widetilde{u}\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta^{-\sigma}\|\widetilde{u}-I_{h}\widetilde{u}\|_{\Phi_{\delta}}$
$\displaystyle\leq C\delta^{-\sigma}\|\widetilde{u}\|_{\Phi_{\delta}}\leq
C\delta^{-\sigma}\|\widetilde{u}\|_{W^{\sigma,2}(\mathbb{R}^{d})}$
$\displaystyle\leq C\delta^{-\sigma}\|Eu\|_{W^{\sigma,2}(\mathbb{R}^{d})}\leq
C\delta^{-\sigma}\|u\|_{W^{\sigma,2}(\Omega)}.$

On the other hand, $I_{h}u-s_{u}\in W^{\sigma,2}(\Omega)$ satisfies the
equations (3)-(4) with $f=L(I_{h}u-s_{u})$ and $g=I_{h}u-s_{u}$. Hence, with
the help of the priori inequality (Lemma 2.5) we have

$\|I_{h}u-s_{u}\|_{L^{2}(\Omega)}\leq
C\left\\{\|L(I_{h}u-s_{u})\|_{L^{2}(\Omega)}+\|I_{h}u-s_{u}\|_{W^{1/2,2}(\partial\Omega)}\right\\}.$
(23)

So we need to bound the two terms on the right-hand side separately. Using the
two testing operators $\Pi_{X^{I}}$ and $\Pi_{X^{B}}$ and combining with the
sampling inequality, we can bound $\|L(I_{h}u-s_{u})\|_{L^{2}(\Omega)}$ and
$\|I_{h}u-s_{u}\|_{W^{1/2,2}(\partial\Omega)}$ respectively.

######  Lemma 4.3.

(coerciveness of $\Pi_{X^{I}},\Pi_{X^{B}}$) Let
$\Omega\subseteq\mathbb{R}^{d}$ be a bounded domain has a $C^{k,s}-$boundary
with $s\in[0,1)$. Let $Y$ be quasi-uniform in the sense that $h_{Y}\leq
cq_{Y}$. Let the testing data sites $X$ also be quasi-uniform. Let
$\sigma=k+s$, $k=\lfloor\sigma\rfloor>d/2+2$. Denote the interpolant of $u\in
W^{\sigma,2}(\Omega)$ on $Y$ by $I_{h}u$. Let $s_{u}\in W_{\delta}$ be the
collocation solution that satisfies (20)-(21). Let $s_{I}$ and $s_{B}$ be the
fill distance of the data sites $X^{I}$ and $X^{B}$ respectively, and
$s_{X}=\max\\{s_{I},s_{B}\\}$. If the testing discretizations is finer than
the trial discretization and satisfies condition

$Cs_{X}^{\sigma-2}h_{Y}^{-\sigma}<\frac{1}{2},$ (24)

then there exists a constant $C>0$ such that

$\|I_{h}u-s_{u}\|^{2}_{L^{2}(\Omega)}\leq
C\left\\{\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|^{2}_{\infty,X^{I}}+s_{B}^{-1}\|\Pi_{X^{B}}(I_{h}u-s_{u})\|^{2}_{\infty,X^{B}}\right\\}.$
(25)

######  Proof 4.4.

Using Lemma 2.1, Lemma 2.4, Lemma 3.6, and Lemma 3.9, we have

$\displaystyle\|L(I_{h}u-s_{u})\|_{L^{2}(\Omega)}$ $\displaystyle\leq
C\left\\{s_{I}^{\sigma-2}\|L(I_{h}u-s_{u})\|_{W^{\sigma-2,2}(\Omega)}+\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|_{\infty,X^{I}}\right\\}$
$\displaystyle\leq
Cs_{I}^{\sigma-2}\|I_{h}u-s_{u}\|_{W^{\sigma,2}(\Omega)}+C\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|_{\infty,X^{I}}$
$\displaystyle\leq
Cs_{I}^{\sigma-2}\|E(I_{h}u-s_{u})\|_{W^{\sigma,2}(\mathbb{R}^{d})}+C\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|_{\infty,X^{I}}$
$\displaystyle\leq
Cs_{I}^{\sigma-2}q_{Y}^{-\sigma}\|E(I_{h}u-s_{u})\|_{L^{2}(\mathbb{R}^{d})}+C\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|_{\infty,X^{I}}$
$\displaystyle\leq
Cs_{I}^{\sigma-2}q_{Y}^{-\sigma}\|I_{h}u-s_{u}\|_{L^{2}(\Omega)}+C\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|_{\infty,X^{I}}$
$\displaystyle\leq
Cs_{X}^{\sigma-2}h_{Y}^{-\sigma}\|I_{h}u-s_{u}\|_{L^{2}(\Omega)}+C\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|_{\infty,X^{I}}.$

For the boundary term, we use the definition of the Sobolev norm on the
boundary, Lemma 2.1, Lemma 2.2, and Lemma 3.9. If we denote
$w_{j}=((I_{h}u-s_{u})\omega_{j})\circ\Psi_{j}\in W^{\sigma-1/2,2}(B)$, then

$\displaystyle\quad\|I_{h}u-s_{u}\|^{2}_{W^{1/2,2}(\partial\Omega)}=\sum_{j=1}^{K}\|w_{j}\|^{2}_{W^{1/2,2}(B)}$
$\displaystyle\leq
C\sum_{j=1}^{K}\left(s_{Bj}^{\sigma-1}\|w_{j}\|_{W^{\sigma-1/2,2}(B)}+s_{Bj}^{-1/2}\|\Pi_{\psi_{j}^{-1}\left(X^{B}\bigcap
V_{j}\right)}w_{j}\|_{\infty,\psi_{j}^{-1}\left(X^{B}\bigcap
V_{j}\right)}\right)^{2}$ $\displaystyle\leq
C\sum_{j=1}^{K}\left(s_{Bj}^{2\sigma-2}\|w_{j}\|^{2}_{W^{\sigma-1/2,2}(B)}+s_{Bj}^{-1}\|\Pi_{\psi_{j}^{-1}\left(X^{B}\bigcap
V_{j}\right)}w_{j}\|^{2}_{\infty,\psi_{j}^{-1}\left(X^{B}\bigcap
V_{j}\right)}\right)$ $\displaystyle\leq
Cs_{B}^{2\sigma-2}\|I_{h}u-s_{u}\|^{2}_{W^{\sigma-1/2,2}(\partial\Omega)}+Cs_{B}^{-1}\|\Pi_{X^{B}}(I_{h}u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq
Cs_{B}^{2\sigma-2}\|I_{h}u-s_{u}\|^{2}_{W^{\sigma,2}(\Omega)}+Cs_{B}^{-1}\|\Pi_{X^{B}}(I_{h}u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq
Cs_{X}^{2\sigma-2}h_{Y}^{-2\sigma}\|I_{h}u-s_{u}\|^{2}_{L^{2}(\Omega)}+Cs_{B}^{-1}\|\Pi_{X^{B}}(I_{h}u-s_{u})\|^{2}_{\infty,X^{B}},$

where the last inequality is obtained by the same as the last four steps for
the term $\|L(I_{h}u-s_{u})\|_{L^{2}(\Omega)}$.

From the inequality (23) and the condition (24), we have

$\displaystyle\|I_{h}u-s_{u}\|^{2}_{L^{2}(\Omega)}$ $\displaystyle\leq
C\|L(I_{h}u-s_{u})\|^{2}_{L^{2}(\Omega)}+C\|I_{h}u-s_{u}\|^{2}_{W^{1/2,2}(\partial\Omega)}$
$\displaystyle\leq\frac{1}{2}\|I_{h}u-s_{u}\|^{2}_{L^{2}(\Omega)}+C\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|^{2}_{\infty,X^{I}}+Cs_{B}^{-1}\|\Pi_{X^{B}}(I_{h}u-s_{u})\|^{2}_{\infty,X^{B}}.$

This yields the result (25).

If we assume the linear systems (20)-(21) can be solved by $s_{u}\in
W_{\delta}$ with the tolerance

$\|\Pi_{X^{I}}L(u-s_{u})\|^{2}_{\infty,X^{I}}+s_{B}^{-1}\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}\leq
C\delta^{-2\sigma}h_{Y}^{2(\sigma-2-d/2)}\|u\|^{2}_{W^{\sigma,2}(\Omega)},$
(26)

then we can obtain the boundedness of $\Pi_{X^{I}},\Pi_{X^{B}}$.

######  Lemma 4.5.

(boundedness of $\Pi_{X^{I}},\Pi_{X^{B}}$) Under the same assumption of Lemma
4.3. Suppose one of the linear solvers for the equations (20)-(21) satisfies
(26). Then there exists a constant $C>0$ such that

$\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|^{2}_{\infty,X^{I}}+s_{B}^{-1}\|\Pi_{X^{B}}(I_{h}u-s_{u})\|^{2}_{\infty,X^{B}}\leq
C\delta^{-2\sigma}h^{2(\sigma-2-d/2)}_{Y}\|u\|^{2}_{W^{\sigma,2}(\Omega)}.$
(27)

######  Proof 4.6.

From Lemma 3.9, Lemma 2.4, Lemma 4.1, we can bound

$\displaystyle\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|^{2}_{\infty,X^{I}}$
$\displaystyle\leq
2\|\Pi_{X^{I}}L(I_{h}u-u)\|^{2}_{\infty,X^{I}}+2\|\Pi_{X^{I}}L(u-s_{u})\|^{2}_{\infty,X^{I}}$
$\displaystyle=2\|L(I_{h}u-u)\|^{2}_{\infty,X^{I}}+2\|\Pi_{X^{I}}L(u-s_{u})\|^{2}_{\infty,X^{I}}$
$\displaystyle\leq
2\|L(I_{h}u-u)\|^{2}_{\infty,\Omega}+2\|\Pi_{X^{I}}L(u-s_{u})\|^{2}_{\infty,X^{I}}$
$\displaystyle\leq
Ch_{I}^{2(\sigma-2-d/2)}\|L(I_{h}u-u)\|^{2}_{W^{\sigma-2,2}(\Omega)}+2\|\Pi_{X^{I}}L(u-s_{u})\|^{2}_{\infty,X^{I}}$
$\displaystyle\leq
Ch_{I}^{2(\sigma-2-d/2)}\|I_{h}u-u\|^{2}_{W^{\sigma,2}(\Omega)}+2\|\Pi_{X^{I}}L(u-s_{u})\|^{2}_{\infty,X^{I}}$
$\displaystyle\leq
C\delta^{-2\sigma}h_{I}^{2(\sigma-2-d/2)}\|u\|^{2}_{W^{\sigma,2}(\Omega)}+2\|\Pi_{X^{I}}L(u-s_{u})\|^{2}_{\infty,X^{I}}.$

To bounding the boundary term, we denote
$w_{j}=((I_{h}u-u)\omega_{j})\circ\Psi_{j}\in W^{\sigma-1/2,2}(B)$. Then we
can use the sampling inequality on the unit ball
$B=B(\textbf{0},1)\subseteq\mathbb{R}^{d-1}$. Using the sampling inequality,
the definition of the Sobolev norm on the boundary, the trace theorem, and
Lemma 4.1, then we have

$\displaystyle\|\Pi_{X^{B}}(I_{h}u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq
2\|\Pi_{X^{B}}(I_{h}u-u)\|^{2}_{\infty,X^{B}}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle=2\|I_{h}u-u\|^{2}_{\infty,X^{B}}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq
2\|I_{h}u-u\|^{2}_{\infty,\partial\Omega}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq C\max_{1\leq j\leq
K}\|w_{j}\|^{2}_{L^{\infty}(B)}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq C\max_{1\leq j\leq
K}h_{Bj}^{2(\sigma-1/2-d/2)}\|w_{j}\|^{2}_{W^{\sigma-1/2,2}(B)}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq
Ch_{B}^{2(\sigma-1/2-d/2)}\sum_{j=1}^{K}\|w_{j}\|^{2}_{W^{\sigma-1/2,2}(B)}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle=Ch_{B}^{2(\sigma-1/2-d/2)}\|I_{h}u-u\|^{2}_{W^{\sigma-1/2,2}(\partial\Omega)}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq
Ch_{B}^{2(\sigma-1/2-d/2)}\|I_{h}u-u\|^{2}_{W^{\sigma,2}(\Omega)}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq
C\delta^{-2\sigma}h_{B}^{2(\sigma-1/2-d/2)}\|u\|^{2}_{W^{\sigma,2}(\Omega)}+2\|\Pi_{X^{B}}(u-s_{u})\|^{2}_{\infty,X^{B}}.$

We now multiply the boundary inequality by a factor $s_{B}^{-1}$ and combine
it with the domain inequality. By using the condition
$\lfloor\sigma\rfloor>d/2+2$, the condition (24), the quasi-uniform property
of $X$, the quasi-uniform property of $Y$, and the condition (26), we have

$\displaystyle\quad\|\Pi_{X^{I}}L(I_{h}u-s_{u})\|^{2}_{\infty,X^{I}}+s_{B}^{-1}\|\Pi_{X^{B}}(I_{h}u-s_{u})\|^{2}_{\infty,X^{B}}$
$\displaystyle\leq
C\delta^{-2\sigma}\left(h_{I}^{2(\sigma-2-d/2)}+s_{B}^{-1}h_{B}^{2(\sigma-1/2-d/2)}\right)\|u\|^{2}_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta^{-2\sigma}\left(h_{Y}^{2(\sigma-2-d/2)}+h_{Y}^{-\sigma/(\sigma-2)}h_{Y}^{2(\sigma-1/2-d/2)}\right)\|u\|^{2}_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta^{-2\sigma}h^{2(\sigma-2-d/2)}_{Y}\|u\|^{2}_{W^{\sigma,2}(\Omega)}.$

The next theorem is our main convergence result of the one-level unsymmetric
collocation for the equations (3)-(4).

######  Theorem 4.7.

(Convergence of one-level unsymmetric collocation) Let
$\Omega\subseteq\mathbb{R}^{d}$ be a bounded domain has a $C^{k,s}-$boundary
with $s\in[0,1)$. Let the trial data $Y$ with the fill distance
$h_{Y}=\max\\{h_{I},h_{B}\\}$ and the testing data $X$ with the fill distance
$s_{X}=\max\\{s_{I},s_{B}\\}$ both be quasi-uniform. Let $\sigma=k+s$,
$k=\lfloor\sigma\rfloor>d/2+2$. Let $u\in W^{\sigma,2}(\Omega)$ be the
solution of (3)-(4). Suppose $s_{u}\in W_{\delta}$ is the collocation solution
that satisfies (20)-(21). Assume that (20)-(21) can be solved by $s_{u}$ with
the tolerance (26). If the testing discretizations is finer than the trial
discretization and satisfies condition (24), then there exists a constant
$C>0$ such that

$\|u-s_{u}\|_{L^{2}(\Omega)}\leq
C\delta^{-\sigma}h^{\sigma-2-d/2}_{Y}\|u\|_{W^{\sigma,2}(\Omega)}.$

######  Proof 4.8.

Using Lemma 3.9 and combining Lemma 4.3 with Lemma 4.5, we have

$\displaystyle\|u-s_{u}\|_{L^{2}(\Omega)}$
$\displaystyle\leq\|u-I_{h}u\|_{L^{2}(\Omega)}+\|I_{h}u-s_{u}\|_{L^{2}(\Omega)}$
$\displaystyle\leq
Ch_{Y}^{\sigma}\|u-I_{h}u\|_{W^{\sigma,2}(\Omega)}+C\delta^{-\sigma}h^{\sigma-2-d/2}_{Y}\|u\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta^{-\sigma}h_{Y}^{\sigma}\|u\|_{W^{\sigma,2}(\Omega)}+C\delta^{-\sigma}h^{\sigma-2-d/2}_{Y}\|u\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta^{-\sigma}h^{\sigma-2-d/2}_{Y}\|u\|_{W^{\sigma,2}(\Omega)}.$

##  5 Multilevel unsymmetric collocation

We now consider implementing the unsymmetric collocation for (3)-(4) on the
increasingly dense data sites. Assume that we are given a sequence of interior
centers $Y^{I}_{1},Y^{I}_{2},\ldots\subseteq\Omega$ and boundary centers
$Y^{B}_{1},Y^{B}_{2},\ldots\subseteq\partial\Omega$. Corresponding, we are
also given a sequence of interior testing data sites
$X^{I}_{1},X^{I}_{2},\ldots\subseteq\Omega$ and boundary testing data sites
$X^{B}_{1},X^{B}_{2},\ldots\subseteq\partial\Omega$. We denote

$Y_{j}=Y_{j}^{I}\bigcup Y_{j}^{B},\quad X_{j}=X_{j}^{I}\bigcup X_{j}^{B}.$

We denote the fill distance of $Y_{j}^{I}$ and $X_{j}^{I}$ by
$\tilde{h}_{j},\tilde{s}_{j}$, and the fill distance of $Y_{j}^{B}$ and
$X_{j}^{B}$ by $\tilde{\tilde{h}}_{j},\tilde{\tilde{s}}_{j}$ respectively. Let
$h_{j}=\max\\{\tilde{h}_{j},\tilde{\tilde{h}}_{j}\\},s_{j}=\max\\{\tilde{s}_{j},\tilde{\tilde{s}}_{j}\\}$
be the fill distance of $Y_{j}$ and $X_{j}$ respectively, which satisfy

$Cs_{j}^{\sigma-2}h_{j}^{-\sigma}<\frac{1}{2}.$ (28)

Then, with a radial function $\Phi$ satisfied (9) and a series of decreasing
scaling parameters $\delta_{1}>\delta_{2}>\ldots>\delta_{j}>\ldots\in(0,1]$,
we can define

$\Phi_{j}:=\Phi_{\delta_{j}}=\delta_{j}^{-d}\Phi((\textbf{x}-\textbf{y})/\delta_{j}),\quad\textbf{x},\textbf{y}\in\mathbb{R}^{d}.$
(29)

Using the radial functions $\Phi_{j}$ and the trial centers $Y_{j}$, the one-
level kernel-based trial spaces can be constructed as

$W_{j}=\textrm{span}\\{\Phi_{j}(\cdot-\textbf{y})|\textbf{y}\in Y_{j}\\}.$
(30)

Let $v_{j}\in W_{j}$ be some trial functions which have the forms

$v_{j}(\textbf{x})=\sum_{j=1}^{\sharp(Y_{j})}c_{j}\Phi_{j}(\textbf{x}-\textbf{y}_{j}),\quad\textbf{y}_{j}\in
Y_{j},$

then a multilevel unsymmetric collocation algorithm for the equations (3)-(4)
can be obtained as the following form.

(multilevel unsymmetric collocation)

Given the right-hand sides $f$ and $g$, we implement

(1) Set $u_{0}=0,f_{0}=f,g_{0}=g$

(2) for $j=1,2,\ldots$ do

$\bullet$ Determine the local correction $v_{j}$ to $f_{j-1}$ and $g_{j-1}$
with

$\displaystyle Lv_{j}(\textbf{x})$
$\displaystyle=f_{j-1}(\textbf{x}),\quad\textbf{x}\in X_{j}^{I},$ (31)
$\displaystyle v_{j}(\textbf{x})$
$\displaystyle=g_{j-1}(\textbf{x}),\quad\textbf{x}\in X_{j}^{B},$ (32)

$\bullet$ Update the global approximation and the residuals

$\displaystyle u_{j}$ $\displaystyle=u_{j-1}+v_{j},$ $\displaystyle f_{j}$
$\displaystyle=f_{j-1}-Lv_{j},$ $\displaystyle g_{j}$
$\displaystyle=g_{j-1}-v_{j}.$

Suppose $u\in W^{\sigma,2}(\Omega)$ is the exact solution of the equations
(3)-(4), we denote $e_{j}=u-u_{j}$ be the error at level $j$. Then Algorithm 5
satisfies the following relations:

$u_{j}=\sum_{k=1}^{j}v_{k},\quad e_{j}=u-u_{j}=e_{j-1}-v_{j},\quad
f_{j}=f-Lu_{j},\quad\textrm{and}\quad g_{j}=g-u_{j}.$

######  Lemma 5.1.

Let $\Omega\subseteq\mathbb{R}^{d}$ be a bounded domain has a
$C^{k,s}-$boundary with $s\in[0,1)$. Let the trial data $Y_{j}$ with the fill
distance $h_{j}$ and the testing data $X_{j}$ with the fill distance $s_{j}$
both be quasi-uniform for $j=1,2,\ldots$. Let $\sigma=k+s$,
$k=\lfloor\sigma\rfloor>d/2+2$. Denote the interpolant of $e_{j-1}\in
W^{\sigma,2}(\Omega)$ on $Y_{j}$ by $I_{j}:e_{j-1}\rightarrow I_{j}e_{j-1}\in
W_{j}$. Suppose $v_{j}\in W_{j}$ are the local correction decided by Algorithm
5. Assume that (31)-(32) can be solved by $v_{j}$ with the tolerance

$\|\Pi_{X^{I}_{j}}Le_{j}\|^{2}_{\infty,X^{I}_{j}}+\tilde{\tilde{s}}_{j}^{-1}\|\Pi_{X^{B}_{j}}e_{j}\|^{2}_{\infty,X^{B}_{j}}\leq
C\delta_{j}^{-2\sigma}h_{j}^{2(\sigma-2-d/2)}\|e_{j-1}\|^{2}_{W^{\sigma,2}(\Omega)},$
(33)

for $j=1,2,\ldots$. If the testing discretizations is finer than the trial
discretization and satisfies condition (28), then there exists a constant
$C>0$ such that

$\|e_{j}\|_{W^{\sigma,2}(\Omega)}\leq
C\delta_{j}^{-\sigma}h_{j}^{-(2+d/2)}\|e_{j-1}\|_{W^{\sigma,2}(\Omega)}.$ (34)

######  Proof 5.2.

From Lemma 4.1, Lemma 2.1, Lemma 3.6, Lemma 4.3, and Lemma 4.5, we obtain

$\displaystyle\|e_{j}\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle=\|e_{j-1}-v_{j}\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq\|e_{j-1}-I_{j}e_{j-1}\|_{W^{\sigma,2}(\Omega)}+\|I_{j}e_{j-1}-v_{j}\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta_{j}^{-\sigma}\|e_{j-1}\|_{W^{\sigma,2}(\Omega)}+\|E(I_{j}e_{j-1}-v_{j})\|_{W^{\sigma,2}(\mathbb{R}^{d})}$
$\displaystyle\leq
C\delta_{j}^{-\sigma}\|e_{j-1}\|_{W^{\sigma,2}(\Omega)}+Ch_{j}^{-\sigma}\|E(I_{j}e_{j-1}-v_{j})\|_{L^{2}(\mathbb{R}^{d})}$
$\displaystyle\leq
C\delta_{j}^{-\sigma}\|e_{j-1}\|_{W^{\sigma,2}(\Omega)}+Ch_{j}^{-\sigma}\|I_{j}e_{j-1}-v_{j}\|_{L^{2}(\Omega)}$
$\displaystyle\leq
C\delta_{j}^{-\sigma}\|e_{j-1}\|_{W^{\sigma,2}(\Omega)}+C\delta_{j}^{-\sigma}h_{j}^{-\sigma}h_{j}^{\sigma-2-d/2}\|e_{j-1}\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta_{j}^{-\sigma}h_{j}^{-(2+d/2)}\|e_{j-1}\|_{W^{\sigma,2}(\Omega)}.$

We are now in the position to prove convergence of the multilevel unsymmetric
collocation for the equations (3)-(4).

######  Theorem 5.3.

(Convergence of multilevel unsymmetric collocation) Let
$\Omega\subseteq\mathbb{R}^{d}$ be a bounded domain has a $C^{k,s}-$boundary
with $s\in[0,1)$. Let the trial data $Y_{j}$ with the fill distance $h_{j}$
and the testing data $X_{j}$ with the fill distance $s_{j}$ both be quasi-
uniform for $j=1,2,\ldots$. Let $\sigma=k+s$, $k=\lfloor\sigma\rfloor>d/2+2$.
Let $u\in W^{\sigma,2}(\Omega)$ be the solution of (3)-(4). Suppose $v_{j}\in
W_{j}$ are the local correction decided by Algorithm 5. Assume that (31)-(32)
can be solved by $v_{j}$ with the tolerance (33). Assume that $\delta_{j}$,
$h_{j}$ satisfy the relations:

$\delta_{j}=h_{j-1},\quad h_{j}=\mu
h_{j-1}^{\frac{2\sigma}{\sigma-2-d/2}},\quad j=1,2,\ldots.$ (35)

with appropriate $h_{0}$ and $0<\mu<1$. And assume the constant $\mu$ has been
chosen sufficiently small such that

$\alpha:=C\mu^{\sigma-2-d/2}<1.$

If the testing discretizations is finer than the trial discretization and
satisfies condition (28), then there exists a constant $C>0$ such that

$\|u-u_{k}\|_{L^{2}(\Omega)}\leq C\alpha^{k}\|u\|_{W^{\sigma,2}(\Omega)}.$

######  Proof 5.4.

First, we establish the error genetic relationship from $j$ level to $j-1$
level. The technical process is similar to the proofs in Chernih & Le Gia
(2014); Farrell & Wendland (2013); Wendland (2010, 2018).

$\displaystyle\|Ee_{j}\|^{2}_{\Phi_{j+1}}$
$\displaystyle=\int_{\mathbb{R}^{d}}\frac{|\widehat{Ee_{j}}(\bm{\omega})|^{2}}{\widehat{\Phi_{j+1}}(\bm{\omega})}d\bm{\omega}=\int_{\mathbb{R}^{d}}\frac{|\widehat{Ee_{j}}(\bm{\omega})|^{2}}{\widehat{\Phi}(\delta_{j+1}\bm{\omega})}d\bm{\omega}$
$\displaystyle\leq
C\int_{\mathbb{R}^{d}}|\widehat{Ee_{j}}(\bm{\omega})|^{2}(1+\delta_{j+1}^{2}\|\bm{\omega}\|_{2}^{2})^{\sigma}d\bm{\omega}$
$\displaystyle\leq
C\int_{\|\bm{\omega}\|_{2}\leq\frac{1}{\delta_{j+1}}}|\widehat{Ee_{j}}(\bm{\omega})|^{2}(1+\delta_{j+1}^{2}\|\bm{\omega}\|_{2}^{2})^{\sigma}d\bm{\omega}$
$\displaystyle\quad+C\int_{\|\bm{\omega}\|_{2}\geq\frac{1}{\delta_{j+1}}}|\widehat{Ee_{j}}(\bm{\omega})|^{2}(1+\delta_{j+1}^{2}\|\bm{\omega}\|_{2}^{2})^{\sigma}d\bm{\omega}$
$\displaystyle=:CI_{1}+CI_{2}.$

For the first term on the right-hand side, we use Lemma 2.1, the convergence
of one-level unsymmetric collocation, Lemma 3.2, and the variable relationship

$\delta^{-4\sigma}_{j}h^{2(\sigma-2-d/2)}_{j}=h_{j-1}^{-4\sigma}h_{j}^{2(\sigma-2-d/2)}=\mu^{2(\sigma-2-d/2)},$

we obtain

$\displaystyle I_{1}$ $\displaystyle\leq
2^{\sigma}\int_{\|\bm{\omega}\|_{2}\leq\frac{1}{\delta_{j+1}}}|\widehat{Ee_{j}}(\bm{\omega})|^{2}d\bm{\omega}\leq
2^{\sigma}\int_{\mathbb{R}^{d}}|\widehat{Ee_{j}}(\bm{\omega})|^{2}d\bm{\omega}$
$\displaystyle=2^{\sigma}\|Ee_{j}\|^{2}_{L^{2}(\mathbb{R}^{d})}\leq
C\|e_{j}\|^{2}_{L^{2}(\Omega)}$ $\displaystyle\leq
C\delta^{-2\sigma}_{j}h^{2(\sigma-2-d/2)}_{j}\|e_{j-1}\|^{2}_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta^{-2\sigma}_{j}h^{2(\sigma-2-d/2)}_{j}\|Ee_{j-1}\|^{2}_{W^{\sigma,2}(\mathbb{R}^{d})}$
$\displaystyle\leq
C\delta^{-4\sigma}_{j}h^{2(\sigma-2-d/2)}_{j}\|Ee_{j-1}\|^{2}_{\Phi_{j}}$
$\displaystyle\leq C\mu^{2(\sigma-2-d/2)}\|Ee_{j-1}\|^{2}_{\Phi_{j}}$

For the second term on the right-hand side, we use Lemma 2.1, Lemma 5.1, Lemma
3.2, and the variable relationship

$\delta_{j+1}^{2\sigma}\delta_{j}^{-4\sigma}h_{j}^{-(4+d)}=h_{j}^{2\sigma}h_{j-1}^{-4\sigma}h_{j}^{-(4+d)}=\mu^{2(\sigma-2-d/2)},$

we obtain

$\displaystyle I_{2}$ $\displaystyle\leq
2^{\sigma}\delta_{j+1}^{2\sigma}\int_{\|\bm{\omega}\|_{2}\geq\frac{1}{\delta_{j+1}}}|\widehat{Ee_{j}}(\bm{\omega})|^{2}\|\bm{\omega}\|_{2}^{2\sigma}d\bm{\omega}$
$\displaystyle\leq
2^{\sigma}\delta_{j+1}^{2\sigma}\int_{\mathbb{R}^{d}}|\widehat{Ee_{j}}(\bm{\omega})|^{2}(1+\|\bm{\omega}\|_{2}^{2})^{\sigma}d\bm{\omega}$
$\displaystyle\leq
2^{\sigma}\delta_{j+1}^{2\sigma}\|Ee_{j}\|^{2}_{W^{\sigma,2}(\mathbb{R}^{d})}$
$\displaystyle\leq
C\delta_{j+1}^{2\sigma}\|e_{j}\|^{2}_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta_{j+1}^{2\sigma}\delta_{j}^{-2\sigma}h_{j}^{-(4+d)}\|e_{j-1}\|^{2}_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta_{j+1}^{2\sigma}\delta_{j}^{-4\sigma}h_{j}^{-(4+d)}\|Ee_{j-1}\|^{2}_{\Phi_{j}}$
$\displaystyle\leq C\mu^{2(\sigma-2-d/2)}\|Ee_{j-1}\|^{2}_{\Phi_{j}}.$

From the upper bounds of $I_{1},I_{2}$, choosing $\alpha=C\mu^{\sigma-2-d/2}$
we have

$\|Ee_{j}\|_{\Phi_{j+1}}\leq
C\mu^{\sigma-2-d/2}\|Ee_{j-1}\|_{\Phi_{j}}=\alpha\|Ee_{j-1}\|_{\Phi_{j}}.$
(36)

Then we obtain

$\displaystyle\|u-u_{k}\|_{L^{2}(\Omega)}$
$\displaystyle=\|e_{k}\|_{L^{2}(\Omega)}=\|e_{k-1}-v_{k}\|_{L^{2}(\Omega)}$
$\displaystyle\leq\|e_{k-1}-I_{k}e_{k-1}\|_{L^{2}(\Omega)}+\|I_{k}e_{k-1}-v_{k}\|_{L^{2}(\Omega)}$
$\displaystyle\leq
C\delta_{k}^{-\sigma}h_{k}^{\sigma}\|e_{k-1}\|_{W^{\sigma,2}(\Omega)}+C\delta_{k}^{-\sigma}h_{k}^{\sigma-2-d/2}\|e_{k-1}\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta_{k}^{-\sigma}h_{k}^{\sigma-2-d/2}\|e_{k-1}\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta_{k}^{-\sigma}h_{k}^{\sigma-2-d/2}\|Ee_{k-1}\|_{W^{\sigma,2}(\mathbb{R}^{d})}$
$\displaystyle\leq
C\delta_{k}^{-2\sigma}h_{k}^{\sigma-2-d/2}\|Ee_{k-1}\|_{\Phi_{k}}$
$\displaystyle\leq C\alpha\|Ee_{k-1}\|_{\Phi_{k}}.$

Then using (36) $k$ times, we have

$\|u-u_{k}\|_{L^{2}(\Omega)}\leq C\alpha\|Ee_{k-1}\|_{\Phi_{k}}\leq\ldots\leq
C\alpha^{k}\|Eu\|_{\Phi_{1}}\leq C\alpha^{k}\|u\|_{W^{\sigma,2}(\Omega)}.$

##  6 Numerical example

###  6.1 Computational aspects

By using the two testing operators $\Pi_{X^{I}}$ and $\Pi_{X^{B}}$, the linear
systems (20)-(21) can be rewritten as

$\displaystyle\Pi_{X^{I}}Ls_{u}$ $\displaystyle=\Pi_{X^{I}}f=\Pi_{X^{I}}Lu,$
(37) $\displaystyle\Pi_{X^{B}}s_{u}$
$\displaystyle=\Pi_{X^{B}}g=\Pi_{X^{B}}u.$ (38)

We denote the residual as $r=\left(\begin{array}[]{c}r_{I}\\\ r_{B}\\\
\end{array}\right)$, with

$r_{I}=\Pi_{X^{I}}L(u-s_{u}),\quad r_{B}=\Pi_{X^{B}}(u-s_{u}).$

To ensure the assumption (26), we need to bound $r_{I}$ and $r_{B}$
respectively. That is

$\|r_{I}\|_{\infty,X^{I}}\leq
C\delta^{-\sigma}h_{Y}^{\sigma-2-d/2}\|u\|_{W^{\sigma,2}(\Omega)},$
$\displaystyle\|r_{B}\|_{\infty,X^{I}}$ $\displaystyle\leq
Cs_{B}^{1/2}\delta^{-\sigma}h_{Y}^{\sigma-2-d/2}\|u\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
Cs_{X}^{1/2}\delta^{-\sigma}h_{Y}^{\sigma-2-d/2}\|u\|_{W^{\sigma,2}(\Omega)}$
$\displaystyle\leq
C\delta^{-\sigma}h_{Y}^{\sigma/(2\sigma-4)+\sigma-2-d/2}\|u\|_{W^{\sigma,2}(\Omega)},$

where we used the condition (24) for the proof of the second inequality. Thus,
we only ask the residual to meet

$\|r\|_{\infty,X}\leq
C\delta^{-\sigma}h_{Y}^{\sigma/(2\sigma-4)+\sigma-2-d/2}\|u\|_{W^{\sigma,2}(\Omega)}.$
(39)

The condition (33) is the same as (26), but it needs to be satisfied at level
$j$.

We consider the following Poisson problem with Dirichlet boundary conditions:

$\displaystyle\triangle u(x,y)$ $\displaystyle=$
$\displaystyle-\frac{5}{4}\pi^{2}\sin(\pi x)\cos(\frac{\pi
y}{2}),\quad(x,y)\in\Omega=(0,1)^{2},$ $\displaystyle u(x,y)$ $\displaystyle=$
$\displaystyle\sin(\pi x),\quad(x,y)\in\Gamma_{1},$ $\displaystyle u(x,y)$
$\displaystyle=$ $\displaystyle 0,\quad(x,y)\in\Gamma_{2},$

where $\Gamma_{1}=\\{(x,y):0\leq x\leq 1,y=0\\}$ and
$\Gamma_{2}=\partial\Omega\setminus\Gamma_{1}$. The exact solution of the
problem is given by

$u(x,y)=\sin(\pi x)\cos(\frac{\pi y}{2}).$

In our experiments, Wendland’s compactly supported function
$\phi(r)=(1-r)_{+}^{8}(32r^{3}+25r^{2}+8r+1)\in C^{6}(\mathbb{R}^{2})$ is used
to construct trial spaces. This function can generate Sobolev space
$W^{\sigma,2}(\mathbb{R}^{2})$ with $\sigma=4.5$. For the every non square
linear systems

$Ac=b$

produced by RBF discretization, we use the conjugate gradient method (CG) to
solve it by multiplying the left and right sides by $A^{T}$. Simple
calculation shows that the tolerance of CG is about $h_{Y}^{2.4}$.

###  6.2 Numerical results

Although Fasshauer (2007) has provided some numerical examples to show the
performance of one-level and multilevel unsymmetric collocation, we will
restrict ourselves here to nonsquare collocation because of Hon & Schaback
(2001). Computations were performed on a laptop with 1.3 GHz Intel Core
i7-1065G7 processor, using MATLAB running in the Windows 10 operating system.

We choose the point sets to be on nested uniform grids and create additional
equally spaced $4(\sqrt{N}-1)$ boundary points. To ensure the conditions (24)
or (28), the collocation is implemented on the next fine point sets. For the
one-level collocation case, we fix $\delta=2.0$. For the multilevel case, by
using the conditions of the Theorem 5.3 we use a variable

$\delta_{j}=v\left(\frac{h_{j}}{\mu}\right)^{\frac{\sigma-2-d/2}{2\sigma}},$

but let the meshsize have a linear relationship $h_{j}=\mu h_{j-1},\mu=0.5$ as
the same as the one-level case. In order to be consistent with the experiments
in Farrell & Wendland (2013), we select $v=2.4$.

The numerical results are shown in Tables 1,2, where we have given
$L^{2}(\Omega)$ error discretized on a $10000\times 10000$ grid, the producing
order, the tolerance determined by (26) or (33), and the number of CG
iterations. It seems that we can get the expected approximation order. These
results differ from Table 6.2 in Farrell & Wendland (2013) and Table 41.3 in
Fasshauer (2007), because we are implementing nonsquare collocation under the
conditions (24) or (28), and the tolerance (26) or (33).

Table 1: One-level unsymmetric collocation: fixed $\delta=2.0$, expected order $\approx 1.5$. Level | $\delta$ | $N$ | $L^{2}(\Omega)$ | Order | Tolerance | CG
---|---|---|---|---|---|---
1 |  | 2.0 |  | 9 |  | 4. | 936e-01 |  |  | 0. | 1895 | 6
2 |  | 2.0 |  | 25 |  | 3. | 623e-01 | 0.446 |  | 0. | 0359 | 20
3 |  | 2.0 |  | 81 |  | 9. | 849e-02 | 1.879 |  | 0. | 0068 | 297
4 |  | 2.0 |  | 289 |  | 2. | 830e-02 | 1.799 |  | 0. | 0013 | 8241
Table 2: Multilevel unsymmetric collocation: variable $\delta_{j}=v\left(\frac{h_{j}}{\mu}\right)^{\frac{\sigma-2-d/2}{2\sigma}}$, $v=2.4$, expected order $\approx 1.5$. Level | $\delta_{j}$ | $N$ | $L^{2}(\Omega)$ | Order | Tolerance | CG
---|---|---|---|---|---|---
1 |  | 2.4 |  | 9 |  | 4. | 334e-01 |  |  | 0. | 1895 | 6
2 |  | 2.1 |  | 25 |  | 3. | 028e-01 | 0.517 |  | 0. | 0359 | 13
3 |  | 1.9 |  | 81 |  | 1. | 076e-01 | 1.493 |  | 0. | 0068 | 236
4 |  | 1.7 |  | 289 |  | 2. | 897e-02 | 1.893 |  | 0. | 0013 | 9896

##  7 Conclusions

We proved convergence of one-level and multilevel unsymmetric collocation for
second order elliptic boundary value problems. The main theoretical results
are Theorem 4.7 and Theorem 5.3. These theoretical results are obtained with
the help of the regularity theory of the solution (Lemmas 2.2-2.5), the norm
equivalence between Sobolev space $W^{\sigma,2}(\mathbb{R}^{d})$ and the
reproducing kernel Hilbert space generated by $\Phi_{\delta}$ (Lemma 3.2), the
inverse inequality which is satisfied by the functions from kernel-based trial
space $W_{\delta}$ (Lemma 3.6), the sampling inequality (Lemma 3.9). Although
we obtain $L^{2}$ error of multilevel unsymmetric collocation, it is currently
not yet optimal and deserve refinement. The condition (35) is too restrictive,
which is not conducive to numerical calculation. In fact, it is caused by the
counteracting term $h_{j}^{-(2+d/2)}$ in error transfer relations (34). It
becomes the price we have to pay for the proof of convergence in multilevel
case. The future proof will eliminate the counteracting term by avoiding the
use of (18).

Many papers have performed a large number of numerical experiments to verify
the effectiveness of one-level unsymmetric collocation. Fasshauer’s numerical
experiments show that multilevel unsymmetric collocation seems to have
convergence in the absence of the condition (35) (see Fasshauer, 2007), when
the experiments were carrying out under the condition of testing side has the
same data sites with the trial side. But we still need to consider the
nonsquare system when implementing unsymmetric collocation because of Hon &
Schaback (2001).

Many possibilities for enhancement and extension need to be further studied in
the future:

(1) The convergence results of multilevel unsymmetric collocation still need
improvement by proving better Lemma 5.1. We predict that the ideal result may
be:

$\delta_{j}\approx\left(\frac{h_{j}}{\mu}\right)^{1-\frac{2+d/2}{\sigma}},\quad
h_{j}=\mu h_{j-1}.$

(2) Observe and prove the condition number of $A^{T}A$ produced by nonsquare
collocation matrix $A$. We are designing several preconditioners and iterative
solvers for solving nonsquare systems obtained by unsymmetric discretization.
(see Liu & Xu, 2022).

(3) Perform large-scale numerical experiments and compare the observed
convergence order with the theoretical ones of the paper.

## Declarations

Funding: The research of the first author was supported by Natural Science
Foundations of China (No.12061057). The research of the second author was
supported by the Fourth Batch of the Ningxia Youth Talents Supporting Program
(No.TJGC2019012).
Conflicts of Interests: The authors declare no conflicts of interest.

## References

  * Adams & Fournier (2003) Adams, R. A., & Fournier, P. (2003)  _Sobolev Spaces_. Pure and Applied Mathematics, 2nd ed.; Academic Press: New York, NY, USA
  * Chen _et al._ (2002) Chen, C.S., Ganesh, M., Golberg, M.A., & Cheng, A.H.D. (2002)  Multilevel compact radial functions based computational schemes for some elliptic problems.  _Comput. Math. Appl._ , 43, 359–378.
  * Chernih & Le Gia (2012) Chernih, A., & Le Gia, Q.T. (2012)  Multiscale methods with compactly supported radial basis functions for elliptic partial differential equations on bounded domains.  _ANZIAM J._ , 54, C137–C152.
  * Chernih & Le Gia (2013) Chernih, A., & Le Gia, Q.T. (2013)  Multiscale methods with compactly supported radial basis functions for the Stokes problem on bounded domains.  _Adv. Comput. Math._ , 42, 1187–1208.
  * Chernih & Le Gia (2014) Chernih, A., & Le Gia, Q.T. (2014)  Multiscale methods with compactly supported radial basis functions for Galerkin approximation of elliptic PDEs.  _IMA J. Numer. Anal._ , 34, 569–591.
  * Farrell & Wendland (2013) Farrell, P., & Wendland, H. (2013)  RBF multiscale collocation for second order elliptic boundary value problems.  _SIAM J. Numer. Anal._ , 51, 2403–2425.
  * Farrell _et al._ (2017) Farrell, P., Gillow, K., & Wendland, H. (2017)  Multilevel interpolation of divergence-free vector fields.  _IMA J. Numer. Anal._ , 37, 332–353.
  * Fasshauer (1997) Fasshauer, G.E. (1997)  Solving partial differential equations by collocation with radial basis functions. In: M$\acute{\textrm{e}}$haut$\acute{\textrm{e}}$, A.L., Rabut, C., & Schumaker, L.L. (eds.) Surface Fittingand Multiresolution Methods, pp. 131–138. Vanderbilt University Press, Nashville.
  * Fasshauer (1999) Fasshauer, G.E. (1999)  Solving differential equations with radial basis functions: multilevel methods and smoothing.  _Adv. Comput. Math._ , 11, 139–159.
  * Fasshauer (2007) Fasshauer, G. E. (2007)  _Meshfree Approximation Methods with MATLAB_. Interdisciplinary Mathematical Sciences, vol. 6. Singapore: World Scientific Publishing Co.
  * Floater& Iske (1996) Floater, M. S., & Iske, A. (1996)  Multistep scattered data interpolation using compactly supported radial basis functions.  _J. Comput. Appl. Math._ , 73, 65–78.
  * Franke & Schaback (1998) Franke, C., & Schaback, R. (1998)  Convergence order estimates of meshless collocation methods using radial basis functions.  _Adv. Comput. Math._ , 8, 381–399.
  * Giesl & Wendland (2007) Giesl, P., & Wendland, H. (2007)  Meshless collocation: Error estimates with application to dynamical systems.  _SIAM J. Numer. Anal._ , 45, 1723–1741.
  * Gilbarg & Trudinger (2001) Gilbarg, D., & Trudinger, N. S. (2001)  _Elliptic Partial Differential Equations of Second Order_. Grundlehren Math. Wiss. 224, Springer, Berlin.
  * Hon & Schaback (2001) Hon, Y.C., & Schaback, R. (2001)  On unsymmetric collocation by radial basis functions.  _J. Appl. Math. Comput._ , 119, 177–186.
  * Kansa (1986) Kansa E. J. (1986)  Application of Hardy’s multiquadric interpolation to hydrodynamics.  in Proceedings of the 1986 Annual Simulations Conference, Vol. 4, San Diego, CA, 111–117.
  * Le Gia _et al._ (2010) Le Gia, Q. T., Sloan, I. H., & Wendland, H. (2010)  Multiscale analysis in Sobolev spaces on the sphere.  _SIAM J. Numer. Anal._ , 48, 2065–2090.
  * Le Gia _et al._ (2012) Le Gia Q. T., Sloan I. H., & Wendland H. (2012)  Multiscale RBF collocation for solving PDEs on spheres.  _Numer. Math._ , 121, 99–125.
  * Liu & Xu (2022) Liu, Z., & Xu Q. (2022)  Preconditioning and fast solvers of unsymmetric collocation for second order elliptic boundary value problems. In preparation.
  * Narcowich _et al._ (2006) Narcowich, F.J., Ward, J.D., & Wendland, H. (2006)  Sobolev error estimates and a Bernstein inequality for scattered data interpolation via radial basis functions.  _Constr. Approx._ , 24, 175–186.
  * Rieger _et al._ (2010) Rieger, C., Schaback, R., & Zwicknagl, B. (2010)  Sampling and stability. Mathematical Methods for Curves and Surfaces. Lecture Notes in Computer Science, vol. 5862, pp. 347–369. Springer, New York.
  * Schaback (2007) Schaback, R. (2007)  Convergence of unsymmetric kernel-based meshless collocation methods.  _SIAM J. Numer. Anal._ , 45(1), 333–351.
  * Schaback (2010) Schaback, R. (2010)  Unsymmetric meshless methods for operator equations.  _Numer. Math._ , 114, 629–651.
  * Schaback (2022) Schaback, R. (2022)  Private communication.
  * Townsend & Wendland (2013) Townsend, A., & Wendland, H. (2013)  Multiscale analysis in Sobolev spaces on bounded domains with zero boundary values.  _IMA J. Numer. Anal._ , 33, 1095–1114.
  * Wendland (1995) Wendland, H. (1995)  Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree.  _Adv. Comput. Math._ , 4, 389–396.
  * Wendland (1998) Wendland, H. (1998)  Meshless Galerkin methods using radial basis functions.  _Math. Comput._ , 68, 1521–131.
  * Wendland & Rieger (2005) Wendland, H., & Rieger, C. (2005)  Approximate interpolation with applications to selecting smoothing parameters.  _Numer. Math._ , 101, 729–748.
  * Wendland (2010) Wendland, H. (2010)  Multiscale analysis in Sobolev spaces on bounded domains.  _Numer. Math._ , 116, 493–517.
  * Wendland (2017) Wendland, H. (2017)  Multiscale radial basis functions. In: Pesenson, I., Gia, Q.T.L., Mayeli, A., Mhaskar, H., & Zhou, D.X. (eds.) Frames and Other Bases in Abstract and Function Spaces – Novel Methods in Harmonic Analysis, vol. 1, pp. 265–299. Birkh$\ddot{\textrm{a}}$user, Cham.
  * Wendland (2018) Wendland H. (2018)  Solving partial differential equations with multiscale radial basis functions,” in Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan, Dick J., Kuo F. Y., & Wozniakowski H., (eds.), Springer, Berlin, Germany, pp. 1191–1213.
  * Wloka (1987) Wloka, J. (1987)  _Partial Differential Equations_. Cambridge University Press, Cambridge, UK.
  * Wu (1992) Wu, Z. (1992)  Hermite-Birkhoff interpolation of scattered data by radial basis functions.  _Approx. Theory Appl._ , 8, 1–10.
  * Wu (1995) Wu, Z. (1995)  Compactly supported positive definite radial functions.  _Adv. Comput. Math._ , 4, 283–292.