Preliminary Exam, Numerical Analysis, August 2000

Sensitivity Analysis Consider the linear system \(Ax=b\) where \(A\) is a square, non-singular matrix. A numerical solution \(\hat {x}\) actually satisfies \[ (A+\delta A)\hat {x}=b+\delta b. \] If we denote \(\delta x=\hat {x}-x\), derive an upper bound for the relative error \[ E_1=\frac {\lVert \delta x\rVert }{\lVert \hat {x}\rVert } \] in terms of the condition number of \(A\) and the norms of \(A,\hat {x},\delta A,\delta b\), where \(\lVert \cdot \rVert \) is a suitable vector norm. Also, we can define another relative error \[ E_2=\frac {\lVert \delta x\rVert }{\lVert x\rVert }. \] Derive an upper bound for \(E_2\) in terms of the condition number of \(A\) and the norms of \(\delta A,A,\delta b\) and \(b\). When are these two errors close to each bound? What’s the significance of the condition number?

Linear Least Squares Let \(A\) be a real \(m\times n\) matrix of full rank \((m>n)\) and let \(b\in \mathbb {R}^m\). The Least Square problem is to find \(x\in \mathbb {R}^n\) such that \[ \lVert Ax-b\rVert _2 \] is minimized.

Describe the following three approaches to solve the problem: 1) normal equations, 2) QR decomposition, and 3) Singular Value Decomposition (SVD). Discuss briefly the advantages and disadvantages of these approaches. In particular, give a geometric interpretation of the normal equation approach and explain why it is not often used?

Eigenvalue Problems Let \(\lambda \) be a simple eigenvalue of \(A\) (not necessarily symmetric), with right eigenvector \(x\) (i.e., \(Ax=\lambda x\)), and left eigenvector \(y\) (i.e., \(y^*A=\lambda y^*\)). Assume that \(\lVert x\rVert _2=\lVert y\rVert _2=1\). Let \(\lambda +\delta \lambda \) be the corresponding eigenvalue of \(A+\delta A\).

a) Show that \[ \delta \lambda =\frac {y^*\delta A x}{y^*x}+O(\lVert \delta A\rVert ^2), \] and derive an upper bound for \(\lvert \delta \lambda \rvert \). What is the condition number for \(\lambda \) with respect to changes in \(A\)?

b) Consider the matrix \[ \begin {bmatrix} 0 & 1 & 0 & \cdots & 0\\ 0 & 0 & 1 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & 1\\ \epsilon & 0 & \cdots & 0 & 0 \end {bmatrix}. \] Compute \(d\lambda /d\epsilon \) and show that the condition number becomes infinite as \(\epsilon \) approaches zero.

c) Describe the power method for finding the eigenvalue of the largest absolute magnitude, and inverse iteration for the eigenvalue closest to a given value. How fast do you expect these algorithms to converge?

Singular Value Decomposition Define the singular value decomposition of a real \(m\times n\) matrix with \(m\ge n\). Is the SVD unique for a given matrix \(A\)? How is an SVD problem connected with an eigendecomposition of a symmetric matrix? Sketch the general structure of algorithms for those imported from eigendecomposition, namely, how do you reduce \(A\) to some form more manageable? How do you obtain the information about the rank of \(A\) through the SVD of \(A\)? If \(A\) is square and nonsingular, how does the SVD of \(A\) help you determine the sensitivity of the solution \(x\) for \(Ax=b\)?

Iterative Methods for Linear Systems Consider the linear system \(Ax=b\) and a splitting of \(A:A=M-K\), with \(M\) nonsingular, and the iteration \[ x_{m+1}=Rx_m+c, \] where \(R=M^{-1}K\) and \(c=M^{-1}b\). Show that the method converges for any \(x_0\) if \(\lVert R\rVert <1\) where \(\lVert \cdot \rVert \) is any operator norm.

Given an \((N-1)\times (N-1)\) \[ \setlength {\arraycolsep }{5pt} A= \begin {bmatrix} 2 & -1 & 0 & \cdots & 0\\ -1 & 2 & -1 & \ddots & 0\\ 0 & -1 & \ddots & \ddots & 0\\ \vdots & \ddots & -1 & 2 & -1\\ 0 & \cdots & 0 & -1 & 2 \end {bmatrix}, \qquad b=\frac {1}{N^2} \begin {pmatrix} f_1\\ f_2\\ \cdot \\ f_{N-2}\\ f_{N-1} \end {pmatrix}. \] Analyze the convergence properties of the Jacobi and Gauss-Seidel methods for this problem. For each method, express the convergence speed as a function of \(N\). How does the number of iterations required to reduce the initial error by a factor of \(\delta \) depend on \(N\) for each method?

Wave Equations Consider the wave equation in one space dimension: \[ u_t+au_x=0,\qquad -\infty <x<\infty ,\qquad t>0, \] with initial condition \[ u(x,0)=u_0(x). \] Consider the usual discretization \[ U_m^k\approx u(x_m,t_k) \] where \(x_m=m\Delta x\) and \(t_k=k\Delta t\). For an explicit scheme, what is the CFL condition? Give an intuitive explanation of the condition. Give the first-order upwind scheme for this equation and derive the truncation error.

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.