Prelims Numerical Analysis, August 2003

Newton’s Method Describe how (the two-variable version of) Newton’s Method can be used to solve the nonlinear system \[ \begin {aligned} x^2+y^2 &= 1,\\ e^x-y &= 0 \end {aligned} \tag {1} \] Discuss the selection of a starting point and the advantages and disadvantages of Newton’s method.

The \(QR\) factorization Describe the \(QR\) factorization of an \(m\times n\) matrix \(A\), how to compute it, and what it can be used for.

The QR Algorithm Outline the basic ingredients of the \(QR\) algorithm for solving eigenvalue problems.

The Singular Value Decomposition Define the term “singular value decomposition” and show that every \(m\times n\) matrix \(A\) has a singular value decomposition.

The Jacobi Method Let \(A\) be a strictly diagonally dominant \(n\times n\) matrix, i.e., \[ \lvert a_{ii}\rvert >\sum _{j\ne i}\lvert a_{ij}\rvert , \qquad i=1,\ldots ,n. \tag {2} \] Describe the Jacobi method applied to the linear system \[ Ax=b \tag {3} \] and prove that it converges for all initial approximations of the solution.

Spline Spaces Let \(T\) be a triangulation of a domain \(\Omega \), and \(S\) the linear space of functions on \(T\) that are continuous on \(\Omega \) and that on each triangle in \(T\) can be written as a (bivariate) polynomial of degree \(d\). Derive the dimension of \(S\).

Numerical ODEs Define the terms linear multistep method (LMM), order, consistency, zero-stability, local truncation error, and region of absolute stability of an LMM. What is the highest order implicit 1 step method and discuss its region of absolute stability?

Numerical PDEs Consider the Initial-Boundary Value Problem \[ u_t=u_{xx},\qquad x\in [0,1],\qquad t\ge 0, \qquad u\text { given for }x=0,\ x=1,\text { and }t=0. \tag {4} \] Describe the Crank-Nicolson Method, and analyze its local truncation error and stability.

Ill Conditioning Define the condition number of a square matrix \(A\) and its significance for the solution of the linear system \[ Ax=b. \tag {5} \] Can you define a similar number that describes the conditioning of the eigenvalue problem \[ Ax=\lambda x? \tag {6} \]

Multigrid Describe the basic ideas of the multigrid technique for the solution of elliptic PDEs.