Exam
Preliminary Exam, Numerical Analysis, August 2018
Fall 2018 · 8 questions in this exam.
Questions in This Exam
Ordered by the question sequence in the original exam.
-
Question 1
**Singular values and eigenvalues** Let \(A\in\mathbb{C}^{N\times N}\). Prove the following statements: **(a)** The set of squared singular values of \(A\) equals the set of eigenvalues of \(A^*A\). **(b)** Assume that \(A\) is diagonalizable and that every eigenvalue \(\lambda\) of \(A\) satisfies \(|\lambda|<1\). Then: \[ \lim_{n\to\infty}\|A^n\|=0. \]
-
Question 2
**Unitary matrices** Let \(A,B\in\mathbb{C}^{N\times N}\). \(A\) and \(B\) are unitarily equivalent if there is a unitary matrix \(Q\) such that \(A=QBQ^*\). For each of the following statements, prove that it is true, or demonstrate that it is false: **(a)** If \(A\) and \(B\) are unitarily equivalent, then they have the same singular values. **(b)** If \(A\) and \(B\) have the same singular values, then they are unitarily equivalent.
-
Question 3
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?
-
Question 4
Lebesgue’s Lemma
Let \(I\) be a closed, bounded interval on the real line and let \(\|f\|_\infty :=\sup _{x\in I}|f(x)|\). Given \(N\) distinct points \(x_1,\ldots ,x_N\in I\) and a continuous function \(f\), consider the Lagrange form of the degree-\((N-1)\) polynomial interpolant of \(f\): \[ I_N f := \sum _{j=1}^{N}f(x_j)\ell _j(x), \]
where \(\{\ell _j(\cdot )\}_{j=1}^{N}\) are cardinal Lagrange polynomials. Show that \[ \sup _{\|g\|_\infty =1}\|I_N g\|_\infty \le \Lambda := \sum _{j=1}^{N}|\ell _j(x)|, \] and that \[ \|f-I_N f\|_\infty \le (1+\Lambda )\inf _{p\in P_{N-1}}\|f-p\|_\infty , \] where \(P_{N-1}=\operatorname {span}\{1,x,\ldots ,x^{N-1}\}\).
Note: In problems 5–8, the notations \(k=\Delta t\) and \(h=\Delta x\) are used.
-
Question 5
**Elliptic Problems** Consider the one dimensional problem for \(v(x)\) \[ v''(x)=f(x), \tag{1} \] in the interval \([0,1]\) along with homogeneous Dirichlet boundary conditions. Define the difference operator \[ \Delta_h U_j\equiv\frac{1}{h^2}(U_{j-1}-2U_j+U_{j+1}), \] and consider the scheme for Eq. 1 \[ \Delta_h U_j=f_j \] for \(j=1,2,\ldots,N-1\) where \(Nh=1\), \(f_j\equiv f(jh)\), and \(U_0=U_N=0\). The approximate solution satisfies a linear system \(AU=b\), where \(U=(U_1,U_2,\ldots,U_{N-1})^T\) and \(b=h^2(f_1,f_2,\ldots,f_{N-1})^T\). **(a)** State and prove the maximum principle for any grid function \(V=\{V_j\}\) with values for \(j=0,1,\ldots,N\), that satisfies \(\Delta_h V_j\ge0\) for \(j=1,2,\ldots,N-1\). Sketch a grid function for which \(\Delta_h V_j\ge0\). **(b)** Derive an expression for the local truncation error and find the equation that relates the local trunction error and the global error \(e_j=v(x_j)-U_j\). **(c)** Use the maximum principle from part (a) to show that \(\|e\|_\infty=O(h^2)\) as the space step \(h\to0\). **(d)** Prove that the matrix \(A\) is nonsingular.
-
Question 6
Heat Equation Stability
Consider the variable coefficient diffusion equation \[ v_t=(\beta (x)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)\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 THE PROBLEM HAS VARIABLE COEFFICIENTS AND THAT THERE ARE BOUNDARY CONDITIONS AT 0 AND 1!
-
Question 7
**Numerical Methods for ODE Initial Value Problems** Consider the Linear Multistep Method \[ y_{n+2}-\frac{4}{3}y_{n+1}+\frac{1}{3}y_n=\frac{2}{3}k f_{n+2} \] for solving an initial value problem \(y'=f(y,x)\), \(y(0)=\eta\). You may assume that \(f\) is Lipschitz continuous with respect to \(y\) uniformly for all \(x\). **(a)** Analyze the consistency, stability, accuracy, and convergence properties of this method. **(b)** Sketch a graph of the solution to the following initial value problem. \[ y'=-10^8[y-\cos(x)]-\sin(x),\qquad y(0)=2. \] Would it be more reasonable to use this method or the forward Euler method for this problem? What issues should be considered in choosing a timestep \(k\) for each of the methods? Justify your answer.
-
Question 8
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)\).