Multigrid Methods for Time-Fractional Evolution Equations: A Numerical Study

Abstract

In this work, we develop an efficient iterative scheme for a class of nonlocal evolution models involving a Caputo fractional derivative of order $\alpha (0,1)$ in time. The fully discrete scheme is obtained using the standard Galerkin method with conforming piecewise linear finite elements in space and corrected high-order BDF convolution quadrature in time. At each time step, instead of solving the linear algebraic system exactly, we employ a multigrid iteration with a Gauss–Seidel smoother to approximate the solution efficiently. Illustrative numerical results for nonsmooth problem data are presented to demonstrate the approach.

Appendix A: Proof of Theorem 2.3

Proof

In a customary way, we split the error $e^{n,m}=U_h^{n,m}-u(t_n)$ into

$$\begin{aligned} e^{n,m}= (U_h^{n,m}-R_h u(t_n)) + (R_h u(t_n)-u(t_n)) =: \vartheta ^n + \varrho ^n. \end{aligned}$$

In view of (12), it suffices to bound $\vartheta ^n$. Note that $\vartheta ^n$ satisfies $\vartheta ^0=0$ and

$$\begin{aligned}&{\bar{\partial }}_\tau ^\alpha \vartheta ^n + A_h\vartheta ^n = ({\bar{\partial }}_\tau ^\alpha (U_h^{n,m}-v_h)+ A_hU_h^{n,m}) -{\bar{\partial }}_\tau ^\alpha (R_hu(t_n)-v_h) - A_hR_hu(t_n), \\&\quad n=1,\cdots ,N. \end{aligned}$$

Let the auxiliary function ${\bar{U}}_h^n\in X_h$ satisfy ${\bar{U}}_h^0 = R_hv$ and

$$\begin{aligned} \tau ^{-\alpha } \left( {\bar{U}}_h^n + \sum _{j=1}^n b_{n-j}^{(\alpha )} U_h^{j,m} - \sum _{j=0}^n b_{n-j}^{(\alpha )} U_h^0\right) + A_h \bar{U}_h^n = f_h^n,\quad n=1,2,\cdots ,N. \end{aligned}$$

This together with the identities (4), (1) and (9) implies

$$\begin{aligned} {\bar{\partial }}_\tau ^\alpha \vartheta ^n + A_h \vartheta ^n= \sigma ^n \quad {\text {with }} \ \sigma ^n = (I+\tau ^\alpha A_h) \eta ^n + \omega ^n, \end{aligned}$$

(A1)

with the errors $\eta ^n$ and $\omega ^n$ given by

$$\begin{aligned} \eta ^n&=\tau ^{-\alpha } (U_h^{n,m} - {\bar{U}}_h^n) \quad \text {and} \nonumber \\ \omega ^n&= ( P_h - R_h ) {\partial _t^\alpha }(u(t_n)-v) - R_h ({\bar{\partial }}_\tau ^\alpha - {\partial _t^\alpha })(u(t_n)-v). \end{aligned}$$

(A2)

By the discrete maximal $\ell ^p$ regularity in Lemma 2.1 and the triangle inequality, for any $q\in (\frac{2}{\alpha },\infty )$ and $n=1,2,\cdots ,N$, we have

$$\begin{aligned} \Vert \vartheta ^n \Vert _{L^2(\Omega )}&\le c\Vert (A_h^{-\frac{1}{2}}\sigma ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} \\&\le c\Vert ((I+\tau ^{\alpha } A_h)A_h^{-\frac{1}{2}}\eta ^{j})_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} + c\Vert (A_h^{-\frac{1}{2}}\omega ^j)_{j=1}^n\Vert _{\ell ^q((\Omega ))}. \end{aligned}$$

Since u is sufficiently smooth, (13) and (14) imply

$$\begin{aligned} \Vert A_h^{-\frac{1}{2}}\omega ^j\Vert _{L^2(\Omega )}\le c\Vert \omega ^j\Vert _{L^2(\Omega )}\le c(u)(h^2+\tau ^k). \end{aligned}$$

Further, direct computation gives

$$\begin{aligned} \Vert (I+\tau ^\alpha A_h)A_h^{-\frac{1}{2}}\eta ^j\Vert _{L^2(\Omega )} \le c|\eta ^j|. \end{aligned}$$

(A3)

The preceding three estimates imply (with $|\cdot |_X=|\cdot |$)

$$\begin{aligned} \Vert \vartheta ^n \Vert _{L^2(\Omega )} \le c \Vert (\eta ^{j})_{j=1}^n\Vert _{\ell ^q(X)} + c(u) (h^2 + \tau ^k). \end{aligned}$$

(A4)

Next, we find a bound of the summand $|\eta ^j|$. Given a tolerance $\delta >0$ to be determined, under assumption (11), there exists an $m\in {\mathbb {N}}$ such that $c_0 \kappa ^m \le \delta$ and by the triangle inequality

$$\begin{aligned} |U_h^{n,m} - {\bar{U}}_h^n| \le \delta |U_h^{n,0}-{\bar{U}}_h^n| \le \delta ( |U_h^{n,0} - U_h^{n,m}| + |U_h^{n,m} - {\bar{U}}_h^n | ). \end{aligned}$$

With $\epsilon =\delta (1-\delta )^{-1}$, rearranging the inequality gives $|U_h^{n,m} - {\bar{U}}_h^n| \le \epsilon |U_h^{n,0} - U_h^{n,m} |$. Hence,

$$\begin{aligned} |\eta ^n| = \tau ^{-\alpha } |U_h^{n,m} - {\bar{U}}_h^n| \le \epsilon \tau ^{-\alpha } |U_h^{n,0} - U_h^{n,m} |. \end{aligned}$$

Meanwhile, the choice of $U_h^{n,0}$ in (8) and the triangle inequality imply

$$\begin{aligned} |U_h^{n,m} - U_h^{n,0}| \le \tau ^{k+1} |{\tilde{\partial }}_\tau ^{k+1} \theta ^{n}| + \tau ^{k+1}|{\tilde{\partial }}_\tau ^{k+1} R_h u(t_n)| , \end{aligned}$$

where ${\tilde{\partial }}_\tau ^{k+1}$ denotes the $(k+1)$th backward difference approximation (of the backward Euler type). The last two estimates together with the inverse inequality (in time) imply

$$\begin{aligned} \Vert (\eta ^{j})_{j=1}^n\Vert _{\ell ^q(X)}&\le c\epsilon \tau ^{1-\alpha }\Vert ({\bar{\partial }}_\tau \theta ^j)_{j=1}^n\Vert _{\ell ^q(X)} + c\epsilon \tau ^{k+1-\alpha }\Vert u\Vert _{C^{k+1}([0,T];H_0^1(\Omega ))} \nonumber \\&\le c\epsilon \Vert ({\bar{\partial }}_\tau ^\alpha \theta ^j)_{j=1}^n\Vert _{\ell ^q(X)} + c\epsilon \tau ^{k+1-\alpha }\Vert u\Vert _{C^{k+1}([0,T];H_0^1(\Omega ))}. \end{aligned}$$

(A5)

Let $I_h=(I+\tau ^{\alpha } A_h)^{-\frac{1}{2}}$. Then, the identity

$$\begin{aligned} |{\bar{\partial }}_\tau ^\alpha \vartheta ^j|= \Vert (I+\tau ^{\alpha } A_h) {\bar{\partial }}_\tau ^\alpha I_h\vartheta ^j\Vert _{L^2(\Omega )} \end{aligned}$$

and the triangle inequality imply

$$\begin{aligned} \Vert ({\bar{\partial }}_\tau ^\alpha \vartheta ^j)_{j=1}^n\Vert _{\ell ^q(X)}&\le \Vert ( {\bar{\partial }}_\tau ^\alpha I_h\vartheta ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} + \tau ^\alpha \Vert ({\bar{\partial }}_\tau ^\alpha A_hI_h\vartheta ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} \\&:=\mathrm{I}+\mathrm{II} . \end{aligned}$$

By the discrete maximal $\ell ^p$ regularity in Lemma 2.1, we have

$$\begin{aligned} \mathrm{I}&\le c\Vert (I_h\sigma ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))}, \end{aligned}$$

and similarly, the inverse inequality (in time) and discrete maximal $\ell ^p$ regularity yield

$$\begin{aligned} \mathrm{II}&\le c\Vert (A_hI_h\vartheta ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))} \le c\Vert (I_h\sigma ^j)_{j=1}^n\Vert _{\ell ^q(L^2(\Omega ))}. \end{aligned}$$

Combining the preceding three estimates with (A1), and the errors (13) and (14) gives

$$\begin{aligned} \Vert ({{\bar{\partial}}_{\tau}^{\alpha} \vartheta^{j})}_{j=1}^{n}\Vert_{\ell ^q(X)} \le c(u) (\tau +h^2) + c\epsilon \Vert ({{\bar{\partial}}_{\tau}^{\alpha}\theta^{j})}_{j=1}^n\Vert _{\ell ^q(X)}. \end{aligned}$$

(A6)

Now, it follows from (A5) and (A6) that

$$\begin{aligned} \Vert ({\bar{\partial }}_\tau ^\alpha \vartheta ^j)_{j=1}^n\Vert _{\ell ^q(X)} \le c(u) (\tau +h^2) + c\epsilon \Vert ({\bar{\partial }}_\tau ^\alpha \theta ^j)_{j=1}^n\Vert _{\ell ^q(X)}. \end{aligned}$$

Thus, by choosing a sufficiently small $\epsilon$, we get

$$\begin{aligned} \Vert ({\bar{\partial }}_\tau ^\alpha \vartheta ^j)_{j=1}^n\Vert _{\ell ^q(X)} \le c(u) (\tau +h^2). \end{aligned}$$

This, (A4) and (A5) give $\Vert \vartheta ^n \Vert _{L^2(\Omega )} \le c(u) (\tau +h^2)$, which completes the proof.