Numerical Analysis Prelim, January 2004

Householder Reflections A Householder Reflection \(H\) is an \(n\times n\) orthogonal matrix of the form \[ H=I-2uu^T \tag {1} \] where \[ \lVert u\rVert _2=1 \tag {2} \] and \(I\) is the \(n\times n\) identity matrix. Let \(a\in \mathbb {R}^n\) be a given (non-zero) vector. Show how to pick \(u\) in (1) such that \[ Ha=\lVert a\rVert _2 e_1 \tag {3} \] where \(e_1\) is the first unit vector. Describe how to use this technique to compute the \(QR\) factorization of an \(n\times n\) matrix \(A\).

Frobenius Norm The Frobenius Norm \(\lVert A\rVert _F\) of an \(n\times n\) matrix \(A\) is defined by \[ \lVert A\rVert _F= \sqrt {\sum _{i=1}^n\sum _{j=1}^n a_{ij}^2}. \tag {4} \] Let \(H=I-2uu^T\) be a Householder reflection as in the preceding problem and compute the Frobenius Norm of \(H\).

Gaussian Quadrature Consider the quadrature formula \[ \int _a^b w(x)f(x)\,dx=\sum _{i=1}^n \alpha _i f(\xi _i)+E. \tag {5} \] \(w\) is a given positive weight function. How do you pick the knots \(\xi _i\) and the weights \(\alpha _i\) such that the formula is exact (i.e., \(E=0\)) for all polynomials of degree up to \(2n-1\)? Show that your choice works and that you can find suitable weights and knots for all intervals \([a,b]\) and positive weight functions \(w\).

Bernstein-Bezier Form Let \(T\) be a non-degenerate triangle with vertices \(V_1\), \(V_2\), and \(V_3\). The barycentric coordinates \(b_1\), \(b_2\), and \(b_3\) of a point \(x\in \mathbb {R}^2\) with respect to \(T\) are defined by \[ x=\sum _{i=1}^3 b_i V_i \qquad \text {where}\qquad \sum _{i=1}^3 b_i=1. \tag {6} \] A polynomial \(p\) of degree \(d\) can be written uniquely in its Bernstein-Bezier form as \[ p(x)=\sum _{i+j+k=d}\frac {d!}{i!j!k!}c_{ijk}b_1^i b_2^j b_3^k. \tag {7} \] Assuming you know the coefficients \(c_{ijk}\) of \(p\) as a polynomial of degree \(d\), show how to write \(p\) as a polynomial of degree \(d+1\) in Bernstein-Bezier form. What are the coefficients of \(p\) if \(p(x)=1\)?

Sensitivity Analysis Consider the (square, non-singular) linear system \[ Ax=b. \tag {8} \] 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 {9} \] 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 \).

ODEs Consider the initial value problem of ODEs: \[ y'=f(x,y),\qquad y(a)=y_0. \tag {10} \] Describe the Trapezoidal Rule applied to this problem and analyze its local accuracy and its region of absolute stability.

PDEs Consider the one-dimensional Heat Equation \[ u_t=u_{xx},\qquad t\ge 0,\qquad x\in [0,1],\qquad u(x,0)=f(x),\qquad u(0,t)=u(1,t)=0. \tag {11} \] Describe how to discretize this problem by applying the Method of Lines and the Backward Euler Method. Analyze the stability and local accuracy of your method.