January 31, 2024
Can graded meshes yield more accurate numerical solution than uniform meshes? A time-dependent nonlocal diffusion problem with a weakly singular kernel is considered using collocation method. For its steady-state counterpart, under the sufficiently smooth solution, we first clarify that the standard graded meshes are worse than uniform meshes and may even lead to divergence; instead, an optimal convergence rate arises in so-called anomalous graded meshes. Furthermore, under low regularity solutions, it may suffer from a severe order reduction in (Chen, Qi, Shi and Wu, IMA J. Numer. Anal., 41 (2021) 3145–3174). In this case, conversely, a sharp error estimates appears in standard graded meshes, but offering far less than first-order accuracy. For the time-dependent case, however, second-order convergence can be achieved on graded meshes. The related analysis are easily extended for certain multidimensional problems. Numerical results are provided that confirm the sharpness of the error estimates.
nonlocal diffusion problems; graded meshes; low regularity solution; error analysis.
Nonlocal diffusion problems have been used to model very different applied situations [1]–[3], for example in biology, mechanics, coagulation models, image processing, particle systems, and nonlocal anisotropic models for phase transition, etc. In this paper, we study an error estimates of a collocation method on graded meshes for solving the time-dependent nonlocal diffusion problems with weakly singular kernels, whose prototype equations are [1], [2] \[\label{equ1461} \left\{ \begin{align} u_t(x,t) - \mathcal{L}u(x,t) &=f(x,t), & & x \in \Omega,\, t>0,\\ u(x,0)&=u_0(x), & & x \in \Omega,\\ u(x,t)&=0, & & x \in \mathbb{R}\setminus \Omega, \end{align} \right.\tag{1}\] and its steady-state counterpart \[\label{equ1462} \left\{ \begin{align} - \mathcal{L} u(x) &=f(x), & & x \in \Omega,\\ u(x)&=0, & &x \in \mathbb{R}\setminus \Omega. \end{align} \right.\tag{2}\] The nonlocal operator \(\mathcal{L}\) is defined by, for \(0<\alpha<1\), \[\label{equ1463} \mathcal{L}u(x)=\int_{\Omega} \frac{u(y)-u(x)}{|x-y|^\alpha}dy ~~\forall x \in \Omega.\tag{3}\] In this model, diffusion takes place inside \(\Omega\) and \(u\) vanishes outside \(\Omega\). In the biological interpretation, there is a hostile environment outside \(\Omega\), and any individual that jumps outside dies instantaneously [1]. The well-posedness (existence and uniqueness) is addressed in the monograph [1].
Note that Fredholm weakly singular integral equations of the second or third kind have the following form [4], [5] \[\lambda(x) u(x)- \int^b_a \frac{u(y)}{|x-y|^\alpha}dy =f(x), \quad x \in (a,b) ,\quad 0< \alpha <1,\] where \(\lambda(x)\) is a nonzero complex constant or vanishes at least once in the interval \([a,b]\), respectively. Nevertheless, the nonlocal models 2 may exhibit similarities but not belong to the aforementioned Fredholm integral equations, since the variable coefficients of 2 are great than zero, i.e., \[\lambda(x):=\int^b_a \frac{1}{|x-y|^\alpha}dy=\frac{1}{1-\alpha}\left[ \left(x-a\right)^{1-\alpha}+\left(b-x\right)^{1-\alpha} \right]>0,\quad 0< \alpha <1.\] Indeed, there still exist some significant differences between these two models. For example, the inverse operators of Fredholm integral equations of the second kind are uniformly bounded, see Theorem 4.2.1 in [4]. However, the inverse operators of nonlocal models 2 are unbounded, as shown in Lemma 3.5 of [6].
There has been some important progress in numerically solving nonlocal diffusion problems including finite element methods [7], collocation methods [8]–[10], fast conjugate gradient method [6], [7] and multigrid method [11]. Among various techniques for solving nonlocal problems 2 , collocation methods are the simplest, but unfortunately, it poses more challenges in numerical analysis. For example, Fredholm weakly singular integral equations of the second kind have second-order convergence [4]. However, the numerical results for 2 with \(\alpha=1\) indicate that the convergence rate appears to be close to 1.5 [8], although it remains to be proved. In fact, it exhibits only first-order convergence under the sufficiently smooth solution [10].
As mentioned above in [8]–[10], the convergence rates both assume that the unknown solution has several continuous derivatives. However, the solution is rarely smoothly differentiable; instead, it often exhibits somewhat singular behavior in the neighborhood of the boundary. These phenomena arise naturally in the integral equation with singular kernels, such as Volettra integral equation[12], Fredholm integral equation [13], time-fractional diffusion equation [14], and nonlocal/regional fractional Laplacian [15]–[18] with the low regularity of the solutions \[\label{equ1464} \begin{align} \left|\frac{\partial^{\ell} }{\partial x ^{\ell}} u(x)\right| & \le C[(x-a)(b-x)]^{\sigma-\ell}, ~0<\sigma<1 \;\text{ for } \ell=0,1,2. \end{align}\tag{4}\] To capture the multi-scale/singularities behaviors and achieve more accurate, the graded meshes technique are effectively employed for such problems [14], [15], [17].
Can graded meshes yield more accurate numerical solutions than uniform meshes? For steady-state counterpart 2 , under the sufficiently smooth of the solutions, we provide a sharp error estimate in Theorem 1, namely, \[\max_{1\leq i \leq 2N-1} |u(x_i)-u_{i}| \leq \begin{cases} C N^{r-2}, & {\rm if}~~r>\frac{2}{3}, \\ C N^{r-2}\ln N, & {\rm if}~~r=\frac{2}{3}, \\ C N^{-2r}, & {\rm if}~~r<\frac{2}{3}. \end{cases}\] Here \(u_i\) is the approximate solution of \(u(x_{i})\), \(N\) is the number of grid points, and \(r> 1\) is the grading exponent of the standard graded meshes; instead, for \(0<r< 1\), is called anomalous graded meshes. These results imply that the standard graded meshes are worse than the uniform grid and even lead to divergence for \(r\geq 2\). It also indicates that an optimal convergence rate (great than one) arises in anomalous graded meshes. Conversely, a sharp error estimate (far less than one) appears in standard graded meshes with the low regularity of solution 4 , since it possess the following convergence rate as shown in Theorem 2 \[\max_{1\leq i \leq 2N-1} |u(x_i)-u_{i}| \leq \begin{cases} C N^{r-2} , &{\rm if}~~ r> \frac{2}{\sigma+1},\\ C N^{r-2} \ln N, &{\rm if}~~ r =\frac{2}{\sigma+1}, \\ C N^{-r \sigma}, &{\rm if}~~ r <\frac{2}{\sigma+1}. \\ \end{cases}\] Finally, second-order convergence \(\mathcal{O}\left( N^{-\min \left\{r \left(1+\sigma-\alpha\right), \,2 \right\} } \right)\) can be achieved on graded meshes for the time-dependent nonlocal problems 1 under the low regularity of solution 4 , as demonstrated in Theorem 3.
In this section, we derive numerical discretization schemes for nonlocal diffusion problem 1 and the corresponding steady-state problem 2 in \(\Omega:=(a,b) \subseteq \mathbb{R}\), respectively.
Let the partition \(\pi_h\) with the interval \((a,b)\) \[\pi_h: a =x_{0}<x_{1}<x_{2}<\dots<x_{2N-1}<x_{2N}=b.\] We focus on graded meshes as \[\label{neq2461} x_j= \begin{cases} a+\frac{b-a}{2}\left( \frac{j}{N} \right)^r, & j=0,1,\dots ,N,\\ b-\frac{b-a}{2}\left(2-\frac{j}{N} \right)^r, & j=N+1,N+2,\dots ,2N \end{cases}\tag{5}\] with the grid sizes \(h_j :=x_j-x_{j-1}\). Here \(r> 1\) is the grading exponent of the standard graded meshes. We extend it, for \(0<r< 1\), called anomalous graded meshes.
Let \(S^{h}\) be the space of continuous piecewise-linear polynomials defined with respect to the partition \(\pi_h\) and choose the standard hat functions as a basis which we denote as \(\left\{\phi_{j }(x) \right\}_{0}^{2N}\). Namely, the piecewise linear basis function is defined by \[\phi_j(x)= \begin{cases} \frac{x-x_{j-1}}{x_j-x_{j-1}}, & x \in \left[x_{j-1}, x_{j}\right],\\ \frac{x_{j+1}-x}{x_{j+1}-x_j}, & x \in \left[x_{j}, x_{j+1}\right],\\ 0, & {\rm otherwise}, \end{cases}\] with \(j=1,\cdots,2N-1\), \[\phi_{0}(x)= \begin{cases} \frac{x_{1}-x}{x_{1}-x_0}, & x \in \left[x_{0}, x_{1}\right],\\ 0, & {\rm otherwise}, \end{cases} ~~~{\rm and}~~~ \phi_{2N}(x)= \begin{cases} \frac{x-x_{2N-1}}{x_{2N}-x_{2N-1}}, & x \in \left[x_{2N-1}, x_{2N}\right],\\ 0, & {\rm otherwise}. \end{cases}\]
Let \(\Pi_{h} u(x)\) be the piecewise linear interpolation approximation for the solution \(u(x)\) with homogeneous Dirichlet boundary conditions, namely, \[\Pi_{h} u(x)=\sum_{k=0}^{2N} u \left(x_{k}\right) \phi_{k}(x)=\sum_{k=1}^{2N-1} u \left(x_{k}\right) \phi_{k}(x).\]
Taking it into 2 yields approximation for the value of \(-\mathcal{L} u(x_{i})\) given by \[\begin{align} -\mathcal{L}[\Pi_{h} u](x_{i}) &= \int_{a}^{b} \frac{\sum_{k=1}^{2N-1} u \left(x_{k}\right) \phi_{k}(x_{i}) -\sum_{k=1}^{2N-1} u \left(x_{k}\right) \phi_{k}(y)}{\left|x_{i}-y\right|^{\alpha}} \, d{y} =\sum_{k=1}^{2N-1} a_{i,k} u \left(x_{k}\right) \end{align}\] with the coefficients \[\label{neq2462} a_{i,k}:= \int_{a}^{b} \frac{ \phi_{k}(x_{i}) - \phi_{k}(y)}{\left|x_{i}-y\right|^{\alpha}} \, dy,~~~i,k=1,2,\cdots,2N-1.\tag{6}\] Therefore, we can rewrite 2 as \[\label{neq2463} -\mathcal{L}[\Pi_{h} u](x_{i}) =f(x_{i}) +R_{i}, ~~~i=1,2,\cdots,2N-1,\tag{7}\] with the local truncation error \[\label{nequ2464} R_{i}=\mathcal{L}[u-\Pi_{h}u](x_{i})=\int_{a}^{b} {\frac{u(y)-\Pi_{h}u(y)}{|x_{i}-y|^{\alpha}}\,dy}.\tag{8}\]
Let \(u_{i}\) be the approximation of \(u(x_{i})\) and \(f_{i}:=f(x_{i})\). It yields the follow numerical scheme by 7 : \[\mathcal{L}_h u_{i} =f_{i}~~~{\rm with}~~~\mathcal{L}_h u_{i}:=\sum_{k=1}^{2N-1}a_{i,k}u_{k}.\] In particular, the above system of equations has the matrix form \[\label{nequ2465} AU=F,\tag{9}\] where the coefficient matrix \(A\) and the matrix of the grid function are defined by \[A=(a_{i,k})\in \mathbb{R}^{\left(2N-1\right)\times \left(2N-1\right)} , \;U=(u_{1},\dots,u_{2N-1})^T, \;F=(f_{1},\dots,f_{2N-1})^T.\]
In the time direction, we use Crank-Nicolson scheme [19] on uniform meshes with \(t_{j}=j\tau\), \(\tau=\frac{1}{M}\), \(j=0,1,\cdots, M\). Here we mainly focus on the space direction, since the convergence rate with \(\mathcal{O}\left( M^{-2 } \right)\) of the time discretization is well understood.
Let \(u_i^j\) be the approximation of \(u(x_{i},t_{j})\) and \(f_{i}^j=f(x_{i},t_j)\). From 9 , the full discretization of nonlocal diffusion problem 1 has the matrix form \[\label{nequ2466} \left(I+\frac{\tau }{2}A\right) U^{j}=\left(I-\frac{\tau }{2}A\right) U^{j-1}+ \tau F^{j-\frac{1}{2}},~~~j=1,2,\cdots,M,\tag{10}\] where the coefficient matrix \(A\) is given in 9 and the matrix of the grid function are defined by \[U^{j}=(u_{1}^{j},\dots,u_{2N-1}^{j})^T, \;F^{j-\frac{1}{2}}=(f_{1}^{j-\frac{1}{2}},\dots,f_{2N-1}^{j-\frac{1}{2}})^T.\]
First, we give some lemmas that will be used.
Lemma 1. [20]A real matrix \(A\) of order \(n\) is positive definite if and only if its symmetric part \(H=\frac{A+A^T}{2}\) is positive definite. Let \(H \in \mathbb{R}^{n\times n}\) be symmetric. Then \(H\) is positive definite if and only if the eigenvalues of \(H\) are positive.
Lemma 2. [21]Assume \(A\) is diagonally dominant by rows. Then \[\left\|A^{-1} \right\|_{\infty} \leq \frac{1}{\delta}~~~{\rm with}~~~\delta=\min_{i} \left( \left|a_{i,i} \right| - \sum_{j\neq i} \left|a_{i,j}\right| \right).\]
Lemma 3. Let the matrix \(G_\alpha=(g_{i,j})\in \mathbb{R}^{\left(2N-1\right)\times \left(2N-1\right)}\) and its the element \(g_{i,j}:=\int_{a}^{b} \frac{ \phi_{j}({y})}{\left|x_{i}-y\right|^{\alpha}} \, dy\). Then \(G_\alpha\) is a positive matrix and \(g_{i,j}\) is explicitly computed as \[g_{i,j}=\frac{1}{\left(1-\alpha\right)\left(2-\alpha\right)}C_{j}Q_j^i>0\] with \[C_j= \left(\frac{1}{h_{j}},-\frac{1}{h_{j}}-\frac{1}{h_{j+1}},\frac{1}{h_{j+1}}\right) ~~~{\rm and}~~~ Q_{j}^{i}=\left( \begin{array}{c} \left| x_{j-1}-x_i \right|^{2-\alpha}\\ \left| x_j-x_i \right|^{2-\alpha}\\ \left| x_{j+1}-x_i \right|^{2-\alpha}\\\end{array} \right).\]
Proof. Taking \(C_{\alpha}:=\frac{1}{\left(1-\alpha\right)\left(2-\alpha\right)}\), we can check \(g_{i,i} =C_{\alpha} \left(h_{i+1}^{1-\alpha} +h_{i}^{1-\alpha} \right)>0.\) On the other hand, for \(j\neq i\), there exists \[\begin{align} g_{i,j} & = C_{\alpha} \left[\frac{\left|x_{i}-x_{j+1} \right|^{2-\alpha}}{h_{j+1}} - \frac{h_{j}+h_{j+1}}{h_{j}h_{j+1}}\left|x_{i}-x_{j}\right|^{2-\alpha} +\frac{\left|x_{i}-x_{j-1} \right|^{2-\alpha}}{h_{j}}\right]\\ & =C_{\alpha} \frac{h_{j}+h_{j+1}}{h_{j}h_{j+1}} \left[\frac{h_{j} \left|x_{i}-x_{j+1} \right|^{2-\alpha}}{h_{j}+h_{j+1}} - \left|x_{i}-x_{j}\right|^{2-\alpha} +\frac{h_{j+1} \left|x_{i}-x_{j-1} \right|^{2-\alpha}}{h_{j}+h_{j+1}}\right].\\ \end{align}\] Since \(\frac{h_{j} }{h_{j}+h_{j+1}} \left|x_{i}-x_{j+1} \right| +\frac{h_{j+1} }{h_{j}+h_{j+1}}\left|x_{i}-x_{j-1} \right| = \left|x_{i}-x_{j}\right|\) and \(x \mapsto x^{2-\alpha}\) is a convex function for \(x\geq 0\) under \(0<\alpha<1\), by Jensen’s inequality we have \[\frac{h_{j} }{h_{j}+h_{j+1}} \left|x_{i}-x_{j+1} \right|^{2-\alpha} +\frac{h_{j+1} }{h_{j}+h_{j+1}}\left|x_{i}-x_{j-1} \right|^{2-\alpha} >\left|x_{i}-x_{j}\right|^{2-\alpha},~j\neq i.\] The proof is completed. ◻
From 6 , 9 and Lemma 3, the entries of the stiffness matrix \(A=(a_{ij})\in\mathbb{R}^{\left(2N-1\right)\times \left(2N-1\right)}\) with \(\alpha \in (0,1)\) can be explicitly evaluated by \[\label{nequ2467} A=D_\alpha-G_\alpha,\tag{11}\] where the diagonal matrix \(D_\alpha\) is defined by \[D_\alpha={\rm diag}\left( d_{1},d_{2},\cdots,d_{2N-1}\right)~~{\rm with}~~d_{i}:=\int_{a}^{b}{\frac{dy}{|x_{i}-y|^{\alpha}}}\] for \(i=1,2,\cdots,2N-1\).
Lemma 4. Let the matrix \(A\) be defined by 9 . Then \(A\) is a strictly diagonally dominant matrix by rows with positive entries on the diagonal and nonpositive off-diagonal entries. Moreover, the linear equation 9 has a unique solution.
Proof. It is evident to observe that \[\label{nequ2468} \begin{align} a_{ii} & =\int_{x_{i-1}}^{x_{i+1}}{\frac{1-\phi_{i}\left(y\right)}{\left|x_{i}-y\right|^{\alpha}} \, dy}\\ & =\frac{1}{1-\alpha}\left[(x_{i}-a)^{1-\alpha}+(b-x_{i})^{1-\alpha} \right] - \frac{1}{\left(1-\alpha\right)\left(2-\alpha\right)} \left(h_{i}^{1-\alpha} + h_{i+1}^{1-\alpha} \right) >0\\ \end{align}\tag{12}\] and \(a_{i,j}=-g_{i,j}<0\) for \(j\neq i\) by Lemma 3.
On the other hand, for \(1\leq i\leq 2N-1\), using Taylor series expansion, we have \[\label{nequ2469} \begin{align} \sum_{j=1}^{2N-1}a_{i,j} & = \int_{a}^{b}{\frac{dy}{|x_{i}-y|^{\alpha}}} -\sum_{j=1}^{2N-1}\int_{x_{j-1}}^{x_{j+1}} {\frac{\phi_{j}\left(y\right)}{\left|x_{i}-y\right|^{\alpha}}\, dy} \\ &= \int_{x_{0}}^{x_{1}} {\frac{\phi_{0}\left(y\right)}{\left|x_{i}-y\right|^{\alpha}}\, dy} + \int_{x_{2N-1}}^{x_{2N}} {\frac{\phi_{2N}\left(y\right)}{\left|x_{i}-y\right|^{\alpha}}\, dy}\\ &= \frac{1}{1-\alpha} \left[\left(x_{i}-x_{0}\right)^{1-\alpha} - \frac{\left( x_{i}-x_{0}\right)^{2-\alpha}-\left( x_{i}-x_{1}\right)^{2-\alpha}}{\left(2-\alpha\right)h_{1}} \right]\\ &\quad+\frac{1}{1-\alpha} \left[\left(x_{2N}-x_{i} \right)^{1-\alpha} -\frac{\left( x_{2N}-x_{i}\right)^{2-\alpha}-\left( x_{2N-1}-x_{i}\right)^{2-\alpha}}{\left(2-\alpha\right)h_{2N}} \right]\\ & \geq \frac{1}{2}\left[ h_{1} \left(x_{i}-x_{0}\right)^{-\alpha} + h_{2N} \left(x_{2N}-x_{i}\right)^{-\alpha}\right]>0, \end{align}\tag{13}\] which implies that the matrix \(A\) is M-matrix. From Theorem 1.21 of [22], the matrix \(A\) is nonsigular. The proof is completed. ◻
Let the condition number \(\kappa_{p}= \left\|A\right\|_{p} \left\|A^{-1}\right\|_{p}\) with \(p=1,2,\cdots,\infty\). Then there is
Lemma 5. Let the matrix \(A\) is defined as 9 . Then the condition number \[\kappa_{\infty}=\left\|A\right\|_{\infty} \left\|A^{-1}\right\|_{\infty} = \mathcal{O} \left(N^{r}\right),\] where \(r\) is the grading exponent of graded meshes.
Proof. From Lemma 4 and 12 , we have \[\left\|A\right\|_{\infty}\leq 2 \max_{1\leq i \leq 2N-1} a_{i,i} \leq \frac{4}{1-\alpha} \left(b-a\right)^{1-\alpha}.\] On the other hand, it yields \(\left\|A^{-1}\right\|_{\infty} \leq 2 \left(\frac{b-a}{2}\right)^{\alpha} N^{r}\) by Lemma 2, since \[\begin{align} \left|a_{i,i} \right| - \sum_{j\neq i} \left|a_{i,j}\right| & =\sum_{j=1}^{2N-1} a_{i,j} \geq \frac{1}{2} \left(\frac{b-a}{2}\right)^{-\alpha} N^{-r}. \end{align}\] The proof is completed. ◻
Remark 1. From Lemma 4 and Theorem \(1.21\) of [22], it yields \[{\mathbb{R}}\left(\lambda(A)\right)>0\] and \(A\) nonsingular for \(r>0\). In particular, the matrix \(A\) is symmetric positive-definite for uniform meshes with \(r=1\).
However, from Lemma 1 and counter-example in Table [table2461], it shows that \[\min\left( \lambda\left(H\right) \right)<0,~~\max\left( \lambda\left(H\right) \right)>0~~{\rm with}~~H=\frac{A+A^T}{2}.\] That is, the matrix \(A\) may be a nonsymmetric and indefinite for graded meshes.
cells = c, hlines, vlines, \(r\) & 0.2 & 0.9 & 1 & 1.1 & 4
\(\max(\lambda(H))\) & 8.8728 & 5.5807 & 5.5766 & 5.5727 & 5.4974
\(\min(\lambda(H))\) & -4.6418 & -0.0023 & 0.0039 & -0.0046 & -0.8304
In this section, we first clarify that standard graded meshes perform worse than the uniform grid, and may even lead to divergence for the steady-state counterpart, despite the solution being sufficiently smooth. However, optimal convergence rates arise in anomalous graded meshes.
Without loss of generality, we take \(\Omega=\left( 0,2T\right)\) and rewrite 5 as \[\label{eqn3461} x_j= \begin{cases} T\left( \frac{j}{N} \right) ^r, &{\rm for}~~ j=0,1,\dots ,N,\\ 2T-T\left( 2-\frac{j}{N} \right) ^r, &{\rm for}~~ j=N+1,N+2,\dots ,2N. \end{cases}\tag{14}\] From the mean value theorem and the definition of \(\{h_j\}_{j=0}^{2N}\), it follows that [14], [16] \[\label{eqn3462} h_j =x_j-x_{j-1} \le \begin{cases} CN^{-r}j^{r-1}, \;&{\rm for}~~ j=1,\dots, N, \\ CN^{-r}(2N+1-j)^{r-1}, \;&{\rm for}~~ j=N+1,\dots, 2N. \end{cases}\tag{15}\] Note that \(h_{j}\leq CN^{-1}\) for standard graded meshes \(r\geq1\); however, \(h_1>{N}^{-1}\) for anomalous graded meshes \(0<r<1\).
Notation. Throughout this article and above, \(C\) denotes a positive constant, not necessarily the same at different occurrences, that is independent of \(N\) and of any index such as \(i\) or \(j\). For any real number \(s\in \mathbb{R}\), \(\lceil s \rceil\) represents the smallest integer that is not less than \(s\).
We next study the local truncation error for 8 under the smooth solution. From 8 , we have \[\label{eqn3463} R_{i}= \sum_{k=1}^{2N} {\int_{x_{k-1}}^{x_{k}} \frac{u \left( y \right) -\Pi_h u \left( y \right)}{\left|x_i -y \right|^{\alpha}} \,dy} =\sum_{k=1}^{2N} {\mathcal{T}_{i,k}}\tag{16}\] with \[\label{eqn3464} \mathcal{T}_{i,k} := \int_{x_{k-1}}^{x_{k}} \frac{u \left( y \right) -\Pi_h u \left( y \right)}{\left|x_i -y \right|^{\alpha}} \,dy.\tag{17}\]
Lemma 6. If \(u(x)\in C^{2}(\bar{\Omega})\) and \(r\geq 1\), then there exists a constant \(C\) such that \[\left| R_{i} \right| \leq C N^{-2}\] for \(i=1,2,\cdots,2N-1\).
Proof. Since \(u(x)\in C^{2}(\bar{\Omega})\), by mean value theorem, there exists \[\begin{align} \left| R_{i} \right| & \leq \sum_{k=1}^{2N} \left| \mathcal{T}_{i,k} \right|\\ & \leq C \sum_{k=1}^{2N}h_{k}^{2} \left(\max_{s\in[x_{k-1}, x_{k}]} \left| u_{xx}(s)\right|\right) \int_{x_{k-1}}^{x_{k}} \left| x_{i}-y \right|^{-\alpha} \,dy\\ & \leq C {N}^{-2} \int_{x_{0}}^{x_{2N}} \left| x_{i}-y \right|^{-\alpha} \,dy \leq CN^{-2}, \end{align}\] for \(i=1,2,\cdots,2N-1\). The proof is completed. ◻
The conclusion of Lemma 6 may not hold for the anomalous graded meshes \(r<1\) due to the presence of \(h_{1}>N^{-1}\).
Lemma 7. If \(u(x)\in C^{2}(\bar{\Omega})\) and \(r<1\), then there exists a constant \(C\) such that \[\sum_{k=1}^{N} \left|\mathcal{T}_{i,k}\right| \leq \begin{cases} C N^{-r\left(3-\alpha\right)} i^{-r\alpha}, & {\rm if}~~3r-2<0, \\ C N^{-r\left(3-\alpha\right)} i^{-r\alpha} \ln N, & {\rm if}~~3r-2=0, \\ C N^{-\left(2-r\alpha\right)} i^{-r\alpha}, & {\rm if}~~3r-2>0 \end{cases}\] for \(i=1,2,\cdots,N\).
Proof. Since \(u\in C^{2}\left(\bar{\Omega}\right)\), there exists a constant \(C\) such that \[\label{eqn3465} \left| \mathcal{T}_{i,k}\right| \leq C \int_{x_{k-1}}^{x_{k}} {\frac{\left(y-x_{k-1}\right) \left(x_{k}-y\right)}{\left|x_{i}-y\right|^{\alpha}}} \, dy \leq C h_{k}^{2} \int_{x_{k-1}}^{x_{k}} {\frac{1}{\left|x_{i}-y\right|^{\alpha}}} \, dy.\tag{18}\]
We next estimate the local truncation error. From 18 , one has \[\left|\mathcal{T}_{1,1}\right| \leq C \int_{x_{0}}^{x_{1}} {y\left(x_{1}-y\right)^{1-\alpha}} \, dy \leq C x_{1}^{3-\alpha} =C N^{-r\left(3-\alpha\right)},\] and \[\begin{align} \left|\mathcal{T}_{i,1}\right| & \leq C h_{1}^{3} \left(x_{i}-x_{1}\right)^{-\alpha} \leq C N^{-r\left(3-\alpha\right)} i^{-r\alpha},~~i>1. \end{align}\]
For \(1<k\leq\lceil\frac{i}{2}\rceil\), using 18 and 15 , we calculate \[\begin{align} \sum_{k=2}^{\lceil\frac{i}{2}\rceil} \left|\mathcal{T}_{i,k}\right| & \leq C \sum_{k=2}^{\lceil\frac{i}{2}\rceil} h_{k}^{3} \left(x_{i}-x_{k}\right)^{-\alpha } \leq C \sum_{k=2}^{\lceil\frac{i}{2}\rceil} h_{k}^{3} \left(x_{i}-x_{\lceil\frac{i}{2}\rceil}\right)^{-\alpha }\\ & \leq C \sum_{k=2}^{\lceil\frac{i}{2}\rceil} N^{-r\left(3-\alpha\right)} i^{-r\alpha} k^{3r-3}\\ & \leq \begin{cases} C N^{-r\left(3-\alpha\right)} i^{-r\alpha} , & {\rm if}~~3r-2<0, \\ C N^{-r\left(3-\alpha\right)} i^{-r\alpha} \ln i, & {\rm if}~~3r-2=0, \\ C N^{-r\left(3-\alpha\right)} i^{-r\alpha} i^{3r-2}, & {\rm if}~~3r-2>0. \end{cases} \end{align}\]
For \(\lceil\frac{i}{2}\rceil<k<i\), we also obtain \[\begin{align} \sum_{k=\lceil\frac{i}{2}\rceil+1}^{i-1} \left|\mathcal{T}_{i,k}\right| & \leq C \left(N^{-r}i^{r-1}\right)^{2} \int_{x_{\lceil\frac{i}{2}\rceil}}^{x_{i-1}} {\left(x_{i}-y\right)^{-\alpha}} \, dy \\ & \leq C \left(N^{-r}i^{r-1}\right)^{2} \left(x_{i}-x_{\lceil\frac{i}{2}\rceil}\right)^{1-\alpha} \\ & \leq C N^{-r\left(3-\alpha\right)} i^{r\left(3-\alpha\right)-2}. \end{align}\] We deduce the following, for \(i>1\), \[\begin{align} \left| \mathcal{T}_{i,i} \right| & \leq C h_{i}^{3-\alpha} \leq N^{-r\left(3-\alpha\right)} i^{r\left(3-\alpha\right)-\left(3-\alpha\right)}, \\ \end{align}\] and \[\begin{align} \left|\mathcal{T}_{i,i+1}\right| \leq C h_{i+1}^{3-\alpha} \leq C N^{-r\left(3-\alpha\right)} i^{r\left(3-\alpha\right)-\left(3-\alpha\right)}. \end{align}\]
Let \({J}=\min\left\{2i,N\right\}\). From 18 and 15 , we have \[\begin{align} \sum_{k=i+2}^{J} \left|\mathcal{T}_{i,k}\right| & \leq C \sum_{k=i+2}^{J} h_{k}^{2} \int_{x_{k-1}}^{x_{k}} {\left(y-x_{i}\right)^{-\alpha}} \, dy \\ & \leq C N^{-2r} i^{2r-2} \int_{x_{i}}^{x_{J}} {\left(y-x_{i}\right)^{-\alpha}} \, dy\\ & \leq C N^{-r\left(3-\alpha\right)} i^{r\left(3-\alpha\right)-2}, \end{align}\] and for the special case \(J=2i<N\), it yields \[\begin{align} \sum_{k=J+1}^{N} \left|\mathcal{T}_{i,k}\right| & \leq C\sum_{k=J+1}^{N} h_{k}^{3} \left(x_{k-1}-x_{i}\right)^{-\alpha} \\ &\leq C \sum_{k=J+1}^{N} N^{-r\left(3-\alpha\right)} i^{-r\alpha} k^{3r-3}\\ & \leq \begin{cases} CN^{-r\left(3-\alpha\right)} i^{-r\alpha}, & {\rm if}~~3r-2<0, \\ CN^{-r\left(3-\alpha\right)} i^{-r\alpha}\ln N, & {\rm if}~~3r-2=0, \\ CN^{-\left(2-r\alpha\right)} i^{-r\alpha}, & {\rm if}~~3r-2>0. \end{cases} \end{align}\] The proof is completed. ◻
Lemma 8. If \(u(x)\in C^{2}(\bar{\Omega})\) and \(r<1\), then there exists a constant \(C\) such that \[\sum_{k=N+1}^{2N} \left|\mathcal{T}_{i,k}\right| \leq \begin{cases} C N^{-r\left(3-\alpha\right)} i^{-r\alpha}, & {\rm if}~~3r-2<0, \\ C N^{-r\left(3-\alpha\right)} i^{-r\alpha} \ln N, & {\rm if}~~3r-2=0, \\ C N^{-\left(2-r\alpha\right)} i^{-r\alpha}, & {\rm if}~~3r-2>0 \end{cases}\] for \(i=1,2,\cdots,N\).
Proof. For \(N+1\leq k \leq 2N-i\), taking \(\zeta =2T-y\) and using 14 , 15 , 18 , it yields \[\begin{align} \left|T_{i,k} \right| &\leq C h_{k}^{2} \int_{x_{k-1}}^{x_{k}} \left(y-x_{i}\right)^{-\alpha} \, dy = C h_{2N-k+1}^{2} \int_{x_{k-1}}^{x_{k}} \left(y-2T+2T-x_{i}\right)^{-\alpha} \, dy\\ & =C h_{2N-k+1}^{2} \!\int_{x_{2N-k}}^{x_{2N-k+1}} \!\! \left(2T-x_{i} -\zeta\right)^{-\alpha} \, d\zeta \leq C h_{2N-k+1}^{2} \!\int_{x_{2N-k}}^{x_{2N-k+1}} \!\! \left(\zeta-x_{i}\right)^{-\alpha}\, d\zeta, \end{align}\] since \(2T-x_{i}-\zeta \geq \zeta-x_{i}\geq0\) when \(\zeta\in[x_{2N-k},x_{2N-k+1}]\).
On the other hand, taking \(\zeta =2T-y\), for \(k>2N-i\), there exits \[\begin{align} \left|T_{i,k} \right| & \leq C h_{2N-k+1}^{2} \! \int_{x_{2N-k}}^{x_{2N-k+1}} \!\!\left(2T-x_{i} -\zeta\right)^{-\alpha} \, d\zeta \leq C h_{2N-k+1}^{2} \! \int_{x_{2N-k}}^{x_{2N-k+1}} \!\!\left(x_{i}-\zeta\right)^{-\alpha}\, d\zeta, \end{align}\] because \(2T-x_{i}-\zeta \geq x_{i}-\zeta\geq0\) when \(\zeta\in[x_{2N-k},x_{2N-k+1}]\). The similar arguments can be performed as Lemma 7, the desired results is obtained. ◻
Lemma 9. If \(u(x)\in C^{2}(\bar{\Omega})\) and \(r<1\), then there exists a constant \(C\) such that \[\left|R_{i}\right| \leq \sum_{k=1}^{2N} \left|\mathcal{T}_{i,k}\right| \leq \begin{cases} C N^{-r\left(3-\alpha\right)} i^{-r\alpha}, & {\rm if}~~3r-2< 0, \\ C N^{-r\left(3-\alpha\right)} i^{-r\alpha} \ln N, & {\rm if}~~3r-2= 0, \\ C N^{-\left(2-r\alpha\right)} i^{-r\alpha}, & {\rm if}~~3r-2> 0 \end{cases}\] for \(i=1,2,\cdots,N\), and \[\left|R_{i}\right| \leq \sum_{k=1}^{2N} \left|\mathcal{T}_{i,k}\right| \leq \begin{cases} C N^{-r\left(3-\alpha\right)} \left(2N- i\right)^{-r\alpha}, & {\rm if}~~3r-2< 0, \\ C N^{-r\left(3-\alpha\right)} \left(2N- i\right)^{-r\alpha} \ln N, & {\rm if}~~3r-2= 0, \\ C N^{-\left(2-r\alpha\right)} \left(2N- i\right)^{-r\alpha}, & {\rm if}~~3r-2> 0 \end{cases}\] for \(i=N+1,N+2,\cdots,2N-1\).
Proof. The first part of this lemma can be obtained by Lemmas 7 and 8. For second part can be similarly proved, we omit it here. ◻
Let \(e_{k}:=u\left(x_{k}\right)-u_{k}\) with \(e_{0}=e_{2N}=0\) and \(e=\left(e_{1},e_{2},\cdots,e_{2N-1}\right)^T.\) From 7 and 9 , it leads to \[\label{eq4462} \sum_{k=1}^{2N-1} a_{i,k} e_{k}= R_{i}~~~{\rm for} ~~~i,k=1,2,\cdots,2N-1.\tag{19}\]
Let \(\left|e_{i_{0}}\right|:=\| e\|_\infty=\max_{1\leq k\leq 2N-1 } \left|e_{k}\right|\). By Lemma 4, we have \[\label{eqn3466} \begin{align} \left|R_{i_{0}}\right| & = \left|a_{i_{0},i_{0}}e_{i_{0}} +\sum_{k=1,k\neq i_{0}}^{2N-1} a_{i_{0},k}e_{k} \right| \geq a_{i_{0},i_{0}} \left|e_{i_{0}}\right|- \sum_{k=1,k\neq i_{0}}^{2N-1} \left|a_{i_{0},k}\right| \left|e_{k}\right| \\ & \geq \left(\sum_{k=1}^{2N-1} a_{i_{0},k}\right) \left|e_{i_{0}}\right|. \end{align}\tag{20}\] Then we have the following result.
Theorem 1. If \(u(x)\in C^{2}\left(\bar{\Omega}\right)\) and \(u_{k}\) is the approximate solution of \(u(x_{k})\) computed by the discretization scheme 9 , then \[\label{eq4461} \max_{1\leq i \leq 2N-1} |u\left(x_{i}\right)-u_{i}| \leq \begin{cases} C N^{r-2}, & {\rm if}~~r>\frac{2}{3}, \\ C N^{r-2}\ln N, & {\rm if}~~r=\frac{2}{3},\\ C N^{-2r}, & {\rm if}~~0<r<\frac{2}{3}. \end{cases}\qquad{(1)}\]
Proof. From 13 , 14 , 20 and Lemma 6, we know that, for \(r\geq1\), \[\left\|e\right\|_{\infty} \leq \frac{\left|R_{i_{0}}\right|}{\sum_{k=1}^{2N-1}a_{i_{0},k}} \leq C \frac{N^{-2}}{N^{-r}\left(\left(x_{i_{0}}-x_{0}\right)^{-\alpha} + \left(x_{2N}-x_{i_{0}}\right)^{-\alpha}\right)} \leq C N^{r-2},\] since \(\left(x_{i_{0}}-x_{0}\right)^{-\alpha} + \left(x_{2N}-x_{i_{0}}\right)^{-\alpha}\geq 2T^{-\alpha}\).
We now consider the case for anomalous graded meshes \(0<r<1\). According to 13 , 20 and Lemma 9, we have, for \(1\leq i_{0} \leq N\), \[\left\|e\right\|_{\infty} \leq \frac{\left|R_{i_{0}}\right|}{\sum_{k=1}^{2N-1}a_{i_{0},k}} \leq C\frac{\left|R_{i_{0}}\right|}{h_1 \left(x_{i_{0}}-x_{0}\right)^{-\alpha}} \leq \begin{cases} C N^{r-2}, & {\rm if}~~r>\frac{2}{3}, \\ C N^{r-2}\ln N, & {\rm if}~~r=\frac{2}{3},\\ C N^{-2r}, & {\rm if}~~0<r<\frac{2}{3}; \end{cases}\] and, for \(N+1\leq i_{0} \leq 2N-1\), \[\left\|e\right\|_{\infty} \leq C\frac{\left|R_{i_{0}}\right|}{h_{2N} \left(x_{2N}-x_{i_{0}}\right)^{-\alpha}} \leq \begin{cases} C N^{r-2}, & {\rm if}~~r>\frac{2}{3}, \\ C N^{r-2}\ln N, & {\rm if}~~ r=\frac{2}{3},\\ C N^{-2r}, & {\rm if}~~0<r<\frac{2}{3}. \end{cases}\] The proof is completed. ◻
In the previous section, we clarified that an optimal convergence rate emerges from anomalous graded meshes when considering the smooth solution. Conversely, in this section, a sharp error estimate appears in standard graded meshes due to the low regularity of the solution.
Without loss of generality, we take \(\Omega=\left( 0,2T\right)\) and rewrite 4 as \[\label{eqn4461} \begin{align} \left|\frac{\partial^{\ell} }{\partial x ^{\ell}} u(x)\right| & \le C[x(2T-x)]^{\sigma-\ell}, ~0<\sigma<1 \;\text{ for } \ell=0,1,2. \end{align}\tag{21}\] Throughout the rest of the paper, we study the local truncation error and the global error under the low regularity solution 21 for nonlocal diffusion problems.
By a standard error estimate for linear interpolation, since \(u\in C^2(0,2T)\) in 21 , we estimate 17 as \[\label{eqn4462} \left|\mathcal{T}_{i,k} \right| \leq C h_{k}^{2} \left(\max_{s\in[x_{k-1}, x_{k}]} \left| u_{xx}(s )\right|\right) \int_{x_{k-1}}^{x_{k}} \left| x_{i}-y \right|^{-\alpha} \,dy,~{\rm for }~k \ne 1,2N.\tag{22}\]
Lemma 10. Let \(r>0\) and \(0<\sigma <1\). Then there exists a constant \(C\) such that \[\sum_{k=1}^{i}{|\mathcal{T}_{i,k}|} \le \begin{cases} C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha}, &{\rm if}~~ r\left(1+\sigma\right)<2, \\ C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha} \ln i, &{\rm if}~~ r\left(1+\sigma\right)=2, \\ C N^{-r \left(1+\sigma -\alpha \right)} i^{r \left(1+\sigma-\alpha \right)-2}, &{\rm if}~~ r\left(1+\sigma\right)>2 \end{cases}\] for all \(i\in\{1, \dots, N\}\).
Proof. Let \(i\in\{1, \dots, N\}\) be arbitrary but fixed. Consider separately the cases \(k=1=i,\;k=1<i, \;1< k=i\) and \(1<k<i\).
From 17 and 21 , it can be computed \[\label{eqn4463} \begin{align} \left|\mathcal{T}_{1,1} \right| &\leq \int_{x_{0}}^{x_{1}} \left|u(y)\right|\left(x_{1}-y\right)^{-\alpha} \, dy +\int_{x_{0}}^{x_{1}} \left|\Pi_{h}u(y)\right|\left(x_{1}-y\right)^{-\alpha} \, dy\\ & \leq C \left[ \int_{x_{0}}^{x_{1}}{y^{\sigma}\left(x_{1}-y \right)^{-\alpha} \, dy} + \frac{x_{1}^{\sigma}}{h_{1}} \int_{x_0}^{x_1} {y \left(x_{1}-y \right)^{-\alpha}} \,dy \right] \\ & \leq C x_{1}^{1+\sigma-\alpha} \leq N^{-r \left(1+\sigma-\alpha \right)}, \end{align}\tag{23}\] and, for \(i>1\), \[\label{eqn4464} \begin{align} \left| \mathcal{T}_{i,1} \right| & \leq C \left(x_{i}-x_{1} \right)^{-\alpha}\int_{x_{0}}^{x_{1}} \left| u \left(y\right) -\Pi_h u\left(y\right) \right| \, dy \\ & \leq C \left(x_{1}^{\sigma+1} + x_{1}^{\sigma}h_{1}\right) \left(N^{-r} i^{r}\right)^{-\alpha} \leq C N^{-r \left(1+\sigma-\alpha\right)} i^{-r\alpha}. \end{align}\tag{24}\]
For \(1<k \le \left\lceil \frac{i}{2} \right\rceil\), using 15 , 22 and the well-known convergence properties of the series \(\sum_{j=2}^\infty j^{ \mu }\) \((\mu \in\mathbb{R})\) , it yields \[\label{eqn4465} \begin{align} \sum_{k=2}^{\left\lceil i/2 \right\rceil}\left|\mathcal{T}_{i,k}\right| & \leq C \sum_{k=2}^{\left\lceil i/2 \right\rceil} h_{k}^{3} x_{k-1}^{\sigma-2} \left( x_{i} - x_{k}\right)^{-\alpha} \\ & \leq C \sum_{k=2}^{\left\lceil i/2 \right\rceil} \left(N^{-r}k^{r-1}\right)^{3} \left(N^{-r} k^{r}\right)^{\sigma-2} \left(N^{-r} i^{r} \right)^{-\alpha}\\ & \leq C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha} \sum_{k=2}^{\left\lceil i/2 \right\rceil} k^{r\left(1+\sigma\right)-3}\\ &\leq \begin{cases} C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha}, &{\rm if}~~ r\left(1+\sigma\right)<2, \\ C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha} \ln i, &{\rm if}~~ r\left(1+\sigma\right)=2, \\ C N^{-r \left(1+\sigma -\alpha \right)} i^{r \left(1+\sigma-\alpha \right)-2}, &{\rm if}~~ r\left(1+\sigma\right)>2. \end{cases} \end{align}\tag{25}\]
For \(\left\lceil \frac{i}{2} \right\rceil <k<i\), using 22 and 15 , there exist \[\label{eqn4466} \begin{align} \sum_{k=\lceil i/2 \rceil +1}^{i-1}{\left| \mathcal{T}_{i,k} \right|} & \leq C \sum_{k=\lceil i/2 \rceil +1}^{i-1} h_{k}^{2} x_{k-1}^{\sigma-2} \int_{x_{k-1}}^{x_{k}}{\left(x_{i}-y \right)^{-\alpha} \, dy} \\ & \leq C \left(N^{-r} i^{r-1} \right)^{2} \left(N^{-r} i^{r}\right)^{\sigma-2} \int_{x_{\lceil i/2 \rceil}}^{x_{i-1}}{\left(x_{i}-y \right)^{-\alpha} \, dy} \\ & \leq C \left(N^{-r} i^{r-1} \right)^{2} \left(N^{-r} i^{r}\right)^{\sigma-2} \left[\left(x_{i}-x_{\lceil i/2 \rceil}\right)^{1-\alpha} -h_{i}^{1-\alpha} \right] \\ & \leq C N^{-r\left(1+\sigma-\alpha \right)} i^{r \left(1+\sigma-\alpha\right) - 2},\\ \end{align}\tag{26}\] and, for \(i>1\), \[\label{eqn4467} \begin{align} \left|\mathcal{T}_{i,i} \right| & \leq C h_{i}^{2} x_{i-1}^{\sigma-2} \int_{x_{i-1}}^{x_{i}} {\left(x_{i}-y \right)^{-\alpha} \, dy} \\ & \leq C h_{i}^{3-\alpha} x_{i}^{\sigma-2}\\ & \leq C N^{-r \left(1+\sigma-\alpha\right)} i^{r \left(1+\sigma-\alpha\right) - \left( 3-\alpha \right)}. \end{align}\tag{27}\] Combining bounds 23 , 24 , 25 , 26 and 27 yields the desired result. ◻
Lemma 11. Let \(r>0\) and \(0<\sigma <1\). Then there exists a constant \(C\) such that \[\sum_{k=i+1}^N |\mathcal{T}_{i,k}| \le \begin{cases} C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha}, &{\rm if }~~ r \left(1+\sigma\right) <2, \\ C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha} \ln N, &{\rm if }~~ r \left(1+\sigma\right) =2, \\ C N^{-\left(2-r\alpha\right)} i^{-r\alpha}, &{\rm if }~~ r \left(1+\sigma\right) >2 \end{cases}\] for all \(i\in\{1, \dots, N-1\}\).
Proof. From 22 , 14 and 15 , we can figure out \[\label{eqn4468} \begin{align} \left|\mathcal{T}_{i,i+1} \right| & \leq C h_{i+1}^{2} x_{i}^{\sigma-2} \int_{x_{i}}^{x_{i+1}} {\left(y - x_{i} \right)^{-\alpha} \, dy} \\ & \leq C h_{i+1}^{3-\alpha} x_{i}^{\sigma-2}\\ & \leq C N^{-r \left( 1+\sigma -\alpha\right)} i^{r \left( 1+\sigma -\alpha\right) - \left( 3-\alpha \right)}. \end{align}\tag{28}\]
Taking \(K =\min \{2i, N\}\) and using 22 , 15 , it leads to \[\label{eqn4469} \begin{align} \sum_{k=i+2}^{K}{\left|\mathcal{T}_{i,k} \right|} & \leq C \sum_{k=i+2}^{K} h_{k}^{2} x_{k-1}^{\sigma-2} \int_{x_{k-1}}^{x_{k}} {\left(y-x_{i} \right)^{-\alpha}} \, dy \\ & \leq C \left(N^{-r}i^{r-1}\right)^{2} \left(N^{-r}i^{r}\right)^{\sigma-2} \int_{x_{i+1}}^{x_{K}} {\left(y-x_{i} \right)^{-\alpha}} \, dy \\ & \leq C \left(N^{-r}i^{r-1}\right)^{2} \left(N^{-r}i^{r}\right)^{\sigma-2} \left(x_{K}-x_{i}\right)^{1-\alpha} \\ & \leq C N^{-r \left( 1+\sigma -\alpha\right)} i^ {r \left( 1+\sigma -\alpha\right)-2}. \end{align}\tag{29}\] For the special case \(K=2i <N\), from 22 , 14 and 15 , it yields \[\label{eqn44610} \begin{align} \sum_{k=K+1}^{N}\left|\mathcal{T}_{i,k} \right| &\leq C \sum_{k=K+1}^{N} {h_{k}^{3}} x_{k}^{\sigma-2}\left(x_{k-1}-x_{i} \right)^{-\alpha} \\ & \leq C \sum_{k=K+1}^{N} \left( N^{-r} k^{r-1}\right)^{3} \left(N^{-r} k^{r}\right)^{\sigma-2} \left(N^{-r} i^{r} \right)^{-\alpha}\\ &\leq C N^{-r\left(1+\sigma-\alpha\right)} i^{-r\alpha} \sum_{k=K+1}^{N} k^{r\left(1+\sigma\right)-3}\\ &\le \begin{cases} C N^{-r\left(1+\sigma -\alpha \right)} i^{-r\alpha}, &{\rm if } ~~r \left(1+\sigma\right)<2, \\ C N^{-r\left(1+\sigma -\alpha \right)} i^{-r\alpha} \ln N, &{\rm if } ~~r \left(1+\sigma\right)=2, \\ C N^{-\left(2-r\alpha\right)} i^{-r\alpha}, &{\rm if } ~~r \left(1+\sigma\right)>2. \end{cases} \end{align}\tag{30}\] Adding 28 , 29 and 30 gives the desired result. ◻
Lemma 12. Let \(r>0\) and \(0<\sigma <1\). Then there exists a constant \(C\) such that \[\sum_{k=N+1}^{2N} |\mathcal{T}_{i,k}| \le \begin{cases} C N^{-r\left(1+\sigma\right)}, &{\rm if } ~~r\left(1+\sigma\right)<2, \\ C N^{-r\left(1+\sigma\right)} \ln N, &{\rm if } ~~r\left(1+\sigma\right)=2, \\ C N^{-2}, &{\rm if } ~~r\left(1+\sigma\right)>2 \end{cases}\] for all \(i\in\{1, \dots, N\}\).
Proof. From 22 and 15 , we have \[\label{eqn44611} \begin{align} \left| \mathcal{T}_{i,N+1} \right| & \leq C h_{N+1}^{2} \left( 2T- x_{N+1}\right)^{\sigma-2} \int_{x_{N}}^{x_{N+1}}\left(y -x_{i} \right)^{-\alpha} \, dy \\ & \leq C h_{N+1}^{3-\alpha}= CN^{-\left( 3-\alpha\right) }, \end{align}\tag{31}\] since \[\int_{x_{N}}^{x_{N+1}} \left(y -x_{i} \right)^{-\alpha}\,dy = \frac{1}{1-\alpha} \,h_{N+1}^{1-\alpha}~~{\rm for}~~i=N,\] and \[\int_{x_{N}}^{x_{N+1}} \left(y -x_{i} \right)^{-\alpha}\,dy \leq h_{N+1}\left(x_{N} -x_{i} \right)^{-\alpha} \leq h_{N+1}^{1-\alpha}~~{\rm for}~~i<N.\]
Furthermore, we can derive that, from 22 , 14 and 15 , \[\label{eqn44612} \begin{align} \sum_{k=N+2}^{\left\lceil 3N/2 \right\rceil} \left|\mathcal{T}_{i,k} \right| & \leq C \sum_{k=N+2}^{\left\lceil 3N/2 \right\rceil} h_{k}^{2} \left(2T-x_{k} \right)^{\sigma-2} \int_{x_{k-1}}^{x_{k}} \left(y-x_{i} \right)^{-\alpha} \,dy \\ & \leq C N^{-2} \int_{x_{N+1}}^{x_{\left\lceil 3N/2 \right\rceil}} \left(y-x_{i} \right)^{-\alpha} \, dy \\ & \leq C N^{-2}. \end{align}\tag{32}\]
According to 14 , 15 and 22 , there exists \[\begin{align} \label{eqn44613} \sum_{k=\left\lceil 3N/2 \right\rceil+1}^{2N-1}\left|\mathcal{T}_{i,k} \right| & \leq C \sum_{k=\left\lceil 3N/2 \right\rceil+1}^{2N-1} h_{k}^{2} \left(2 T -x_{k} \right)^{\sigma-2} \int_{x_{k-1}}^{x_{k}} \left(y-x_{i} \right)^{-\alpha} \,dy \notag\\ & \leq C \sum_{k=\left\lceil 3N/2 \right\rceil+1}^{2N-1} h_{k}^{3} \left( 2 T- x_{k}\right)^{\sigma-2} \notag\\ & \leq C \sum_{k=\left\lceil 3N/2 \right\rceil+1}^{2N-1} \left(N^{-r} \left(2N+1-k\right)^{r-1} \right)^{3} \left( N^{-r} \left(2N-k\right)^{r} \right)^{\sigma-2}\notag \\ & \leq C N^{-r\left(1+\sigma\right)} \sum_{q=2}^{\left\lceil N/2 \right\rceil } q^{r\left(1+\sigma\right)-3} \notag \\ & \le \begin{cases} C N^{-r\left(1+\sigma\right)}, &{\rm if}~~ r\left(1+\sigma\right)<2, \\ C N^{-r\left(1+\sigma\right)} \ln N, &{\rm if}~~ r\left(1+\sigma\right)=2, \\ C N^{-2}, &{\rm if}~~ r\left(1+\sigma\right)>2. \end{cases} \end{align}\tag{33}\] By 22 and 15 , it yields \[\label{eqn44614} \begin{align} \left|\mathcal{T}_{i,2N} \right| &\leq \int_{x_{2N-1}}^{x_{2N}}\frac{\left|u \left(y \right)- \Pi_h u \left( y\right) \right|}{\left( y-x_{i}\right)^{\alpha}} \, dy \\ & \leq C \int_{x_{2N-1}}^{x_{2N}} \left(2T-y \right)^{\sigma} \, dy + \frac{\left| u\left(x_{2N-1} \right)\right|}{h_{2N}} \int_{x_{2N-1}}^{x_{2N}} {\left(x_{2N}-y\right) \, dy} \\ & \leq C h_{2N}^{1+\sigma} \leq C N^{-r\left(1+\sigma\right)}. \end{align}\tag{34}\] Adding 31 , 32 , 33 and 34 gives the desired result. ◻
Lemma 13. Let \(r>0\) and \(0<\sigma <1\). Then there exists a constant \(C\) such that \[|R_{i}| \leq \begin{cases} C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha}, &{\rm if}~~ r \left(1+\sigma\right) <2, \\ C N^{-r \left(1+\sigma -\alpha \right)} i^{-r\alpha} \ln N, &{\rm if}~~ r \left(1+\sigma\right) =2, \\ C N^{-\left(2-r\alpha\right)} i^{-r\alpha}, &{\rm if}~~ r \left(1+\sigma\right) >2 \end{cases}\] for \(i\in{1,2,\cdots,N}\), and \[|R_{i}| \leq \begin{cases} C N^{-r \left(1+\sigma -\alpha \right)} \left(2N-i\right)^{-r\alpha}, &{\rm if}~~ r \left(1+\sigma\right) <2, \\ C N^{-r \left(1+\sigma -\alpha \right)} \left(2N-i\right)^{-r\alpha} \ln N, &{\rm if}~~ r \left(1+\sigma\right) =2, \\ C N^{-\left(2-r\alpha\right)} \left(2N-i\right)^{-r\alpha}, &{\rm if}~~ r \left(1+\sigma\right) >2 \end{cases}\] for \(i\in{N+1,N+2,\cdots,2N}\).
Proof. For \(i=1,2\dots, N\), this result is an immediate consequence by Lemmas 10–12. The similar arguments can be performed as Lemmas 10–12 for \(i\in{N+1,N+2,\cdots,2N}\), we omit it here. ◻
We start with the global error analysis for the steady-state problem 2 under the low regularity solution.
Theorem 2. Let \(r>0\) and \(0<\sigma <1\). Then there exist constants \(C\) such that \[\max_{1\leq i \leq 2N-1} \left|u\left(x_{i}\right)-u_{i}\right| \leq \begin{cases} C N^{r-2} , &{\rm if}~~ r\left( 1+\sigma\right) >2,\\ C N^{r-2} \ln N, &{\rm if}~~ r\left( 1+\sigma\right) =2, \\ C N^{-r \sigma}, &{\rm if}~~ r\left( 1+\sigma\right) <2. \\ \end{cases}\]
Proof. From 13 , 20 and Lemma 13, we obtain, for \(1\leq i_{0}\leq N\), \[\begin{align} \left\|e\right\|_{\infty} \leq C\frac{\left|R_{i_{0}}\right|}{h_1 \left(x_{i_{0}}-x_{0}\right)^{-\alpha}} \leq \begin{cases} C N^{r-2} , &{\rm if}~~ r\left( 1+\sigma\right) >2,\\ C N^{r-2} \ln N, &{\rm if}~~ r\left( 1+\sigma\right) =2, \\ C N^{-r \sigma}, &{\rm if}~~ r\left( 1+\sigma\right) <2, \\ \end{cases} \end{align}\] and, for \(N+1\leq i_{0} \leq 2N-1\), \[\begin{align} \left\|e\right\|_{\infty} \leq C\frac{\left|R_{i_{0}}\right|}{h_{2N} \left(x_{2N}-x_{i_{0}}\right)^{-\alpha}} \leq \begin{cases} C N^{r-2} , &{\rm if}~~ r\left(1+\sigma\right) >2,\\ C N^{r-2} \ln N, &{\rm if}~~ r\left(1+\sigma\right) =2, \\ C N^{-r \sigma}, &{\rm if}~~ r\left(1+\sigma\right) <2. \\ \end{cases} \end{align}\] The proof is completed. ◻
An optimal error estimate with far less than first-order accuracy is demonstrated in section 4 for the steady-state problems. Now, we further study time-dependent case, however, second-order convergence can be achieved on graded meshes.
Before we start to discuss the time-dependent nonlocal problem 1 we shall briefly review and revise the local truncation error for the corresponding stationary problem 2 .
Lemma 14. Let \(r>0\) and \(0<\sigma <1\). Then there exists a constant \(C\) such that \[\left|R_{i}\right| \leq \begin{cases} C N^{-r\left(1+\sigma -\alpha \right)}, &{\rm if } ~~r \left(1+\sigma- \alpha\right)<2, \\ C N^{-r\left(1+\sigma -\alpha \right)}\ln N, &{\rm if } ~~r \left(1+\sigma- \alpha\right)=2, \\ C N^{-2}, &{\rm if } ~~r \left(1+\sigma- \alpha\right)>2 \end{cases}\] for \(i=1,2,\cdots,2N-1\).
Proof. We only consider \(1\leq i\leq N\); the case of \(N+1 \leq i \leq 2N-1\) can be proved in the same way.
From Lemma 10, it is clear that \[\label{eqn5461} \sum_{k=1}^{i} \left|\mathcal{T}_{i,k}\right| \leq \begin{cases} C N^{-r\left(1+\sigma-\alpha\right)}, &{\rm if}~~ r\left(1+\sigma-\alpha\right) \leq 2,\\ C N^{-2}, &{\rm if}~~ r\left(1+\sigma-\alpha\right) > 2. \end{cases}\tag{35}\]
Taking \(K=\min \left\{2i,N\right\}\), from 28 and 29 , we can get \[\sum_{k=i+1}^{K} \left|\mathcal{T}_{i,k}\right| \leq \begin{cases} C N^{-r\left(1+\sigma-\alpha\right)}, &{\rm if}~~ r\left(1+\sigma-\alpha\right) \leq 2,\\ C N^{-2}, &{\rm if}~~ r\left(1+\sigma-\alpha\right) > 2. \end{cases}\] In particular, for \(K=2i <N\), by 30 , it yields \[\begin{align} \sum_{k=K+1}^{N}\left|\mathcal{T}_{i,k} \right| & \leq C \sum_{k=K+1}^{N} \left( N^{-r} k^{r-1}\right)^{3} \left(N^{-r} k^{r}\right)^{\sigma-2} \left(N^{-r} k^{r} \right)^{-\alpha}\\ &\leq C N^{-r\left(1+\sigma-\alpha\right)} \sum_{k=K+1}^{N} k^{r\left(1+\sigma- \alpha\right)-3}\\ &\le \begin{cases} C N^{-r\left(1+\sigma -\alpha \right)} , &{\rm if } ~~r \left(1+\sigma- \alpha\right)<2, \\ C N^{-r\left(1+\sigma -\alpha \right)}\ln N, &{\rm if } ~~r \left(1+\sigma- \alpha\right)=2, \\ C N^{-2}, &{\rm if } ~~r \left(1+\sigma- \alpha\right)>2. \end{cases} \end{align}\] Then we can conclude the following results \[\label{equa5463} \sum_{k=i+1}^{N} \left|\mathcal{T}_{i,k} \right| \leq \begin{cases} C N^{-r\left(1+\sigma -\alpha \right)}, &{\rm if } ~~r \left(1+\sigma- \alpha\right)<2, \\ C N^{-r\left(1+\sigma -\alpha \right)}\ln N, &{\rm if } ~~r \left(1+\sigma- \alpha\right)=2, \\ C N^{-2}, &{\rm if } ~~r \left(1+\sigma- \alpha\right)>2. \end{cases}\tag{36}\]
From Lemma 12, we can check that \[\label{eqn5462} \sum_{k=N+1}^{2N} \left|\mathcal{T}_{i,k}\right| \leq \begin{cases} C N^{-r\left(1+\sigma-\alpha\right)}, &{\rm if}~~ r\left(1+\sigma-\alpha\right) \leq 2,\\ C N^{-2}, &{\rm if}~~ r\left(1+\sigma-\alpha\right) > 2, \end{cases}\tag{37}\] since, for \(r\left(1+\sigma\right) \leq 2\), there exist \(N^{-r\left(1+\sigma\right)}\leq N^{-r\left(1+\sigma\right)}\ln N \leq C N^{-r\left(1+\sigma-\alpha\right)}\) and \(r\left(1+\sigma-\alpha\right) < 2\); moreover, \(N^{-2}\leq N^{-r\left(1+\sigma-\alpha\right)}\) for \(r\left(1+\sigma-\alpha\right) \leq 2\).
We mainly focus on the convergence analysis for the time-dependent nonlocal problem 1 , since the stability can be easily obtained by Lax’s equivalence theorem [23].
Theorem 3. Let \(u_{i}^{k}\) be the approximate solution of \(u(x_{i},t_{k})\) computed by the discretization scheme 10 . Then \[\max_{\substack{1\leq i \leq 2N-1\\1\leq k \leq M}} |u\left(x_{i},t_{k}\right)-u_{i}^{k}| \leq \begin{cases} C \left(N^{-r\left(1+\sigma -\alpha \right)} +M^{-2}\right), &{\rm if } ~~r \left(1+\sigma- \alpha\right)<2, \\ C \left(N^{-r\left(1+\sigma -\alpha \right)}\ln N+M^{-2}\right), &{\rm if } ~~r \left(1+\sigma- \alpha\right)=2, \\ C \left(N^{-2}+M^{-2}\right), &{\rm if } ~~r \left(1+\sigma- \alpha\right)>2. \end{cases}\]
Proof. Let \(e_{i}^{k}=u\left(x_{i},t_{k}\right)-u_{i}^{k}\), with \(e_{i}^{0}=0\), \(i=1,2,\cdots,2N-1\), \(k=0,1,\cdots,M\) and \(E^{k}=\left(e_{1}^{k},e_{2}^{k}, \cdots,e_{2N-1}^{k} \right)^T\). From 10 with perturbation equation, we obtain \[\label{eq7} \left(1+\frac{\tau}{2}a_{i,i} \right)e_{i}^{k} = e_{i}^{k-1} -\frac{\tau}{2} \sum_{j=1}^{2N-1} a_{i,j}e_{j}^{k-1} -\frac{\tau}{2}\sum_{j=1,j\ne i}^{2N-1}a_{i,j}e_{j}^{k} + \tau R_{i}^{k-\frac{1}{2}},\tag{38}\] where the local truncation error is \(\left|R_{i}^{k-\frac{1}{2}}\right| \leq C\left (|R_i|+M^{-2}\right)\) and \(R_i\) is given in Lemma 14.
Let \(\left|e_{i_{0}}^{k} \right|:=\|E^k\|_{\infty} =\max\limits_{j=1,2,\cdots,2N-1}\left|e_{j}^{k} \right|\). From 38 and Lemma 4, we have \[\begin{align} \left(1+\frac{\tau}{2}a_{i_{0},i_{0}} \right)\left|e_{i_{0}}^{k}\right| & \le \left|e_{i_{0}}^{k-1}\right| +\frac{\tau}{2 }\sum_{j=1}^{2N-1}\!\left|a_{i_{0},j}\right|\left|e_{j}^{k-1}\right| +\frac{\tau}{2}\sum_{j=1,j\ne i_{0}}^{2N-1} \left|a_{i_{0},j}\right| \left|e_{j}^{k} \right| +\tau\left|R_{i_{0}}^{k-\frac{1}{2}}\right| \\ & \le \left(1+\tau a_{i_{0},i_{0}} \right) \|E^{k-1}\|_{\infty} + \frac{\tau}{2}a_{i_{0},i_{0}} \left|e_{i_{0}}^{k}\right| +\tau\left|R_{i_{0}}^{k-\frac{1}{2}}\right|. \\ \end{align}\]
Let \(\|R^{k-\frac{1}{2}}\|_{\infty} =\max\limits_{j=1,2,\cdots,2N-1}\left|R_{j}^{k-\frac{1}{2}} \right|\), for \(k=1,2,\cdots,M\). Form 12 , it yields \[a_{i_{0},i_{0}}<\frac{2^{2-\alpha}}{1-\alpha}T^{1-\alpha}:=C_a.\] Thus, using the above equations with \(\|E^{0}\|_{\infty}=0\), we get that \[\begin{align} \|E^{k}\|_{\infty} & \leq \left(1+\tau C_a\right)\|E^{k-1}\|_{\infty} +\tau \|R^{k-\frac{1}{2}}\|_{\infty} \\ & \leq \left(1+\tau C_{a}\right)^{k}\|E^{0}\|_{\infty} +\tau \sum_{l=1}^{k}\left(1+\tau C_a\right)^{k-l} \|R^{l-\frac{1}{2}}\|_{\infty}\\ & \leq \begin{cases} C \left(N^{-r\left(1+\sigma -\alpha \right)} +M^{-2}\right), &{\rm if } ~~r \left(1+\sigma- \alpha\right)<2, \\ C \left(N^{-r\left(1+\sigma -\alpha \right)}\ln N+M^{-2}\right), &{\rm if } ~~r \left(1+\sigma- \alpha\right)=2, \\ C \left(N^{-2}+M^{-2}\right), &{\rm if } ~~r \left(1+\sigma- \alpha\right)>2. \end{cases}\\ \end{align}\] The proof is completed. ◻
Remark 2. The above error analysis are easily extended for certain multidimensional problems, e.g., \[\label{eqn5463} u_t\left(x,y,t\right)- \int_{\Omega} \frac{u(\bar{x},\bar{y},t)-u(x,y,t)}{\left|x-\bar{x}\right|^{\alpha}\left|y-\bar{y}\right|^{\beta}} \,d\bar{x}\,d\bar{y} = f\left(x,y,t\right).\qquad{(2)}\] From [6] and 10 , the full discretization of ?? has the matrix form \[\label{neqn5465} \left(I+\frac{\tau }{2}\mathcal{A}\right) U^{k}=\left(I-\frac{\tau }{2}\mathcal{A}\right) U^{k-1}+ \tau F^{k-\frac{1}{2}},~~~k=1,2,\cdots,M.\qquad{(3)}\] Here \(\mathcal{A}:=D_{\alpha}\otimes D_{\beta}-G_{\alpha}\otimes G_{\beta}\) and \(D_{\alpha}\), \(D_{\beta}\), \(G_{\alpha}\), \(G_{\beta}\) are defined in 11 . Moreover, the grid function are defined by \[\begin{align} & U^{k}=\left(U_{1}^{k},U_{2}^{k},\cdots,U_{2N-1}^{k}\right)^{T}, ~U_{i}^{k}=\left(u_{i,1}^{k},u_{i,2}^{k},\cdots,u_{i,2N-1}^{k}\right).\\ \end{align}\]
We numerically verify the above theoretical results including the convergence rates. The maximum norm is employed to measure the numerical errors. All numerical experiments are executed in Julia 1.10.0.
Example 1. Steady-state problems with smooth solution. Consider the steady-state problems 2 in the domain \(0<x<1\). The exact solution of the equation is \(u(x)=e^{x}\sin{x}\). Here the forcing function is calculated by the JacobiGL algorithm, as demonstrated in [24] or [25].
Maximum errors and convergence rates of 9 with smooth solution
Table [smooth1] shows that the standard graded meshes are worse than the uniform grid and even lead to divergence for \(r\geq 2\). It also indicates that an optimal convergence rate (great than one) arises in anomalous graded meshes if \(r=\frac{2}{3}\), which are in agreement with Theorem 1.
Example 2. Steady-state problems with low regularity solution. Consider the steady-state problems 2 under the low regularity solution in the domain \(0<x<1\). The exact solution of the equation is \(u(x)=e^{x}x^{0.3}\left(1-x\right)^{0.3}\). Here the forcing function is calculated by the JacobiGL algorithm [24], [25].
Maximum errors and convergence rates of 9 with low regularity solution
Table [ODElow:1] shows that it is contrary to the results of smooth functions, its sharp error estimate (far less than one) appears in standard graded meshes with the low regularity of solution 4 , which are in agreement with Theorem 2.
Example 3. Time-dependent problems for 1D and 2D. Consider the time-dependent problems 1 for 1D and [rem5461] for 2D under the low regularity solution in the domain \(0<x,y<1\), \(0<t<1\). The exact solution of the equations are \(u(x,t)=e^{x+t}x^{0.3}\left(1-x\right)^{0.3}\) and \[u(x,y,t)=e^{x+y+t}x^{0.3}\left(1-x\right)^{0.3}y^{0.3}\left(1-y\right)^{0.3},\] respectively. Here the forcing function is calculated by the JacobiGL algorithm [24], [25].
Maximum errors and convergence rates of 10 with low regularity solution
Maximum errors and convergence rates of ?? with low regularity solution
Table [PDE1] and [PDE2] show that second-order convergence \(\mathcal{O}\left( N^{-\min \left\{r \left(1+\sigma-\alpha\right), \,2 \right\} } \right)\) can be achieved on graded meshes for the time-dependent nonlocal problems 1 including two-dimensional case under the low regularity of solution 4 , as demonstrated in Theorem 3 and Remark 2.
The nonlocal diffusion models involve the weakly singular kernels, which exhibit a severe order reduction by many methods. In this work we first derive an optimal error estimate (far less than second-order) for the steady-state counterpart either the standard graded meshes or anomalous graded meshes, under the sufficient smooth and mild regularity of the solution. And the second-order convergence rate are well established for the time-dependent problems including two-dimensional case on graded meshes. Based on the idea of Lemmas 13 and 14, it is interesting to further analyze the second-order convergence rate for Riesz fractional operator [17], [26], [27]\[\frac{\partial ^{\alpha+1}}{\partial |x|^{\alpha+1}}u(x) =\kappa_{\alpha}\frac{\partial^2 u}{\partial x^2} \int^b_a \frac{u(y)}{|x-y|^\alpha}dy,~0<\alpha<1\] with a constant \(\kappa_{\alpha}\).
School of Mathematics and Statistics, Gansu Key Laboratory of Applied Mathematics and Complex Systems, Lanzhou University, Lanzhou 730000, China. Email address: chenmh@lzu.edu.cn↩︎
School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China.↩︎
School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China.↩︎
Key Laboratory of Mechanics on Disaster and Environment in Western China, the Ministry of Education,College of Civil Engineering and Mechanics, Lanzhou University, Lanzhou 730000, China Email address: jzwang@lzu.edu.cn↩︎
Submitted to the editors DATE.↩︎