Numerical Analysis Qualifying Exam, Fall 2014

Let \(A\) be an \(m\times n\) matrix where you may assume that \(m\geq n\). Define what is meant by the Singular Value Decomposition of \(A\). Then use it to show that if the rank of \(A\) is \(p\) then there exists an \(m\times p\) matrix \(X\) and an \(n\times p\) matrix \(Y\) such that \[ A=XY^T. \]

Consider the quadrature rule \[ \int _a^b w(x)f(x)dx = \sum _{j=1}^n w_jf(x_j)+E_n. \] Assume that \(w\) is a positive weight function. Discuss how to pick the knots \(x_1,\ldots ,x_n\) and weights \(w_1,\ldots ,w_n\) to make the error \(E_n\) zero for all polynomials \(f\) up to a degree as high as possible.

Consider the (square) linear system \(Ax=b\). Suppose you have obtained a numerical approximation \(\hat {x}\). Define the error and residual, respectively, by \[ e=x-\hat {x}\qquad \text {and}\qquad r=b-A\hat {x}. \] Let \(\|\cdot \|\) denote a vector norm, and the induced matrix norm. Show that \[ \frac {1}{\|A\|\|A^{-1}\|}\frac {\|r\|}{\|b\|} \leq \frac {\|e\|}{\|x\|} \leq \|A\|\|A^{-1}\|\frac {\|r\|}{\|b\|} \] and discuss the significance of these inequalities.

Suppose \(A\) is an \(m\times n\) real matrix with \(m>n\), and \(b\in \mathbb {R}^m\). For any vector \(v\in \mathbb {R}^m\), let \[ \|v\|_2=\sqrt {\sum _{i=1}^m v_i^2} \] as usual. Describe how to solve the Least Squares Problem \[ \|Ax-b\|_2=\min \] using the \(QR\) factorization of \(A\). Briefly state how you would compute the \(QR\) factorization.

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 variational principle: \[ I(u)=\int _0^1 \left (u'(x)\right )^2+k^2\left (u(x)\right )^2 dx=\min \qquad \text {subject to}\qquad u(0)=u(1)=1. \] Suppose you want to use the Ritz Method to approximate the solution of this problem by a polynomial of degree \(n\). Derive a linear system for the coefficients of that polynomial.

Define what is meant by a linear multistep method and its region of absolute stability. Show that a convergent explicit linear multistep method cannot have an infinite region of absolute stability.

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.