Local Truncation Error and Global Error

(20 pts) On an equidistant mesh \(x_j = jh\), define the operator \(\widetilde {D}_0\) as, \[ \widetilde {D}_0u(x_j) = \frac {u(x_j+h/2)-u(x_j-h/2)}{h}, \] For a given smooth \(\kappa \) and \(f\), consider the scheme, \[ -\widetilde {D}_0\left (\kappa (x_j)\widetilde {D}_0u_j\right ) = f(x_j), \] for the ODE \[ -\frac {d}{dx}\left (\kappa (x)\frac {d}{dx}u(x)\right ) = f(x). \] What order is the local truncation error?

(20 pts) On an equidistant mesh \(x_j = jh\), define the operator \(\widetilde {D}_0\) as, \[ \widetilde {D}_0u(x_j) = \frac {u(x_j+h/2)-u(x_j-h/2)}{h}, \] For a given smoooth \(\kappa \) and \(f\), consider the scheme, \[ -\widetilde {D}_0\left (\kappa (x_j)\widetilde {D}_0u_j\right ) = f(x_j), \] for the ODE \[ -\frac {d}{dx}\left (\kappa (x)\frac {d}{dx}u(x)\right ) = f(x). \] What order is the local truncation error?

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.

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.

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 What is the local truncation error of a numerical scheme? What does consistency mean? Give a specific and precise example.

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.

Elliptic Problems:

Consider the standard five-point difference approximation (centered difference for both the gradient and divergence operators) for the variable coefficient Poisson equation \[ -\nabla \cdot (a\nabla v)=f \] with Dirichlet boundary conditions, in a two-dimensional rectangular region. We assume that \(a(x,y)\geq a_0>0\). The approximate solution \(\{u_{i,j}\}\) satisfies a linear system \(Au=b\).

1. State and prove the maximum principle for the numerical solution \(u_{i,j}\).

2. Derive the matrix \(A\) in the one-dimensional case and show that it is symmetric and positive definite.

3. For the one-dimensional and constant-coefficient case, show that the global error \(e_j=v(x_j)-u_j\) satisfies \(\|e\|_2=O(h^2)\) as the space step \(h\to 0\).

4. Discuss the advantages and disadvantages of trying to solve the system for the two-dimensional problem using (i) the SOR (Successive Over Relaxation) method and (ii) the (preconditioned) Conjugate Gradient method.

Elliptic Problems:

Consider the standard five-point difference approximation (centered difference for both the gradient and divergence operators) for the variable coefficient Poisson equation \[ -\nabla \cdot (a\nabla v)=f \] with Dirichlet boundary conditions, in a two-dimensional rectangular region. We assume that \(a(x,y)\geq a_0>0\). The approximate solution \(\{u_{i,j}\}\) satisfies a linear system \(Au=b\).

1. State and prove the maximum principle for the numerical solution \(u_{i,j}\).

2. Derive the matrix \(A\) in the one-dimensional case and show that it is symmetric and positive definite.

3. For the one-dimensional and constant-coefficient case, show that the global error \(e_j=v(x_j)-u_j\) satisfies \(\|e\|_2=O(h^2)\) as the space step \(h\to 0\).

4. Discuss the advantages and disadvantages of trying to solve the system for the two-dimensional problem using (i) the SOR (Successive Over Relaxation) method and (ii) the (preconditioned) Conjugate Gradient method.

Linear Multistep Methods Consider the initial value problem \[ y'=f(x,y),\qquad y(a)=y_0 \] Let \(h\) be some stepsize, \(x_n=a+nh\), \(y_n\approx y(x_n)\), and \(f_n=f(x_n,y_n)\), for \(n=0,1,2,3,\ldots \). Let \(k\) be some step number, and ignore the question of obtaining starting values \(y_1,y_2,\ldots ,y_{k-1}\). Suppose the approximations \(y_n\), \(n=k,k+1,\ldots \) are obtained by the Linear Multistep Method \[ \sum _{j=0}^k \alpha _j y_{n+j} =h\sum _{j=0}^k \beta _j f_{n+j}. \tag {4} \] Define what is meant by the local truncation error and the order of the linear multistep method (4). Compute the order and the local truncation error of Euler’s Method \[ y_{n+1}-y_n=hf_n. \tag {5} \]

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.

Elliptic Problems:

Consider the standard five-point difference approximation (centered difference for both the gradient and divergence operators) for the variable coefficient Poisson equation \[ -\nabla \cdot (a\nabla v)=f \] with Dirichlet boundary conditions, in a two-dimensional rectangular region. We assume that \(a(x,y)\geq a_0>0\). The approximate solution \(\{u_{i,j}\}\) satisfies a linear system \(Au=b\).

1. State and prove the maximum principle for the numerical solution \(u_{i,j}\).

2. Derive the matrix \(A\) in the one-dimensional case and show that it is symmetric and positive definite.

3. For the one-dimensional and constant-coefficient case, show that the global error \(e_j=v(x_j)-u_j\) satisfies \(\|e\|_2=O(h^2)\) as the space step \(h\to 0\).

4. Discuss the advantages and disadvantages of trying to solve the system for the two-dimensional problem using (i) the SOR (Successive Over Relaxation) method and (ii) the (preconditioned) Conjugate Gradient method.

Numerical ODEs Define the terms linear multistep method (LMM), order, consistency, zero-stability, local truncation error, and region of absolute stability of an LMM. What is the highest order implicit 1 step method and discuss its region of absolute stability?

Numerical PDEs Consider the Initial-Boundary Value Problem \[ u_t=u_{xx},\qquad x\in [0,1],\qquad t\ge 0, \qquad u\text { given for }x=0,\ x=1,\text { and }t=0. \tag {4} \] Describe the Crank-Nicolson Method, and analyze its local truncation error and stability.

Wave Equations Consider the first-order wave equation in one space dimension: \[ u_t+au_x=0,\qquad -\infty <x<\infty ,\qquad t>0, \] where \(a\) is a constant, with the initial condition \[ u(x,0)=u_0(x),\qquad -\infty <x<\infty \] for a given function \(u_0\). We use the usual discretization \[ U_j^n\approx u(x_j,t^n), \] where \(x_j=j\Delta x\) and \(t^n=n\Delta t\). For a finite difference scheme to solve this problem, what is the CFL condition? Give an intuitive explanation for the condition. Derive the first-order upwind scheme for this equation and its truncation error. For numerical stability, derive the conditions for stability in the maximum norm (maximum principle) and the \(\ell _2\) norm (Fourier analysis).

Heat Equation Derive the Crank-Nicolson scheme for the following problem \[ u_t=u_{xx},\qquad t>0,\qquad 0<x<1, \] with the boundary conditions \[ u(0,t)=u(1,t)=0,\qquad t\ge 0, \] and the initial data \[ u(x,0)=u_0(x),\qquad 0\le x\le 1, \] for some given function \(u_0\). Use the usual discretization with uniform mesh points \(x_j=jh\) where \(h=1/N\) and \(j=0,1,2,\ldots ,N\). Show that the method is second order by deriving the truncation error. What other conditions do we need to guarantee the convergence of the numerical solution? Derive the stability condition in \(\ell _2\) norm by using Fourier analysis. For any value of \(\nu =\Delta t/(\Delta x)^2\), do we always have the maximum principle satisfied? If we have some initial data such that \(0\le u_0(x)\le 1\), derive the condition that should be imposed on \(\nu \) so that \(0\le u_j^n\le 1\) also holds for all \(j\) and \(n>0\).

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.

Numerical ODEs Define the terms linear multistep method (LMM), order, consistency, zero-stability, local truncation error, and region of absolute stability of an LMM. Derive the highest order implicit 2 step method and discuss its region of absolute stability.

Numerical PDEs Consider the PDE \[ u_t+u_x=0 \tag {5} \] and the usual discretization \[ U_m^n\approx u(x_m,t_n) \qquad \text {where}\qquad x_m=mh\quad \text {and}\quad t_n=nk. \tag {6} \] The Leap Frog Method is given by \[ U_m^{n+1}=U_m^{n-1}-\frac {k}{h}\left (U_{m+1}^n-U_{m-1}^n\right ). \tag {7} \] Compute the local truncation error and discuss the stability of this method.

Local Truncation Error. What is the local truncation error of a numerical scheme? What does consistency mean? Give a specific and precise example.

Newton Type Methods Suppose \(f(x)\) is a real-valued function defined for all values of the real variable \(x\), and that \(f'\) is Lipschitz continuous. Consider the discrete Newton method: Guess \(x_0\) and for \(k=0,1,2,\ldots \), do: \[ a_k=\frac {f(x_k+h_k)-f(x_k)}{h_k} \] \[ x_{k+1}=x_k-\frac {f(x_k)}{a_k} \] Analyze the local convergence properties of this method. How does the speed of convergence depend on the choice of \(h_k\) (ignore any effect of round-off errors in this analysis)? Now taking roundoff into account what would be a reasonable size for \(h_k\) in practice?

a) Derive a multistep method to approximate \(y'=f(t,y)\) of the form \[ y_{n+1}=y_n+h(b_{-1}y'_{n+1}+b_0y'_n+b_1y'_{n-1}) \] with \(y'_j=f(t_j,y_j)\), \(t_j=t_0+jh\) by interpolating \(f(s,y(s))\) at \(t_{n-1}\), \(t_n\), \(t_{n+1}\).

b) Analyze the local truncation error of this method and the consequences regarding convergence. What would be an appropriate predictor for this method?

c) Discuss the region of absolute stability of this method, and the predictor-corrector method described in part b).