Preliminary Exam, Numerical Analysis, August 2010

The Companion Matrix Show that \[ \begin {aligned} &\det \left ( \begin {bmatrix} \alpha _{n-1} & \alpha _{n-2} & \cdots & \alpha _1 & \alpha _0\\ 1 & 0 & \cdots & 0 & 0\\ 0 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end {bmatrix} - \lambda I \right ) \\ &\qquad = (-1)^n\left [\lambda ^n-\sum _{j=0}^{n-1}\alpha _j\lambda ^j\right ]. \end {aligned} \tag {1} \] Describe how this fact can be used to find the roots of a polynomial. Also briefly describe why the reverse process, finding the eigenvalues of a matrix by computing the characteristic polynomial, and finding its roots, is not generally viable.

Sherman-Morrison-Woodbury Formula Suppose \(A\) is an invertible \(n\times n\) matrix, and \(U\) and \(V\) are \(n\times k\) matrices such that \(A+UV^T\) and the \(k\times k\) matrix \(I+V^TA^{-1}U\) are invertible. Show that \[ (A+UV^T)^{-1} = A^{-1}-A^{-1}U(I+V^TA^{-1}U)^{-1}V^TA^{-1} \tag {2} \] Explain why this means that a rank \(k\) change of \(A\) leads to a rank \(k\) change of \(A^{-1}\).

SVD Let \(A\) be an \(m\times n\) matrix. Define what we mean by the singular value decomposition of \(A\). Show that the singular value decomposition exists.

The interpolant to symmetric data is symmetric Suppose you are given symmetric data \[ (x_i,y_i),\qquad i=-n,-n+1,\cdots ,n-1,n, \tag {3} \] such that \[ x_{-i}=-x_i,\qquad \text {and}\qquad y_{-i}=y_i\qquad i=0,1,\cdots ,n. \tag {4} \] What is the required degree of the interpolating polynomial \(p\)? Show that the interpolating polynomial is even, i.e., \[ p(x)=p(-x) \tag {5} \] for all real numbers \(x\).

Explicit Methods Define what we mean by Linear Multistep Method and what we mean by its region of absolute stability. Show that a convergent explicit linear multistep method cannot have an unbounded region of absolute stability.

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.

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.