Instructions. Solve the problems for your course track. Formulate your answers clearly and cogently. Sketch out an approach on scratch paper first. Concisely 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. Sign each page thus acknowledging honor code rules. Do not turn in scratch work.

Grading. $4\mathrm{problems}\times 5\mathrm{points}/\mathrm{problem}=20\mathrm{points}$. $\mathrm{Midterm}n=max(\mathrm{Midterm}\mathrm{score},2\times \mathrm{problem}n)$

Preamble. The course objectives set out in the syllabus are reproduced below, along with a formulary. Problems probe understanding of the course concepts, rather than rote memorization.

“There are just four mathematics ideas that are considered in this course:

Comparable simplicity is encountered in computational ideas:

Formulary. Newton method to solve $f\left(x\right)=0$: $x_{n+1}=x_n-f\left(x_n\right)/f^{\text{'}}\left(x_n\right)$.

Newton form of interpolating polynomial: $p_n\left(t\right)=\left[y_0\right]+[y_1,y_0](t-x_0)+\cdots +[y_n,\cdots ,y_0](t-x_0)...(t-x_{n-1})$

Divided differences: $\left[y_k\right]=y_k$, $[y_{k+m},...,y_k]=([y_{k+m},...,y_{k+1}]-[y_{k+m-1},...,y_k])/(x_{k+m}-x_k)$

Finite difference operators: $E^{k}f\left(x\right)=f(x+kh)$, $\Delta f\left(x\right)=(E-I)f\left(x\right)$, $\nabla f\left(x\right)=(I-E^{-1})f\left(x\right)$, $\delta f\left(x\right)=(E^{1/2}-E^{-1/2})f\left(x\right)$

Binomial expansion: ${(x+y)}^n={\sum }_{k=0}^n\left(\begin{array}{l}n\\ k\end{array}\right)x^{n-k}{y}^k$, $\left(\begin{array}{l}n\\ k\end{array}\right)=$, $n\in \mathbb{N}$

Generalized binomial expansion: ${(x+y)}^{\alpha }={\sum }_{k=0}^{\infty }\left(\begin{array}{l}\alpha \\ k\end{array}\right)x^{\alpha -k}{y}^k$, $\alpha \in ℝ$

Interpolation operator: $x_k=x_0+kh$, $p_n(x_0+\alpha h)={(I+▵)}^a{y}_0$

Householder reflector $𝑯=𝑰-2$

1Track 1

1. Consider $𝑨,𝑩\in {ℝ}^{m\times m}$ symmetric. Determine if the following are also symmetric.

   1. ${𝑨}^2-{𝑩}^2$

   2. $(𝑨+𝑩)(𝑨-𝑩)$

   3. $𝑨𝑩𝑨$

   4. $𝑨𝑩𝑨𝑩$

2. Construct a spline interpolant of data $𝒟=\{(x_i,y_i),i=0,1,..,n\}$ using piecewise trigonometric functions $s_i:[x_{i-1},x_i]\to ℝ$, $i=1,2,..,n$

   ${\displaystyle s_i\left(t\right)=a_i+b_i\cos \left(t\right)+c_i\sin \left(t\right).}$

3. Find a quadrature formula

   ${\displaystyle \underset{-1}{\overset{1}{\int }}f\left(x\right)dx\cong c(f\left(x_0\right)+f\left(x_1\right)+f\left(x_2\right))}$

   that is exact for all quadratic polynomials.

4. Newton's method to solve $f\left(x\right)=0$ uses data ${𝒟}_n=\left\{(x_n,f_n,f_n^{\text{'}})\right\}$ to construct a linear approximant $g$, and the next iterate $x_{n+1}$ is the solution of $g\left(x\right)=0$. Construct an analogous method based upon data $𝒟=\{(x_{n-1},f_{n-1},f_{n-1}^{\text{'}}),(x_n,f_n,f_n^{\text{'}})\}$, and establish its order of convergence ($f_n=f\left(x_n\right)$, $f_n^{\text{'}}=f^{\text{'}}\left(x_n\right)$).

2Track 2

1. For $𝑨=\left[A_{ij}\right],𝑩=\left[B_{ij}\right],𝑪=\left[C_{ij}\right]\in {ℝ}^{m\times m},m=2$, the Strassen algorithm computes $𝑪=𝑨𝑩$ as

   $\circ$

   ${\displaystyle P_1=(A_{11}+A_{22})(B_{11}+B_{22}),P_2=(A_{21}+A_{22})B_{11},P_3=A_{11}(B_{12}-B_{22}),P_4=A_{22}(B_{21}-B_{11}),}$

   ${\displaystyle P_5=(A_{11}+A_{12})B_{22},P_6=(A_{21}-A_{11})(B_{11}+B_{12}),P_7=(A_{12}-A_{22})(B_{21}+B_{22}),}$ ${\displaystyle C_{11}=P_1+P_4-P_5+P_7,C_{12}=P_3+P_5,C_{21}=P_2+P_4,C_{22}=P_1+P_3-P_2+P_6.}$

   In[21]:=

   P[1]=(A[11]+A[22])(B[11]+B[22])

   $(A\left(11\right)+A\left(22\right))(B\left(11\right)+B\left(22\right))$

   In[22]:=

   P[2]=(A[21]+A[22])B[11]

   $(A\left(21\right)+A\left(22\right))B\left(11\right)$

   In[14]:=

   P[3]=A[11](B[12]-B[22])

   $A\left(11\right)(B\left(12\right)-B\left(22\right))$

   In[24]:=

   P[4]=A[22](B[21]-B[11])

   $A\left(22\right)(B\left(21\right)-B\left(11\right))$

   In[29]:=

   P[5]=(A[11]+A[12])B[22]

   $(A\left(11\right)+A\left(12\right))B\left(22\right)$

   In[17]:=

   P[6]=(A[21]-A[11])(B[11]+B[12])

   $(A\left(21\right)-A\left(11\right))(B\left(11\right)+B\left(12\right))$

   In[18]:=

   P[7]=(A[12]-A[22])(B[21]+B[22])

   $(A\left(12\right)-A\left(22\right))(B\left(21\right)+B\left(22\right))$

   In[30]:=

   Expand[P[1]+P[4]-P[5]+P[7]]

   $A\left(11\right)B\left(11\right)+A\left(12\right)B\left(21\right)$

   In[31]:=

   Expand[P[3]+P[5]]

   $A\left(11\right)B\left(12\right)+A\left(12\right)B\left(22\right)$

   In[32]:=

   Expand[P[2]+P[4]]

   $A\left(21\right)B\left(11\right)+A\left(22\right)B\left(21\right)$

   In[33]:=

   Expand[P[1]+P[3]-P[2]+P[6]]

   $A\left(21\right)B\left(12\right)+A\left(22\right)B\left(22\right)$

   In[34]:=

   1. Compare the computational complexity of the Strassen algorithm with that of standard matrix multiplication

      ${\displaystyle C_{ij}=\sum _{k=1}^m{A}_{ik}{B}_{kj}.}$

      Separately count multiplications and additions.

   2. Consider $m=2n$ and block-structured matrices $𝑨,𝑩,𝑪$, e.g., $A_{ij}\in {ℝ}^{n\times n}$. Compare the computational complexity of the Strassen algorithm with that of standard matrix multiplication in this case.

   3. Consider $m=2^p$ and compare the computational complexities of Strassen and standard matrix multiplication.

   4. In two-decimal-digit floating point arithmetic (${𝔽}_2$) the matrices

      ${\displaystyle 𝑨=𝑩=\left[\begin{array}{ll}.99& .0010\\ .0010& .99\end{array}\right],}$

      are exactly represented. The Strassen algorithm produces ${\stackrel{\sim }{C}}_{12}=0.0$. Compute $C_{12}$ in ${𝔽}_2$ using standard multiplication and identify the source of any discrepancy with respect to ${\stackrel{\sim }{C}}_{12}$.

2. Consider the cubic spline interpolant $S\left(t\right)$ of $f:[-1,1]\to ℝ$, constructed from data $𝒟=\{(x_i,y_i=f\left(x_i\right)),i=0,1,..,n\}$.

   1. Define the mathematical problem $𝒫$ of constructing $S\left(t\right)$.

   2. Determine the condition number $\kappa$ of problem $𝒫$.

   3. Can $\kappa =1$? Under what conditions on $f$ and choice of sampling points $x_i$.

3. Construct a Gauss quadrature for integrals of form

   ${\displaystyle \underset{0}{\overset{1}{\int }}{e}^{-t𝑷}𝒇\left(t\right)dt,}$

   that is exact for cubic $𝒇\left(t\right)$, where $𝑷\in {ℝ}^{m\times m}$ is a projection matrix.

4. Construct a second-order accurate scheme to solve the integro-differential equation

   ${\displaystyle m{y}^{\text{'}\text{'}}+c{y}^{\text{'}}+ky=\underset{0}{\overset{t}{\int }}R(t-\tau )y\left(\tau \right)d\tau ,}$

   that describes the motion of a point mass $m$ subject to drag $-cv=-c{y}^{\text{'}}$, elastic force $-ky$, and internal relaxation $R\ast y$, starting from initial conditions $y\left(0\right)=y_0$, $y^{\text{'}}\left(0\right)=v_0$.