Solve the problems for your appropriate course track. Problems probe understanding of the course concepts. Formulate your answers clearly and cogently. Sketch out an approach on scratch paper first. Then briefly transcribe the approach to the answer you turn in, followed by appropriate calculations and conclusions, within allotted time. Use concise, complete English sentences in the description of your approach.

Each question is meant to be completely answered and transcribed from proof to final copy within thirty minutes. Concentrate foremost on clear exposition of the concept underlying your approach.

1Track 1

1. Consider the solution $f\left(t\right)$ to

   ${\displaystyle f\left(t\right)=\arg {min}_{p\left(t\right)}{||\cos t-p\left(t\right)||}_{\infty },}$

   where $p\left(t\right)$ is a first-degree polynomial. Is $f\left(t\right)$ an acceptable approximation of $\cos t$ over the interval $[0,\pi /2]$? If not, is there a restriction of $f$ to a subinterval $[a,b]\subset [0,\pi /2]$ that is an acceptable approximation?

   Solution. Per equi-oscillation theorem the error $e\left(t\right)=p\left(t\right)-f\left(t\right)$, $p\left(t\right)=c_0+c_{1}t$ would change sign three times over interval $[0,\pi /2]$, at 0, $\xi ,\pi /2$, where $\xi$ is some intermediate point $0<\xi <\pi /2$. This implies $e\left(0\right)=p\left(0\right)-f\left(0\right)=p\left(0\right)-1>0$, hence $p\left(0\right)>1$, an inadmissable value for cosine. An inf-norm approximant $q\left(t\right)=d_0+d_{1}t$ can be constructed on some interval $[a,\pi /2]$ such that $q\left(a\right)=1$.

   Figure 1.

2. Determine the quadrature nodes $x_i$ such that

   ${\displaystyle \underset{0}{\overset{\infty }{\int }}{e}^{-\alpha t}f\left(t\right)dt=\sum _{i=0}^1{w}_{i}f\left(x_i\right)+e_2,}$

   has maximal order of accuracy.

   Solution. The quadrature error $e_2$ has minimal order for Gauss-Laguerre quadrature with scalar product

   ${\displaystyle (f,g)=\underset{0}{\overset{\infty }{\int }}{e}^{-\alpha t}f\left(t\right)g\left(t\right)dt=\frac{1}{\alpha }\underset{0}{\overset{\infty }{\int }}{e}^{-s}f(s/\alpha )g(s/\alpha )ds.}$

   The quadrature nodes are roots of ${\phi }_2$ obtained by orthogonalization of $\{1,s,s^2\}$. Carry out Gram-Schmidt.

   0

   ${\phi }_0=1/{(1,1)}^{1/2}$

   ${\displaystyle (1,1)=\underset{0}{\overset{\infty }{\int }}{e}^{-s}ds=1\Rightarrow {\phi }_0=1.}$

   1

   ${\phi }_1=g_1/{(g_1,g_1)}^{1/2}$, $g_1=s-(s,{\phi }_0){\phi }_0$

   ${\displaystyle (s,{\phi }_0)=\underset{0}{\overset{\infty }{\int }}{e}^{-s}sds=1,}$ ${\displaystyle g_1=s-1}$ ${\displaystyle (g_1,g_1)=1\Rightarrow }$ ${\displaystyle {\phi }_1=s-1}$

   2

   ${\phi }_2=g_2/{(g_2,g_2)}^{1/2}$, $g_2=s^2-(s^2,{\phi }_0){\phi }_0-(s^2,{\phi }_1){\phi }_1$

   ${\displaystyle (s^2,{\phi }_0)=2,(s^2,{\phi }_1)=4\Rightarrow }$ ${\displaystyle g_2=s^2-4\cdot (s-1)-2\cdot 1=s^2-4s+2}$

   Roots of ${\phi }_2$ are the same as of $g_2$, hence the quadrature nodes are at

   ${\displaystyle s_{1,2}=2\pm \sqrt{2},}$

   or in terms of $t$

   ${\displaystyle t_{1,2}=\frac{1}{\alpha }(2\pm \sqrt{2}).}$ ${\displaystyle \underset{0}{\overset{\infty }{\int }}{e}^{-\alpha t}f\left(t\right)dt\cong \sum _{i=0}^1{w}_{i}f\left(x_i\right)=w_{0}f\left(\frac{1}{\alpha }(2-\sqrt{2})\right)+w_{1}f\left(\frac{1}{\alpha }(2+\sqrt{2})\right).}$

   The weights are determined by imposing moment conditions for $1,t$

   ${\displaystyle \underset{0}{\overset{\infty }{\int }}{e}^{-\alpha t}\cdot 1dt=\frac{1}{\alpha }=w_0+w_1}$ ${\displaystyle \underset{0}{\overset{\infty }{\int }}{e}^{-\alpha t}\cdot tdt=\frac{1}{{\alpha }^2}=w_0\cdot \left(\frac{1}{\alpha }(2-\sqrt{2})\right)+w_1\cdot \left(\frac{1}{\alpha }(2+\sqrt{2})\right).}$

3. For what values $a$ is the matrix

   ${\displaystyle 𝑨=\left[\begin{array}{lll}1& a& a\\ a& 1& a\\ a& a& 1\end{array}\right]}$

   positive definite?

   Solution. $𝑨$ is positive definite if for any $𝒃\in {ℝ}^3$, ${𝒃}^T𝑨𝒃>0$, under which condition $𝑨$ is symmetric positive definite, and admits an orthogonal diagonalization

   ${\displaystyle 𝑨={𝑸}^T𝚲𝑸,}$

   hence ${𝒄}^T𝚲𝒄>0$, with $𝒄=𝑸𝒃$, and $𝑨$ would need to have positive eigenvalues for it to be positive definite. The eigenvalue problem is

   ${\displaystyle 𝑨𝒙=\lambda 𝒙\Rightarrow (𝑨-\lambda 𝑰)𝒙=𝟎,}$

   and $\lambda$ is an eigenvalue if the homogeneous system admits a non-trivial solution, or is a root of the characteristic polynomial

   ${\displaystyle p\left(\lambda \right)=\det (𝑨-\lambda 𝑰)=1-3a^2+2a^3-3\lambda +3a^2\lambda +3{\lambda }^2-{\lambda }^3}$

   Since

   ${\displaystyle \left[\begin{array}{lll}a& a& a\\ a& a& a\\ a& a& a\end{array}\right]}$

   is of rank 1, $\lambda =a-1$ is a double eigenvalue

   ${\displaystyle p\left(\lambda \right)={(a-1-\lambda )}^2(1+2a-\lambda ).}$

   $𝑨$ is s.p.d. if

   ${\displaystyle {\lambda }_{1,2}=1+a>0\Rightarrow a>-1}$

   and

   ${\displaystyle {\lambda }_3=1+2a>0\Rightarrow a>-1/2.}$

   The more restrictive condition is $a>-1/2$.

4. Compute the first three significant digits of eigenvalue $\lambda \cong 10$ of

   ${\displaystyle 𝑨=\left[\begin{array}{lll}2& 0& -1\\ -2& -10& 0\\ -1& -1& 4\end{array}\right].}$

   Solution. Apply inverse power iteration with shift ${\mu }_0=10$, from starting vector

   ${\displaystyle {𝒗}_0=\left[\begin{array}{l}1\\ 0\\ 0\end{array}\right]}$ ${\displaystyle (𝑨-\mu 𝑰){𝒗}_1={𝒗}_0\iff }$ ${\displaystyle \left[\begin{array}{lll}-8& 0& -1\\ -2& -20& 0\\ -1& -1& -6\end{array}\right]{𝒗}_1=\left[\begin{array}{l}1\\ 0\\ 0\end{array}\right]\Rightarrow {𝒗}_1=\frac{1}{157}\left[\begin{array}{l}-20\\ 2\\ 3\end{array}\right]}$

   Compute Raleigh quotient to obtain next approximant ${\mu }_1$ of eigenvalue

   ${\displaystyle {\mu }_1=\frac{{𝒗}_1^T𝑨{𝒗}_1}{{𝒗}_1^T{𝒗}_1}=2.4,}$

   and continue procedure to convergence.

   ${\displaystyle }$

5. Reduce the matrix $𝑨$ above to lower triangular form by a Givens rotation.

   Solution. Only one rotation has to be applied in order to eliminate element 1,3

   ${\displaystyle \left[\begin{array}{lll}\cos \theta & 0& -\sin \theta \\ 0& 1& 0\\ \sin \theta & 0& \cos \theta \end{array}\right]\left[\begin{array}{lll}2& 0& -1\\ -2& -10& 0\\ -1& -1& 4\end{array}\right]=\left[\begin{array}{lll}& & -\cos \theta -4\sin \theta \\ & & \\ & & \end{array}\right],}$

   with $\theta$ determined from

   ${\displaystyle \cos \theta +4\sin \theta =0\Rightarrow \tan \theta =-\frac{1}{4}.}$

2Track 2

1. Determine the eigenvalues, determinant, and singular values of a Householder reflector.

   Solution. A Householder reflector $𝑯\in {ℝ}^{m\times m}$

   ${\displaystyle 𝑯=𝑰-2\frac{𝒗{𝒗}^T}{{𝒗}^T𝒗}}$

   is an orthogonal matrix hence eigenvalues are $\pm 1$, determinant is $\pm 1$, and singular values are all $1$.

2. Construct a second-order, centered discretization of the Laplacian operator

   ${\displaystyle {\nabla }^{2}u(x_i,y_j)}$

   on a Cartesian grid $x_i=ih$, $i=0,..,m+1$, $y_j=jh$, $j=0,..,n+1$. Assume $u_{0j}=u_{i0}=u_{m+1,j}=u_{i,n+1}=0$. Express the discretization as a matrix $𝑨$ acting on the vector

   ${\displaystyle 𝒖={\left[\begin{array}{lllllll}{u}_{11}& u_{21}& ..& u_{m1}& u_{12}& ..& u_{mn}\end{array}\right]}^T.}$

   Present an efficient algorithm to orthonormalize $𝑨$, i.e., compute $𝑸𝑹=𝑨$.

   Solution. The second-order centered derivative approximation is

   ${\displaystyle \frac{df}{\mathrm{dt}}\cong \delta f=\frac{f_{i+1/2}-f_{i-1/2}}{h}\Rightarrow \frac{d^{2}f}{{\mathrm{dt}}^2}\cong {\delta }^{2}f=\frac{f_{i+1}-2f_i+f_{i-1}}{h^2}.}$

   The Laplacian at $(i,j)$ is approximated by

   ${\displaystyle {\nabla }^{2}u(x_i,y_j)=\frac{1}{h^2}(u_{i+1,j}+u_{i,j+1}+u_{i-1,j}+u_{i,j-1}-4u_{i,j}),}$

   with $𝑨$ a penta-diagonal matrix

   ${\displaystyle 𝑨=\left[\begin{array}{lllllll}-4& 1& 0& \cdots & 1& \cdots & \cdots \\ 1& -4& 1& \cdots & 0& 1& \cdots \\ & 1& -4& 1& ?& & \\ & & & \ddots & & & \end{array}\right].}$

   Given that $𝑨$ is sparse, the most efficient $QR$ factorization is through Givens rotators to eliminate element $(i,j)$

   ${\displaystyle G_{i,j}=\left[\begin{array}{lllllll}1& & & & & & \\ & \ddots & & & & & \\ & & \cos \theta & \cdots & -\sin \theta & & \cdots \\ & & & \ddots & & & \\ & & \sin \theta & & \cos \theta & & \\ & & & & & \ddots & \end{array}\right]}$

3. Prove that the eigenvalues of a Hermitian matrix are real. Prove that the eigenvalues of a skew-Hermitian matrix are pure imaginary.

   Solution. Take adjoint of

   ${\displaystyle 𝑨𝒙=\lambda 𝒙\Rightarrow {𝒙}^{\ast }{𝑨}^{\ast }={𝒙}^{\ast }𝑨=\bar{\lambda }{𝒙}^{\ast }}$

   Multiply first on left by ${𝒙}^{\ast }$, second on right by $𝒙$ and obtain

   ${\displaystyle {𝒙}^{\ast }𝑨𝒙=\lambda {𝒙}^{\ast }𝒙=\bar{\lambda }{𝒙}^{\ast }𝒙}$

   Since $𝒙\ne 𝟎$ it results that $\lambda =\bar{\lambda }$, hence $\lambda$ is real. Similar proof for skew-hermitian case ${𝑨}^{\ast }=-𝑨$

4. Find a two-point Gaussian quadrature for the integral

   ${\displaystyle F\left(s\right)=\underset{0}{\overset{\infty }{\int }}{e}^{-st}f\left(t\right)dt,s>0.}$

   Derive the error expression, its leading order, and how it scales with $s$ as $s\to \infty$.

   Solution. Upon rescaling

   ${\displaystyle \underset{0}{\overset{\infty }{\int }}{e}^{-st}f\left(t\right)dt=\frac{1}{s}\underset{0}{\overset{\infty }{\int }}{e}^{-u}f\left(\frac{u}{s}\right)du.}$

   See Track 1 for Gauss-Laguerre quadrature, and apply.

5. Determine the values $a,b,c$ such that

   ${\displaystyle f\left(t\right)=\{\begin{array}{ll}3+t-9t^2& t\in [0,1]\\ a+b(t-1)+c{(t-1)}^2+d{(t-1)}^3& t\in [1,2]\end{array}.,}$

   is a cubic spline with knots $x_0=0$, $x_1=1$, and $x_2=2$. Determine $d$ such ${||f^{\text{'}\text{'}}||}_2$ is a minimum.

   Solution. At the common node (knot) $x_1$ impose continuity in function and first two derivatives

   ${\displaystyle -5=a}$ ${\displaystyle -17=b}$ ${\displaystyle -18=2c\Rightarrow c=-9.}$

   Compute

   ${\displaystyle S\left(d\right)={||f^{\text{'}\text{'}}||}_2=\underset{0}{\overset{2}{\int }}f\left(t\right)dt=\underset{0}{\overset{1}{\int }}{(-18)}^{2}dt+\underset{1}{\overset{2}{\int }}{(-18+6d(t-1))}^{2}dt}$

   and impose

   ${\displaystyle S^{\text{'}}\left(d\right)=0}$

   to determine $d$.