Exam
Preliminary Examination, Numerical Analysis, August 2013
Fall 2013 · 6 questions in this exam.
Questions in This Exam
Ordered by the question sequence in the original exam.
-
Question 1
**Application of Matrix Factorizations** **a)** Show that for any real \(n\times n\) matrix \(A\) and any \(\epsilon>0\), there is a nonsingular matrix \(B\) for which \(\|A-B\|_2<\epsilon\). **b)** Show that for any real \(n\times n\) matrix \(A\) and any \(\epsilon>0\), there is a diagonalizable matrix \(B\) for which \(\|A-B\|_2<\epsilon\).
-
Question 2
**Least Squares Problems** **a)** For a real full rank \(m\times n\) matrix \(A\) and vector \(\mathbf{b}\in\mathbb{R}^m\), explain how to solve the least-squares problem of finding \(\mathbf{x}\in\mathbb{R}^n\) that minimizes \(\|A\mathbf{x}-\mathbf{b}\|_2\) using i) the normal equations, and b) a QR factorization of the matrix \(A\). What are the advantages and disadvantages of each of these methods? **b)** For a full rank real \(m\times n\) matrix \(A\), show that \(X=A^\dagger\), the pseudoinverse of \(A\), minimizes \(\|AX-I\|_F\) over all \(n\times m\) matrices \(X\). What is the value of the minimum? (Hint: Relate the problem to a set of least-squares problems).
-
Question 3
**Interpolation:** Consider equally spaced points \(x_j=a+jh\), \(j=0,\ldots,n\) on the interval \([a,b]\), where \(nh=b-a\). Let \(f(x)\) be a smooth function defined on \([a,b]\). **a)** Show that there is a unique polynomial \(p(x)\) of degree \(n\) which interpolates \(f\) at all of the points \(x_j\). **b)** Derive the formula for the interpolation error at an arbitrary point \(x\) in the interval \([a,b]\): \[ f(x)-p(x)\equiv E(x) = \frac{1}{(n+1)!}(x-x_0)(x-x_1)\cdots(x-x_n)f^{n+1}(\eta). \] for some \(\eta\in[a,b]\).
-
Question 4
**Iterative Methods for Linear Systems** Consider the boundary value problem \[ -u''(x)+\beta u(x)=f(x),\qquad \text{for }0\leq x\leq1 \] where \(\beta>0\), and with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+(2+\beta h^2)\,U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots,N-1\) where \(Nh=1\), \(F_j\equiv h^2f(jh)\), and \(U_0=U_N=0\). **a)** For the case \(\beta\) is constant, analyze the convergence properties of the Jacobi iterative method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). How does the number of iterations required to reduce the initial error by a factor \(\delta\) depend on \(h\)? In practice, would you use this method to solve this one-dimensional problem? If so, explain why this is a good idea? If not, how would you solve it in practice? **b)** For the case that \(\beta\) is a function of \(x\) which satisfies \(\beta(x)\geq\beta_0>0\), prove that the Jacobi iteration method converges.
-
Question 5
**Elliptic Problems:** For the one dimensional Poisson problem for \(v(x)\) \[ -v''(x)=f(x) \] with Dirichlet boundary conditions in the interval \([0,1]\), consider the scheme \[ -(D_+D_-U)_j\equiv -U_{j-1}+2\,U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots,N-1\) where \(Nh=1\), \(F_j\equiv h^2f(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=(F_1,F_2,\ldots,F_{N-1})^T\). **a)** State and prove the maximum principle for the numerical solution \(U_j\). **b)** Derive the matrix \(A\) and show that it is symmetric and positive definite. **c)** Show that the global error \(e_j=v(x_j)-U_j\) satisfies \(\|e\|_\infty=O(h^2)\) as the space step \(h\to0\).
-
Question 6
Heat Equation Stability:
Consider the variable coefficient diffusion equation \[ v_t=(\beta 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)\geq \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.
NOTE: Because of the boundary conditions and the variable coefficients, von Neumann (Fourier) analysis does not apply.
7) Numerical Methods for ODEs: Consider the initial value problem for a system of ODEs \[ y'=Ay \] where \(A\) has eigenvalues with real parts ranging from \(-10^6\) to \(-1\). Which of the following schemes would be the best choice for solving this problem? Justify your answer in terms of stability, accuracy, and efficiency. Does your answer change depending on the size of the system and the condition number of \(A\)? Explain your answer. \[ y^{n+1}=y^n+kAy^n, \tag {1} \] \[ y^{n+1}=y^n+kAy^{n+1}, \tag {2} \] \[ y^{n+1}=y^n+\frac {k}{2}\left (Ay^n+Ay^{n+1}\right ). \tag {3} \]