Preliminary Examination, Numerical Analysis, Fall 1995

Sensitivity of Solution of Linear System Suppose that \(A\) is a real non-singular \(n\times n\) matrix. Consider the family of linear systems \(Ax(\epsilon )=b+\epsilon c\), where \(b\) and \(c\) are given nonzero vectors in \(\mathbb {R}^n\), and \(\epsilon \) is a real parameter. Let \(x=x(0)\) be the solution for \(\epsilon =0\). Let \(\lVert \cdot \rVert _2\) denote the Euclidean vector norm.

a) Show that \[ \frac {\lVert x(\epsilon )-x\rVert _2}{\lVert x\rVert _2} \le \lVert A\rVert _2\lVert A^{-1}\rVert _2 \frac {\lVert \epsilon c\rVert _2}{\lVert b\rVert _2}. \] The expression \(\lVert A\rVert _2\lVert A^{-1}\rVert _2\) is the condition number of \(A\). Interpret the above inequality and explain its significance?

b) What is the Singular Value Decomposition (SVD) of \(A\)? Express the condition number above in terms of \(A\)’s singular values.

c) When the condition number is very large, the matrix is called ill-conditioned. Sometimes people say that an ill-conditioned matrix is ‘nearly-singular’. Make this precise by expressing the (relative) distance between \(A\) and the nearest singular matrix to \(A\) in terms of the condition number of \(A\).

Linear Least Squares Let \(A\) be a real \(m\times n\) matrix of full rank and let \(b\in \mathbb {R}^m\) and consider the Least Squares problem: \[ \text {Find }x\in \mathbb {R}^n\text { such that }\lVert Ax-b\rVert _2\text { is minimized.} \] 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? What is the Singular Value Decomposition (SVD) 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.

Iterative Methods for Linear Systems Consider the boundary value problem \[ -u''(x)=f(x),\qquad \text {for }0\le x\le 1 \] 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=h^2f(jh)\). Imagine applying the Jacobi iterative method to solve this system of linear equations. Analyze the convergence properties of the Jacobi method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). You may find it helpful to recall that the \((N-1)\times (N-1)\) matrix \(M\) defined by \[ m_{ij}= \begin {cases} 2, & \text {if } i=j,\\ -1, & \text {if } \lvert i-j\rvert =1,\\ 0, & \text {otherwise} \end {cases} \] has eigenvalues \[ \mu _l=4\sin ^2\left (\frac {\pi l}{2N}\right ),\qquad l=1,2,\ldots ,N-1. \] (NOTE: This is a model problem designed to give you a simple linear system on which to analyze the Jacobi method; one would certainly not use an iterative method to solve a tri-diagonal system in practice!)

Eigenvalue Problems Let \(A\) be a real \(n\times n\) matrix with simple eigenvalue \(\lambda \), 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\). a) Show that the condition number for \(\lambda \) to changes in \(A\) is given by \(s(\lambda )=1/\lvert y^*x\rvert \). b) Give an example of a matrix \(A\) which has a badly conditioned eigenvalue, and another matrix \(A\) which has only well-conditioned eigenvalues. c) Sketch a reasonably efficient algorithm for finding the largest eigenvalue of a symmetric matrix \(A\) with distinct eigenvalues. How fast do you expect this algorithm to converge?

Newton Type Methods Suppose \(f(x)\) is a real-valued function defined for all values of the real variable \(x\), and that \(f'\) is Lipschitz continuous. Consider the discrete Newton method: Guess \(x_0\) and for \(k=0,1,2,\ldots \), do: \[ a_k=\frac {f(x_k+h_k)-f(x_k)}{h_k} \] \[ x_{k+1}=x_k-\frac {f(x_k)}{a_k} \] Analyze the local convergence properties of this method. How does the speed of convergence depend on the choice of \(h_k\) (ignore any effect of round-off errors in this analysis)? Now taking roundoff into account what would be a reasonable size for \(h_k\) in practice?

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}hf_{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\) for all \(x\). a) Analyze the consistency, stability, accuracy, and convergence properties of this method. b) Would this method be a reasonable one to use for the initial value problem: \[ y'=-10^8[y-\cos (x)]-\sin (x),\qquad y(0)=1? \] Justify your answer.

Finite-Difference Methods Consider the spatially-periodic initial value problem for \(v(x,t)\): \[ v_t=cv_x,\qquad \text {for }0\le x\le 1 \] with \[ v(x,0)=f(x),\qquad \text {for }0\le x\le 1. \] Here the function \(f\) has period 1, and \(c\) is a positive constant. Note that the exact solution of the problem is \(v(x,t)=f(x+ct)\).

Consider the following difference approximations to the PDE: \[ \begin {aligned} \text {i)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{h}(u_{j+1}^n-u_j^n),\\ \text {ii)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{h}(u_j^n-u_{j-1}^n),\\ \text {iii)}\quad &u_j^{n+1}=u_j^n+\frac {ck}{2h}(u_{j+1}^n-u_{j-1}^n). \end {aligned} \] In each case, \(Nh=1\), and the difference scheme is supplemented with the discrete initial conditions \(u_j^0=f(jh)\) for \(j=0,1,\ldots ,N\) and boundary conditions \(u_N^n=u_0^n\), \(u_{-1}^n=u_{N-1}^n\), and \(u_{N+1}^n=u_1^n\) for all time levels \(n\ge 0\). For each scheme, tell whether it is a reasonable scheme to use on the above problem, and justify your answers.

Finite-Element Methods Consider the problem: \[ -u''+u=f,\qquad \text {on }[0,1] \] with \[ u(0)=0\qquad \text {and}\qquad u(1)=1. \]

Derive a variational formulations of this problem (be sure to define the space on which your variational problem is to be solved). Formulate a Galerkin finite-element method for the variational problem using piecewise linear functions. Prove that the linear system which arises in the finite-element method has a solution. In what sense is the solution optimal?