Numerical Analysis Qualifying Exam, Winter 2015

Interpolation Suppose \(f\) is arbitrarily often differentiable and let \(p\) be the unique polynomial of degree \(d\) satisfying \[ p(x_i)=f(x_i),\qquad i=0,\ldots ,n \] where the abscissas \(x_i\) are distinct. Derive a suitable expression for the error \(f(x)-p(x)\) and discuss its properties.

Positive Definite Matrices The Cholesky decomposition of a (symmetric and) positive definite matrix is defined to be a factorization of the form \(A=LL^T\) where \(L\) is lower triangular. Show that the Cholesky decomposition exists. Discuss whether or not it is unique.

Iterative Methods for Linear Systems Consider the square linear system \(Ax=b\) and the Gauss-Jacobi Method \[ x_i^{[k+1]}= \frac {1}{a_{ii}}\left ( b_i-\sum _{j=1}^{i-1}a_{ij}x_j^{[k]} -\sum _{j=i+1}^{n}a_{ij}x_j^{[k]} \right ) \] where \(i=1,\ldots ,n\) and \(k=0,1,\ldots \). Show that this method converges for all starting vectors \(x^{[0]}\) if \(A\) is diagonally dominant, i.e., \[ \sum _{j=1}^{k}\lvert a_{ij}\rvert + \sum _{j=k+1}^{n}\lvert a_{ij}\rvert < \lvert a_{ii}\rvert \qquad \text {for all } i=1,2,\ldots ,n. \]

Padé Approximants Define what is meant by the Padé approximant of a function \(f\) and compute the \([1/1]\) Padé approximant of the exponential.

Multigrid Describe the basic ideas and ingredients of the multigrid technique for the solution of elliptic PDEs.

ODEs Consider the initial value problem for a system of ODEs \(y'=Ay\) where \(A\) has eigenvalues that are widely spread in the left half plane. Which of the following schemes would be the best choice for solving this problem? Justify your answer in terms of stability, accuracy, and efficiency. \[ \begin {aligned} (1)\quad y^{n+1} &= y^n+kAy^n,\\ (2)\quad y^{n+1} &= y^n+kAy^{n+1},\\ (3)\quad y^{n+1} &= y^n+\frac {k}{2}A\left (y^n+y^{n+1}\right ). \end {aligned} \]

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.

Heat Equation Consider the following heat equation problem \[ u_t=u_{xx},\qquad t>0,\qquad 0<x<1, \] \[ u(0,t)=u(1,t)=0,\qquad t>0, \] \[ u(x,0)=u_0(x),\qquad 0\le x\le 1. \] Using the forward or backward difference for the time derivative and central difference for the space derivative, derive the explicit and implicit schemes. What’s the stability condition for each case? Perform a Fourier analysis on both the explicit and implicit methods and use the von Neumann condition to verify these stability conditions.