3
$\begingroup$

I'm having a lot of difficulty and I was hoping someone could help me out. I'm looking at a variety of PDEs but for the sake of this post, lets just look at the advection equation

$$u_{t} = -u_{x}$$

If I apply the Backward Euler formula (implicit) to the time derivative only, so it is semi discrete, we end up with

\begin{align} u_{t} &\approx \frac{u_{n+1} - u_{n}}{h} \\ \implies \frac{u_{n+1} - u_{n}}{h} &= -u_{(n+1)x} \\ \implies u_{n} &= (1 + hD)u_{n+1} \\ \end{align}

where $D$ is the derivative operator $\frac{d}{dx}$ acting upon $u_{n+1}$. Now, is there anyway to check the convergence and stability of this ODE? I realise that the literature states that the Backward Euler is stable if

$$ \lvert 1 + h \lambda \rvert^{-1} \le 1$$

but does this still apply when instead of an eigenvalue ($\lambda$), we have an operator? And how do I check the convergence of such a scheme? Most of the literature discusses the CFL number, but this seems to only apply when you have discretised both time and space? Or have I got that wrong?

I've been stuck at this for hours and the literature can be quite confusing and dense. If anyone has any suggestions for literature available on the internet, or could answer my above questions, that would be great.

$\endgroup$
3
$\begingroup$

Let's extend your PDE with some initial and boundary conditions $$ u_t = -u_x, x \in [0, 1]\\ u\big|_{x=0} = \beta(t)\\ u\big|_{t=0} = u_0(x) $$ By discretizing the time, you've obtained the system of ODEs with initial conditions: $$\begin{aligned} &u_{n+1}(x) + h u'_{n+1}(x) = u_{n}(x)\\ &u_{n+1}(0) = \beta((n+1)h). \end{aligned} $$ From this point, there are two ways to show the absolute stability of the scheme.

Maximum principle. One can show that $||u_{n+1}||_C \leq \max(||\beta||_C, ||u_n||_C)$. Proof: Provided that $u_{n+1}(x) \in C^1[0,1]$ the global maximum of $|u_{n+1}(x)|$ can be reached either at $x = 0$, or at $x = 1$ or at some point $0 < x < 1$ with $u'_{n+1}(x) = 0$. If the maximum is at $x = 0$ then $||u_{n+1}||_C \leq ||\beta||_C$. If the maximum is at $0 < x < 1$ then $$ ||u_{n+1}||_C = |u_{n+1}(x)| = |u_{n}(x)| \leq ||u_n||_C $$ due to $u_{n+1}'(x) = 0$. Finally, if the maximum is at $x = 1$, then $$ \operatorname{sign}(u_{n+1}(1)) u'_{n+1}(1) \geq 0 $$ so $$ |u_{n+1}(1)| + h\operatorname{sign}(u_{n+1}(1)) u'_{n+1}(1) = \operatorname{sign}(u_{n+1}(1))u_n(1). $$ Since the left side is nonnegative, the right side should be $|u_n(1)|$. Again $$ |u_{n+1}(1)| \leq |u_n(1)| \leq ||u_n||_C. $$ So we have proved that $$ ||u_{n+1}||_C \leq \max(||u_n||_C, ||\beta||_C) \leq \max(||u_0||_C, ||\beta||_C) $$ i.e. the scheme is stable under $||\cdot||_C$ norm.

Operator norm theory. First, let's simplify the problem a bit: $$ u_{n+1}(x) + h u_{n+1}'(x) = u_n(x)\\ u_{n+1}(0) = \beta((n+1)h) $$ by introducing $y_{n+1}(x) = u_{n+1}(x) - \beta((n+1)h)$: $$ y_{n+1}(x) + h y_{n+1}'(x) = y_n(x) - \beta((n+1)h) + \beta(nh)\\ y_{n+1}(0) = 0 $$ Now every $y_{n+1}(x)$ belongs to subspace of $C^1[0,1]$ with $y_{n+1}(0) = 0$ condition.

Let's rewrite the operator scheme in form $$ B y_{n+1} = y_n + \varphi_n $$ with $A$ and $B$ being some operators. $$ B = I + h D\\ \varphi_n = \beta(nh)-\beta((n+1)h). $$

Let the inner product $(u,v)$ be the $$ (u,v) = \int_{0}^1 u(x)v(x) dx. $$ Then $$ (By,y) = (y,y) + h(Dy,y)\\ (Dy,y) = \int_0^1 y y'dx = \int_{y(0)}^{y(1)} y dy = \frac{y^2(1)}{2} - \frac{y^2(0)}{2} = \frac{y^2(1)}{2}\\ (By,y) = (y,y) + h\frac{y^2(1)}{2} \equiv ||y||_B^2 \geq (y,y) \equiv ||y||^2\\ (Dy,y) = \frac{y^2(1)}{2} $$ so $B$ is positive definite and $D$ is positive-semidefinite. Thus there exists $B^{-1}$. We would like to find some Hilbert space where $B^{-1}$ has norm not greater than 1.

Using the inequality $||y||^2 \leq ||y||^2_B$ $$ ||B^{-1}x||^2 \leq ||B^{-1}x||^2_B = (BB^{-1}x,B^{-1}x) = (x, B^{-1}x) \leq ||x||\cdot||B^{-1}x||\\ ||B^{-1}x|| \leq ||x|| $$ we can conclude that $||B^{-1}|| \leq 1$ (so the space has simply $(u,v)$ for its inner product).

Now $$ y_{n+1} = B^{-1}(y_n + \varphi_n)\\ ||y_{n+1}|| \leq ||B^{-1}||(||y_n||+||\varphi||) \leq ||y_n|| + ||\varphi_n||\\ ||y_{n+1}|| \leq ||y_0|| + \sum_{k=0}^{n} ||\varphi_k|| $$ Since $\varphi_k(x) = \beta(nh)-\beta((n+1)h)$, $$ ||\varphi_k|| = |\beta((n+1)h)-\beta(nh)|\sqrt{\int_0^1 dx} = |\beta((n+1)h)-\beta(nh)| \leq h \max_{0 \leq t \leq (n+1)h} |\beta'(t)| $$ $$ ||y_{n+1}|| \leq ||y_0|| + \int_0^{(n+1)h} |\beta'(t)|dt $$ Thus again we've proved that the scheme is stable, but in $L_2$ norm this time.

$\endgroup$
  • $\begingroup$ Mate, thank you so much for your response, I really appreciate it. The operator norm proof was especially good. Just to be clear, do the proofs you give above describe the $\textit{stability of the backward Euler method}$ (which is what I'm after), or do they describe the stability of the PDE (as that is what I'm used to using the maximum principle for)? I assume the maximum principle holds for the BDF2 formula then (as BE is from the same family) as well? $\endgroup$ – Mattos Jun 20 '15 at 0:13
  • $\begingroup$ I'm afraid it's only BE that would grant C-norm stability, I'd rather make some numerical experiments to show violations of the maximum principle for BDF2+ used as time integrator. $L_2$ stability should hold, that is what $r(h\lambda(D)) < 1$ about. But it might be more tricky to show that $D$'s spectrum (mostly imaginary but with a little bit of a real part) lies inside BDF2+ stability domain. $\endgroup$ – uranix Jun 20 '15 at 5:22
  • $\begingroup$ Forget what I said about spectrum, It seems to be empty. $\endgroup$ – uranix Jun 20 '15 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.