Zero-Stability and Root Conditions

(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) For the ODE \(u' = f(t,u)\) with initial condition \(u(0)\) and \(f\) globally Lipschitz continuous in \(u \in \mathbb {R}^M\) uniformly in \(t\), show that forward Euler with initial state \(u_0 = u(0)\) is convergent to first order. A possibly helpful definition: a scheme is 0-stable if, \[ \max _{n\in [N]}\|e_n\| \le C \max _{n\in [N]}\|R_n(u(t_n))\|, \] where \(e_n\) is the time-\(t_n\) error, and \(R_n(u(t_n))\) is the scheme residual using the exact solution.

(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) For the ODE \(u' = f(t,u)\) with initial condition \(u(0)\) and \(f\) globally Lipschitz continuous in \(u \in \mathbb {R}^M\) uniformly in \(t\), show that forward Euler with initial state \(u_0 = u(0)\) is convergent to first order. A possibly helpful definition: a scheme is 0-stable if, \[ \max _{n\in [N]}\|e_n\| \le C \max _{n\in [N]}\|R_n(u(t_n))\|, \] where \(e_n\) is the time-\(t_n\) error, and \(R_n(u(t_n))\) is the scheme residual using the exact solution.

For the initial value problem \(u'(t) = f(u(t),t)\), \(u(0) = \eta \), where \(f(u,t)\) is continuous with respect to \(t\) and Lipschitz continuous with respect to \(u\), consider the scheme \[ \frac {U^{n+2}-\frac {4}{3}U^{n+1}+\frac {1}{3}U^n}{k} = \frac {2}{3}f(U^{n+2},t_{n+2}), \] where \(t_n = nk\), and \(U^n\) is supposed to approximate \(u(t_n)\).

1. Analyze the consistency, zero-stability, and convergence of this scheme.

2. If you apply this scheme to the initial value problem

   \[ u'(t) = -10^{12}(u(t)-\cos (t))-\sin (t),\qquad u(0) = 2, \]

   what issues should you consider in choosing the timestep \(k\)? Are there time intervals in which \(k\) must be very small to get a reasonable solution and others in which it does not? Explain your answers.

Suppose you are trying find an approximation \(u(t)\) to a function \(v(t)\) and you know that the following two equations hold:

\[ v(t_{n+1}) = C(k)v(t_n) + k\tau (t_n) \]

for some smooth function \(\tau (t,k)\) that is not identically 0. Here, \(k > 0\), \(t_n = nk\), and \(C(k)\) is a linear operator which depends on \(k\) but not on \(u(t)\) or \(v(t)\). State and prove conditions on \(C(k)\) and \(\tau (t,k)\) which are sufficient to imply that \[ \lim _{k \to 0,\ nk=t_n=t} u(t_n) = v(t). \]

For the initial value problem \(u'(t) = f(u(t),t)\), \(u(0) = \eta \), where \(f(u,t)\) is continuous with respect to \(t\) and Lipschitz continuous with respect to \(u\), consider the scheme \[ \frac {U^{n+2}-\frac {4}{3}U^{n+1}+\frac {1}{3}U^n}{k} = \frac {2}{3}f(U^{n+2},t_{n+2}), \] where \(t_n = nk\), and \(U^n\) is supposed to approximate \(u(t_n)\).

1. Analyze the consistency, zero-stability, and convergence of this scheme.

2. If you apply this scheme to the initial value problem

   \[ u'(t) = -10^{12}(u(t)-\cos (t))-\sin (t),\qquad u(0) = 2, \]

   what issues should you consider in choosing the timestep \(k\)? Are there time intervals in which \(k\) must be very small to get a reasonable solution and others in which it does not? Explain your answers.

Linear Multistep Methods

Give the definition of linear multistep method (give formula).

a) State necessary and sufficient condition for linear multistep method to be consistent.

b) State root condition for linear multistep method.

c) Construct an example of a consistent but not stable linear multistep method. Justify your answer.

Linear Multistep Methods

Define linear multistep method (give formula).

a) State necessary and sufficient condition for linear multistep method to be consistent.

b) State root condition for linear multistep method.

c) What can you say about consistency and stability properties of the method: \[ y_{n+1}-3y_n+2y_{n-1}=-h f(y_{n-1})? \]

Wave Equation Consider the wave equation in one space dimension: \[ u_{tt}=c^2u_{xx},\qquad c>0. \] Suppose \(0\le x\le 1\) and \(t\ge 0\). The problem requires initial and boundary conditions but you can ignore them for the purposes of this question. Consider the usual discretization \[ \frac {1}{k^2}\left (U_m^{n+1}-2U_m^n+U_m^{n-1}\right ) = \frac {c^2}{h^2}\left (U_{m+1}^n-2U_m^n+U_{m-1}^n\right ) \] where \[ U_m^n\approx u(x_m,t_n) \] and \[ x_m=mh,\qquad h=\frac {1}{M},\qquad \text {and}\qquad t_n=nk,\qquad h,k>0. \] Let the grid constant \(r\) be defined by \[ r=\frac {kc}{h}. \] Derive the constraint on \(r\) imposed by the Courant-Friedrichs-Lewy condition. There is a value of \(r\) for which the local truncation error of the difference scheme is zero. Derive that value.

Let \(u,v\) be non-zero elements of a Hilbert space \(H\). Consider the linear operator \(T:H\to H\) defined for \(x\in H\) by \(Tx=u(x,v)\).

1. Briefly explain why the operator \(T\) is compact.
2. Find a condition on \(u\) and \(v\) that guarantees that the equation \[ (I-T)x=y \] admits a unique solution \(x\) for all \(y\in H\).

Consider the initial-boundary-value problem \[ u=u(x,t)=?,\qquad u_t=u_{xx},\qquad x\in [0,1],\qquad t\geq 0, \] subject to the initial and boundary conditions \[ u(x,0)=f(x),\qquad u(0,t)=g_0(t),\qquad u(1,t)=g_1(t) \] Explain how to use the method of lines to solve this problem. Describe the scheme you obtain by using the Backward Euler Method to solve the resulting ODEs and compute the local truncation error of that scheme.

Local Truncation Error Consider the wave equation \[ u_{tt}=c^2u_{xx} \tag {7} \] and its discretization \[ x_m=mh,\qquad t_n=nk,\qquad U_m^n\approx u(x_m,t_n) \tag {8} \] and \[ U_m^{n+1}-2U_m^n+U_m^{n-1} = r\left (U_{m+1}^n-2U_m^n+U_{m-1}^n\right ) \tag {9} \] where \(r=c^2k^2/h^2\) is the grid constant. For the purposes of this problem, ignore the issues of initial and boundary conditions. Compute the local truncation error of (9) and show that there is a value of \(r\) for which the local truncation error is exactly zero. Give a physical interpretation of this fact.

The windowed Fourier transform of a function \(f(x)\in L^2(-\infty ,\infty )\) is defined by \[ Gf(\omega ,\mu )=\int _{-\infty }^{\infty }g(x-\mu )f(x)e^{-\omega x}\,d\mu \,dx. \] Suppose \(g(x)\) is a real valued function. State and verify the formula for the reconstruction of \(f(x)\) from \(Gf\), including any additional conditions on \(g(x)\). You may assume the validity of the Fourier transform.

Local Truncation Error Consider the wave equation \[ u_{tt}=c^2u_{xx} \tag {10} \] and its discretization \[ x_m=mh,\qquad t_n=nk,\qquad U_m^n\approx u(x_m,t_n) \tag {11} \] and \[ U_m^{n+1}-2U_m^n+U_m^{n-1} = r\left (U_{m+1}^n-2U_m^n+U_{m-1}^n\right ) \tag {12} \] where \(r=c^2k^2/h^2\) is the grid constant. For the purposes of this problem, ignore the issues of initial and boundary conditions. Compute the local truncation error of (12) and show that there is a value of \(r\) for which the local truncation error is exactly zero. Give a physical interpretation of this fact.

Eigenvalue Problems Let \(\lambda \) be a simple eigenvalue of \(A\) (not necessarily symmetric), with right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). Let \(\lambda +\delta \lambda \) be the corresponding eigenvalue of \(A+\delta A\).

a) Show that \[ \delta \lambda =\frac {y^*\delta A x}{y^*x}+O(\lVert \delta A\rVert ^2), \] and derive an upper bound for \(\lvert \delta \lambda \rvert \). What is the condition number for \(\lambda \) with respect to changes in \(A\)?

b) Consider the matrix \[ \begin {bmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ \epsilon & 0 & \cdots & 0 & 0 \end {bmatrix}. \] Compute \(d\lambda /d\epsilon \) and show that the condition number becomes infinite as \(\epsilon \) approaches zero.

c) Describe the power method for finding the eigenvalue of the largest absolute magnitude, and inverse iteration for the eigenvalue closest to a given value. How fast do you expect these algorithms to converge?

Wave Equations Consider the wave equation in one space dimension: \[ u_t+au_x=0,\qquad -\infty <x<\infty ,\qquad t>0, \] with initial condition \[ u(x,0)=u_0(x). \] Consider the usual discretization \[ U_m^k\approx u(x_m,t_k) \] where \(x_m=m\Delta x\) and \(t_k=k\Delta t\). For an explicit scheme, what is the CFL condition? Give an intuitive explanation of the condition. Give the first-order upwind scheme for this equation and derive the truncation error.

Construct the Green function for the equation \[ u''(x)=f(x)\quad \text {on the interval }0\le x\le 1 \] if \(u\) satisfies the auxiliary conditions \[ \int _0^1 xu(x)\,dx=0\qquad \text {and}\qquad u(0)+u'(1)=0. \]

Eigenvalue Problems Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). a) Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). b) Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues. c) Sketch a reasonably efficient algorithm for finding the largest eigenvalue of a symmetric matrix \(A\) with distinct eigenvalues. How fast do you expect this algorithm to converge?

Newton’s Method Suppose \(f(x)\) is a real-valued function defined for all values of the real variable \(x\), and that \(f'\) is Lipschitz continuous. State and prove a local convergence theorem for Newton’s method for finding a simple zero of \(f\). How does this result change if the root is a double root? Is Newton’s method globally convergent? If you answered yes, prove your claim. If you answered no, sketch an example which illustrates your claim, and outline a method that has the Newton method’s local convergence properties but which is globally convergent.

Let \(A\) be an \(m\times n\) matrix and let the \(n\times m\) matrix \(A'\) denote the Least Square Pseudo-Inverse of \(A\).

1. State the conditions that define \(A'\).
2. Show that \(A'\) always exists.
3. Construct \(A'\) explicitly for the \(2\times 2\) matrix \[ A=\begin {pmatrix} 1 & 1\\ 0.5 & 0.5 \end {pmatrix}. \]

Eigenvalue Problems Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). a) Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). b) Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues. c) Sketch a reasonably efficient algorithm for finding the largest eigenvalue of a symmetric matrix \(A\) with distinct eigenvalues. How fast do you expect this algorithm to converge?

a) Give an identity that is the basis of one stage of the Fast Fourier Transform algorithm applied to a vector of length \(2^J\). Explain the approximate operation count for the complete algorithm.

b) Describe the application of the FFT to the solution of the heat equation with periodic boundary conditions, and how this may be viewed as performing a fast convolution.

Let \(A\) be an \(m\times n\) matrix and let the \(n\times m\) matrix \(A'\) denote the Least Square Pseudo-Inverse of \(A\).

1. State the conditions that define \(A'\).
2. Show that \(A'\) always exists.
3. Construct \(A'\) explicitly for the \(2\times 2\) matrix \[ A=\begin {pmatrix} 1 & 1\\ 0 & 0 \end {pmatrix}. \]

Construct the Green’s function for the equation \(u''(x)=f(x)\) on the interval \(0\le x\le 1\) if \(u\) satisfies the auxiliary conditions \[ \int _0^1 xu(x)\,dx=0\qquad \text {and}\qquad u(0)+u'(1)=0. \]