Abstract
A space–time Petrov–Galerkin spectral method for time fractional diffusion equations is developed in this paper. The Petrov–Galerkin method is used to simplify the computation of stiffness matrix but leads to full non-symmetric mass matrix. However, the matrix decomposition method based on eigen-decomposition is numerically unstable for non-symmetric linear systems. A QZ decomposition is adopted instead of eigen-decomposition. The QZ decomposition has essentially the same computational complexity as the eigen-decomposition but is numerically stable. Moreover, the enriched Petrov–Galerkin method is developed to resolve the weak singularity at the initial time. We also carry out the error analysis for the proposed methods and present ample numerical results to validate the accuracy and robustness of our numerical schemes.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
We consider in this paper the following time fractional diffusion equation (TFDE):
with the initial condition
and the homogeneous boundary conditions. In the above, \(\alpha \in (0,1),\)\(\Omega \) is a bounded domain in \( \mathbb {R}^d\), \({\mathcal {L}}\) is a linear self-adjoint elliptic operator and \({\mathcal {N}}\) is a lower-order nonlinear operator, and \(^{C}_{0}D^{\alpha }_{t}\) (\(0<\alpha <1\)) is the left-sided Caputo fractional derivative of order \(\alpha \) (see the definition in 2.4).
There is now a vast literature on the numerical methods for the fractional differential equations, mostly with the finite difference methods (e.g., [3, 6, 19, 22, 32, 38, 39] and the references therein) and the finite element methods (e.g., [8, 16,17,18, 36] and the references therein).
The two main difficulties in solving fractional PDEs such as (1.1) are (i) fractional derivatives are non-local operators and generally lead to full nonsymmetric matrices; and (ii) their solutions are often singular so polynomial based approximations are not efficient.
Since spectral methods are capable of providing exceedingly accurate numerical results with less degrees of freedoms, they have been widely used for numerical approximations [1, 10, 28, 29]. In particular, well designed spectral methods appear to be particularly attractive to deal with the difficulties associated with fractional PDEs mentioned above. Polynomial based spectral methods have been developed for TFDEs, e.g., [2, 21, 33]. However, these methods use polynomial basis functions which are not particularly suitable for TFDEs whose solutions are generally non-smooth at \(t=0\). Spectral methods for fractional PDEs with non-smooth solutions have been a subject of intensive study in the last few years, e.g., Zayernouri and Karniadakis [35] first proposed to approximate the singular solutions by Jacobi poly-fractonomials, which were defined as eigenfunctions of a fractional Sturm–Liouville problem; Chen et al. [5] constructed efficient Petrov–Galerkin methods for fractional PDEs by using the generalized Jacobi functions (GJFs) which include Jacobi poly-fractonomials as special cases. Subsequently, some authors developed spectral methods by using Jacobi poly-fractonomials/GJFs to solve fractional PDEs [14, 34, 37, 40]. Hou and Xu [12, 13] introduced a Müntz spectral method for some weakly singular integro-differential equations and fractional differential equations. Liu et al. [23] proposed a novel spectral scheme using nonstandard singular basis function for time fractional differential equation. Very recently, Chen and Shen [4] developed the enriched spectral-Galerkin method for the problems with weakly singular solution.
In a previous work [31], we introduced a space–time Petrov–Galerkin spectral method for linear/nonlinear time fractional diffusion equation, which employs the GJFs in temporal discretization and Fourier-like basis in spatial discretization. The use of Fourier-like basis functions in space can be regarded as using the matrix decomposition/diagonalization method [11, 24, 30]. However, this approach is not feasible when \(\Omega \) is not a simple tensor product domain, one cannot construct a Fourier-like basis and the degree of freedom (DoF) in space is too large to perform eigen-decomposition. In this paper, we focus on how to construct an efficient matrix decomposition method based on time variable. The two main difficulties here are: (i) the stiffness matrix in the time variable is not symmetric so the matrix decomposition method based the eigen-decomposition is not suitable; and (ii) the solution has weak singularity at \(t=0\) which limits the accuracy of the approximation by the GJFs.
We shall present in this paper an enriched Petrov–Galerkin spectral method for linear and nonlinear TFDEs. This work introduces several new aspects: (i) We develop a novel direct solver for time Petrov–Galerkin spectral method, which employs QZ decomposition to solve the non-symmetric linear system efficiently in a stable manner; (ii) For the time variable, we choose GJFs to match the leading singularity of the underlying solution; (iii) We use an enriched Petrov–Galerkin method to match leading singular terms of the underlying solution, and thus significantly improved the accuracy.
The remainder of this paper is structured as follows. In Sect. 2, we introduce the basis functions for the time variable, and present some useful properties of fractional calculus. In Sect. 3, we develop efficient Petrov–Galerkin methods for TFDEs and establish the error bounds for the proposed method. We present the enriched Petrov–Galerkin method for TFDEs in Sect. 4. Numerical results for nonlinear problems and applications to time fractional Allen–Cahn equations are presented in Sect. 5. Some concluding remarks are given in the last section.
2 Preliminaries
In this section, we review some basics of fractional integrals/derivatives, define some suitable functional spaces to be used later, and introduce some properties of the shifted generalized Jacobi functions and the shifted Legendre polynomials.
2.1 Fractional Derivatives
We start with some preliminary definitions of fractional derivatives (see, e.g. [7, 25]).
Let \(I=(0,T)\). For \(\rho \in \mathbb {R}^{+},\) the left-sided and right-sided Riemann–Liouville integrals are respectively defined as
where \(\Gamma (\cdot )\) is the usual Gamma function.
For \(\nu \in [m-1,m)\) with \(m\in \mathbb {N},\) the left-sided Riemann–Liouville fractional derivative of order \(\nu \) is defined by
and the right-sided Riemann–Liouville fractional derivative of order \(\nu \) is defined by
For \(\nu \in [m-1,m)\) with \(m\in \mathbb {N},\) the left-sided Caputo fractional derivative of order \(\nu \) is defined by
and the right-sided Caputo fractional derivative of order \(\nu \) is defined by
The following lemma shows the relationship between the Riemann–Liouville and Caputo fractional derivatives (see, e.g., [7, 25]).
Lemma 2.1
For \(\nu \in [k-1,k)\) with \(k\in \mathbb {N}\), we have
2.2 Some Functional Spaces and Their Properties
We now introduce some functional spaces to be used later.
Let \(C^\infty _0(I)\) be the space of smooth functions with compact support in I, and \(H^s_0(I)\) denote the closure of \(C_0^\infty (I)\) with respect to norm \(\Vert \cdot \Vert _{s,I}\).
For any real \(s>0\), we introduce some useful spaces.
-
Let \({\widetilde{H}}^s(I)\) be the set of functions in \(H^s(I)\) whose extension by zero to \(\mathbb {R}\) is in \(H^s(\mathbb {R})\).
-
Let \({\widetilde{H}}^s_l(I)\) be the set of functions u whose extension by zero, denoted by \(\tilde{u}\) is in \(H^s(-\infty ,T)\).
-
Let \({\widetilde{H}}^s_r(I)\) be the set of functions u whose extension by zero, denoted by \(\tilde{u}\) is in \(H^s(0,\infty )\).
Therefore, a direct consequence is as follows, see, e.g, [15].
Lemma 2.2
The operators \({}_{0}D_{t}^{s}\) and \({}_{t}D_{T}^{s}\) extend continuously to bounded operators from \({\widetilde{H}}^s_l(I)\) and \({\widetilde{H}}^s_r(I)\), respectively, to \(L^2(I)\).
We define the following space in x-direction,
equipped with the norm
The notation \(\langle \cdot ,\cdot \rangle _{L^2(\Omega )}\) denotes the duality pairing between \(H_{{\mathcal {L}}}(\Omega )\) and its dual \(H_{{\mathcal {L}}}^{\!-1}(\Omega )\), also the inner product in \(L^2(\Omega )\). For \(u,v\in L^2(D)\), for each \(t\in I\), \(u(t),\,v(t)\in H_{{\mathcal {L}}}(\Omega )\), we denote
and the Bochner spaces on D :
Below we will also use \(\langle \cdot ,\cdot \rangle _{L^2(D)}\) for the duality pairing between \(\mathbb {V}\) and \(\mathbb {V}^*\). For any \(s\in (0,1)\), we also define space
equipped with the norm
The following Lemma are useful; see, e.g., [8].
Lemma 2.3
For all \(0<\alpha <1\), if \(u\in B^\alpha (D),\) then
2.3 Trial & Test Functions in Time
We introduce below the trial & test functions that we will use for the time variable. For \(\alpha ,\beta >-1,\) let \(P_n^{(\alpha ,\beta )}(x),\)\(x\in \Lambda \) be the standard Jacobi polynomial of degree n, and denote the weight function \(\chi ^{(\alpha ,\beta )}(x)=(1-x)^\alpha (1+x)^\beta \). The set of Jacobi polynomials is a complete \(L^2_{\chi ^{(\alpha ,\beta )}}(\Lambda )\)-orthogonal system, i.e.,
where \(\delta _{l,m}\) is the Kronecker function, and
In particular, \(P_0^{(\alpha ,\beta )}(x)=1.\)
The shifted Jacobi polynomial of degree n is defined by
Clearly, the set of \(\{{\widetilde{P}}_n^{(\alpha ,\beta )}(t)\}_{n\ge 0}\) is a complete \(L^2_{\omega ^{(\alpha ,\beta )}}(I)\)-orthogonal system with the weight function \(\omega ^{(\alpha ,\beta )}(t)={(T-t)}^{\alpha }t^\beta ,\) by (2.12) and (2.13) we get that
For any \(\alpha ,~\beta >-1,\) the shifted generalized Jacobi functions on I is defined by (cf. [27])
and our approximation space on I is defined by
which incorporates the homogeneous boundary conditions at \(t=0.\)
A particular case is the shifted Legendre polynomial \(L_n(t)\), \(t\in I\) is defined by
The set of \(L_n(t)\) is a complete \(L^2(I)\)-orthogonal system, namely,
Clearly, we derive from (2.15)–(2.17) and a direct calculation that (cf. [5])
3 A Petrov–Galerkin Space–Time Method
In this section, we will propose a Petrov–Galerkin spectral method for (1.1). We shall start by considering a special case of (1.1) with \({\mathcal {N}} v=\beta v-g\):
with the initial and boundary conditions (1.2) and the constant \(\beta \ge 0\). Note that the above linear equation will be used as a preconditioner for nonlinear equation (1.1) later.
3.1 GJFs Petrov–Galerkin Method for (3.1)
Throughout this paper, we assume that \(v_0\in H^2(\Omega )\cap H^1_0(\Omega )\). For the case of non-homogeneous initial conditions \(v(\varvec{x},0)=v_0(\varvec{x})\), we first decompose the solution \(v(\varvec{x},t)\) into two parts as
with \(u(\varvec{x},0)=0\). Hence, by (3.2) and (2.6), the Eq. (3.1) is equivalent to the following equation with Riemann–Liouville fractional derivative:
where
with homogeneous initial
and the corresponding boundary conditions.
We first recall the weak formulation of (3.1): find \(u\in B^\alpha (D)\) such that
where \(b(\cdot ,\cdot )\) and \(\mathbb {V}\) are defined in (2.9) and (2.10), respectively. Without loss of generality, we assume that the bilinear form \(b(\cdot ,\cdot ):\mathbb {V}\times \mathbb {V}\rightarrow \mathbb {R}\) satisfies
-
Continuity: \(\exists \,C_1>0\) such that \(|b(u,v)|\le C_1\Vert u\Vert _{\mathbb {V}}\Vert v\Vert _{\mathbb {V}}\),
-
Coercivity: \(\exists \,C_2>0\) such that \(|b(u,u)|\ge C_2\Vert u\Vert _{\mathbb {V}}^2\).
A direct consequence is the following.
Theorem 3.1
For any \(f\in \mathbb {V}^*\), problem (3.5) has a unique solution \(u\in B^\alpha (D)\), and it satisfies
Proof
By using an argument similar to the proof of Lemma 2.4 in [8], we deduce that
Hence, the existence, uniqueness and stability follow directly from the continuity and inf-sup condition of the bilinear form \({\mathcal {A}}(\cdot ,\cdot )\). \(\square \)
Remark 3.1
The Galerkin weak formulation (see, e.g., [21]) is to find: \(u\in \tilde{B}^{\frac{\alpha }{2}}:=H^{\frac{\alpha }{2}}(I;L^2(\Omega ))\cap L^2(I;H^1_0(\Omega ))\) such that
Then, the bilinear form \(a(\cdot ,\cdot )\) is continuous and coercive on \({\tilde{B}}^{\frac{\alpha }{2}}\), and the variational problem is well-posed. More results on well-posedness and regularity for (3.5), we refer to [9, 20] and the references therein.
Let \(V_h\) be a finite-dimensional approximation space of \(V:=H_{{\mathcal {L}}}(\Omega )\):
For the time variable, we shall use the fractional polynomial space \({\mathcal {F}}_{N}^{(\alpha )}(I)\) defined in (2.16). Then, the Petrov–Galerkin method for (3.3) is to seek \(u_L(\varvec{x},t):=u_{MN}\in V_h \otimes {\mathcal {F}}^{(\alpha )}_N\subset B^\alpha (D)\), such that
Next, we shall construct suitable basis functions of \({\mathcal {F}}_{N}^{(\alpha )}(I)\) so that the above system can be solved efficiently.
For the time variable, we use the generalized Jacobi functions \(J^{(-\alpha ,\alpha )}_{n}(t)\) defined in the last section:
and for \({\mathcal {P}}_{N}(I)\) in the test space, we simply use the scaled Legendre polynomials, namely:
We now describe the numerical implementations for (3.8) under this set of basis functions. We write
Denote
It can be easily verified from (2.18), (2.19) and (3.10) that \(\varvec{S}^t=\varvec{I}\) with \(\varvec{I}\) being the identity matrix. On the other hand,
So \(\varvec{M}^t\) is not sparse but can be accurately computed by Jacobi-Gauss quadrature with index \((0,\alpha )\).
Then, we find that (3.8) is equivalent to the following linear system:
where \(\varvec{M}^h\) and \(\varvec{S}^h\) are the mass matrix and stiffness matrix in the space variable, namely,
Obviously, it is not computationally efficient to use matrix decomposition method in the space direction for non-tensor product domains. Because the size of \(\varvec{M}^{h}\) and \(\varvec{S}^{h}\) alway very large in (3.14). In this paper, we devote to do matrix decomposition in the time direction. Notice that an advantage of using matrix decomposition in time direction is that we only need to solve N times elliptic equation in the space direction. Moreover, it is straightforward to extend this approach to the nonlinear case (1.1), we omitted all the details in this paper.
3.2 Several Algorithms for (3.14)
This subsection focuses on the efficient algorithms for the nonsymmetric linear system.
Algorithm I: Eigen-Decomposition. We consider the generalized eigenvalue problem: let \(\varvec{E}:=({\bar{e}}_0,\ldots ,\bar{e}_{N})=(e_{pq})_{p,q=0,\ldots ,N}\) be the matrix formed by the orthonormal eigenvectors of the generalized eigenvalue problem \(\varvec{M}^t{\bar{e}}_j=\lambda _j\varvec{S}^t{\bar{e}}_j\) and \(\Lambda =\text {diag}(\lambda _0,\ldots ,\lambda _{N})\), i.e.,
Setting \(U=V\varvec{E}^T\), and multiplying (3.14) [or (4.6) respectively] both side by \((\varvec{S}^t\varvec{E})^{-T}\), we arrive at
Hence, the m-th column of the above matrix equation becomes:
where
The coefficient U can be computed by \(U=V\varvec{E}^T\). Finally, we can use (3.11) and (3.2) to get the solution \(u_L\). This approach is very efficient because we only need to solve \(N+1\) times elliptic equation in space, and the total cost is \(O(NT_M)\), where \(T_M\) is the cost of the underlying algorithm in the space direction. However, since \(\varvec{M}^t\) is nonsymmetric, this approach suffer from large round off errors. In Table 1, we tabulate the maximum error of \((\varvec{S}^t\varvec{E})^{-1}\varvec{M}^t\varvec{E}-\Lambda \) for the stifness/mass matrix in (3.12) with various N, which indicate that error of eigen-decomposition is grown as N increases. We then conclude that the eigen-decomposition algorithm for linear system with the full nonsymmetric matrix is not stable.
Algorithm II: Partial QZ Decomposition. We consider following QZ decomposition:
where \(\varvec{Q}\), \(\varvec{Z}\) are the unitary matrices, and \(\varvec{A}\), \(\varvec{B}\) are upper triangular matrices, namely,
Setting \(U=V\varvec{Q}\), and multiplying (3.14) both sides by \(\varvec{Z}\), we arrive at
We can obtain the column of coefficients \({\mathbf {v}}_n=({\widetilde{v}}_{1,n},{\widetilde{v}}_{1,n},\ldots ,{\widetilde{v}}_{M,n})^T,\) one by one, namely,
where
Briefly, we obtain the unknown coefficients \({\mathbf {v}}_n\) in terms of previous computed coefficients \(\{{\mathbf {v}}_k\}_{k=0}^{n-1}\), as stated in Algorithm II below.
Finally, the coefficient matrix U can be computed by \(U=V\varvec{Q}\), and we can use (3.11) and (3.2) to get the value of solution \(u_L\). In this algorithm, we only need to solve \(N+1\) times elliptic equation, so this new approach is also very efficient. Let \(T_M\) be the cost of solving one elliptic equation in space, then the total cost is \(O(N^2M)+(N+1)T_M\) (usually \(N\ll M\)). In Table 2, we tabulate the maximum error of \(\max \{|\varvec{Q}^T\,\varvec{A}\varvec{Z}^T -\varvec{S}^t|,| \varvec{Q}^T\,\varvec{B}\varvec{Z}^T -\varvec{M}^t|\}\) for the stifness/mass in (3.12) with various N, which indicate that error of eigen decomposition is awaly stable. We find that QZ decomposition are much more stable than eigen decomposition for full nonsymmetric matrix.
Algorithm III: Full Decomposition. In cases where it is feasible to diagonalize also in the space variables, e.g., when \(\Omega \) is a simple geometric (such as rectangular domains), we can simplify the algorithm even further.
We consider following eigen decomposition in space and QZ decomposition in time:
where \(\varvec{E}^h\) and \(\Lambda ^h\) are matrix form eigenvectors and eigenvalues, \(\varvec{Q}^t\), \(\varvec{Z}^t\) are the unitary matrices, and \(\varvec{A}^t\), \(\varvec{B}^t\) are upper triangular matrices.
Setting \(U=\varvec{E}\,V\varvec{Q}^t\), and multiplying the left (resp. right) of Eq. (3.14) by \((\varvec{S}^h\varvec{E}^h)^{-1}\) (resp. \(\varvec{Z}^t\)), we arrive at
We can solve the coefficients \(\{{\widetilde{v}}_{mn}\}_{0\le n\le N},\) one by one, namely,
where
Briefly, we obtain tcoefficients \(\{{\widetilde{v}}_{mn}\}_{0\le n\le N},\) in terms of previous computed coefficients \(\{{\widetilde{v}}_{mj}\}_{j=0,1\ldots ,n-1}\), as stated in Algorithm III below.
Finally, the coefficient matrix U can be computed by \(U=\varvec{E}\,V\varvec{Q}^t\), and we can use (3.2) to get the value of solution \(u_L\). Notice that the full decomposition algorithm procedure is simpler to implement than the partial QZ decomposition algorithm, when \(\Omega \) is a simple geometric.
We summarize the three algorithms below: (i) all the three algorithm are only need to consists of solving \(N+1\) times systems of order M; (ii) Algorithms II and III are very stable for solving nonsymmetric linear systems, while Algorithms I are not; (iii) Algorithms II and III provide the same numerical result when \(\Omega \) is a simple geometric, and Algorithm III is simpler to implement than Algorithm II; (iv) It is worthwhile to point out that we can use QZ decomposition in both time and space direction when the spatial discretization is nonsymmetric too.
3.3 Error Estimates for Petrov–Galerkin Spectral Method
In this subsection, we conduct an error analysis for the Petrov–Galerkin method described in the previous section. Since the full error analysis for the nonlinear system is beyond the scope of this paper, we shall only consider the analysis for the linear case of (3.1) with \({\mathcal {L}}=-\Delta \), that is
In order to characterize the regularity of u in t, we define the following non-uniformly weighted space involving fractional derivatives
The correspongding projection operator in time is \(\pi ^{(-\alpha ,\alpha )}_N:\; L^2_{\omega ^{(-\alpha ,-\alpha )}}(I)\rightarrow {\mathcal {F}}_{N}^{(\alpha )}(I)\) defined by
It is shown in [5] that
We recall from [27] that
Lemma 3.1
Let \(\alpha \in (0,1),\) for any \(v\in {\mathcal {B}}^s_{-\alpha ,\alpha }(I),\) with integer \(0\le s\le N\). Then
and
Let \(\pi ^h\) be the \(H^1_0\)-orthogonal projection in space direction
Hence, using Lemma 3.1, we arrive at following result.
Theorem 3.2
Let u be the solution of (3.3) and \(u_L\) be the numerical solution (3.8). If \(u\in B^\alpha (D)\) and \({}_{0}D_{t}^{\alpha +s}u\in L^2_{\omega ^{(s,s)}}(I,H_{{\mathcal {L}}}(\Omega ))\) there holds
Proof
The discrete inf-sup condition can be derived in a similar fashion as Lemma 3.3 of [8], namely, there is a constant \(c_\alpha >0\), independent N, such that
We can derive from continuity and Theorem 3.1 and 3.31 that 3.8 admits a unique solution \(u_L\in B^\alpha (D)\) satisfying
Moreover, we have
Taking \(v=\pi ^{(-\alpha ,\alpha )}_N\pi ^hu=\pi ^h\pi ^{(-\alpha ,\alpha )}_Nu\) into 3.32, we obtain from above equation that
In view of this, taking \(s=0\) in (3.28), we conclude that
By (3.29), we treat the second term \(I_2\) as
A combination of the above estimates and Lemma 2.2 leads to the desired result. \(\square \)
3.4 Numerical Examples
We employ the Petrov–Galerkin method to the linear TFDEs to demonstrate the spatial and temporal convergence rates of the proposed algorithms.
Example 1
We first consider following linear TFDEs in rectangular domains
with the exact solution \(u(x,y,t)=\sin (\pi x)\sin (\pi y)(t^{\alpha }\sin (\pi t)+1),\)\(a(x,y)=1\), and non-homogeneous initial conditions \(u_0(x,y)=\sin (\pi x)\sin (\pi y)\).
Without loss of generality, we use piecewise linear FEM for spatial discretization and GJFs Petrov–Galerkin method for temporal discretization. Let \({\mathcal {T}}_h=\{K\}\) be a uniformly regular family of rectangular in \((-1,1)^2\), and define the mesh size h. In Fig. 1, we list the maximum errors of (3.34), in log–log scale (or semi-log scale) at \(T=1\). We see from Fig. 1 (left) the proposed scheme has a second-order convergence rate in time. In Fig. 1 (right), we observe an exponential decrease of the numerical errors with increasing N and a level-off the error curves beyond \(N=8\), due to the saturation of spatial errors.
Example 2
This example is devoted to comparing the numerical stability of algorithms in Sect. 3.2. To this end, we employ GJFs Petrov–Galerkin method in temporal discretization and Legendre spectral method in spatial discretization to resolve Example 1 numerically. In Fig. 2 (left), we compare the \(B^\alpha (D)\)-errors of algorithm I with algorithm III, for which we take \(M=40\). Notice that algorithms II and III give the same numerical result, so we prefer to use algorithm III in this example. We observe that for the \(N\le 10\) the numerical results from two algorithms are the same; but for \(N>10\), the algorithm III (or algorithm II) provides more accurate numerical results than algorithm I. This is because the eigen-decomposition is not stable for the nonsymmetric linear system, see Sect. 3.2. In Fig. 2 (right), we also list the \(B^\alpha (D)\)-errors, in semi-log scale, with \(N=40\). Although the exact solution has singularity at \(t=0\), but in the weighted Sobolev spaces \({\mathcal {B}}^s_{-\alpha ,\alpha }(I)\) which involving fractional derivatives, we have \(u|_t\in {\mathcal {B}}^s_{-\alpha ,\alpha }(I)\) for any large s. We observe that the numerical errors decay exponentially as M/N increases. We note in particular that very high accuracy is achieved with quite small M / N for this special problem.
Example 3
We also consider Eq. (3.34) in rectangular domains with the exact solution \(u(x,y,t)=\sin (\pi x)\sin (\pi y)\cdot \sin (\pi t^{\alpha }),\)\(a(x,y)=\frac{x^2+y^2}{2},\) and the homogeneous initial conditions \(u_0(\varvec{x})=0\). Clearly, the singularity of the exact solution in time is more complicated than Example 1. Since we have
The GJFs can match the first leading singularity of the solution, then the convergence rate only depends on the second leading singularity of the solution. Here we take \(\alpha =0.8,\,0.6,\,0.4,\,0.2\). Then, we can derive from Theorem 3.1 and (3.35) that the corresponding convergence rate is \(N^{-4},N^{-3}, N^{-2}, N^{-1}\). In Fig. 3 (left) we plot the \(B^\alpha \)-errors in log–log scale against various N and \(\alpha \) with \(M=20\). We observe that the numerical results are consistent with theoretical results. We also list the \(B^\alpha \)-errors in semi-log scale against various M and \(\alpha \) with \(N=60\) in Fig. 3 (right). They indicate that the numerical errors decay exponentially as M increases, and numerical errors decay algebraically as N increases.
Example 4
We consider TFDEs (3.34) in unit disk \(\Omega =\{x^2+y^2<1\}\) with the exact solution \(u(x,y,t)=(x^2+y^2-1)(\cos (8(x+y))+\sin (8(x+y)))\cdot t^{\alpha }\sin (\pi t),\)\(a(x,y)=1\), and homogeneous initial conditions \(u_0(x,y)=0\). In Fig. 4, we list the \(B^\alpha (D)\)-errors, in semi-log scale. We observe that the numerical errors decay exponentially as M/N increases. We note in particular that very high accuracy is achieved with quite small M / N for this special problem.
Example 5
We also consider Eq. (3.34) in unit disk \(\Omega =\{x^2+y^2<1\}\) with the exact solution \(u(x,y,t)=(x^2+y^2-1)(\cos (8(x+y))+\sin (8(x+y)))\cdot \sin (\pi t^{\alpha }),\)\(a(x,y)=1,\) and the homogeneous initial conditions \(u_0(\varvec{x})=0\). In Fig. 5 (left) the \(B^\alpha (D)\)-errors in log–log scale against various N and \(\alpha \) with \(M=20\) . We also list the \(B^\alpha (D)\)-errors in semi-log scale against various M and \(\alpha \) with \(N=60\) in Fig. 5 (right). We see that the numerical errors decay exponentially as M increases, and numerical errors decay algebraically as N increases.
Example 6
To eliminate the error of spatial direction, we also consider Eq. (3.34) in unit disk \(\Omega =\{x^2+y^2<1\}\) with the given right hand side term \(f(x,y,t)=(x^2+y^2-1)\), \(a(x,y)=1,\) and the homogeneous initial conditions. Since no exact solution is available, we use the numerical solution with \(M=50\), \(N=100\) and add three singular functions (see Sect. 4.2 for more detail) as the reference solution. In Fig. 6 (left) the \(B^\alpha (D)\)-errors in log–log scale against various N and \(\alpha \) with \(M=40\) . We observe that the numerical errors decay algebraically as M increases. Since the GJFs Petrov–Galerkin method only match the first leading singularity of the solution, then the second leading singularity are \(t^\nu =t^{0.8},t^{1.2},t^{1.6}\) with respect to \(\alpha =0.4,0.6,0.8\). We can derive from Theorem 3.2 that the convergence rate are \(N^{-1},N^{-2},N^{-2}\) respectively. Similarly, we plot the \(B^\alpha (D)\)-errors in log–log scale against various N and \(\alpha \) with \(M=40\) with \(f(x,y,t)=(x^2+y^2-1)\cdot \cos (\pi t)\) in Fig. 6 (right).
4 An Improved Algorithm with Enriched Approximation Space in Time
This section is devoted to the improved algorithm with enriched approximation space in time. We develop in this section an enriched Petrov–Galerkin method for TFDEs as well as the error estimate for the proposed method. Some numerical examples to illustrate the efficiency of our method are presented.
4.1 Algorithm
In order to introduce the enriched Petrov–Galerkin method for (3.3), we first need the following basis function space for time variable
and in the test space, we take
where \(\psi _i,~i=1,\ldots ,k\) are some known singular functions.
Remark 4.1
Although we can use the basis in (4.1) directly, due to the added basis \(\{\psi _i\}_{i=1}^k\) are not orthogonal to the original one \(\{J_n^{-\alpha ,\alpha }(t)\}_{n=0}^N\), which leads to ill-condition matrix. Moreover, the ill-condition will affect the accuracy of solving the linear system.
In order to make the implementation more efficient, it is strongly recommended to use following modified Gram–Schmidt process:
and \(\varphi _{N+i},\)\(i=1,\ldots ,k\) can be computed as
where
Then, the enriched Petrov–Galerkin method for (3.3) is to seek \(u^k_L(\varvec{x},t):=u^k_{MN}\in V_h\otimes {\mathcal {F}}_{N}^{(k,\alpha )}\), such that
We now describe the numerical implementations for (4.4) under this set of basis functions. We write
Denote
Then, from (3.2), we find that (4.4) is equivalent to the following linear system:
Then, we can use Algorithm II or Algorithm III [cf. Sect. (3)] to resolve linear system 4.6.
In Table 3, we tabulate the maximum error of \((\varvec{S}^{en}\varvec{E})^{-1}\varvec{M}^{en}\varvec{E}-\Lambda \) (resp. \(\max \{|\varvec{Q}^T\,\varvec{A}\varvec{Z}^T -\varvec{S}^{en}|,| \varvec{Q}^T\,\varvec{B}\varvec{Z}^T -\varvec{M}^{en}|\}\)) for eigen-decomposition (resp. QZ decomposition) in (4.6) with various N, which indicate that error of eigen decomposition is grow as N increases. We observe similar behaviors as in Sect. 3.2 that the QZ decomposition is much more stable than eigen decomposition for the nonsymmetric enriched matrices.
4.2 Error Analysis
In this subsection, we shall restrict our attention to the linear case (3.3) with \({\mathcal {L}}=-\Delta \). To this end, we begin with the representation of the solution of (3.3). Let us consider the following eigenvalue problem
where \(\varphi \) satisfy the homogeneous boundary condition, and it admits a nondecreasing sequence \(\{\lambda _j\}^\infty _{j=1}\) of positive eigenvalues and the eigenfunctions \(\{\varphi _j\}^\infty _{j=1}\) forms an orthonormal basis in \(L^2(\Omega )\). Then, the solution of (3.3) can be expressed as (see e.g., [26])
where \(E_{a, b}(z)\) denotes the two-parameter Mittag–Leffler function:
Denote by \(k\in \mathbb {N}\) the number of elements contained in the set
For any given right hand side \(f\in C^{\overline{k}}(I;L^2(\Omega ))\) in (3.3), we can easily get the singularity of the solution in t-direction. More precisely, for any k, the solution of (4.7) in t-direction can be rewritten as
where the coefficients \(\gamma _{i,j}^\alpha \) are dependent on i, j and \(\alpha .\) Let the leading singularity of \({{\widetilde{u}}}^k(t)\) be \(t^{\nu +\overline{k}-1},\) with \(\nu \in (0,1]\). Clearly, the singularity of our approximation space is \(A(k;\alpha )=\{i\in \mathbb {N}_0,i+\alpha <\overline{k}\},~\overline{k}\in \mathbb {N}\), so the rest part of the singularity is given by
where \(k\in \mathbb {N}\) denote the number of elements contained in \(R(k;\alpha )\) or \(A(k;\alpha )\).
Following the same procedure in Petrov–Galerkin spectral method, we arrive at
To this end, we assume that
then, we take
and by applying Theorem 3.2 we have
Theorem 4.1
Let u be the solution of (3.3) and \(u^k_L\) be the numerical solution (4.4). Assume (4.10) holds and the leading singularity of \({\widetilde{u}}^k|_t\) near \(t=0\) is \(t^{\nu +\overline{k}-1}\) with \(\nu \in (0,1]\) and \(\overline{k}\) is defined in (4.8). If \(u\in B^\alpha (D)\) and \({}_{0}D_{t}^{\alpha +m}{\widetilde{u}}^k\in L^2_{\omega ^{(m,m)}}(I,H_{{\mathcal {L}}}(\Omega ))\), there holds
where the convergence index \(m\in \mathbb {N}\) satisfy
-
for \(\nu -\alpha \in (-1,-\frac{1}{2}]\), we have \(m=2\overline{k}-3\),with \(\overline{k}\ge 2\);
-
for \(\nu -\alpha \in (-\frac{1}{2},0]\), we have \(m=2\overline{k}-2\), with \(\overline{k}\ge 2\);
-
for \(\nu -\alpha \in (0,\frac{1}{2}]\) , we have \(m=2\overline{k}-1\), with \(\overline{k}\ge 1\);
-
for \(\nu -\alpha \in (\frac{1}{2},1]\), we have \(m=2\overline{k}\), with \(\overline{k}\ge 1\);
Proof
Since the leading singularity of \({\widetilde{u}}^k|_{t}\) is \(t^{\nu +\overline{k}-1}\), \(\nu \in (0,1]\), which imply \(\nu -\alpha \in (-\alpha ,1-\alpha ]\). According to Lemma 3.1 and Theorem 3.2, we only need to consider
or equivalently,
To determine the value of \(m\ge 0\), by fact that \(\overline{k}\ge 1\) and a direct computation from (4.13) gives
-
For \(\nu -\alpha \in (-1,-\frac{1}{2}]\) (or \(2(\nu -\alpha )\in (-2,-1]\)), we obtain that \(m=2\overline{k}-3\), namely,
$$\begin{aligned} \begin{array}{ll} \mathrm{If} \;\overline{k}=2,3,4,5,\ldots \quad , \quad \mathrm{we~have}~ m=1,3,5,7\ldots . \end{array} \end{aligned}$$ -
For \(\nu -\alpha \in (-\frac{1}{2},0]\) (or \(2(\nu -\alpha )\in (-1,0]\)), we obtain that \(m=2\overline{k}-2\), namely,
$$\begin{aligned} \begin{array}{ll} \mathrm{If} \;\overline{k}=1,2,3,4,\ldots ,\quad \mathrm{we ~have}~m=0,2,4,6,\ldots . \end{array} \end{aligned}$$ -
For \(\nu -\alpha \in (0,\frac{1}{2}]\) (or \(2(\nu -\alpha )\in (0,1]\)), we obtain that \(m=2\overline{k}-1\), namely,
$$\begin{aligned} \begin{array}{ll} \mathrm{If} \;\overline{k}=1,2,3,4,\ldots ,\quad \mathrm{we ~have}~m=1,3,5,7\ldots . \end{array} \end{aligned}$$ -
For \(\nu -\alpha \in (\frac{1}{2},1]\) (or \(2(\nu -\alpha )\in (1,2]\)), we obtain that \(m=2\overline{k}\), namely,
$$\begin{aligned} \begin{array}{ll} \mathrm{If} \;\overline{k}=1,2,3,4,\ldots ,\quad \mathrm{we ~have}~m=2,4,6,8, \ldots . \end{array} \end{aligned}$$
Note that in the case \(\nu -\alpha \in (-\frac{1}{2},0]\): when \(m=0,\) we got \(\alpha >\nu +\overline{k}-1\) in (4.12), but this is not true. Hence, we have \(m\ge 2\) in the case \(\nu -\alpha \in (-\frac{1}{2},0]\). A combination of the above estimates leads to the desired result. \(\square \)
4.3 Numerical Results
In order to ignore the error in spatial direction, we consider TFDEs (3.34) in 1D with a given source function \(f(x,t)=\sin (\pi x)\cdot \cos (\pi t),\)\(a(x)=\frac{x^2}{2}\) and homogeneous initial conditions. In this example, we use improved algorithm to reslove (3.34) numerically. More specifically, we can take the first k-th singular term \(t^{\nu _j}\) in \(R(k;\alpha )=\{t^{i+j\alpha }, ~i,j\in \mathbb {N}_0,i+j\alpha <\overline{k},j\ne 1\}.\) The exact solution is unknown, we compute a numerical solution with \(M=40\), \(N=100\) and \(k=4\) as the exact solution. In Fig. 7 , we list the Max-errors in log–log scale against various N, k and \(\alpha \) with \(M=30\). They indicate that the enriched Petrov–Galerkin method is better than the Petrov–Galerkin method, and the numerical errors decay algebraically.
5 Numerical Results for Nonlinear Problems
In this section, we shall present some numerical results obtained by the proposed methods introduced in Sect. 3 for nonlinear problem.
Example 5.1
Consider the following time fractional Burgers equation in 1D:
with the initial data \(u_0(x)=-\sin (\pi x)\).
We initially solved this problem by using the preconditioned Jacobian-free Newton-Krylov method. To accelerate the convergence, we employed a two-grid approach. Namely, we use \({\widetilde{N}}\approx N/2\) and \(M\approx M/2\) as the initial data for the iteration the coarse approximation solution with N for the fine approximation solution with N and M. This two-grid approach significantly improved the convergence, only less than 10 iterations are needed to achieve \(10^{-7}\)-digit accuracy.
We plots in Fig. 8a the numerical solution with \(M=100,\)\(N=80,\)\(\alpha =0.7,\)\(\gamma =0.01\) at \(t = 0, ~0.25,~0.5,~0.75,~1\). We observe that, similar to the usual Burgers equation, the profile of solution become steeper as t increases to about \(t = 0.25\), and the solution start to relax towards zero for \(t > 0.25\). To investigate the influence of \(\alpha \) on the solution, we plot the numerical solution with \(\gamma = 0.01, N = 64, M = 100\) at \(t =1\) for various \(\alpha \) in Fig. 8b. As a comparison, we also plot the solution with \(\alpha =1\), i.e., the usual Burgers equation. We observe that, as \(\alpha \) increases, the profile of the solution becomes steeper and dissipates faster.
Example 5.2
Consider the following time fractional Allen–Cahn equation in 1D:
with the initial data
and homogeneous Neumann boundary conditions
In the above, \(f(u)=(u^2-1)u=F^\prime (u)\) is the usual double-well potential, \(\Omega \) is the bounded domain and n is the outward normal. The parameters we use in the following presentation is \(\epsilon =0.1\).
We also employed a two-grid approach (see Example 5.1) to resolve (5.2). Note that in this example, only less than 12 iterations are needed to achieve \(10^{-7}\)-digit accuracy. We plots in Fig. 9a the numerical solution with \(M=250,\)\(N=80,\)\(\alpha =0.7,\)\(\epsilon =0.1\) at \(t = 0, ~0.5,~1,~1.5,~2\). We observe that the relaxation process as t increases is similar to the usual Allen–Cahn equation.
To further investigate the influence of \(\alpha \) on the solution, we plot the numerical solution with \(\epsilon = 0.1, N = 80, M = 250\) at \(t =1\) for various \(\alpha \) in Fig. 8b. As a comparison, we also plot the solution with \(\alpha =1\), i.e., the usual Allen–Cahn equation. We observe that, as \(\alpha \) decreases, the speed of profile relaxation also decreases.
6 Concluding Remarks
We developed an efficient Petrov–Galerkin spectral method for linear/nonlinear TFDEs. The proposed method employs an enriched Petrov–Galerkin method for time discretization and can be coupled with any consistent Galerkin type discretization in space. The main contributions of this paper are: (i) a novel and efficient matrix diagonalization method based on QZ decomposition is introduced to solve the space–time linear system directly; (ii) an enriched Petrov–Galerkin method which significantly improves the accuracy in time; and (iii) rigorous error analysis for the space–time Petrov–Galerkin method with and without additional enriched basis functions.
References
Canuto, C., Hussaini, M.Y., Quarteroni, A., Zang, T.A.: Spectral Methods: Fundamentals in Single Domains. Springer, Berlin (2006)
Chen, F., Xu, Q., Hesthaven, J.S.: A multi-domain spectral method for time-fractional differential equations. J. Comput. Phys. 293, 157–172 (2015)
Chen, H., Holland, F., Stynes, M.: An analysis of the Grünwald–Letnikov scheme for initial-value problems with weakly singular solutions. Appl. Numer. Math. 139, 52–61 (2019)
Chen, S., Shen, J.: Enriched spectral methods and applications to problems with weakly singular solutions. J. Sci. Comput. 77(3), 1468–1489 (2018)
Chen, S., Shen, J., Wang, L.-L.: Generalized Jacobi functions and their applications to fractional differential equations. Math. Comput. 85(300), 1603–1638 (2016)
Deng, W., Li, B., Qian, Z., Wang, H.: Time discretization of a tempered fractional Feynman–Kac equation with measure data. SIAM J. Numer. Anal. 56(6), 3249–3275 (2018)
Diethelm, K.: The Analysis of Fractional Differential Equations: An Application-oriented Exposition Using Differential Operators of Caputo Type. Springer, Berlin (2010)
Duan, B., Jin, B., Lazarov, R., Pasciak, J., Zhou, Z.: Space–time Petrov–Galerkin FEM for fractional diffusion problems. Comput. Methods Appl. Math. 18(1), 1–20 (2018)
Gorenflo, R., Luchko, Y., Yamamoto, M.: Time-fractional diffusion equation in the fractional sobolev spaces. Fract. Calc. Appl. Anal. 18(3), 799–820 (2015)
Guo, B.: Spectral Methods and Their Applications. World Scientific, Singapore (1998)
Haidvogel, D.B., Zang, T.: The accurate solution of poisson’s equation by expansion in Chebyshev polynomials. J. Comput. Phys. 30(2), 167–180 (1979)
Hou, D., Hasan, M.T., Xu, C.: Müntz spectral methods for the time-fractional diffusion equation. Comput. Methods Appl. Math. 18(1), 43–62 (2018)
Hou, D., Chuanju, X.: A fractional spectral method with applications to some singular problems. Adv. Comput. Math. 43(5), 911–944 (2017)
Huang, C., Jiao, Y., Wang, L.-L., Zhang, Z.: Optimal fractional integration preconditioning and error analysis of fractional collocation method using nodal generalized Jacobi functions. SIAM J. Numer. Anal. 54(6), 3357–3387 (2016)
Jin, B., Lazarov, R., Pasciak, J., Rundell, W.: Variational formulation of problems involving fractional order differential operators. Math. Comput. 84(296), 2665–2700 (2015)
Jin, B., Lazarov, R., Pasciak, J., Zhou, Z.: Error analysis of a finite element method for the space-fractional parabolic equation. SIAM J. Numer. Anal. 52(5), 2272–2294 (2014)
Jin, B., Lazarov, R., Zhou, Z.: A Petrov–Galerkin finite element method for fractional convection–diffusion equations. SIAM J. Numer. Anal. 54(1), 481–503 (2016)
Jin, B., Lazarov, R., Zhou, Z.: Two fully discrete schemes for fractional diffusion and diffusion-wave equations with nonsmooth data. SIAM J. Sci. Comput. 38(1), A146–A170 (2016)
Jin, B., Li, B., Zhou, Z.: Numerical analysis of nonlinear subdiffusion equations. SIAM J. Numer. Anal. 56(1), 1–23 (2018)
Li, B., Luo, H., Xie, X.: Analysis of a time-stepping scheme for time fractional diffusion problems with nonsmooth data. SIAM J. Numer. Anal. 57(2), 779–798 (2019)
Li, X., Chuanju, X.: A space–time spectral method for the time fractional diffusion equation. SIAM J. Numer. Anal. 47(3), 2108–2131 (2009)
Lin, Y., Chuanju, X.: Finite difference/spectral approximations for the time-fractional diffusion equation. J. Comput. Phys. 225(2), 1533–1552 (2007)
Liu, W., Wang, L.-L., Xiang, S.: A new spectral method using nonstandard singular basis functions for time-fractional differential equations. Commun. Appl. Math. Comput. 1, 1–24 (2019)
Lynch, R.E., Rice, J.R., Thomas, D.H.: Direct solution of partial difference equations by tensor product methods. Numer. Math. 6(1), 185–199 (1964)
Podlubny, I.: Fractional Differential Equations: An Introduction to Fractional Derivatives, Fractional Differential Equations, to Methods of Their Solution and Some of Their Applications, vol. 198. Academic Press, Cambridge (1998)
Sakamoto, K., Yamamoto, M.: Initial value/boundary value problems for fractional diffusion-wave equations and applications to some inverse problems. J. Math. Anal. Appl. 382(1), 426–447 (2011)
Shen, J., Sheng, C., Wang, Z.: Generalized Jacobi spectral-galerkin method for nonlinear Volterra integral equations with weakly singular kernels. J. Math. Study 48(4), 315–329 (2015)
Shen, J., Tang, T.: Spectral and High-Order Methods with Applications. Mathematics Monograph Series, vol. 3. Science Press, Beijing (2006)
Shen, J., Tang, T., Wang, L.-L.: Spectral Methods: Algorithms, Analysis and Applications, vol. 41. Springer, Berlin (2011)
Shen, J., Wang, L.-L.: Fourierization of the Legendre–Galerkin method and a new space–time spectral method. Appl. Numer. Math. 57(5), 710–720 (2007)
Sheng, C., Shen, J.: A space–time Petrov–Galerkin spectral method for time fractional diffusion equation. Numer. Math. Theory Methods Appl. 11, 854–876 (2018)
Sun, Z., Xiaonan, W.: A fully discrete difference scheme for a diffusion-wave system. Appl. Numer. Math. 56(2), 193–209 (2006)
Tian, W.Y., Deng, W., Yujiang, W.: Polynomial spectral collocation method for space fractional advection–diffusion equation. Numer. Methods Partial Differ. Equ. 30(2), 514–535 (2014)
Zayernouri, M., Ainsworth, M., Karniadakis, G.E.: A unified Petrov–Galerkin spectral method for fractional pdes. Comput. Methods Appl. Mech. Eng. 283, 1545–1569 (2015)
Zayernouri, M., Karniadakis, G.E.: Fractional Sturm–Liouville eigen-problems: theory and numerical approximation. J. Comput. Phys. 252, 495–517 (2013)
Zeng, F., Li, C., Liu, F., Turner, I.: The use of finite difference/element approaches for solving the time-fractional subdiffusion equation. SIAM J. Sci. Comput. 35(6), A2976–A3000 (2013)
Zeng, F., Zhang, Z., Karniadakis, G.E.: A generalized spectral collocation method with tunable accuracy for variable-order fractional differential equations. SIAM J. Sci. Comput. 37(6), A2710–A2732 (2015)
Zeng, F., Zhang, Z., Karniadakis, G.E.: Fast difference schemes for solving high-dimensional time-fractional subdiffusion equations. J. Comput. Phys. 307, 15–33 (2016)
Zhang, Y., Sun, Z.: Alternating direction implicit schemes for the two-dimensional fractional sub-diffusion equation. J. Comput. Phys. 230(24), 8713–8728 (2011)
Zhang, Z., Zeng, F., Karniadakis, G.E.: Optimal error estimates of spectral Petrov–Galerkin and collocation methods for initial value problems of fractional differential equations. SIAM J. Numer. Anal. 53(4), 2074–2096 (2015)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The work of J. Shen is partially supported by NSF DMS-1620262, DMS-1720442 and AFOSR FA9550-16-1-0102.
Rights and permissions
About this article
Cite this article
Shen, J., Sheng, CT. An Efficient Space–Time Method for Time Fractional Diffusion Equation. J Sci Comput 81, 1088–1110 (2019). https://doi.org/10.1007/s10915-019-01052-8
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10915-019-01052-8