Von Neumann Stability Analysis

(20 pts) For the ODE \(u'(t) = f(t,u)\), consider the time-integration scheme \[ u_{n+1} = u_n + \frac {k}{4}f(t_n,u_n) + \frac {3k}{4}f\left (t_n+\frac {2}{3}k,\ u_n+\frac {2}{3}kf(t_n,u_n)\right ). \]

1. (5 pts) Identify the Butcher tableau for this scheme.
2. (8 pts) Compute the order of consistency of this scheme.
3. (7 pts) Compute the stability/amplification factor of the scheme.

(20 pts)

1. (10 pts) Use von Neumann stability analysis to determine a stability condition for, \[ D^+u_j^n = D_0u_j^n, \] where \(D^+u_j^n = (u_j^{n+1}-u_j^n)/k\), \(D_0u_j^n = (u_{j+1}^n-u_{j-1}^n)/(2h)\), and \(D_\pm u_j^n = \pm (u_{j\pm 1}^n-u_j^n)/h\).
2. (10 pts) Use von Neumann stability analysis to determine a stability condition for \[ D^+u_j^n = D_+D_-u_j^n. \]

(20 pts) Consider the PDE, \[ u_t + au_x = 0,\qquad u(x,0)=u_0(x),\qquad a > 0, \] with periodic boundary conditions over the spatial domain \(x \in [0, 1)\). Use the standard notation, \(u_j^n \approx u(x_j,t^n)\) with \(x_j = jh\) and \(t^n = nk\) with \(h = \frac {1}{M} > 0\) for some \(M \in \mathbb {N}\) and \(k > 0\). Consider the following semi-Lagrangian scheme: \[ u_j^{n+1}=p_j(y),\qquad y := X(t^n;x_j,t^{n+1}), \] where \(X(t; x, t_0)\) is the time-\(t\) spatial location of the PDE’s characteristic curve passing through spatial location \(x\) at time \(t_0\), and \(p_j(\cdot )\) is the linear interpolant formed by the data \((x_{j-1},u_{j-1}^n)\) and \((x_j,u_j^n)\).

1. (10 pts) Write this scheme as an explicit function of the \(u_j^n\) values.
2. (10 pts) Use von Neumann stability analysis to determine a stability condition for this scheme.

(20 pts)

1. (10 pts) Compute the stability/amplification factor for forward Euler to solve \(u' = f(t,u)\), and plot the region of the stability.
2. (10 pts) Compute the stability/amplification factor for the trapezoidal rule/Crank- Nicolson scheme and use this to show that the scheme is A-stable.

(20 pts)

1. (10 pts) Use von Neumann stability analysis to determine a stability condition for, \[ D^+u_j^n = D_0u_j^n, \] where \(D^+u_j^n = (u_j^{n+1}-u_j^n)/k\), \(D_0u_j^n = (u_{j+1}^n-u_{j-1}^n)/(2h)\), and \(D_\pm u_j^n = \pm (u_{j\pm 1}^n-u_j^n)/h\).
2. (10 pts) Use von Neumann stability analysis to determine a stability condition for \[ D^+u_j^n = D_+D_-u_j^n. \]

( Heat Equation and Stability of the Scheme). Consider the implicit in time, Backward Euler method for the solution of the heat equation: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} -10\frac {u_{m+1}^{n+1}-2u_m^{n+1}+u_{m-1}^{n+1}}{h^2} = f_m^{n+1}, \] \[ u_m^0 = g_m,\qquad m = 0,\pm 1,\pm 2,\ldots ,\qquad n = 0,1,\ldots ,[T/\Delta t]-1, \]

and investigate the stability of the scheme using the von Neumann analysis.

 Heat Equation and Stability of the Scheme

Consider the implicit in time, Backward Euler method for the solution of the heat equation: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - 4\frac {u_{m+1}^{n+1}-2u_m^{n+1}+u_{m-1}^{n+1}}{h^2} = f_m^{n+1}, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1, \] and investigate the stability of the scheme using the von Neumann analysis.

Region of Absolute Stability and Example of Linear One-Step Method

1. Define a region of absolute stability for the linear multistep method.

2. Find the region of absolute stability for the Backward Euler Method.

Trapezoid rule

For the ODE \(y'=f(t,y)\), the Trapezoid rule is \[ \frac {y_{n+1}-y_n}{\Delta t} = \frac {1}{2}\left (f(t_n,y_n)+f(t_{n+1},y_{n+1})\right ). \] Compute the region of absolute stability for the Trapezoid rule. Is this method \(A\)-stable?

Unconditionally stable scheme

For the one-dimensional heat equation, \[ u_t=u_{xx}, \] consider the Crank-Nicolson, central difference scheme \[ \frac {u_j^{n+1}-u_j^n}{\Delta t} = \frac {1}{2} \left ( \frac {u_{j+1}^{n+1}-2u_j^{n+1}+u_{j-1}^{n+1}}{h^2} + \frac {u_{j+1}^{n}-2u_j^{n}+u_{j-1}^{n}}{h^2} \right ) \] where \(\Delta t\) and \(h\) are temporal and spatial stepsizes, respectively, and where \(u_j^n\) is the numerical approximation to \(u(x=jh,t=n\Delta t)\), with \(x_0=0\) and the initial time \(t=0\). Use von Neumann stability analysis to show that this scheme is unconditionally stable.

Central scheme

Consider the one-dimensional advection equation, \[ u_t=cu_x, \] where \(c\in \mathbb {R}\) is the wavespeed. Use von Neumann stability analysis to determine the values of \(c\) for which the following the central difference, forward Euler scheme is stable: \[ \frac {u_j^{n+1}-u_j^n}{\Delta t} = c\frac {u_{j+1}^{n}-u_{j-1}^{n}}{2h}. \]

Heat Equation and Stability of the Scheme

Consider the implicit in time, Backward Euler method for the solution of the heat equation: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - \frac {u_{m+1}^{n+1}-2u_m^{n+1}+u_{m-1}^{n+1}}{h^2} = f_m^{n+1}, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1. \] and investigate the stability of the scheme using the von Neumann analysis.

Region of Absolute Stability and Example of Linear One-Step Method

1. Define a region of absolute stability for Linear Multistep Method.

2. Find the region of absolute stability for the Forward Euler Method.

Upwind Scheme

Consider the advection equation \[ u_t+5u_x=0,\qquad x_L<x<x_R,\qquad 0<t\le T, \] where \(u(x,0)=g(x)\), and \(u(x_L,t)=u_L(t)\) for \(t>0\).

a) Write the Upwind Scheme for this problem.

b) What is the local truncation error of the Upwind Scheme?

c) What is the stencil of the scheme? What is the CFL condition for this method?

d) Investigate the stability of the method using Von Neumann Stability Analysis.

Upwind Scheme

Consider the advection equation \[ u_t-u_x=0,\qquad x_L<x<x_R,\qquad 0<t\le T, \] where \(u(x,0)=g(x)\), and \(u(x_R,t)=u_R(t)\) for \(t>0\).

a) Write the Upwind Scheme for this problem.

b) What is the stencil of the scheme? What is the CFL condition for this method?

c) Investigate the stability of the method using Von Neumann Stability Analysis.

Heat Equation Consider the following heat equation problem \[ u_t=u_{xx},\qquad t>0,\qquad 0<x<1, \] \[ u(0,t)=u(1,t)=0,\qquad t>0, \] \[ u(x,0)=u_0(x),\qquad 0\le x\le 1. \] Using the forward or backward difference for the time derivative and central difference for the space derivative, derive the explicit and implicit schemes. What’s the stability condition for each case? Perform a Fourier analysis on both the explicit and implicit methods and use the von Neumann condition to verify these stability conditions.

Define what is meant by a linear multistep method and its region of absolute stability. Show that a convergent explicit linear multistep method cannot have an infinite region of absolute stability.

Heat Equation Stability:

Consider the variable coefficient diffusion equation \[ v_t=(\beta v_x)_x,\qquad 0<x<1,\quad t>0 \] with Dirichlet boundary conditions \[ v(0,t)=0,\qquad v(1,t)=0 \] and initial data \(v(x,0)=f(x)\). Assume that \(\beta (x)\geq \beta _0>0\), and that \(\beta (x)\) is smooth. Let \(\beta _{j+1/2}=\beta (x_{j+1/2})\). A scheme for this problem is: \[ \frac {u_j^{n+1}-u_j^n}{k} = \frac {1}{h^2} \left \{ \beta _{j-1/2}u_{j-1}^{n+1} -(\beta _{j-1/2}+\beta _{j+1/2})u_j^{n+1} +\beta _{j+1/2}u_{j+1}^{n+1} \right \}. \] Analyze the 2-norm stability of this scheme for solving this initial boundary value problem.

NOTE: Because of the boundary conditions and the variable coefficients, von Neumann (Fourier) analysis does not apply.

7) Numerical Methods for ODEs: Consider the initial value problem for a system of ODEs \[ y'=Ay \] where \(A\) has eigenvalues with real parts ranging from \(-10^6\) to \(-1\). Which of the following schemes would be the best choice for solving this problem? Justify your answer in terms of stability, accuracy, and efficiency. Does your answer change depending on the size of the system and the condition number of \(A\)? Explain your answer. \[ y^{n+1}=y^n+kAy^n, \tag {1} \] \[ y^{n+1}=y^n+kAy^{n+1}, \tag {2} \] \[ y^{n+1}=y^n+\frac {k}{2}\left (Ay^n+Ay^{n+1}\right ). \tag {3} \]

Stability of the Scheme

Using the von Neumann method investigate the stability of the implicit downwind scheme: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - \frac {u_m^{n+1}-u_{m-1}^{n+1}}{h} = f_m^n, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1. \]

Stability of the Scheme

Using the von Neumann method investigate the stability of the implicit upwind scheme: \[ \frac {u_m^{n+1}-u_m^n}{\Delta t} - \frac {u_{m+1}^{n+1}-u_m^{n+1}}{h} = f_m^n, \] \[ u_m^0=g_m,\qquad m=0,\pm 1,\pm 2,\ldots ,\qquad n=0,1,\ldots ,[T/\Delta t]-1. \] Comment on the CFL condition for this scheme.

Crank Nicolson Method Describe the Crank-Nicolson Method for the solution of the equation \[ u_t=u_{xx} \tag {6} \] and use the von Neumann method to examine its stability.

Finite-Difference Methods Consider the initial boundary value problem \[ v_t=\beta v_{xx},\qquad 0<x<1,\quad t>0,\qquad v(x,0)=f(x) \] with Dirichlet boundary conditions \[ v(0,t)=0,\qquad v(1,t)=0. \] Suppose that the interval \([0,1]\) is partitioned by meshpoints \(x_j=jh\) for \(j=0,1,\ldots ,N\) and \(h=1/N\). A possible discretization of the above problem uses the Crank-Nicolson scheme for the differential equation: \[ \left (I-\frac {\beta k}{2}D_+D_-\right )u_j^{n+1} = \left (I+\frac {\beta k}{2}D_+D_-\right )u_j^n \] for \(j=1,\ldots ,N-1\), combined with the boundary conditions: \[ u_0^n=0\qquad \text {and}\qquad u_N^n=0 \] for each time level \(n\). Initial data is obtained by setting \(u_j^0=f_j\) for \(j=0,1,\ldots ,N\). (Note that \(D_+\) and \(D_-\) are the usual forward and backward difference operators.) Set up the matrix system that must be solved in order to advance the numerical solution from time level \(n\) to time level \(n+1\). Show that the suggested discretization is stable in the \(\ell _2\) norm \[ \lVert u\rVert _2=\left (\sum _{j=0}^N h\lvert u_j\rvert ^2\right )^{1/2} \] for all choices of timestep \(k\) and spacestep \(h\). (Note that von Neumann analysis is not enough to prove stability for the initial boundary value problem.) What other issues are important to consider in deciding whether this scheme is a good choice for the problem?

Fact 1: A real symmetric \(n\times n\) matrix \(A\) can be diagonalized by an orthogonal similarity transformation, and \(A\)’s eigenvalues are real.

Fact 2: The \((N-1)\times (N-1)\) matrix \(M\) defined by \[ M_{ij}= \begin {cases} -2, & i=j,\\ 1, & \lvert i-j\rvert =1,\\ 0, & \text {otherwise} \end {cases} \qquad (1\le i,j\le N-1) \] has eigenvalues \[ \mu _l=-4\sin ^2\left (\frac {\pi l}{2N}\right ),\qquad l=1,2,\ldots ,N-1. \]

Fact 3: The \((N+1)\times (N+1)\) matrix \(M\) defined by \[ M_{ij}= \begin {cases} -1, & i=j\in \{0,N\},\\ -2, & i=j,\ 1\le i\le N-1,\\ 1, & \lvert i-j\rvert =1,\\ 0, & \text {otherwise} \end {cases} \qquad (0\le i,j\le N) \] has eigenvalues \[ \mu _l=-4\sin ^2\left (\frac {\pi l}{2(N+1)}\right ),\qquad l=0,1,\ldots ,N. \]

Fact 4: For a real \(n\times n\) matrix \(A\), the Rayleigh quotient of a vector \(x\in \mathbb {R}^n\) is the scalar \[ r(x)=\frac {x^T Ax}{x^T x}. \] The gradient of \(r(x)\) is \[ \nabla r(x)=\frac {2}{x^T x}(Ax-r(x)x). \] If \(x\) is an eigenvector of \(A\) then \(r(x)\) is the corresponding eigenvalue and \(\nabla r(x)=0\).

PDEs Consider the one-dimensional Heat Equation \[ u_t=u_{xx},\qquad t\ge 0,\qquad x\in [0,1],\qquad u(x,0)=f(x),\qquad u(0,t)=u(1,t)=0. \tag {11} \] Describe how to discretize this problem by applying the Method of Lines and the Backward Euler Method. Analyze the stability and local accuracy of your method.

Heat Equation Consider the following heat equation problem \[ u_t=u_{xx},\qquad t>0,\qquad 0<x<1, \] \[ u(0,t)=u(1,t)=0,\qquad t>0, \] \[ u(x,0)=u_0(x),\qquad 0\le x\le 1. \] Using the forward or backward difference for the time derivative and central difference for the space derivative, derive the explicit and implicit schemes. What’s the stability condition for each case? Perform a Fourier analysis on both the explicit and implicit methods and use the von Neumann condition to verify these stability conditions.