Prelims Numerical Analysis, August 1999

Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=0}^n \alpha _i f(\xi _i)+E. \tag {1} \] \(w\) is a given positive weight function. The knots \(\xi _i\) and the weights \(\alpha _i\) are at your disposal. How do you choose them so that the error \(E\) is 0 for all polynomials \(f\) of degree as high as possible? How high is possible? Give reasons for your answers.

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\)?

A Matrix Compute the eigenvalues and eigenvectors of the tridiagonal \(N\times N\) matrix \[ \setlength {\arraycolsep }{5pt} A= \begin {bmatrix} 2 & 1 & 0 & \cdots & 0 & 0\\ 1 & 2 & 1 & \cdots & 0 & 0\\ 0 & 1 & 2 & \ddots & 0 & 0\\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & \ddots & 2 & 1\\ 0 & 0 & 0 & \cdots & 1 & 2 \end {bmatrix}. \tag {2} \] Note that the diagonal entries are indeed meant to be positive 2, not -2.

Sensitivity Analysis Consider the (square, non-singular) linear system \[ Ax=b. \tag {3} \] Suppose you compute (by any method) a numerical solution \(\hat {x}\) and you are concerned about the relative error \[ E=\frac {\lVert x-\hat {x}\rVert }{\lVert x\rVert } \tag {4} \] where \(\lVert \cdot \rVert \) denotes a suitable vector norm. Derive upper and lower bounds on \(E\) in terms of the residual \(r=b-A\hat {x}\) and the condition number of \(A\) with respect to \(\lVert \cdot \rVert \).

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

Numerical PDEs Consider the PDE \[ u_t+u_x=0 \tag {5} \] and the usual discretization \[ U_m^n\approx u(x_m,t_n) \qquad \text {where}\qquad x_m=mh\quad \text {and}\quad t_n=nk. \tag {6} \] The Leap Frog Method is given by \[ U_m^{n+1}=U_m^{n-1}-\frac {k}{h}\left (U_{m+1}^n-U_{m-1}^n\right ). \tag {7} \] Compute the local truncation error and discuss the stability of this method.