Preliminary Exam, Numerical Analysis, August 2008

QR factorization Show how to compute the QR factorization of a real \(m\times n\) matrix \(A\) (with \(m\geq n\)) using Householder reflections, and describe how to use the QR factorization to solve the Least Squares problem \[ \|Ax-b\|_2=\min . \tag {1} \]

Gaussian Quadrature Let \(w\) be a positive weight function. Explain how to pick the knots \(x_i\) and the weights \(w_i\), \(i=1,\ldots ,n\) such that the integration formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=1}^n w_i f(x_i) \tag {2} \] is exact for polynomials \(f\) of degree as high as possible, and show why this works. How high a polynomial degree is possible?

Interpolation error Let \(I=[a,b]\) and \(f\in C^\infty [a,b]\). Let \(x_i\), \(i=0,\ldots ,n\) be \(n+1\) distinct points in \(I\). Let \(p(x)\) be the unique polynomial of degree at most \(n\) satisfying \(p(x_i)=f(x_i)\), \(i=0,\ldots ,n\). Given \(x\) in \([a,b]\), show that there exists some point \(\xi \in [a,b]\) such that \[ f(x)-p(x) = \frac {\prod _{i=0}^n(x-x_i)}{(n+1)!}\,f^{(n+1)}(\xi ). \tag {3} \]

Singular Value Decomposition Let \(A\) be an \(m\times n\) matrix. You may assume that \(m\geq n\). Define what is meant by the singular value decomposition of \(A\) and show that every \(m\times n\) matrix has one.

Absolute Stability Consider solving the initial value problem \[ y'=f(x,y),\qquad y(a)=y_0 \tag {4} \] by the linear multistep method (LMM) \[ \sum _{j=0}^k \alpha _j y_{n+j} = h\sum _{j=0}^k \beta _j f_{n+j}. \tag {5} \]

where we use the standard notation \[ x_n=a+nh,\qquad y_n\approx y(x_n),\qquad f_n=f(x_n,y_n). \tag {6} \] Define what it means that the LMM is explicit. Define its region of absolute stability. Show that an explicit linear multistep method cannot have an infinite region of absolute stability.

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.