Finite Difference Boundary Value Problems

(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.

Consider the boundary value problem \[ u''(x) = f(x),\quad \text {for }0 < x < 1, \] \[ u(0) = 0,\quad u(1) = 0, \]

where \(f\) is a smooth function on \([0, 1]\), and the finite difference scheme \[ \frac {U_{j-1}-2U_j+U_{j+1}}{h^2} = f(x_j), \qquad j = 1,2,\ldots ,m, \] for finding approximations \(U_j\) to \(u(x_j)\). Here, \(x_j = jh\) and \((m+1)h = 1\).

Analyze the accuracy, stability, and convergence properties of the scheme.

1. Consider the initial value problem for the constant-coefficient diffusion equation (with \(\beta > 0\)) \[ v_t = \beta v_{xx},\quad t > 0 \]

   with initial data \(v(x,0) = f(x)\). A scheme for this problem is: \[ \frac {u_j^{n+1}-u_j^n}{k} = \frac {\beta }{h^2}\left \{u_{j-1}^{n+1}-2u_j^{n+1}+u_{j+1}^{n+1}\right \}. \]

   Analyze the 2-norm stability of this scheme. For which values of \(k > 0\) and \(h > 0\) is the scheme stable? (Note that there are no boundary conditions here.)

2. Consider the variable coefficient diffusion equation \[ v_t = (\beta (x)v_x)_x,\quad 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) \ge \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. DO NOT NEGLECT THE FACT THAT THERE ARE BOUNDARY CONDITIONS!

Finite difference formulas

Given \(h>0\), compute weights \(v_0\) and \(\{w_j\}_{j=-1}^{1}\) for the following finite difference formula for the third derivative \(f^{(3)}(x)\): \[ f^{(3)}(x)\approx v_0f'(x)+\sum _{j=-1}^{1}w_j f(x+jh) \] \[ =v_0f'(x)+w_{-1}f(x-h)+w_0f(x)+w_1f(x+h). \] What is the order of accuracy of your formula?

Higher Order Methods

Consider the following problem for \(v(x)\) on \([0,1]\): \[ v''(x)=f(x), \tag {2} \] with \(v(0)=v(1)=0\). Let \(N\cdot h=1\) and define \(x_j=j\cdot h\) for \(j=0,1,\ldots ,N\). The finite-difference scheme \[ \Delta _h U_j^h\equiv \frac {1}{h^2}\left (U_{j-1}^h-2U_j^h+U_{j+1}^h\right ) = f_j^h, \] for \(j=1,\ldots ,N-1\) with \(U_0^h=U_N^h=0\) gives values \(U_j^h\) that approximate \(v(x_j)\) with an error of \(O(h^2)\). Here the superscript \(h\) is used to indicate the grid size for the solution. Show how to use this method to find a numerical solution \(W_j\) whose values approximate \(v(x_j)\) with an error of \(O(h^4)\) and a numerical solution \(Y_j\) whose values approximate \(v(x_j)\) with an error of \(O(h^6)\).

Solve Laplace’s equation \(\phi _{xx}+\phi _{yy}=0\) in the domain \[ D=\{(x,y)\in \mathbb {R}^2:x^2+y^2>1,\ (x+2)^2+y^2<9\} \] with boundary conditions: \(\phi (x,y)=a\) when \(x^2+y^2=1\) and \(\phi (x,y)=b\) when \((x+2)^2+y^2=9\).

Finite difference formulas

Given \(h>0\), compute weights \(w_j\) for the following 5-point finite difference formula for the third derivative \(f^{(3)}(x)\): \[ f^{(3)}(x)\approx \sum _{j=-2}^{2}w_j f(x+jh) \] \[ = w_{-2}f(x-2h)+w_{-1}f(x-h)+w_0f(x)+w_1f(x+h)+w_2f(x+2h). \] What is the order of accuracy of your formula?

Find the real-valued function \(\Phi (z)\) that solves Laplace’s equation in the region between the two noncentric circles \(\lvert z\rvert =1\) and \(\lvert z-1\rvert =\frac {5}{2}\) subject to the boundary conditions \(\Phi =0\) on \(\lvert z\rvert =1\) and \(\Phi =1\) on \(\lvert z-1\rvert =\frac {5}{2}\).

Solve Laplace’s equation \[ u_{xx}+u_{yy}=0 \quad \text {in the domain}\quad D=\{(x,y)\in \mathbb {R}^2:\ (x-1)^2+y^2>1\ \& \ (x-2)^2+y^2<4\} \] subject to the boundary condition \[ u(x,y)=a\text { when }(x-1)^2+y^2=1 \qquad \text {and}\qquad u(x,y)=b\text { when }(x-2)^2+y^2=4 \] [\(a\) and \(b\) are real parameters; the two circles touch each other; express your answer in terms of the original real variables \(x,y\)].

Solve Laplace’s equation \[ \phi _{xx}+\phi _{yy}=0 \quad \text {in the domain}\quad D=\{z:\lvert z-1\rvert >1,\ \lvert z-2\rvert <2\} \] subject to the boundary condition \[ \phi (x,y)=a\text { when }\lvert z-1\rvert =1 \qquad \text {and}\qquad \phi (x,y)=b\text { when }\lvert z-2\rvert =2 \] (\(a\) and \(b\) are real parameters).

Solve Laplace’s equation \[ \phi _{xx}+\phi _{yy}=0 \quad \text {in the domain}\quad D=\{(x,y)\in \mathbb {R}^2:\ x^2+y^2>1,\ x^2+(y+1)^2<4\} \] subject to the boundary condition \[ \phi (x,y)=a\text { when }x^2+y^2=1 \qquad \text {and}\qquad \phi (x,y)=b\text { when }x^2+(y+1)^2=4 \] (\(a\) and \(b\) are real parameters; the two circles touch each other; express your answer in terms of the original real variables \(x\) ans \(y\)).

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.

Explain how to combine the Shooting method and Newton’s Method to solve the boundary value problem \[ y''=f(x,y,y'),\qquad a\leq x\leq b,\qquad y(a)=A,\qquad y(b)=B \] where \(y=y(x)\) and \(y\) and \(f\) are scalar valued.

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.

Consider the problem \(u''(x)=f(x)\), on \((0,1)\), with boundary conditions \(u'(0)=u'(1)=0\).

1. Write down the weak formulation of the problem.
2. Using a piecewise linear finite element basis with uniform grid size \(h\), use the Galerkin method to find a finite-dimensional (matrix) approximate representation for the problem. Do not solve the equations.
3. Neither of the problems (a) and (b) have unique solutions in general. Explain why not, and describe what can be done to correct the deficiency.

Convergence of Linear Multistep Method

Consider the method \[ y_{n+2}-2y_{n+1}+y_n = \frac {h}{2}\left (f(t_{n+2},y_{n+2})-f(t_n,y_n)\right ) \] Apply the method to the scalar IVP \(y'=y\), \(y(0)=1\) and solve exactly the resulting difference equation, considering the starting values to be \(y_0=y_1=1\). Show theoretically that the numerical solution does not converge as \(h\to 0\) and \(n\to \infty \).

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.

This problem examines features of the differential operator \[ Lu=u'' \] subject to boundary conditions \(u(-1)+u(1)=0\) and \(u'(-1)=u'(1)\).

1. What is the adjoint of this operator? Is it self-adjoint?
2. What is the nullspace of the operator and what is the nullspace of the adjoint operator?
3. Under what conditions on \(f\), \(a\), and \(b\) does the boundary value problem \[ u''=f,\qquad u(-1)+u(1)=a,\qquad u'(-1)-u'(1)=b \] have a solution?
4. Find the smallest least squares solution for the boundary value problem \[ u''=1,\qquad u(-1)+u(1)=1,\qquad u'(-1)-u'(1)=1. \] What equation does this least squares solution satisfy?

Use antiderivatives to evaluate the contour integral \[ I=\int _C\frac {1}{z+i} \] where \(C\) is a contour (possibly with loops) starting at \(z=0\) and ending at \(z=1\). Express your answer in the form \(I=a+ib\) where \(a\) and \(b\) are real. The answer is multivalued. Explain the interpretation of the different values, and account for the difference between successive values using the residue theorem.

Iterative Methods for Linear Systems

Consider the boundary value problem \[ -u''(x)+\beta u(x)=f(x),\qquad \text {for } 0\leq x\leq 1 \] where \(\beta >0\), and with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+(2+\beta h^2)U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots ,N-1\) where \(Nh=1\), \(F_j\equiv h^2f(jh)\), and \(U_0=U_N=0\).

Analyze the convergence properties of the Jacobi iterative method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). How does the number of iterations required to reduce the initial error by a factor \(\delta \) depend on \(h\)? In practice, would you use this method to solve the given problem? If so, explain why this is a good idea? If not, how would you solve it in practice?

Iterative Methods for Linear Systems

Consider the boundary value problem \[ -u''(x)+\beta u(x)=f(x),\qquad \text {for } 0\leq x\leq 1 \] where \(\beta >0\), and with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+(2+\beta h^2)U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots ,N-1\) where \(Nh=1\), \(F_j\equiv h^2f(jh)\), and \(U_0=U_N=0\).

Analyze the convergence properties of the Jacobi iterative method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). How does the number of iterations required to reduce the initial error by a factor \(\delta \) depend on \(h\)? In practice, would you use this method to solve the given problem? If so, explain why this is a good idea? If not, how would you solve it in practice?

1. Let \[ A= \begin {pmatrix} 3 & 1\\ 1 & 3 \end {pmatrix}. \] Find the maximum value of the quadratic form \(\langle Ax,x\rangle \) for \(\lVert x\rVert \le 1\).
2. Prove that eigenvectors corresponding to distinct eigenvalues of a self-adjoint matrix are orthogonal.
3. Let \(H=-\frac {d^2}{dx^2}\) on \(L^2[0,1]\) with boundary conditions \(\psi (0)=\psi (1)=0\). Find the eigenvalues and eigenvectors of \(H\). Show that the eigenvectors of \(H\) corresponding to distinct eigenvalues are orthogonal.

For the differential operator \(Lu=u''+(x^2-1)u'\) on the interval \([0,1]\) with boundary conditions \(u(0)=u'(1)\) and \(u(1)=u'(0)\) find the adjoint operator and its domain.

Convergence Consider the one-dimensional heat equation initial boundary value problem \[ u_t=u_{xx},\quad x\in [0,1],\quad t\geq 0,\quad u(x,0)=f(x),\quad u(0,t)=u(1,t)=0 \tag {7} \] and the discretization \[ x_m=mh,\qquad t_n=nk,\qquad \text {and}\qquad U_m^n\approx u(x_m,t_n) \tag {8} \] where \[ U_m^{n+1}=U_m^n+r\left (U_{m-1}^n-2U_m^n+U_{m+1}^n\right ) \tag {9} \] and \(r=k/h^2\) is the grid constant. Define what it means that this method is convergent, say for what values of \(r\) it is convergent, and show that your statement is correct.

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.

1. What is the weak formulation for the boundary value problem \(u''=f(x)\) subject to boundary conditions \(u(0)=u(1)=0\)?
2. Let \(\phi (x)=N_2(x+1)\) where \(N_2(x)\) is the piecewise linear function \[ N_2(x)= \begin {cases} x, & 0<x<1,\\ 2-x, & 1\le x<2,\\ 0, & \text {elsewhere}. \end {cases} \] Divide the unit interval \([0,1]\) into \(N\) uniform subintervals with endpoints at \(x_k=\frac {k}{N}\), \(k=0,\ldots ,N\). Use \(\phi (x)\) to define a finite element basis for continuous piecewise linear functions on the unit interval which interpolates function values at \(x_k\). Suppose \(u_k=u(x_k)\) is known. Express \(u(x)\) in terms of \(\phi (x)\).
3. Use the Galerkin method to find equations for \(u_k=u(x_k)\) that approximately solve the boundary value problem in part (a), using the piecewise linear finite element basis.

Numerical ODEs

a) The difference equation \[ y_{n+k}+a_1y_{n+k-1}+\cdots +a_ky_n=0 \] can, after the substitution \(\mathbf {y}_j=(y_j,y_{j+1},\ldots ,y_{j+k-1})^T\), be written in the form \(\mathbf {y}_{n+1}=A\mathbf {y}_n\). What does the matrix \(A\) look like? Describe the condition for \(y\) to remain bounded in terms of \(A\).

b) The differential equation \[ y^{(k)}+a_1y^{(k-1)}+\cdots +a_ky=0 \] can, after the substitution \(\mathbf {y}=(y,y',\ldots ,y^{(k-1)})^T\), be written in the form \(\mathbf {y}'=A\mathbf {y}\). What does the matrix \(A\) look like? Describe the condition for \(y\) to remain bounded in terms of \(A\).

c) Show that all solutions of the difference equation \[ y_{n+1}-2\lambda y_n+y_{n-1}=0 \] are bounded, as \(n\to \infty \), if \(\lambda \) is real and \(\lvert \lambda \rvert <1\).

Wave Equations Consider the standard wave equation in one space dimension: \[ u_{tt}=c^2u_{xx},\qquad 0<x<1,\quad t>0, \] with initial conditions \[ u(x,0)=f(x),\qquad u_t(x,0)=g(x),\qquad 0<x<1 \] for given smooth functions \(f\) and \(g\), and boundary condition \[ u(0,t)=u(1,t)=0,\qquad t>0. \] The leap-frog scheme takes advantage of the fact that the equation can be reformulated as a system of first order equations \[ u_t+cv_x=0, \qquad v_t+cu_x=0. \] Denote \(x_j=j\Delta x\), \(U_j^n\approx u(x_j,n\Delta t)\), and \(V_{j+1/2}^{n+1/2}\approx v(x_{j+1/2},(n+\frac {1}{2})\Delta t)\); use central difference approximations for both derivatives to derive the leap-frog scheme for the system of equations. How do you implement the initial and boundary conditions for both \(u\) and \(v\)? Derive the truncation error for this approximation and determine the order of truncation error. For stability, consider solutions in the form \[ \begin {bmatrix} U^n\\ V^{n+1/2} \end {bmatrix} = \lambda ^n e^{ikx} \begin {bmatrix} \widetilde {U}\\ \widetilde {V} \end {bmatrix}, \] for some constants \(\widetilde {U}\) and \(\widetilde {V}\). Substitute this solution into the finite difference equations, find out what condition \(\lambda \) has to satisfy in order for \(\widetilde {U}\) and \(\widetilde {V}\) to have nontrivial solutions. For those \(\lambda \) values, compute \(\lvert \lambda \rvert \) to see if the stability condition \(\lvert \lambda \rvert \le 1\) is satisfied.

Consider a linear chain of \(2N\) atoms with the same spacing \(a\) and force constant \(\beta \) but of two different masses \(m,M\), \(M>m\), placed alternately. Label the light atoms by even integers \(2n\), \(n=0,\ldots ,N-1\) and the heavy atoms by odd integers \(2n-1\), \(n=1,\ldots ,N\). Denoting their displacements from equilibrium by the variables \(U_{2n}\) and \(V_{2n-1}\), Newton’s law of motion gives \[ \begin {aligned} m\ddot {U}_{2n} &= \beta [V_{2n-1}+V_{2n+1}-2U_{2n}],\\ M\ddot {V}_{2n-1} &= \beta [U_{2n}+U_{2n-2}-2V_{2n-1}]. \end {aligned} \] Determine the modes of vibration of the system and sketch the resulting pair of dispersion curves. [Assume periodic boundary conditions \(U_0=U_{2N}\) and \(V_1=V_{2N+1}\).]

The “best” least squares solution of the boundary value problem \(u''+u=0\), \(u(0)=\alpha \), \(u(\pi )=0\) is the unique exact solution of what problem?

Consider a linear chain of \(2N\) atoms with the same spacing \(a\) and force constant \(\beta \) but of two different masses \(m,M\), \(M>m\), placed alternately. Label the light atoms by even integers \(2n\), \(n=0,\ldots ,N-1\) and the heavy atoms by odd integers \(2n-1\), \(n=1,\ldots ,N\). Denoting their displacements from equilibrium by the variables \(U_{2n}\) and \(V_{2n-1}\), Newton’s law of motion gives \[ \begin {aligned} m\ddot {U}_{2n} &= \beta [V_{2n-1}+V_{2n+1}-2U_{2n}],\\ M\ddot {V}_{2n-1} &= \beta [U_{2n}+U_{2n-2}-2V_{2n-1}]. \end {aligned} \] Determine the modes of vibration of the system and sketch the resulting pair of dispersion curves. [Assume periodic boundary conditions \(U_0=U_{2N}\) and \(V_1=V_{2N+1}\).]

1. What is the weak formulation for the boundary value problem \(u''=f(x)\) subject to boundary conditions \(u(0)=u(1)=0\)?
2. Let \(\phi (x)=N_2(x+1)\) where \(N_2(x)\) is the piecewise linear function given in Problem A.2. Divide the unit interval \([0,1]\) interval \(N\) uniform subintervals with endpoints at \(x_k=\frac {k}{N}\), \(k=0,\ldots ,N\). Use \(\phi (x)\) to define a finite element basis for continuous piecewise linear functions on the unit interval which interpolates function values at \(x_k\). Suppose \(u_k=u(x_k)\) is known. Express \(u(x)\) in terms of \(\phi (x)\).
3. Use the Galerkin method to find equations for \(u_k=u(x_k)\) that approximately solve the boundary value problem in part (a), using the piecewise linear finite element basis.

Under what conditions does a solution of the boundary value problem \(u''+u=f(x)\) with \(u(0)=\alpha \), \(u'(\pi /2)=\beta \) exist?

Finite-Difference Methods Consider the initial boundary value problem \[ v_t=\beta v_{xx},\qquad 0<x<1,\qquad 0<t,\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 from 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 \(l_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\). What other issues should be considered in deciding whether the suggested scheme is a good choice for the problem?

The so called “Brachistochrone problem” admits such formulation. “A particle is sliding along a trough (in a vertical plane from the point \((0,0)\) to some given point \((x_1,y_1)\) \((x_1>0,\ y_1<0)\) under the effect of gravity without friction (having zero initial velocity). Find the form \(y=Y(x)\) of the trough which minimizes the time of descent of this particle.”

1. Find the functional that ought to be minimized.
2. Using this functional, write the boundary value problem that ought to be solved for finding the solution of the “Brachistochrone problem”. You do not need to solve this boundary value problem.

Derive the boundary value problem for a minimizer \(w_0\) of the functional \[ \min _{\substack {w\in C^2[0,1]\\ w(0)=0}} \frac {\int _0^1\left (\phi (x)(w'')^2+w^2\right )\,dx} {\int _0^1\phi (x)(w')^2\,dx+\beta w(1)^2} \] where \(\phi (x)>0\), \(\forall x\in [0,1]\), \(\beta \) is a real parameter.

Finite-Difference Methods Consider the spatially-periodic initial value problem for \(v(x,t)\): \[ v_t=cv_x,\qquad \text {for }0\le x\le 1 \] with \[ v(x,0)=f(x),\qquad \text {for }0\le x\le 1. \] Here the function \(f\) has period 1, and \(c\) is a positive constant. Note that the exact solution of the problem is \(v(x,t)=f(x+ct)\).

Consider the following difference approximations to the PDE: \[ \begin {aligned} \text {i)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{h}(u_{j+1}^n-u_j^n),\\ \text {ii)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{h}(u_j^n-u_{j-1}^n),\\ \text {iii)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{2h}(u_{j+1}^n-u_{j-1}^n). \end {aligned} \] In each case, \(Nh=1\), and the difference scheme is supplemented with the discrete initial conditions \(u_j^0=f(jh)\) for \(j=0,1,\ldots ,N\) and boundary conditions \(u_N^n=u_0^n\), \(u_{-1}^n=u_{N-1}^n\), and \(u_{N+1}^n=u_1^n\) for all time levels \(n\ge 0\). For each scheme, tell whether it is a reasonable scheme to use on the above problem, and justify your answers.

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.

Consider the boundary value problem \(u''=f(x)\), \(u'(0)=0\), \(u(1)=0\) where \(f(x)\) is a prescribed function.

1. Show that the problem has at most one solution.
2. Show that the solution can be written as \[ u(x)=\int _0^1 k(x,y)f(y)\,dy \] for all continuous functions \(f(x)\) where \[ k(x,y)= \begin {cases} x-1, & \text {for }0\le y\le x\le 1,\\ y-1, & \text {for }0\le x\le y\le 1. \end {cases} \]