Exam
Preliminary Examination, Numerical Analysis, January 2017
Spring 2017 · 8 questions in this exam.
Questions in This Exam
Ordered by the question sequence in the original exam.
-
Question 1
**Singular Value Decomposition (SVD):** **a)** Prove the following statement: Singular Value Decomposition: Any matrix \(A\in\mathbb{C}^{m\times n}\) can be factored as \(A=U\Sigma V^*\), where \(U\in\mathbb{C}^{m\times m}\) and \(V\in\mathbb{C}^{n\times n}\) are unitary and \(\Sigma\in\mathbb{R}^{m\times n}\) is a rectangular matrix whose only nonzero entries are non-negative entries on its diagonal. **b)** Relate the matrices \(U\), \(V\), and \(\Sigma\) to the four fundamental subspaces associated with \(A\), that is, the range and null spaces of \(A\) and \(A^T\).
-
Question 2
**Linear Least Squares:** The Linear Least Squares problem for an \(m\times n\) real matrix \(A\) and \(b\in\mathbb{R}^m\) is the problem: \[ \text{Find } x\in\mathbb{R}^n \text{ such that } \|Ax-b\|_2 \text{ is minimized.} \] **a)** Suppose that you have data \(\{(t_j,y_j)\}\), \(j=1,2,\ldots,m\) that you wish to approximate by an expansion \[ p(t)=\sum_{k=1}^{n} x_k\phi_k(t). \] Here, the functions \(\phi_k(t)\) are given functions. Which norm on the difference between the approximation function \(p\) and the data gives rise to a linear least squares problem for the unknown expansion coefficients \(x_k\)? What is the matrix \(A\) in this case, and what is the vector \(b\)? **b)** Suppose that \(A\) is a real \(m\times n\) matrix of full rank and let \(b\in\mathbb{R}^m\). What are the `normal equations' for the Least Squares problem? How can they be used to solve the Least Squares problem? What is the QR factorization of \(A\) and how can it be used to solve the Least Squares problem? Compare and contrast these approaches for numerically solving the Least Square problem.
-
Question 3
**Sensitivity:** **a)** Suppose that \(A\) is an \(n\times n\) nonsingular real matrix. Analyze the sensitivity of solutions of the system \(Ax=b\) to perturbations in \(b\). What quantity related to \(A\) characterizes this sensitivity? **b)** Suppose \(\tilde{x}\) is an approximate solution to the linear system \(Ax=b\), where \(A\) is an \(n\times n\) nonsingular real matrix. The residual is the vector \(r=b-A\tilde{x}\). Derive inequalities relating the residual \(r\) to the error \(e=x-\tilde{x}\).
-
Question 4
**Interpolation and Integration:** **a)** Consider \(n+1\) distinct points \(x_0
- Question 5
**Iterative Methods:** Consider the fixed-point iteration \[ \mathbf{u}^{(k+1)}=T\mathbf{u}^{(k)}+\mathbf{c} \] for finding a solution of the problem \[ \mathbf{u}=T\mathbf{u}+\mathbf{c}, \] where \(T\) is an \(m\times m\) real matrix and \(\mathbf{c}\) is a real \(m\)-vector. **a)** Show that the fixed point iteration will converge for an arbitrary initial guess \(\mathbf{u}^{(0)}\) if and only if the spectral radius of \(T\), \(\rho(T)\), is less than 1. **b)** Consider the boundary value problem \[ -u''(x)=f(x),\qquad \text{for } 0\le x\le1 \] with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+2U_j-U_{j+1}=F_j, \] for \(j=1,2,\ldots,N-1\) where \(Nh=1\) and \(F_j\equiv h^2f(jh)\). Show that the Jacobi iterative method will converge for this problem for any choice of initial guess. 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 the given problem? If so, explain why this is a good idea? If not, how would you solve it in practice?- Question 6
**Elliptic Problems:** For the one dimensional Poisson problem for \(v(x)\) \[ -v''(x)+\alpha v(x)=f(x), \] where \(\alpha\ge0\) is constant, along with Dirichlet boundary conditions in the interval \([0,1]\), consider the scheme \[ \Delta_h U_j\equiv \frac{1}{h^2}\left(-U_{j-1}+2U_j-U_{j+1}\right)=f_j \] for \(j=1,2,\ldots,N-1\) where \(Nh=1\), \(f_j\equiv f(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=h^2(f_1,f_2,\ldots,f_{N-1})^T\). **a)** State and prove the maximum principle for any grid function \(V=\{V_j\}\) with values for \(j=0,1,\ldots,N\), that satisfies \(\Delta_h V_j\ge0\). **b)** Derive the matrix \(A\) and show that it is symmetric and positive definite. **c)** Use the maximum principle to 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 7
**Numerical Methods for ODEs:** Consider the Linear Multistep Method \[ y_{n+2}-\frac{4}{3}y_{n+1}+\frac{1}{3}y_n=\frac{2}{3}k f_{n+2} \] for solving an initial value problem \(y'=f(y,x)\), \(y(0)=\eta\). You may assume that \(f\) is Lipschitz continuous with respect to \(y\) uniformly for all \(x\). **a)** Analyze the consistency, stability, accuracy, and convergence properties of this method. **b)** Sketch a graph of the solution to the following initial value problem. \[ y'=-10^8[y-\cos(x)]-\sin(x),\qquad y(0)=2. \] Would it be more reasonable to use this method or the forward Euler method for this problem? What would you consider in choosing a timestep \(k\) for each of the methods? Justify your answer.- Question 8
Heat Equation Stability:
Consider the variable coefficient diffusion equation \[ v_t=(\beta (x)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)\ge \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.
DO NOT NEGLECT THE FACT THAT THE PROBLEM HAS VARIABLE COEFFICIENTS AND THAT THERE ARE BOUNDARY CONDITIONS AT 0 AND 1!
Fact 1: A real symmetric \(n\times n\) matrix \(A\) can be diagonalized by an orthogonal similarity transformation, and \(A\)’s eigenvalues are real.
Fact 2: The \((N-1)\times (N-1)\) matrix \(M\) defined by \[ M= \begin {pmatrix} -2 & 1 & 0 & \cdots & 0\\ 1 & -2 & 1 & \ddots & \vdots \\ 0 & 1 & -2 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & -2 \end {pmatrix} \] has eigenvalues \[ \mu _l=-4\sin ^2\left (\frac {\pi l}{2N}\right ), \qquad l=1,2,\ldots ,N-1. \]
Fact 3: The \((N+1)\times (N+1)\) matrix: \[ \begin {pmatrix} -1 & 1 & 0 & \cdots & 0\\ 1 & -2 & 1 & \ddots & \vdots \\ 0 & 1 & -2 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ 0 & \cdots & 0 & 1 & -1 \end {pmatrix} \] has eigenvalues \[ \mu _l=-4\sin ^2\left (\frac {\pi l}{2(N+1)}\right ), \qquad l=0,1,\ldots ,N. \]
Fact 4: For a real \(n\times n\) matrix \(A\), the Rayleigh quotient of a vector \(x\in \mathbb {R}^n\) is the scalar \[ r(x)=\frac {x^T Ax}{x^T x}. \] The gradient of \(r(x)\) is \[ \nabla r(x)=\frac {2}{x^T x}(Ax-r(x)x). \] If \(x\) is an eigenvector of \(A\) then \(r(x)\) is the corresponding eigenvalue and \(\nabla r(x)=0\).
Topics Covered by This Exam
Absolute Stability and A-Stability Conditioning, Sensitivity, and Perturbation Bounds Consistency, Stability, and Convergence Eigenvalues, Spectral Radius, and Gershgorin Theorem Elliptic and Poisson Equation Schemes Fixed-Point Iteration Forward Euler and First-Order Convergence Heat and Diffusion Equation Schemes Iterative Methods for Linear Systems Least Squares and Normal Equations Linear Programming and Optimization Local Truncation Error and Global Error Matrix Norms and Induced Norms Matrix Rank and Fundamental Linear Algebra Orthogonal and Unitary Matrices Polynomial Interpolation and Error Formulas QR Factorization Singular Value Decomposition Variable-Coefficient Diffusion Problems - Question 5