# Notes on Finite Element Discretization for a Model Convection-Diffusion
Problem

Constantin Bacuta  University of Delaware, Mathematical Sciences, 501 Ewing
Hall, Newark, DE 19716<EMAIL_ADDRESS>,  Daniel Hayes  University of
Delaware, Department of Mathematics, 501 Ewing Hall 19716<EMAIL_ADDRESS>and  Tyler O’Grady  University of Delaware, Department of Mathematics, 501
Ewing Hall 19716  togrady@@udel.edu

###### Abstract.

We present recent finite element numerical results on a model convection-
diffusion problem in the singular perturbed case when the convection term
dominates the problem. We compare the standard Galerkin discretization using
the linear element with a saddle point least square discretization that uses
quadratic test functions, trying to control and explain the non-physical
oscillations of the discrete solutions. We also relate the up-winding Petrov-
Galerkin method and the stream-line diffusion discretization method, by
emphasizing the resulting linear systems and by comparing appropriate error
norms. Some results can be extended to the multidimensional case in order to
come up with efficient approximations for more general singular perturbed
problems, including convection dominated models.

###### Key words and phrases:

least squares, saddle point systems, mixed methods, optimal test norm, Uzawa
conjugate gradient, preconditioning

###### 2000 Mathematics Subject Classification:

74S05, 74B05, 65N22, 65N55

The work was supported by NSF-DMS 2011615

##  1\. Introduction

We consider the model singularly perturbed convection-reaction-diffusion
problem: Find $u$ defined on $\Omega$ such that

(1.1) $\left\\{\begin{array}[]{rcl}-\varepsilon\,\Delta u+b\cdot\nabla u+cu=\
f&\mbox{in}\ \ \ \Omega,\\\ u=\ 0&\mbox{on}\ \partial\Omega,\\\
\end{array}\right.$

for $\varepsilon>0$, $\operatorname{div}b=0$, and $c(x)\geq c_{0}>0$ on
$\Omega$, a bounded domain in $\Omega\subset\mathbb{R}^{d}$.

A variational formulation of (1.1) is: Find $u\in H_{0}^{1}(\Omega)$ such that

(1.2) ${\varepsilon\,(\nabla u,\nabla v)+(b\cdot\nabla
u,v)+(cu,v)}={(f,v)}\quad\hbox{ for all }v\in H^{1}_{0}(\Omega).$

The simplified one dimensional version of (1.1) with $b=1$ and $c=0$ is: Find
$u=u(x)$ on $[0,1]$ such that

(1.3)
$\begin{cases}-\varepsilon\,u^{\prime\prime}(x)+u^{\prime}(x)=f(x),&0<x<1\\\
u(0)=0,\ u(1)=0.\end{cases}$

We will assume that the problem reaction is dominated, i.e., $\varepsilon\ll
1$ and $f$ is square integrable on $[0,1]$.

In what follows, we will use the following notation:

$\displaystyle a_{0}(u,v)$
$\displaystyle=\int_{0}^{1}u^{\prime}(x)v^{\prime}(x)\,dx,\ \text{and}\
(f,v)=\int_{0}^{1}f(x)v(x)\,dx,\ \text{and}$ $\displaystyle b(v,u)$
$\displaystyle=\varepsilon\,a_{0}(u,v)+(u^{\prime},v)\ \text{for all}\ u,v\in
V:=H^{1}_{0}(0,1).$

The variational formulation of (1.3) is: Find $u\in V:=H_{0}^{1}(0,1)$ such
that

(1.4) $b(v,u)=(f,v),\ \text{for all}\ v\in V.$

The PDE model (1.3), and specially its multi-dimensional extension (1.1),
arise in solving practical problems such as heat transfer problems in thin
domains, as well as when using small step sizes in implicit time
discretizations of parabolic reaction diffusion type problems, see e.g., [27]
and the references in [29]. The solutions to these problems are characterized
by boundary layers [30], which pose numerical challenges due to the
$\varepsilon$-dependence of the error estimates and of the stability
constants.

The goal of this work is to illustrate some challenges of the finite element
discretization of the one dimensional model reaction diffusion problem and to
emphasize on the mixed formulation and discretization advantages. We hope that
ideas, concepts, or methods we present, can be extended to the the
multidimensional case of convection dominated problems of type (1.1).

Saddle Point Least Squares (SPLS) discretizatrion as presented [3, 4, 5, 11,
19, 7] were used before for singularly perturbed problems in order to improve
the stability and the rate of convergence of the discrete solutions in special
norms. The SPLS approach uses an auxiliary variable that represents the
residual of the original variational formulation on the test space and another
simple equation involving the residual variable that leads to a (square)
symmetric saddle point system that is more suitable for analysis and
discretization. The idea is similar to the Lagrange multiplier approach, with
the exception that the Lagrange multiplier here is the variable of interest.
The SPLS method or its variants, such as the Discontinuous Petrov–Galerkin
(DPG) method, was used efficiently for other mixed variational problems, see
e.g., [10, 19, 23, 26]. Many of the aspects regarding SPLS formulation are
common to both the DPG approach [16, 18, 21, 22, 24, 20] and the SPLS approach
developed in [3, 4, 5, 11].

The paper is organized as follows. We review the main ideas of the SPLS
approach in an abstract general setting in Section 2. In Section 3, we present
the SPLS discretization together with some general error approximation
results. We include here a new approximation result for the Petrov-Galerkin
case when the norm on the continuous and discrete test spaces could be
different. Section 4 deals with a review of four know discretization methods
that have $C^{0}-P^{1}$ as trial space and can be viewed as mixed methods. We
illustrate with plots of the discrete solutions the non-physical oscillation
phenomena for the standard and SPLS discretization and emphasize the strong
connection between a Petrov-Galerkin (PG) and the stream-line diffusion (SD)
methods. Numerical results are presented in Section 5.

##  2\. The notation and the general SPLS approach

We now review the main ideas and concepts for the SPLS method for a general
mixed variational formulation. We follow the Saddle Point Least Squares (SPLS)
terminology that was introduced in in [4, 5, 3, 11].

###  2.1. The abstract variational formulation at the continuous level

We consider the (mixed) Petrov-Galerkin formulation of the more general
abstract formulation of (1.3): Find $u\in Q$ such that

(2.1) $b(v,u)={\langle}F,v{\rangle},\ \text{for all}\ v\in V.$

where $Q$ and $V$ are separable Hilbert spaces and $F$ is a continuous linear
functional on $V$. We assume that the inner products $a_{0}(\cdot,\cdot)$ and
$(\cdot,\cdot)_{{Q}}$ induce the norms
$|\cdot|_{V}=|\cdot|=a_{0}(\cdot,\cdot)^{1/2}$ and
$\|\cdot\|_{Q}=\|\cdot\|=(\cdot,\cdot)_{Q}^{1/2}$. We denote the dual of $V$
by $V^{*}$ and the dual pairing on $V^{*}\times V$ by
$\langle\cdot,\cdot\rangle$. We assume that $b(\cdot,\cdot)$ is a continuous
bilinear form on $V\times Q$ satisfying the $\sup-\sup$ condition

(2.2) $\overset{}{\underset{u\in Q}{\sup}}\ \overset{}{\underset{v\in
V}{\sup}}\ \frac{b(v,u)}{|v|\,\|u\|}=M<\infty,$

and the $\inf-\sup$ condition

(2.3) $\overset{}{\underset{u\in Q}{\inf}}\ \overset{}{\underset{v\in
V}{\sup}}\ \frac{b(v,u)}{|v|\,\|u\|}=m>0.$

With the form $b$, we associate the operators ${\mathcal{B}}:V\to{Q}$ defined
by

$({\mathcal{B}}v,q)_{{Q}}=b(v,q)\,\quad\hbox{ for all }v\in V,q\in Q.$

We define $V_{0}$ to be the kernel of ${\mathcal{B}}$, i.e.,

$V_{0}:=Ker({\mathcal{B}})=\\{v\in V|\ {\mathcal{B}}v=0\\}.$

Under assumptions (2.2) and (2.3), the operator ${\mathcal{B}}$ is a bounded
surjective operator from $V$ to $Q$, and $V_{0}$ is a closed subspace of $V$.
We will also assume that the data $F\in V^{*}$ satisfies the compatibility
condition

(2.4) ${\langle}F,v{\rangle}=0\quad\hbox{ for all }v\in
V_{0}=Ker({\mathcal{B}}).$

The following result describes the well posedness of (2.1) and can be used at
the continuous and discrete levels, see e.g. [1, 2, 14, 15].

######  Proposition 2.1.

If the form $b(\cdot,\cdot)$ satisfies (2.2) and (2.3), and the data $F\in
V^{*}$ satisfies the compatibility condition (2.4), then the problem (2.1) has
unique solution that depends continuously on the data $F$.

It is also known, see e.g., [10, 11, 12, 19] that, under the compatibility
condition (2.4), solving the mixed problem (2.1) reduces to solving a standard
saddle point reformulation: Find $(w,u)\in V\times Q$ such that

(2.5) $\begin{array}[]{lclll}a_{0}(w,v)&+&b(v,u)&=\langle F,v\rangle&\
\quad\hbox{ for all }v\in V,\\\ b(w,q)&&&=0&\ \quad\hbox{ for all }q\in
Q.\end{array}$

In fact, we have that $p$ is the unique solution of (2.1) if and only if
$(w=0,p)$ solves (2.5), and the result remains valid if the form
$a_{0}(\cdot,\cdot)$ in (2.5) is replaced by any other symmetric bilinear form
$a(\cdot,\cdot)$ on $V$ that leads to an equivalent norm on $V$.

##  3\. Saddle point least squares discretization

We will assume next that $V$ and $Q$ are Hilbert spaces with norms and inner
products as defined in Section 2. Let $V_{h}\subset V$ and
${\mathcal{M}}_{h}\subset Q$ be finite dimensional approximation spaces. We
assume the following discrete $\inf-\sup$ condition holds for the pair of
spaces $(V_{h},{\mathcal{M}}_{h})$:

(3.1) $\overset{}{\underset{p_{h}\in{\mathcal{M}}_{h}}{\inf}}\
\overset{}{\underset{v_{h}\in V_{h}}{\sup}}\
\frac{b(v_{h},p_{h})}{|v_{h}|\,\|p_{h}\|}=m_{h}>0.$

As in the continuous case we define

$V_{h,0}:=\\{v_{h}\in V_{h}\,|\,b(v_{h},q_{h})=0,\quad\hbox{ for all
}q_{h}\in{\mathcal{M}}_{h}\\},$

and $F_{h}\in V_{h}^{*}$ to be the restriction of $F$ to $V_{h}$, i.e.,
$\langle F_{h},v_{h}\rangle:=\langle F,v_{h}\rangle$ for all $v_{h}\in V_{h}$.
In the case $V_{h,0}\subset V_{0}$, the compatibility condition (2.4) implies
the discrete compatibility condition

$\langle F,v_{h}\rangle=0\quad\hbox{ for all }v_{h}\in V_{h,0}.$

Hence, under assumption (3.1), the PG problem of finding
$u_{h}\in{\mathcal{M}}_{h}$ such that

(3.2) $b(v_{h},u_{h})=\langle F,v_{h}\rangle,\ v_{h}\in V_{h}$

has a unique solution. In general, we might not have $V_{h,0}\subset V_{0}$.
Consequently, even though the continuous problem (2.1) is well posed, the
discrete problem (3.2) might not be well-posed. However, if the form
$b(\cdot,\cdot)$ satisfies (3.1), then the problem of finding
$(w_{h},p_{h})\in V_{h}\times{\mathcal{M}}_{h}$ satisfying

(3.3) $\begin{array}[]{lclll}a_{0}(w_{h},v_{h})&+&b(v_{h},p_{h})&=\langle
f,v_{h}\rangle&\ \quad\hbox{ for all }v_{h}\in V_{h},\\\ b(w_{h},q_{h})&&&=0&\
\quad\hbox{ for all }q_{h}\in{\mathcal{M}}_{h},\end{array}$

does have a unique solution. We call the component $u_{h}$ of the solution
$(w_{h},u_{h})$ of (3.3) the saddle point least squares approximation of the
solution $u$ of the original mixed problem (2.1).

The following error estimate for $\|u-u_{h}\|$ was proved in [11].

######  Theorem 3.1.

Let $b:V\times Q\to\mathbb{R}$ satisfy (2.2) and (2.3) and assume that ${F}\in
V^{*}$ is given and satisfies (2.4). Assume that $u$ is the solution of (2.1)
and $V_{h}\subset V$, ${{\mathcal{M}}}_{h}\subset Q$ are chosen such that the
discrete $\inf-\sup$ condition (3.1) holds. If $\left(w_{h},u_{h}\right)$ is
the solution of (3.3), then the following error estimate holds:

(3.4) $\frac{1}{M}|w_{h}|\leq\|u-u_{h}\|\leq\frac{M}{m_{h}}\
\overset{}{\underset{q_{h}\in{\mathcal{M}}_{h}}{\inf}}\|u-q_{h}\|.$

The considerations made so far in this section remain valid if the form
$a_{0}(\cdot,\cdot)$, as an inner product on $V_{h}$, is replaced by another
inner product $a(\cdot,\cdot)$ which gives rise to an equivalent norm on
$V_{h}$.

##  4\. Discretization with $C^{0}-P^{1}$ trial space for the 1D Convection
reaction problem

In this section we review standard finite element discretizations of (1.3) and
emphasize the ways the corresponding linear system relate. The concepts
presented in this section are focused on uniform mesh discretization, but most
of the results can be easily extended to non-uniform meshes.

We divide the interval $[0,1]$ into $n$ equal length subintervals, using the
nodes $0=x_{0}<x_{1}<\cdots<x_{n}=1$ and denote
$h:=x_{j}-x_{j-1},j=1,2,\cdots,n$. For the above uniform distributed notes on
$[0,1]$, we define the corresponding discrete space ${\mathcal{M}}_{h}$ as the
subspace of $Q=H^{1}_{0}(0,1)$, given by

${\mathcal{M}}_{h}=\\{v_{h}\in V\mid v_{h}\text{ is linear on each
}[x_{j},x_{j+1}]\\},$

i.e., ${\mathcal{M}}_{h}$ is the space of all piecewise linear continuous
functions with respect to the given nodes, that are zero at $x=0$ and $x=1$.
We consider the nodal basis $\\{\varphi_{j}\\}_{j=1}^{n-1}\subset V_{h}$ with
the standard defining property $\varphi_{i}(x_{j})=\delta_{ij}$.

###  4.1. Standard Linear discretization

We couple the above discrete trial space with a discrete test space
$V_{h}:={\mathcal{M}}_{h}$. Thus, the standard (linear) discrete variational
formulation of (1.4) is: Find $u_{h}\in{\mathcal{M}}_{h}$ such that

(4.1) $b(v_{h},u_{h})=(f,v_{h}),\ \text{for all}\ v_{h}\in V_{h}.$

We look for $u_{h}\in V_{h}$ with the nodal basis expansion

$u_{h}:=\sum_{i=1}^{n-1}u_{i}\varphi_{i},\ \text{where}\ \
u_{i}=u_{h}(x_{i}).$

If we consider the test functions $v_{h}=\varphi_{j},j=1,2,\cdots,n-1$ in
(4.1), we obtain the following linear system

(4.2) $\left(\frac{\varepsilon}{h}S+C\right)\,U=F,$

where $U,F\in\mathbb{R}^{n-1}$ and $S,C\in\mathbb{R}^{(n-1)\times(n-1)}$ with:

$U:=\begin{bmatrix}u_{1}\\\ u_{2}\\\ \vdots\\\ u_{n-1}\end{bmatrix},\quad
F:=\begin{bmatrix}(f,\varphi_{1})\\\ (f,\varphi_{2})\\\ \vdots\\\
(f,\varphi_{n-1})\end{bmatrix},\text{and}$ $S:=\begin{bmatrix}2&-1\\\
-1&2&-1\\\ &\ddots&\ddots&\ddots\\\ &&-1&2&-1\\\ &&&-1&2\end{bmatrix},\quad
C:=\frac{1}{2}\begin{bmatrix}0&1\\\ -1&0&1\\\ &\ddots&\ddots&\ddots\\\
&&-1&0&1\\\ &&&-1&0\end{bmatrix}.$

Note that, letting $\varepsilon\to 0$ in (1.4) we obtain the simplified
problem:
Find $w\in H_{0}^{1}(0,1)$ such that

(4.3) $(w^{\prime},v)=(f,v),\ \text{for all}\ v\in V.$

The problem (4.3) has unique solution, if and only if
$\int_{0}^{1}f(x)\,dx=0$. For the case $\int_{0}^{1}f(x)\,dx\neq 0$ we can
consider the reduced problem:
Find $w\in H^{1}(0,1)$ such that

(4.4) $w^{\prime}(x)=f(x)\ \text{for all}\ x\in(0,1),\text{and}\ w(0)=0.$

with the unique solution $w(x)=\int_{0}^{x}f(x)\,dx$.

The corresponding finite element discretization of the simplified problem
(4.3) leads to find $w_{h}:=\sum_{i=1}^{n-1}u_{i}\varphi_{i}$, where

(4.5) $C\,U=F.$

It is interesting to note that, even though (4.3) is not well posed in
general, the system (4.5) decouples into two independent systems, and at least
for $n=2m+1$, it has unique solution. Indeed, by defining $u_{0}=u_{n}=0$,
then for the case $n=2m+1$ we get

(4.6) $\begin{cases}u_{2}-u_{0}&=2(f,\varphi_{1})\\\
u_{4}-u_{2}&=2(f,\varphi_{3})\\\ \vdots\\\
u_{2m}-u_{2m-2}&=2(f,\varphi_{2m-1}),\end{cases}$

and

(4.7) $\begin{cases}u_{3}-u_{1}&=2(f,\varphi_{2})\\\
u_{5}-u_{3}&=2(f,\varphi_{4})\\\ \vdots\\\
u_{2m+1}-u_{2m-1}&=2(f,\varphi_{2m}).\end{cases}$

In this case the systems (4.6) and (4.7) have unique solutions, and can be
solved forward and backward respectively, to get

(4.8) $\begin{cases}u_{2k}&=2\sum_{j=1}^{k}(f,\varphi_{2j-1}),\
k=1,2,\cdots,m\\\ u_{2m-2k+1}&=-2\sum_{j=1}^{k}(f,\varphi_{2m-2j+2}),\
k=1,2,\cdots,m\end{cases}$

For $f=1$ on $[0,1]$, we have $(f,\varphi_{i})=h$ for all $i=1,2,\cdots,2m$,
and

(4.9) $\begin{cases}u_{2k}&=2kh=x_{2k},\ k=1,2,\cdots,m\\\
u_{2m-2k+1}&=-2kh=x_{2m-2k+1}-1,\ k=1,2,\cdots,m.\end{cases}$

Thus, the even components interpolate the solution of the function $x$ and the
odd components interpolate the function $x-1$. The combined solution leads to
a very oscillatory behavior when $n\to\infty$. For $\varepsilon/h<<1$ (a good
threshold is $\varepsilon/h\leq 10^{-4}$ ) the solution of (4.1) is very close
to the solution of the simplified system (4.5), and a similar oscillatory
behavior is observed for the linear finite element solution of (4.1) when
using an odd number of subintervals $n$, see Fig.1. We note that, for an
arbitrary (smooth) $f$, the even components $\\{u_{2k}\\}$, approximate $w(x)$
the solution of the initial value problem (IVP) (4.4), and the the odd
components approximate the function $\theta(x)=w(x)-\int_{0}^{1}f(x)\,dx$, see
Fig.1 and Fig.5. This can be justified by noticing that if we replace in (4.6)
the values $(f,\varphi_{i})$ by $h\,f(x_{i})$ \- the corresponding trapezoid
rule approximation of the integral, the solution of the modified system
coincides with the mid-point method approximation (on the even nodes, $h\to
2h$) of the IVP (4.4).

Fig.1: $f=1,n=101,\varepsilon=10^{-6}$

Fig.2: $f=1,n=102$, $\varepsilon=10^{-6}$

Fig.3: $f=1,n=101,\varepsilon=10^{-4}$

Fig.4: $f=1,n=400,\varepsilon=10^{-4}$

Fig.5:$f=\cos(\frac{7\pi}{2}x)$, $n=101,\ \ \ \ \varepsilon=10^{-6}$

$f=\cos(\frac{7\pi}{2}x)$, $n=300,\varepsilon=10^{-4}$

Similarly, the solution of the modified system (4.7) (obtained by replacing
$(f,\varphi_{i})$ with $h\,f(x_{i})$) coincides with the mid-point method
approximation (on odd nodes) of the IVP

(4.10) $\theta^{\prime}(x)=f(x)\ \text{for all}\ x\in(0,1),\text{and}\
\theta(1)=0.$

The solution of (4.10) is $\theta(x)=-\int_{x}^{1}f(s)\,ds$. Thus,
$\theta(x)=w(x)-\int_{0}^{1}f(x)\,dx$. For the case $n=2m$, the system (4.6)
is the same, but since $u_{0}=u_{2m}=0$, the system might not have a solution.
In addition, the second system (4.7) (with the last equation removed) is
undetermined and could have infinitely many solutions. The discretization of
(4.1) is still very oscillatory in this case, see Fig.2. As the ratio
$\varepsilon/h\to 1$, from numerical tests, we note that the linear finite
element solution of (4.1) oscillates between two curves (that depend on $h$
and are independent of the parity of the number of nodes), and approximate
well the graph of $w$ on intervals $[0,\,\alpha(h)]$ with $\alpha(h)\to 1$ as
$h$ gets closer and closer to $\epsilon$, see Fig.3, Fig.4, and Fig.6.

The behavior of the standard linear finite element approximation motivates the
need for other methods, including saddle point least square or Petrov-Galerkin
methods.

###  4.2. $(P^{1}-P^{2})$-SPLS discretization

For improving the stability and approximability of the finite element
approximation a saddle point least square (SPLS) method can be used, see e.g.,
[19, 20, 10]. The SPLS method for solving (1.4) is: Find $(w,u)\in V\times Q$
such that

(4.11) $\begin{array}[]{lclll}a_{0}(w,v)&+&b(v,u)&=(f,v)&\ \quad\hbox{ for all
}v\in V,\\\ b(w,q)&&&=0&\ \quad\hbox{ for all }q\in Q,\end{array}$

where $V=Q=H^{1}_{0}(0,1)$, with possible different type of norms, and
$b(v,u)=\varepsilon\,a_{0}(u,v)+(u^{\prime},v)=\varepsilon\,(u^{\prime},v^{\prime})+(u^{\prime},v)$.

For the discretization of (4.11) we choose finite element space
${\mathcal{M}}_{h}\subset Q$ and $V_{h}\subset V$ and solve the discrete
problem: Find $(w_{h},u_{h})\in V_{h}\times{\mathcal{M}}_{h}$ such that

(4.12) $\begin{array}[]{lclll}a_{0}(w_{h},v_{h})&+&b(v_{h},u_{h})&=(f,v_{h})&\
\quad\hbox{ for all }v_{h}\in V_{h},\\\ b(w_{h},q_{h})&&&=0&\ \quad\hbox{ for
all }q_{h}\in{\mathcal{M}}_{h}.\end{array}$

Analysis and numerical results for finite element test and trail spaces of
various degree polynomial were done in [20]. We present next some numerical
observations for
${\mathcal{M}}_{h}=C^{0}-P^{1}:=span\\{\varphi_{j}\\}_{j=1}^{n-1}$, with
$\varphi_{j}$’s the standard linear nodal functions and $V_{h}=C^{0}-P^{2}$ on
the given uniformly distributed nodes on $[0,1]$, to show the improvement from
the standard linear discretization. The presence of non-phisical oscillation
is diminished, and the errors are better for the SPLS discretization, see
Table 1 and Table 2.

While for $\int_{0}^{1}f(x)\,dx=0$ there is no much difference in the solution
behaviour for the two methods, for $\int_{0}^{1}f(x)\,dx\neq 0$, numerical
tests showed an essential improuvement for the SPLS solution. Inside the
interval $[3h,1-3h]$ the SPLS solution $u_{h}$, approximates the shift by a
constant of the solution $u$ of the original problem (1.4), see Fig.7-Fig.10.
The oscillations appear only at the ends of the interval. The behavior can be
explained by similar arguments presented in Section 4.1 as follows: The
simplified problem, obtained from (4.11) by letting $\varepsilon\to 0$, is not
well posed when $\int_{0}^{1}f(x)\,dx\neq 0$. However, the simplified linear
system obtained from (4.12) by letting $\varepsilon\to 0$, i.e. find
$(w_{h},u_{h})\in V_{h}\times{\mathcal{M}}_{h}$ such that

(4.13)
$\begin{array}[]{lclll}(w^{\prime}_{h},v^{\prime}_{h})&+&(u^{\prime}_{h},v_{h})&=(f,v_{h})&\
\quad\hbox{ for all }v_{h}\in V_{h},\\\ (w_{h},q^{\prime}_{h})&&&=0&\
\quad\hbox{ for all }q_{h}\in{\mathcal{M}}_{h},\end{array}$

has unique solution, because a discrete $\inf-\sup$ condition can be
demonstrated using a specific choice of norms. Numerical tests (for
$\varepsilon\leq 10^{-3}$) show that the solution of the simplified system
(4.13) approximates (when $h\to 0$) the function $\frac{1}{2}(w(x)+\theta(x))$
where $w,\theta$, are the solution of the reduced problems (4.4) and (4.10). A
similar type of oscillations (depending only on $h$) towards the ends of
$[0,1]$ are still presented. For example, for $f=1$ the solution of (4.13)
with $n=101$, is close to $x-1/2$, see Fig.7. For $\varepsilon/h\leq 10^{-4}$
the solution of (4.12) is close to the solution of (4.13). However, as
$10^{-4}<\varepsilon/h\to 1$, the solution of (4.12) is decreasing the size of
the shifting constant and approximates $u$ (rather than
${1}/{2}(w(x)+\theta(x))$). Similar oscillations are still present, but only
outside of the interval $[3h,1-3h]$.

Fig.7: $f=1,n=101,\varepsilon=10^{-6}$

Fig.8: $f=1,n=400,\varepsilon=10^{-4}$

Fig.9 $f=\cos(\frac{\pi}{2}x),n=101,\varepsilon=10^{-6}$

Fig.10 $n=300,\varepsilon=10^{-4}$

###  4.3. Petrov Galerkin (PG) with bubble enriched test space $V_{h}$

We consider $b(v,u):=\varepsilon\,a_{0}(u,v)+(u^{\prime},v)$ for all $u,v\in
V:=H^{1}_{0}(0,1)$. The second equation in (4.11) implies $w=0$, and the SPLS
problem reduces to: Find $u\in Q$ such that

(4.14) $b(v,u)=(f,v)\ \quad\hbox{ for all }v\in V,\\\ $

which is a Petrov-Galerkin method for solving (1.3).

One of the well known Petrov-Galerkin discretization of the model problem
(4.14) with ${\mathcal{M}}_{h}=span\\{\varphi_{j}\\}_{j=1}^{n-1}$ consists of
modifying the test space such that diffusion is created from the reaction
therm. This is also known as an up-winding finite element scheme, see Sectioin
2.2 in [29]. We define the test space $V_{h}$, by introducing first a bubble
function for each interval $[x_{i-1},x_{i}],i=1,2,\cdots,n$:

$B_{i}:=4\,\varphi_{i-1}\,\varphi_{i},\ \ i=1,2,\cdots,n,$

which is supported in $[x_{i-1},x_{i}]$. The discrete test space $V_{h}$ is

$V_{h}:=span\\{\varphi_{j}+B_{j}-B_{j+1}\\}_{j=1}^{n-1}.$

We note that both ${\mathcal{M}}_{h}$ and $V_{h}$ have dimension $n-1$ and, in
a more general approach the test functions can be defined using up-winding
parameters $\sigma_{i}>0$ to get
$V_{h}:=span\\{\varphi_{j}+\sigma_{i}(B_{j}-B_{j+1})\\}_{j=1}^{n-1}$.

####  4.3.1. Variational formulation and matrices

The Petrov Galerkin discretization for (1.3) is: Find
$u_{h}\in{\mathcal{M}}_{h}$ such that

(4.15) $b(v_{h},u_{h})=(f,v_{h})\ \quad\hbox{ for all }v_{h}\in V_{h}.$

We look for

$u_{h}=\sum_{j=1}^{n-1}\alpha_{j}\varphi_{j},$

and consider a generic test function

$v_{h}=\sum_{i=1}^{n-1}\beta_{i}\varphi_{i}+\sum_{i=1}^{n-1}\beta_{i}(B_{i}-B_{i+1})=\sum_{i=1}^{n-1}\beta_{i}\varphi_{i}+\sum_{i=1}^{n}(\beta_{i}-\beta_{i-1})B_{i},$

where, we define $\beta_{0}=\beta_{n}=0$. Denoting,

$B_{h}:=\sum_{i=1}^{n}(\beta_{i}-\beta_{i-1})B_{i},\ \text{and }\
w_{h}:=\sum_{i=1}^{n-1}\beta_{i}\varphi_{i},$

we have

$v_{h}=w_{h}+B_{h}.$

We note that for a generic bubble function $B$ with support $[a,b]$ we have

$B:=\frac{4}{(b-a)^{2}}(x-a)(b-x),\ \text{with}\ a<b,\ \text{and}$ (4.16)
$\int_{a}^{b}B(x)\,dx=\frac{2(b-a)}{3},\ \int_{a}^{b}B^{\prime}\,dx=0,\
\int_{a}^{b}(B^{\prime})^{2}\,dx=\frac{16}{3(b-a)}.$

Using the above formulas, the fact that $u^{\prime}_{h},w^{\prime}_{h}$ are
constant on each of the intervals $[x_{i-1},x_{i}]$, and that
$w^{\prime}_{h}=\frac{\beta_{i}-\beta_{i-1}}{h}$ on $[x_{i-1},x_{i}]$, we
obtain

$(u^{\prime}_{h},B_{h})=\sum_{i=1}^{n}\int_{x_{i-1}}^{x_{i}}u^{\prime}_{h}(\beta_{i}-\beta_{i-1})B_{i}=\sum_{i=1}^{n}u^{\prime}_{h}\,w^{\prime}_{h}\int_{x_{i-1}}^{x_{i}}B_{i}=\frac{2h}{3}\sum_{i=1}^{n}\int_{x_{i-1}}^{x_{i}}u^{\prime}_{h}w^{\prime}_{h}.$

Thus

(4.17) $(u^{\prime}_{h},B_{h})=\frac{2h}{3}(u^{\prime}_{h},w^{\prime}_{h}),\
\text{where}\ v_{h}=w_{h}+B_{h}.$

In addition,

$(u^{\prime}_{h},B^{\prime}_{i})=0\ \text{for all}\
i=1,2,\cdots,n,\text{hence}$ (4.18)
$(u^{\prime}_{h},B^{\prime}_{h})=0,\text{for all}\
u_{h}\in{\mathcal{M}}_{h},v_{h}=w_{h}+B_{h}\in V_{h}.$

From (4.17) and (4.18), for any
$u_{h}\in{\mathcal{M}}_{h},v_{h}=w_{h}+B_{h}\in V_{h}$ we get

(4.19)
$b(v_{h},u_{h})=\left(\varepsilon+\frac{2h}{3}\right)(u^{\prime}_{h},w^{\prime}_{h})+(u^{\prime}_{h},w_{h}).$

Thus, adding the bubble part to the test space leads to the extra diffusion
term $\frac{2h}{3}(u^{\prime}_{h},w^{\prime}_{h})$ with $\frac{2h}{3}>0$
matching the sign of the coefficient of $u^{\prime}$ in (1.3). It is also
interesting to note that only the linear part of $v_{h}$ appears in expression
of $b(v_{h},u_{h})$. The functional $v_{h}\to(f,v_{h})$ can be also viewed as
functional only of the linear part $w_{h}$. Indeed, using the splitting
$v_{h}=w_{h}+B_{h}$ and that
$B_{h}:=\sum_{i=1}^{n}(\beta_{i}-\beta_{i-1})B_{i}$ we get

$(f,v_{h})=(f,w_{h})+(f,\sum_{i=1}^{n}hw^{\prime}_{h}B_{i})=(f,w_{h})+h\,(f,w^{\prime}_{h}\sum_{i=1}^{n}B_{i}).$

The variational formulation of the up-winding Petrov-Galerkin method can be
reformulated as: Find $u_{h}\in{\mathcal{M}}_{h}$ such that

(4.20)
$\left(\varepsilon+\frac{2h}{3}\right)(u^{\prime}_{h},w^{\prime}_{h})+(u^{\prime}_{h},w_{h})=(f,w_{h})+h\,(f,w^{\prime}_{h}\sum_{i=1}^{n}B_{i}),w_{h}\in
M_{h}.$

The reformulation allows for a new error analysis using an optimal test norm,
see e.g. [6, 8, 9], and for comparison with the known stream-line diffusion
(SD) method of discretization that is reviewed in the next section.

For the analysis of the method, using (4.18) and the last part of (4.16), we
note that for any $v_{h}=w_{h}+B_{h}\in V_{h}$ we have

$\displaystyle(v^{\prime}_{h},v^{\prime}_{h})$
$\displaystyle=(w^{\prime}_{h}+B^{\prime}_{h},w^{\prime}_{h}+B^{\prime}_{h})=(w^{\prime}_{h},w^{\prime}_{h})+(B^{\prime}_{h},B^{\prime}_{h})=$
$\displaystyle=(w^{\prime}_{h},w^{\prime}_{h})+\sum_{i=1}^{n}(\beta_{i}-\beta_{i-1})^{2}(B^{\prime}_{i},B^{\prime}_{i})=$
$\displaystyle=(w^{\prime}_{h},w^{\prime}_{h})+\frac{16h}{3}\sum_{i=1}^{n}\left(\frac{\beta_{i}-\beta_{i-1}}{h}\right)^{2}=$
$\displaystyle=(w^{\prime}_{h},w^{\prime}_{h})+\frac{16}{3}\sum_{i=1}^{n}\left(\int_{x_{i-1}}^{x_{i}}(w^{\prime}_{h})^{2}\right)^{2}=(w^{\prime}_{h},w^{\prime}_{h})+\frac{16}{3}(w^{\prime}_{h},w^{\prime}_{h}).$

Consequently,

(4.21) $|v_{h}|^{2}=\frac{19}{3}|w_{h}|^{2}.$

Using the reformulation (4.20) the linear system to be solved is

(4.22)
$\left(\left(\frac{\varepsilon}{h}+\frac{2h}{3}\right)S+C\right)\,U=F_{PG},$

where $U,F_{PG}\in\mathbb{R}^{n-1}$ with:

$U:=\begin{bmatrix}u_{1}\\\ u_{2}\\\ \vdots\\\ u_{n-1}\end{bmatrix},\quad
F_{PG}:=\begin{bmatrix}(f,\varphi_{1})\\\ (f,\varphi_{2})\\\ \vdots\\\
(f,\varphi_{n-1})\end{bmatrix}+\begin{bmatrix}(f,B_{1}-B_{2})\\\
(f,B_{2}-B_{3})\\\ \vdots\\\ (f,B_{n-1}-B_{n})\end{bmatrix},$

and $S,C$ are the matrices defined at the beginning of this section. Numerical
tests, show that this method does not lead to any kind of non-physical
oscillations.

###  4.4. Stream line diffusion (SD) discretization

The classical way to introduce this method can be found in e.g., [25, 17]. For
our model problem, we present a simple way to introduce and relate the method
with the up-winding PG method. We take
${\mathcal{M}}_{h}=V_{h}=span\\{\varphi_{j}\\}_{j=1}^{n-1}$ and consider the
stream line diffusion method for solving (1.3): Find
$u_{h}\in{\mathcal{M}}_{h}$ such that

(4.23) $b_{sd}(w_{h},u_{h})=F_{sd}(w_{h})\ \quad\hbox{ for all }w_{h}\in
V_{h},$

where

$b_{sd}(w_{h},u_{h}):=\varepsilon\,(u^{\prime}_{h},w^{\prime}_{h})+(u^{\prime}_{h},w_{h})+\sum_{i=1}^{n}\delta_{i}\int_{x_{i-1}}^{x_{i}}u^{\prime}_{h}w^{\prime}_{h}$

with $\delta_{i}>0$ weight parameters, and

$F_{sd}(w_{h}):=(f,w_{h})+\sum_{i=1}^{n}\delta_{i}\int_{x_{i-1}}^{x_{i}}f(x)\,w^{\prime}_{h}\,dx.$

In practice $\delta_{i}$’s are chosen proportional with $x_{i}-x_{i-1}=h$.

For the choice

$\delta_{i}=\frac{2h}{3},\ i=1,2,\cdots,n,$

and arbitrary $w_{h},u_{h}\in{\mathcal{M}}_{h}=V_{h}$ the bilinear form
$b_{sd}$ becomes

$b_{sd}(w_{h},u_{h})=b(w_{h},u_{h})=\left(\varepsilon+\frac{2h}{3}\right)(u^{\prime}_{h},w^{\prime}_{h})+(u^{\prime}_{h},w_{h}),$

and the the corresponding right hand side functional $F_{sd}$ is

(4.24) $F_{sd}(w_{h})=(f,w_{h})+\frac{2h}{3}(f,w^{\prime}_{h}),\ w_{h}\in
V_{h}.$

Thus, by choosing the appropriate weights, the (up-winding) PG and SD
discretization methods lead to the the same stiffness matrix. Comparing the
right hand sides of (4.20) and (4.24) we note that the two methods produce the
same system (solution) if and only if

(4.25) $(f,w^{\prime}_{h}\sum_{i=1}^{n}B_{i})=\frac{2}{3}(f,w^{\prime}_{h}),\
\text{for all}\ w_{h}\in V_{h}.$

This is a feasible condition, as

$\int_{0}^{1}\sum_{i=1}^{n}B_{i}=n\,\frac{2h}{3}=\frac{2}{3}.$

In fact, the condition (4.25) is satisfied for $f=1$. In this case, both sides
of (4.25) are zero. In general, we expect that, for certain error norms, the
PG to perform better. It is known, [13, 28, 29] that the error estimate for
the SD method is defined using a special SD-norm that, in the one dimensional
case with same weights $\delta_{i}=\delta$, becomes

$\|v\|^{2}_{sd}=\varepsilon|v|^{2}+\delta|v|^{2}.$

For a fair comparison with the PG method we take $\delta=\frac{2h}{3}$. For
the continuous solution $u$ of (1.3) and the discrete solution $u_{h}$ of
(4.23), we have

(4.26) $\|u-u_{h}\|_{sd}\leq c_{sd}\,h^{3/2}\|u^{\prime\prime}\|.$

For comparison of the implementation of the two methods we can compare also
the load vector $F_{PG}$ defined above with the load vector for the SD method:

$F_{SD}:=\begin{bmatrix}(f,\varphi_{1})\\\ (f,\varphi_{2})\\\ \vdots\\\
(f,\varphi_{n-1})\end{bmatrix}+\frac{2h}{3}\begin{bmatrix}(f,\varphi^{\prime}_{1})\\\
(f,\varphi^{\prime}_{2})\\\ \vdots\\\ (f,\varphi^{\prime}_{n})\end{bmatrix}.$

##  5\. Numerical experiments

We will compare numerically the standard linear finite element with the
$P^{1}-P^{2}$-SPLS formulation, and the Streamline Diffusion with Petrov-
Galerkin in a variety of norms. In order to compact the tables, we will use
the notation $E_{i,method}$ where $i=0$ is the $L^{2}$ error $||u-u_{h}||$,
and $i=1$ is the $H^{1}$ error $|u-u_{h}|$. For the methods, we have $L$ for
standard linear, $S$ for SPLS, $SD$ for Streamline Diffusion, and $P$ for
Petrov-Galerkin.

###  5.1. Standard linear versus SPLS discretization

We note here that even in the case when the solution is independent of
$\varepsilon$, the standard finite element solution can exhibit non-physical
oscillations, see e.g.. Figure 5.1 for the exact solution
$u(x)=-x^{3}+1.5x^{2}-0.5$ and the behavior depends on the parity of $n$-the
number of subintervals on $[0,1]$.

Figure 5.1.  $\varepsilon=10^{-4}$. Left: $n=24$, Right: $n=25$

For the first test, we take $f=1-2x$ which satisfies the condition
$\overline{f}=0$. We will compare the standard linear finite element method
and the SPLS formulation in this case for two values of $\varepsilon$ that are
at least 2 orders of magnitude greater than $h$ at the finest level. Table 1
contains the errors of the two methods over six refinements where
$h_{i}=2^{-i-5}$. We can see that for this problem, both discretizatin perform
well. The explanation for this nice behavior is that, in the case
$\overline{f}=0$, the interpolant has good approximation properties on the
uniform mesh, see the Appendix. We also note that at all levels for both
values of $\varepsilon$ and both errors, SPLS produces smaller error.

Level/$\varepsilon$ | $10^{-6}$
---|---
$E_{1,L}$ | $E_{1,S}$ | $E_{0,L}$ | $E_{0,S}$
1 | 0.289 | 0.144 | 0.046 | 0.011
2 | 0.144 | 0.072 | 0.011 | 0.003
3 | 0.072 | 0.036 | 0.003 | 0.001
4 | 0.036 | 0.018 | 0.001 | 1.8e-4
5 | 0.018 | 0.009 | 1.7e-4 | 4.4e-5
6 | 0.009 | 0.005 | 4.4e-5 | 1.0e-5
Order | 1 | 1 | 2 | 2
Level/$\varepsilon$ | $10^{-10}$
$E_{1,L}$ | $E_{1,S}$ | $E_{0,L}$ | $E_{0,S}$
1 | 0.289 | 0.144 | 0.046 | 0.011
2 | 0.144 | 0.072 | 0.011 | 0.003
3 | 0.072 | 0.036 | 0.003 | 0.001
4 | 0.036 | 0.018 | 0.001 | 1.8e-4
5 | 0.018 | 0.009 | 1.8e-4 | 4.5e-5
6 | 0.009 | 0.005 | 4.5e-5 | 1.1e-5
Order | 1 | 1 | 2 | 2
Table 1. L vs. SPLS: $f(x)=1-2x$

Table 2 contains errors for standard linear finite elements and SPLS for
$f(x)=2x$ measured in a balanced norm
$||\cdot||_{B}^{2}=\varepsilon|\cdot|^{2}+||\cdot||^{2}$. As this choice of
right hand side does not satisfy the condition that $\overline{f}=0$ we can
expect the results to be less impressive than those of Table 1. In Table 2 we
can see for larger values of $\varepsilon$ the magnitudes of the errors are
comparable for both methods. As $\varepsilon$ decreases, while the standard
linear elements appear to do better as they attain second order convergence,
this is somewhat misleading as the errors are significantly larger than those
of SPLS. The SPLS method appears to have a stagnation of error, which is due
in part to the overall shift of the approximation which can be seen in the
right plot of figure 5.2. It can be also seen in the previously mentioned
figure that SPLS does a better job at capturing the behavior of the exact
solution aside from the shift.

Table 3 contains errors in the $H^{1}$, $L^{2}$, and balanced norms for the
SPLS approximation for $f(x)=2x$ with accounting for the expected shift, as
presented in Section 4.2. In that test, the $u_{h}$ that we measure the error
with is taken to be $u_{h}+\overline{f}/2=u_{h}+1/2$. The table shows that for
small $\varepsilon$, the shifted SPLS approximation is able to display some
convergence order, as anticipated in Section 4.2. This degeneracy of
convergence order may be attributed to the small oscillatory behavior that
occurs near both boundaries. The orders improve if the errors are computed on
the interval $[3h,1-3h]$, but a rigorous analysis of the shift conjecture and
its implications remains to be investigated.

Level/$\varepsilon$ | $10^{-4}$
---|---
$||u-u_{h,L}||_{B}$ | Order | $||u-u_{h,S}||_{B}$ | Order
1 | 9.75e-01 | 0.00 | 4.97e-01 | 0.00
2 | 7.26e-01 | 0.43 | 4.91e-01 | 0.02
3 | 7.04e-01 | 0.04 | 4.77e-01 | 0.04
4 | 6.76e-01 | 0.06 | 4.86e-01 | -0.03
5 | 6.95e-01 | -0.04 | 5.88e-01 | -0.27
6 | 6.29e-01 | 0.14 | 5.76e-01 | 0.03
Level/$\varepsilon$ | $10^{-8}$
$||u-u_{h,L}||_{B}$ | Order | $||u-u_{h,S}||_{B}$ | Order
1 | 7.05e+03 | 0.00 | 5.02e-01 | 0.00
2 | 1.76e+03 | 2.00 | 5.01e-01 | 0.00
3 | 4.40e+02 | 2.00 | 5.01e-01 | 0.00
4 | 1.10e+02 | 2.00 | 5.00e-01 | 0.00
5 | 2.75e+01 | 2.00 | 5.00e-01 | 0.00
6 | 6.91e+00 | 1.99 | 5.00e-01 | 0.00
Table 2. L vs. SPLS: $f(x)=2x$ Level/$\varepsilon$ | $10^{-8}$
---|---
$E_{1,S}$ | Order | $E_{2,S}$ | Order | $||u-u_{h}||_{B}$ | Order
1 | 9.35e+00 | 0.00 | 6.97e-02 | 0.00 | 6.97e-02 | 0.00
2 | 1.32e+01 | -0.50 | 4.93e-02 | 0.50 | 4.93e-02 | 0.50
3 | 1.87e+01 | -0.50 | 3.49e-02 | 0.50 | 3.49e-02 | 0.50
4 | 2.64e+01 | -0.50 | 2.46e-02 | 0.50 | 2.48e-02 | 0.49
5 | 3.74e+01 | -0.50 | 1.74e-02 | 0.50 | 1.78e-02 | 0.48
6 | 5.30e+01 | -0.50 | 1.23e-02 | 0.50 | 1.34e-02 | 0.41
Table 3. SPLS: $f(x)=2x$ with shift

Figure 5.2.  $\varepsilon=10^{-6}$. Left: Linear, Right: SPLS

###  5.2. Streamline Diffusion versus PG discretization

For the second test, we take $f=2x$ and compare Streamline Diffusion and
Petrov-Galerkin. In this case, the exact solution will have a boundary layer
at $x=1$ of width $|\varepsilon\log(\varepsilon)|$. We will also include two
tables for this test. Table 4 compares the errors of the Streamline Diffusion
approximation $u_{h,sd}$ with the Petrov-Galerkin approximation $u_{h,pg}$ in
the SD norm $||u-u_{h}||_{sd}$. As we can see in Table 4, the expected order
for streamline diffusion is observed. Further, the same order is attained by
Petrov-Galerkin with errors of smaller magnitude.

Level/$\varepsilon$ | $10^{-4}$
---|---
$||u-u_{h,sd}||_{sd}$ | Order | $||u-u_{h,pg}||_{sd}$ | Order
1 | 1.56e-02 | 0.00 | 1.54e-02 | 0.00
2 | 2.57e-03 | 2.60 | 2.51e-03 | 2.62
3 | 5.45e-04 | 2.24 | 4.92e-04 | 2.35
4 | 1.05e-04 | 2.37 | 4.21e-05 | 3.55
5 | 3.86e-05 | 1.45 | 1.54e-05 | 1.46
6 | 1.45e-05 | 1.41 | 5.78e-06 | 1.41
Level/$\varepsilon$ | $10^{-8}$
$||u-u_{h,sd}||_{sd}$ | Order | $||u-u_{h,pg}||_{sd}$ | Order
1 | 1.46e-02 | 0.00 | 1.45e-02 | 0.00
2 | 2.16e-03 | 2.76 | 2.09e-03 | 2.79
3 | 3.98e-04 | 2.44 | 3.16e-04 | 2.72
4 | 1.01e-04 | 1.97 | 4.04e-05 | 2.97
5 | 3.60e-05 | 1.50 | 1.43e-05 | 1.50
6 | 1.27e-05 | 1.50 | 5.06e-06 | 1.50
Table 4. SD vs. PG: $f(x)=2x$

In Table 4 and Table 5, the SD and PG approximations are compared in the SD
norm $||u-u_{h}||_{*,h}$, and the balanced norm $||u-u_{h}||_{B}$ for
$f(x)=2x$. These tables show that overall, the PG approximation performs
better than the SD method for both choices of norms. More interestingly, for
the balance norm with small $\varepsilon$ the PG method exhibits higher order
of convergence.

Level/$\varepsilon$ | $10^{-4}$
---|---
$||u-u_{h,sd}||_{B}$ | Order | $||u-u_{h,pg}||_{B}$ | Order
1 | 1.12e-02 | 0.00 | 2.28e-03 | 0.00
2 | 5.75e-03 | 0.96 | 3.97e-04 | 2.52
3 | 2.93e-03 | 0.97 | 9.84e-05 | 2.01
4 | 1.47e-03 | 0.99 | 1.13e-05 | 3.13
5 | 7.38e-04 | 0.99 | 5.61e-06 | 1.01
6 | 3.70e-04 | 1.00 | 2.80e-06 | 1.00
Level/$\varepsilon$ | $10^{-8}$
$||u-u_{h,sd}||_{B}$ | Order | $||u-u_{h,pg}||_{B}$ | Order
1 | 1.11e-02 | 0.00 | 1.60e-03 | 0.00
2 | 5.74e-03 | 0.95 | 1.62e-04 | 3.31
3 | 2.93e-03 | 0.97 | 1.65e-05 | 3.30
4 | 1.47e-03 | 0.99 | 7.00e-07 | 4.55
5 | 7.38e-04 | 0.99 | 1.82e-07 | 1.94
6 | 3.70e-04 | 1.00 | 5.16e-08 | 1.82
Table 5. SD vs. PG:$f(x)=2x$

##  6\. Conclusion

We compared four discretization methods for a model convection-diffusion
problem. Some concepts and observations we noted in the one dimensional case
can be used to efficiently discretize and analyze multi-dimensional cases. One
such observation is that if the simplified problem ($\varepsilon\to 0$) does
not have a unique solution but a particular discretization we choose of the
simplified problem has unique solution exhibiting non-physical oscillations,
then the chosen discretization for the original problem is likely to produce
non-physical oscillations. To eliminate the non-physical solutions one can
split the data $f=(f-\overline{f})+\overline{f}$ and solve the two
corresponding problems for the data $f-\overline{f}$ and $\overline{f}$.

For the the model problem we considered, the best method turns out to be the
upwinding PG method. Even though we can view this PG method as mixed method
with the test space a subspace of $C^{0}-P^{2}$-the test space for SPLS, the
SPLS method is not performing better. How the upwinding PG method can be
extended and related with other SPLS discretizations in two or more
dimensions, will be further investigated.

##  7\. Appendix

We present stability estimates for the model problem (1.3) that justify why in
the case of compatibility case $\int_{0}^{1}f(x)\,dx=0$ the standard
$C^{0}-P^{1}$ or SPLS discretizations lead to standard approximation
properties, Table 1.

###  7.1. Stability of the 1D Convection-Difussion model problem

The results presented in this section might be well known in a more general
setting. However, we are able to provide sharp norm estimates for the
simplified PDE (1.3). We derive estimates for the derivatives that are used in
the next section for establishing approximation properties for the piece-wise
linear interpolant. All results of this appendix refer to the solution
$u=u(x)$ of the problem (1.3). We assume next that $f$ is continuous on
$[0,1]$. The Green’s function for this problem allows for the representation

(7.1) $u(x)=\int_{0}^{1}G(x,s)f(s)\,ds.$

where $G(x,s)$ can be explicitly determined by using standard integration
arguments, and

$G(x,s)=\frac{1}{e^{\frac{1}{\varepsilon}}-1}\begin{cases}(e^{\frac{1}{\varepsilon}}-e^{\frac{x}{\varepsilon}})(1-e^{-\frac{s}{\varepsilon}}),&0\leq
s<x\\\ (e^{\frac{x}{\varepsilon}}-1)(e^{\frac{1-s}{\varepsilon}}-1),&x\leq
s\leq 1.\end{cases}$

Define $u_{1}(x)$ to be the solution for $f(x)=1$, or equivalently

$u_{1}(x)=\int_{0}^{1}G(x,s)\,ds=x-\frac{e^{\frac{x}{\varepsilon}}-1}{e^{\frac{1}{\varepsilon}}-1}.$

We let $f_{\min}$ and $f_{\max}$ denote the minimum and maximum (respectively)
of $f$ on $[0,1]$, and note that, for any fixed $x\in(0,1)$, the function

$s\,\to G(x,s),\ s\in[0,1],$

is increasing on $[0,x]$, and decreasing on $[x,1]$, thus for any
$s,x\in[0,1]$, we have

(7.2) $0\leq G(x,s)\leq
G(x,x)=\frac{(e^{\frac{1}{\varepsilon}}-e^{\frac{x}{\varepsilon}})(1-e^{\frac{-x}{\varepsilon}})}{e^{\frac{1}{\varepsilon}}-1}\leq\frac{e^{\frac{1}{2\varepsilon}}-1}{e^{\frac{1}{2\varepsilon}}+1}:=G_{\infty}<1.$

For this problem, we can prove the following inequalities relating the the
point values $u(x),u_{1}(x)$ and $f$.

######  Theorem 7.1.

If $f\in L^{\infty}(0,1)$ and $u$ is the solution to (1.3) then:

  1. i)

$|u(x)|\leq\|f\|_{\infty}u_{1}(x)$;

  2. ii)

$f_{\min}\,u_{1}(x)\leq u(x)\leq f_{\max}\,u_{1}(x)$;

  3. iii)

$|u(x)|\leq G(x,x)\|f\|_{L^{1}(0,1)}$ and consequently
$\|u\|_{\infty}\leq G_{\infty}\|f\|_{L^{1}(0,1)}\leq
G_{\infty}\|f\|_{L^{2}(0,1)}$.

###### Proof.

The proofs are base on the the definition of $u_{1}$ and the inequalities of
the Green’s function (7.2).

  1. i)

We have:

$\displaystyle|u(x)|$
$\displaystyle=\left|\int_{0}^{1}G(x,s)f(s)ds\right|\leq\int_{0}^{1}G(x,s)|f(s)|ds$
$\displaystyle\leq\|f\|_{\infty}\int_{0}^{1}G(x,s)ds=\|f\|_{\infty}u_{1}(x).$

  2. ii)

Since $f_{\min}\leq f(s)\leq f_{\max}$ we have

$\displaystyle f_{\min}\,G(x,s)\leq f(s)G(x,s)\leq f_{\max}\,G(x,s),\
\text{which implies}$ $\displaystyle
f_{\min}\int_{0}^{1}G(x,s)ds\leq\int_{0}^{1}f(s)G(x,s)ds\leq
f_{\max}\int_{0}^{1}G(x,s)ds,\ \text{consequently}$ $\displaystyle
f_{\min}\,u_{1}(x)\leq u(x)\leq f_{\max}\,u_{1}(x).$

  3. iii)

First we observe that:

$|u(x)|\leq\int_{0}^{1}G(x,s)\,|f(s)|ds\leq\int_{0}^{1}G(x,x)\,|f(s)|ds=G(x,x)\,\int_{0}^{1}|f(s)|ds.$

Consequently,

$\|u\|_{\infty}\leq G_{\infty}\|f\|_{L^{1}(0,1)}$

The last part follows from $\|f\|_{L^{1}(0,1)}\leq\|f\|_{L^{2}(0,1)}$.

∎

######  Theorem 7.2.

If $u$ is the solution to (1.3) and $f(x)\in C^{0}([0,1])$ satisfies
$\int_{0}^{1}f(s)ds=0$ (i.e. has average 0), then

$|u^{\prime}(x)|\leq\|f\|_{\infty},\quad\forall x\in[0,1].$

###### Proof.

Using the explicit form of $G(x,s)$, we have

$\displaystyle|u^{\prime}(x)|$
$\displaystyle=\frac{e^{\frac{x}{\varepsilon}}}{e^{\frac{1}{\varepsilon}}-1}\left|\int_{0}^{x}\frac{1}{\varepsilon}e^{-\frac{s}{\varepsilon}}f(s)ds+\int_{x}^{1}\frac{1}{\varepsilon}e^{\frac{1-s}{\varepsilon}}f(s)ds\right|$
$\displaystyle\leq\frac{e^{\frac{x}{\varepsilon}}}{e^{\frac{1}{\varepsilon}}-1}\left(\left|\int_{0}^{x}\frac{1}{\varepsilon}e^{-\frac{s}{\varepsilon}}f(s)ds\right|+\left|\int_{x}^{1}\frac{1}{\varepsilon}e^{\frac{1-s}{\varepsilon}}f(s)ds\right|\right).$

Estimating the two integrals

$\displaystyle\left|\int_{0}^{x}\frac{1}{\varepsilon}e^{-\frac{s}{\varepsilon}}f(s)ds\right|$
$\displaystyle\leq\|f\|_{\infty}\int_{0}^{x}\frac{1}{\varepsilon}e^{-\frac{s}{\varepsilon}}ds$
$\displaystyle=\|f\|_{\infty}(1-e^{-\frac{x}{\varepsilon}})$
$\displaystyle\left|\int_{x}^{1}\frac{1}{\varepsilon}e^{\frac{1-s}{\varepsilon}}f(s)ds\right|$
$\displaystyle\leq\|f\|_{\infty}\int_{x}^{1}\frac{1}{\varepsilon}e^{\frac{1-s}{\varepsilon}}ds$
$\displaystyle=\|f\|_{\infty}(e^{\frac{1-x}{\varepsilon}}-1),$ leads to:
$\displaystyle|u^{\prime}(x)|$
$\displaystyle\leq\|f\|_{\infty}\frac{e^{\frac{x}{\varepsilon}}}{e^{\frac{1}{\varepsilon}}-1}(1-e^{-\frac{x}{\varepsilon}}+e^{\frac{1-x}{\varepsilon}}-1)=\|f\|_{\infty}.$

∎

######  Corollary 7.3.

Under the same assumptions of Theorem 2, we have that

(7.3) $|u^{\prime\prime}(x)|\leq\frac{2}{\varepsilon}\|f\|_{\infty}.$

###### Proof.

Since $u$ solves

$-\varepsilon u^{\prime\prime}(x)+u^{\prime}(x)=f(x),$

we have that:

$\displaystyle\varepsilon|u^{\prime\prime}(x)|$
$\displaystyle\leq|u^{\prime}(x)|+|f(x)|$
$\displaystyle\leq\|f\|_{\infty}+\|f\|_{\infty},$

implying the desired result. ∎

###  7.2. Linear interpolant approximation properties

For the special case $\int_{0}^{1}f(x)\,dx=0$ and $f\in C^{0}([0,1])$ we can
use the estimate of theorem 7.2,

$|u^{\prime}(x)|\leq\|f\|_{\infty},\quad\forall x\in[0,1],$

to derive an approximation property for the linear interpolant $\varepsilon$
(assuming that $f$ is independent of $\varepsilon$).

First we will need an error estimate for the interpolant that does not require
the second derivative of the function. We will assume $u\in H^{1}([0,1])$ and
$u^{\prime}\in L^{\infty}([0,1])$ we consider the linear interpolantc
$0=x_{0}<x_{1}<\cdots<x_{n}=1$ with $h:=x_{j}-x_{j-1},j=1,2,\cdots,n$. We note
first that

(7.4)
$\|u-u_{I}\|^{2}_{L^{2}(0,1)}=\sum_{i=1}^{n}\int_{x_{i-1}}^{x_{i}}(u(x)-u_{I}(x))^{2}\,dx,$

and un each interval $[x_{i-1},x_{i}]$, we have

$u(x)-u_{I}(x)=\int_{x_{i-1}}^{x}(u(s)-u_{I}(s))^{\prime}\,ds.$

Thus,

$\displaystyle(u(x)-u_{I}(x))^{2}$
$\displaystyle\leq\int_{x_{i-1}}^{x}1^{2}\,ds\int_{x_{i-1}}^{x}(u^{\prime}(s)-u^{\prime}_{I}(s))^{2}\,ds$
$\displaystyle\leq(x-x_{i-1})\int_{x_{i-1}}^{x_{i}}(u^{\prime}(s)-u^{\prime}_{I}(s))^{2}\,ds.$

Since
$\int_{x_{i-1}}^{x_{i}}u^{\prime}(s)=u(x_{i})-u(x_{i-1})=hu^{\prime}_{I}(s)$
we have that

$\displaystyle\int_{x_{i-1}}^{x_{i}}(u^{\prime}(s)-u^{\prime}_{I}(s))^{2}\,ds$
$\displaystyle=\int_{x_{i-1}}^{x_{i}}(u^{\prime}(s))^{2}\,ds-h(u^{\prime}_{I}(s))^{2}\,ds$
$\displaystyle\leq\int_{x_{i-1}}^{x_{i}}(u^{\prime}(s))^{2}\,ds\leq
h\|u^{\prime}\|^{2}_{\infty}.$

Combining the last two estimates, we obtain the following result:

(7.5)
$\int_{x_{i-1}}^{x_{i}}(u(x)-u_{I}(x))^{2}\,dx\leq\frac{h^{3}}{2}\|u^{\prime}\|^{2}_{\infty}.$

Now, from (7.4) and (7.5) we get the following result:

######  Proposition 7.4.

If $u\in H^{1}([0,1])$ with $u^{\prime}\in L^{\infty}([0,1])$ and $u_{I}$ is
the linear interpolant on a uniform mesh on $[0,1]$, then

(7.6)
$\|u-u_{I}\|^{2}_{L^{2}(0,1)}\leq\frac{h^{2}}{2}\|u^{\prime}\|^{2}_{\infty}.$

Assuming now that $f\in C^{0}([0,1])$, and $u$ is the solution of (1.3). We
clearly have that the regularity assumptions of Proposition 7.4 are satisfied
for the solution $u$. Thus, we obtain

(7.7) $\|u-u_{I}\|_{L^{2}(0,1)}\leq\frac{h}{\sqrt{2}}\|f\|_{\infty},$

an estimate independent of $\varepsilon$.

We note here that, as well known from the finite element approximation theory,
this inequality is not optimal. We can get a standard estimate $O(h^{2})$ for
$\|u-u_{I}\|_{L^{2}(0,1)}$, at the price of having an estimate constant that
depends on $\varepsilon$.

First, we note that the following Poincare Inequality

(7.8) $\|w\|\leq\frac{(b-a)}{\pi}\,|w|,\text{ for all }w\in L^{2}_{0}(a,b)\cap
H^{1}(a,b).$

can be proved using the spectral theorem for compact operators on Hilbert
spaces for the inverse of the (1d) Laplace operator with homogeneous Neumann
boundary conditions.

Next, if $u\in H^{2}(0,1)$ then using
$\int_{x_{i-1}}^{x_{i}}u^{\prime}(s)=u(x_{i})-u(x_{i-1})=hu^{\prime}_{I}(s)$
and the Poincare inequality (7.8),

$\displaystyle\int_{x_{i-1}}^{x_{i}}(u^{\prime}(s)-u^{\prime}_{I}(s))^{2}\,ds$
$\displaystyle=\int_{x_{i-1}}^{x_{i}}\left(u^{\prime}(s)-\frac{1}{h}\int_{x_{i-1}}^{x_{i}}u^{\prime}(s)\right)^{2}\,ds$
$\displaystyle\leq\frac{h^{2}}{\pi^{2}}\|u^{\prime\prime}\|_{L^{2}(x_{i-1},x_{i})}^{2}.$

Thus,

(7.9)
$\int_{x_{i-1}}^{x_{i}}(u(x)-u_{I}(x))^{2}\,dx\leq\frac{h^{4}}{\pi^{2}}\|u^{\prime\prime}\|_{L^{2}(x_{i-1},x_{i})}^{2},$

which combined with (7.4) gives

(7.10) $\|u-u_{I}\|\leq\frac{h^{2}}{\pi}\|u^{\prime\prime}\|_{L^{2}(0,1)}$

Combining with the estimate with (7.3) we obtain

(7.11)
$\|u-u_{I}\|_{L^{2}(0,1)}\leq\frac{2}{\varepsilon\pi}\,h^{2}\|f\|_{\infty}.$

## References

  * [1] A. Aziz and I. Babuška.  Survey lectures on mathematical foundations of the finite element method.  The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations, A. Aziz, editor, 1972.
  * [2] C. Bacuta.  Schur complements on Hilbert spaces and saddle point systems.  J. Comput. Appl. Math., 225(2):581–593, 2009.
  * [3] C. Bacuta and J. Jacavage.  A non-conforming saddle point least squares approach for an elliptic interface problem.  Comput. Methods Appl. Math., 19(3):399–414, 2019.
  * [4] C. Bacuta and J. Jacavage.  Saddle point least squares preconditioning of mixed methods.  Computers & Mathematics with Applications, 77(5):1396–1407, 2019\.
  * [5] C. Bacuta and J. Jacavage.  Least squares preconditioning for mixed methods with nonconforming trial spaces.  Applicable Analysis, Available online Feb 27, 2019:1–20, 2020.
  * [6] C. Bacuta, D. Hayes, and J. Jacavage.  Notes on a saddle point reformulation of mixed variational problems.  Comput. Math. Appl., 95:4–18, 2021.
  * [7] C. Bacuta, P. Vassilevski, and S. Zhang.  A new approach for solving Stokes systems arising from a distributive relaxation method.  Numerical Methods for Partial Differential Equations, 27:4, 898-914, 2011.
  * [8] C. Bacuta, D. Hayes, and J. Jacavage.  Efficient discretization and preconditioning of the singularly perturbed reaction-diffusion problem.  Comput. Math. Appl., 109:270–279, 2022.
  * [9] C. Bacuta, D. Hayes, and T. O’Grady.  Results on a Mixed Finite Element Approach for a Model Convection-Diffusion Problem  Comput. Math. Appl., submitted, 2023.
  * [10] C. Bacuta and P. Monk.  Multilevel discretization of symmetric saddle point systems without the discrete LBB condition.  Appl. Numer. Math., 62(6):667–681, 2012.
  * [11] C. Bacuta and K. Qirko.  A saddle point least squares approach to mixed methods.  Comput. Math. Appl., 70(12):2920–2932, 2015.
  * [12] C. Bacuta and K. Qirko.  A saddle point least squares approach for primal mixed formulations of second order PDEs.  Comput. Math. Appl., 73(2):173–186, 2017.
  * [13] S. Bartels.  Numerical approximation of partial differential equations, volume 64 of Texts in Applied Mathematics.  Springer, [Cham], 2016.
  * [14] D. Boffi, F. Brezzi, L. Demkowicz, R. G. Durán, R. Falk, and M. Fortin.  Mixed finite elements, compatibility conditions, and applications, volume 1939 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin; Fondazione C.I.M.E., Florence, 2008.  Lectures given at the C.I.M.E. Summer School held in Cetraro, June 26–July 1, 2006, Edited by Boffi and Lucia Gastaldi.
  * [15] D. Boffi, F. Brezzi, and M. Fortin.  Mixed finite element methods and applications, volume 44 of Springer Series in Computational Mathematics.  Springer, Heidelberg, 2013.
  * [16] T. Bouma, J. Gopalakrishnan, and A. Harb.  Convergence rates of the DPG method with reduced test space degree.  Comput. Math. Appl., 68(11):1550–1561, 2014.
  * [17] F. Brezzi, D. Marini, and A. Russo.  Applications of the pseudo residual-free bubbles to the stabilization of convection-diffusion problems.  Comput. Methods Appl. Mech. Engrg., 166(1-2):51–63, 1998.
  * [18] L. Demkowicz C. Carstensen and J. Gopalakrishnan.  Breaking spaces and form for the DPG method and applications including maxwell equations.  Computers and Mathematics with Applications, 72:494–522, 2016.
  * [19] A. Cohen, W. Dahmen, and G. Welper.  Adaptivity and variational stabilization for convection-diffusion equations.  ESAIM Math. Model. Numer. Anal., 46(5):1247–1273, 2012.
  * [20] L. Demkowicz, T. Führer, N. Heuer, and X. Tian.  The double adaptivity paradigm (how to circumvent the discrete inf-sup conditions of Babuška and Brezzi).  Technical report, 2021.
  * [21] L. Demkowicz and J. Gopalakrishnan.  A class of discontinuous Petrov-Galerkin methods. Part I: the transport equation.  Comput. Methods Appl. Mech. Engrg., 199(23-24):1558–1572, 2010\.
  * [22] L. Demkowicz and J. Gopalakrishnan.  A class of discontinuous Petrov–Galerkin methods. ii. optimal test functions.  Numerical Methods for Partial Differential Equations, 27(1):70–105, 2011.
  * [23] L. Demkowicz and L. Vardapetyan.  Modelling electromagnetic/scattering problems using hp-adaptive finite element methods.  Comput, Methods Appl. Mech. Engrg. Numerical Mathematics, 152:103 – 124, 1998.
  * [24] J. Gopalakrishnan.  Five lectures on DPG methods.  arXiv 1306.0557, 2013.
  * [25] T. J. R. Hughes and A. Brooks.  A multidimensional upwind scheme with no crosswind diffusion.  In Finite element methods for convection dominated flows (Papers, Winter Ann. Meeting Amer. Soc. Mech. Engrs., New York, 1979), volume 34 of AMD, pages 19–35. Amer. Soc. Mech. Engrs. (ASME), New York, 1979.
  * [26] K. W. Morton J. W. Barrett, and.  Optimal Petrov-Galerkin methods through approximate symmetrization.  IMA J. Numer. Anal., 1(4):439–468, 1981.
  * [27] R. Lin and M. Stynes.  A balanced finite element method for singularly perturbed reaction-diffusion problems.  SIAM Journal on Numerical Analysis, 50(5):2729–2743, 2012.
  * [28] Alfio Quarteroni, Riccardo Sacco, and Fausto Saleri.  Numerical mathematics, volume 37 of Texts in Applied Mathematics.  Springer-Verlag, Berlin, second edition, 2007.
  * [29] H.-G. Roos, M. Stynes, and L. Tobiska.  Numerical methods for singularly perturbed differential equations, volume 24 of Springer Series in Computational Mathematics.  Springer-Verlag, Berlin, 1996.  Convection-diffusion and flow problems.
  * [30] H.G. Roos and M. Schopf.  Convergence and stability in balanced norms of finite element methods on shishkin meshes for reaction-diffusion problems: Convergence and stability in balanced norms.  ZAMM Journal of applied mathematics and mechanics: Zeitschrift für angewandte Mathematik und Mechanik, 95(6):551–565, 2014.


# On a problem of Nathanson related to minimal asymptotic bases of order $h$

Shi-Qiang Chen, Csaba Sándor , Quan-Hui Yang School of Mathematics and
Statistics, Anhui Normal University, Wuhu 241003, P. R. China;
<EMAIL_ADDRESS>of Stochastics, Institute of Mathematics and
Department of Computer Science and Information Theory, Budapest University of
Technology and Economics, Műegyetem rkp. 3., H-1111 Budapest, Hungary; MTA-BME
Lendület Arithmetic Combinatorics Research Group, ELKH, Műegyetem rkp. 3.,
H-1111 Budapest, Hungary. Email<EMAIL_ADDRESS>This author was
supported by the NKFIH Grants No. K129335.School of Mathematics and
Statistics, Nanjing University of Information Science and Technology, Nanjing
210044, China<EMAIL_ADDRESS>
###### Abstract

For integer $h\geq 2$ and $A\subseteq\mathbb{N}$, we define $hA$ to be all
integers which can be written as a sum of $h$ elements of $A$. The set $A$ is
called an asymptotic basis of order $h$ if $n\in hA$ for all sufficiently
large integers $n$. An asymptotic basis $A$ of order $h$ is minimal if no
proper subset of $A$ is an asymptotic basis of order $h$. For
$W\subseteq\mathbb{N}$, denote by $\mathcal{F}^{*}(W)$ the set of all finite,
nonempty subsets of $W$. Let $A(W)$ be the set of all numbers of the form
$\sum_{f\in F}2^{f}$, where $F\in\mathcal{F}^{*}(W)$. In this paper, we give
some characterizations of the partitions $\mathbb{N}=W_{1}\cup\cdots\cup
W_{h}$ with the property that $A=A(W_{1})\cup\cdots\cup A(W_{h})$ is a minimal
asymptotic basis of order $h$. This generalizes a result of Chen and Chen,
recent result of Ling and Tang, and also recent result of Sun.

2010 Mathematics Subject Classification: 11B13

Keywords and phrases: Asymptotic bases; minimal asymptotic bases; binary
representation

##  1 Introduction

Let $\mathbb{N}$ be the set of all nonnegative integers. For integer $h\geq 2$
and $A\subseteq\mathbb{N}$, we define

$hA=\\{n:n=a_{1}+\cdots+a_{h},a_{i}\in A,i=1,2,\ldots,h\\}.$

The set $A$ is called an asymptotic basis of order $h$ if $n\in hA$ for all
sufficiently large integers $n$. An asymptotic basis $A$ of order $h$ is
minimal if no proper subset of $A$ is an asymptotic basis of order $h$. This
means that for any $a\in A$, the set $E_{a}=hA\setminus h(A\setminus\\{a\\})$
is infinite.

Let $W$ be a nonempty subset of $\mathbb{N}$. Denote by $\mathcal{F}^{*}(W)$
the set of all finite, nonempty subsets of $W$. Let $A(W)$ be the set of all
numbers of the form $\sum\limits_{f\in F}2^{f}$, where
$F\in\mathcal{F}^{*}(W)$.

In 1988, Nathanson [8] gave a construction of minimal asymptotic bases of
order $h$.

######  Theorem A.

Let $h\geq 2$ and let $W_{i}=\\{n\in\mathbb{N}:n\equiv i\pmod{h}\\}$ for
$i=0,1,\ldots,h-1$. Let $A=A(W_{0})\cup A(W_{1})\cup\cdots\cup A(W_{h-1})$.
Then $A$ is a minimal asymptotic basis of order $h$.

Let $h\geq 2$ and $\mathbb{N}=W_{1}\cup\cdots\cup W_{h}$ be a partition such
that $W_{i}\cap W_{j}=\emptyset$ if $i\neq j$. The following all partitions
meet this condition. Nathanson also posed the following open problem:

######  Problem 1.1.

Characterise the partitions $\mathbb{N}=W_{1}\cup\cdots\cup W_{h}$ with the
property that $A=A(W_{1})\cup\cdots\cup A(W_{h})$ is a minimal asymptotic
basis of order $h$?

In 2011, Chen and Chen [1] solved Problem 1.1 for $h=2$.

######  Theorem B.

Let $\mathbb{N}=W_{1}\cup W_{2}$ be a partition with $0\in W_{1}$ such that
$W_{1}$ and $W_{2}$ are infinite. Then $A=A(W_{1})\cup A(W_{2})$ is a minimal
asymptotic basis of order $2$ if and only if either $W_{1}$ contains no
consecutive integers or $W_{2}$ contains consecutive integers or both.

In 2020, Ling and Tang [7] focus on Problem 1.1 for $h=3$, they proved that
the following result:

######  Theorem C.

For any $i\in\\{0,1,2,3,4,5\\}$, if $W_{0}=\\{n\in\mathbb{N}:n\equiv
i,i+1\pmod{6}\\}$, $W_{1}=\\{n\in\mathbb{N}:n\equiv i+2,i+4\pmod{6}\\}$ and
$W_{2}=\\{n\in\mathbb{N}:n\equiv i+3,i+5\pmod{6}\\}$, then $A=A(W_{0})\cup
A(W_{1})\cup A(W_{2})$ is a minimal asymptotic basis of order three.

In 2021, Sun [10] gave a generalization of Theorem A.

######  Theorem D.

Let $h$ and $t$ be two positive integers with $h\geq 2$. Let

$W_{j}=\bigcup_{i=0}^{\infty}[iht+jt,iht+jt+t-1]$

for $j=0,1,\cdots,h-1$. Then $A=A(W_{0})\cup A(W_{1})\cup\cdots\cup
A(W_{h-1})$ is a minimal asymptotic basis of order $h$.

In 2011, Chen and Chen gave a sufficient condition for Problem 1.1.

######  Theorem E.

Let $h\geq 2$ and $r$ be the least integer with $r>\log h/\log 2$. Let
$\mathbb{N}=W_{1}\cup\dots\cup W_{h}$ be a partition such that each set
$W_{i}$ is infinite and contains $r$ consecutive integers for $i=1,\dots,h$.
Then $A=A(W_{1})\cup\dots\cup A(W_{h})$ is a minimal asymptotic basis of order
$h$.

For other related results about minimal asymptotic bases, see [2-6,9,11].

In this paper, we continue focus on Problem 1.1, we give a generalization of
Theorem C and Theorem D. For $W\subseteq\mathbb{N}$, set $W(x)=|\\{n\in
W:n\leq x\\}|$.

######  Theorem 1.2.

Let $h\geq 2$ be an integer and $\mathbb{N}=W_{1}\cup\cdots\cup W_{h}$ be a
partition such that each set $W_{j}~{}(1\leq j\leq h)$ satisfying
$|W_{j}(ht-1)|=t$ for infinitely many integers $t$. Then
$A=A(W_{1})\cup\cdots\cup A(W_{h})$ is a minimal asymptotic basis of order
$h$.

The second theorem is a generalization of Theorem E.

######  Theorem 1.3.

Let integer $h\geq 2$ and $\mathbb{N}=W_{1}\cup\dots\cup W_{h}$ be a partition
such that each set $W_{i}$ is infinite for $i=1,\dots,h$, $0\in W_{1}$ and
every $W_{i}$ contains $\lceil\frac{\log(h+1)}{\log 2}\rceil$ consecutive
integers for $i=2,\dots,h$. Then $A=A(W_{1})\cup\dots\cup A(W_{h})$ is a
minimal asymptotic basis of order $h$.

######  Remark 1.4.

It is easy to see that $\lceil\frac{\log(h+1)}{\log 2}\rceil$ is the least
integer greater than $\log h/\log 2$.

##  2 Lemmas

######  Lemma 2.1.

(See [8, Lemma 1].) Let $\mathbb{N}=W_{1}\cup\cdots\cup W_{h}$, where
$W_{i}\neq\emptyset$ for $i=1,\ldots,h$. Then $A=A(W_{1})\cup\cdots\cup
A(W_{h})$ is an asymptotic basis of order $h$.

######  Lemma 2.2.

Let $w_{1},\ldots,w_{s}$ be $s$ distinct nonnegative integers. If

$\sum\limits_{i=1}^{s}2^{w_{i}}\equiv\sum\limits_{j=1}^{t}2^{x_{j}}\pmod{2^{w_{s}+1}},$

where $0\leq x_{1},\ldots,x_{t}<w_{s}+1$ are integers that not necessarily
distinct, then there exist nonempty disjoint sets $J_{1},\ldots,J_{s}$ of
$\\{1,2,\ldots,t\\}$ such that

$2^{w_{i}}=\sum\limits_{j\in J_{i}}2^{x_{j}}$

for $i=1,\ldots,s$.

###### Proof.

By the proof of Lemma 2 from [8], there exist nonempty subsets
$J_{1},\ldots,J_{s}$ of $\\{1,2,\ldots,t\\}$ such that

$2^{w_{i}}=\sum\limits_{j\in J_{i}}2^{x_{j}}$

for $i=1,\ldots,s$.

The result is trivial for $s=1$. Now we assume that $s\geq 2$. Since there
exists a subset $J_{1}$ of $\\{1,2,\ldots,t\\}$ such that

$2^{w_{1}}=\sum\limits_{j\in J_{1}}2^{x_{j}},$

it follows that

$\sum\limits_{2\leq i\leq
s}2^{w_{i}}\equiv\sum\limits_{j\in\\{1,\ldots,t\\}\setminus
J_{1}}2^{x_{j}}\pmod{2^{w_{s}+1}},$

which implies that there exists a subset $J_{2}$ of
$\\{1,2,\ldots,t\\}\setminus J_{1}$ such that

$2^{w_{2}}=\sum\limits_{j\in J_{2}}2^{x_{j}},$

and so $J_{1}\cap J_{2}=\emptyset$. Continuing this process, it follows that
there exist nonempty disjoint subsets $J_{1},\ldots,J_{s}$ of
$\\{1,2,\ldots,t\\}$ such that

$2^{w_{i}}=\sum\limits_{j\in J_{i}}2^{x_{j}},$

for $i=1,\ldots,s$.

This completes the proof of Lemma 2.2. ∎

##  3 Proof of Theorem 1.2

By Lemma 2.1, it follows that $A$ is an asymptotic basis of order $h$. For any
$a\in A$, there exists $j\in\\{1,2,\ldots,h\\}$ such that $a\in A(W_{j})$.
Without loss of generality, we may assume that $a\in A(W_{1})$. Then there
exists a set $K\subseteq W_{1}$ such that $a=\sum\limits_{i\in K}2^{i}$. Since
there exist infinitely many $t$ such that

$|W_{j}(ht-1)|=t$

for $j=1,2,\ldots,h$, it follows that there exists an integer $t_{n}$ such
that

$t_{n}h\leq\min K<t_{n+1}h.$

Let

$n_{T}=a+\sum\limits_{j=2}^{h}\sum\limits_{v\in
W_{j}\cap[0,t_{n+1}h-1]}2^{v}+\sum\limits_{j=2}^{h}\sum\limits_{v\in
W_{j}\cap[t_{n+1}h,T]}2^{v},$

where $T$ is an integer such that $2^{T}>a$. Next we shall prove $n_{T}\in
E_{a}$. Noting that $K(t_{n+1}h-1)\neq\emptyset$ and

$n_{T}=\sum\limits_{j\in
K(t_{n+1}h-1)}2^{j}+\sum\limits_{j=2}^{h}\sum\limits_{v\in
W_{j}\cap[0,t_{n+1}h-1]}2^{v}+2^{t_{n+1}h}m$

for some $m\geq 0$. Let $n_{T}=b_{1}+b_{2}+\cdots+b_{h}$ be any representation
of $n_{T}$ as a sum of $h$ elements of $A$ and let

$b_{i}=\sum\limits_{i\in S_{i}}2^{i}$

for $i=1,2\ldots,h$. Let

$c_{i}=\sum\limits_{j\in S_{i}(t_{n+1}h-1)}2^{j}$

for $i=1,2,\ldots,h$. Then

$c_{i}\equiv b_{i}\pmod{2^{t_{n+1}h}}$

and

$|S_{i}(t_{n+1}h-1)|\leq t_{n+1}$

for $i=1,2,\ldots,h$, which implies that

$\sum\limits_{k\in K(t_{n+1}h-1)}2^{k}+\sum\limits_{j=2}^{h}\sum\limits_{v\in
W_{j}\cap[0,t_{n+1}h-1]}2^{v}\equiv\sum\limits_{1\leq i\leq
h}c_{i}\equiv\sum\limits_{1\leq i\leq h}\sum\limits_{j\in
S_{i}(t_{n+1}h-1)}2^{j}\pmod{2^{t_{n+1}h}}.$

Let

$\sum\limits_{k\in K(t_{n+1}h-1)}2^{k}+\sum\limits_{j=2}^{h}\sum\limits_{v\in
W_{j}\cap[0,t_{n+1}h-1]}2^{v}\equiv\sum\limits_{j=1}^{s}2^{x_{j}}\pmod{2^{t_{n+1}h}},$

where $s$ is an integer such that $s\leq t_{n+1}h$. By Lemma 2.2, there exist
nonempty disjoint subsets $J_{0},J_{1},\ldots,J_{t_{n+1}(h-1)}$ of
$\\{1,2,\ldots,s\\}$ such that

$2^{\min K}+\sum\limits_{j=2}^{h}\sum\limits_{v\in
W_{j}\cap[0,t_{n+1}h-1]}2^{v}=\sum\limits_{j\in
J_{0}}2^{x_{j}}+\sum\limits_{j\in J_{1}}2^{x_{j}}+\sum\limits_{j\in
J_{2}}2^{x_{j}}+\cdots+\sum\limits_{j\in J_{t_{n+1}(h-1)}}2^{x_{j}}.$

Therefore,

$1+t_{n+1}(h-1)\leq 1+|J_{1}|+\cdots+|J_{t_{n+1}(h-1)}|\leq s\leq t_{n+1}h,$

and so

$t_{n+1}(h-1)\leq|J_{1}|+\cdots+|J_{t_{n+1}(h-1)}|\leq t_{n+1}h-1.$ (1)

Since $|W_{j}(t_{n+1}h-1)|=t_{n+1}$ for any $j\geq 2$, it follows from (1) and
Lemma 2.2 that for any $j\geq 2$, there exist $w\in W_{j}$,
$J\subseteq\\{1,2,\ldots,s\\}$ and $|J|=1$ such that

$2^{w}=\sum\limits_{j\in J}2^{x_{j}},$

which implies that $x_{j}=w\in W_{j}$, and so

$\\{b_{1},\ldots,b_{h}\\}\not\subseteq\bigcup\limits_{j=1,j\neq
m}^{h}A(W_{j})$

for any $m\geq 2$. Renumbering the indexes, we always assume that

$b_{i}\in A(W_{i}),~{}~{}~{}i\geq 2.$

Then

$b_{1}=a+\left(\sum\limits_{j=2}^{h}\sum\limits_{v\in
W_{j}\cap[0,t_{n+1}h-1]}2^{v}+\sum\limits_{j=2}^{h}\sum\limits_{v\in
W_{j}\cap[t_{n+1}h,T]}2^{v}-\sum\limits_{2\leq i\leq h}b_{i}\right).$

Since the binary representation of $b_{1}$ is unique, it follows that
$b_{1}=a$, that is $n_{T}\in E_{a}$. Noting that $T$ is infinite, we have $A$
is minimal.

This completes the proof of Theorem 1.2.

##  4 Proof of Theorem 1.3

By Lemma 2.1, it follows that $A$ is an asymptotic basis of order $h$. For
$a\in A$, we assume that $a\in A(W_{i})$. Let $E_{a}=hA\setminus
h(A\setminus\\{a\\})$. Now we prove that $E_{a}$ is infinite.

Let

$n_{T}=a+\sum_{w\in[0,T]\setminus W_{i}}2^{w},$

where $T$ is an integer with $T>a$ such that each $[0,T]\cap W_{j}$ contains
$\lceil\frac{\log(h+1)}{\log 2}\rceil$ consecutive integers for
$j=2,\ldots,h$. To prove $n_{T}\in E_{a}$, it suffices to prove that if
$n_{T}=a_{1}+a_{2}+\dots+a_{h}$ with $a_{i}\in A$ for $1\leq i\leq h$, then
there exists at least one $a_{k}=a$.

We distinguish two cases according to whether $i=1$ or $2\leq i\leq h$.

Case 1. $i=1$. Suppose that there exists an integer $j\geq 2$ such that

$\\{a_{1},a_{2},\dots,a_{h}\\}\subseteq\bigcup_{1\leq l\leq h,l\neq
j}A(W_{j}).$

Let $\\{b+1,b+2,\dots,b+\lceil\frac{\log(h+1)}{\log
2}\rceil\\}\subseteq[0,T]\cap W_{j}$. Then by Lemma 2.2 there exists

$\\{a_{1}^{\prime},\dots,a_{h}^{\prime}\\}\subseteq\bigcup_{1\leq l\leq
h,l\neq j}A(W_{j})\cup\\{0\\}$

such that

$2^{b+1}+\cdots+2^{b+\lceil\frac{\log(h+1)}{\log
2}\rceil}=a_{1}^{\prime}+\cdots+a_{h}^{\prime}.$

Since $a_{i}^{\prime}\notin A(W_{j})$ for $i=1,\dots,h$, we have

$a_{i}^{\prime}\leq 2^{0}+2^{1}+\cdots+2^{b}=2^{b+1}-1$

for $i=1,\dots,h$. It follows that

$2^{b+1}+\cdots+2^{b+\lceil\frac{\log(h+1)}{\log 2}\rceil}\leq
h(2^{b+1}-1)<h2^{b+1},$

that is $2^{\lceil\frac{\log(h+1)}{\log 2}\rceil}-1<h$, a contradiction.
Hence, for any integer $j\geq 2$, we have

$\\{a_{1},a_{2},\ldots,a_{h}\\}\nsubseteq\bigcup_{1\leq l\leq h,l\neq
j}A(W_{l}).$

Renumbering the indexes, we may assume that $a_{i}\in A(W_{i})$ for
$i=2,3,\dots,h$. It follows that

$a_{1}=a+\sum_{2\leq j\leq h}(\sum_{w\in[0,T]\cap W_{j}}2^{w}-a_{j}).$

Since $a\in A(W_{1})$, $W_{1},\dots,W_{h}$ are disjoint, and the binary
representation of $a_{1}$ is unique, we have $a_{1}=a$. Therefore $n_{T}\in
E_{a}$, and $E_{a}$ is infinite.

Case 2. $i\geq 2$. Since $n_{T}$ is odd, therefore we may assume that
$a_{1}\in A(W_{1})$. Let $2\leq j\leq h$, $j\neq i$. Similar to the Case 1, we
get that

$\\{a_{1},\dots,a_{h}\\}\nsubseteq\bigcup_{1\leq k\leq h,k\neq j}A(W_{k}).$

Renumbering the indexes, we may assume that $a_{j}\in A(W_{j})$ for
$j=2,3,\dots,i-1,i+1,\dots,h$. It follows that

$a_{i}=a+\sum_{1\leq j\leq h,j\neq i}(\sum_{w\in[0,T]\cap W_{j}}2^{w}-a_{j}).$

Since $a\in A(W_{i})$, $W_{1},\dots,W_{h}$ are disjoint, and the binary
representation of $a_{i}$ is unique, we have $a_{i}=a$. Therefore $n_{T}\in
E_{a}$, and $E_{a}$ is infinite.

This completes the proof.

## References

  * [1] F.J. Chen, Y.G. Chen, On minimal asymptotic bases, European J. Comb. 32 (2011) 1329-1335.
  * [2] Y.G. Chen, M. Tang, On a problem of Nathanson, Acta Arith. 185 (2018) 275-280.
  * [3] P. Erdős, M.B. Nathanson, Minimal asymptotic bases for the natural numbers, J. Number Theory 12 (1980) 154-159.
  * [4] E. Härtter, Ein Beitrag zur Theorie der Minimalbasen, J. Reine Angew. Math. 196 (1956) 170-204.
  * [5] M. Jańczak, T. Schoen, Dense minimal asymptotic bases of order two, J. Number Theory 130 (2010) 580-585.
  * [6] X.D. Jia, M.B. Nathanson, A simple construction of minimal asymptotic bases, Acta Arith. 52 (1989) 95-101.
  * [7] D.R. Ling, M. Tang, Some remarks on minimal asymptotic bases of order three, Bull. Aust. Math. Soc. 102 (2020) 21-30.
  * [8] M.B. Nathanson, Minimal bases and powers of $2$, Acta Arith. 49 (1988) 525-532.
  * [9] A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe II, J. Reine Angew. Math. 194 (1955) 111-140.
  * [10] C.F. Sun, On a problem of Nathanson on minimal asymptotic bases, J. Number Theory 218 (2021) 152-160.