Solve the problems for your appropriate course track. Problems probe understanding of the definitions and results from the modules on real function approximation. 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 ten minutes. The test also contains 5 short Quiz 03 questions, meant to be answered in one minute each. Present a succint motivation for your quiz answers taking into account time constraints.

1Track 1

1. Construct the polynomial interpolant of data $𝒟=\{(1,3),(2,4),(3,-1),(4,-18)\}$ in Lagrange form.

   Solution. The Lagrange form of the interpolant of $𝒟=\{(x_i,y_i),i=0,..,n\}$ is

   ${\displaystyle p\left(t\right)=\sum _{i=0}^n{\ell }_i\left(t\right)y_i,{\ell }_i\left(t\right)=\prod _{j=0}^n{}^{\text{'}}\frac{t-x_j}{x_i-x_j}.}$

   For the given data,

   ${\displaystyle p\left(t\right)=3{\ell }_0\left(t\right)+4{\ell }_1\left(t\right)-{\ell }_2\left(t\right)-18{\ell }_3\left(t\right),}$

   with

   ${\displaystyle \begin{array}{ll}{\ell }_0\left(t\right)=\frac{(t-2)(t-3)(t-4)}{(1-2)(1-3)(1-4)}& {\ell }_1\left(t\right)=\frac{(t-1)(t-3)(t-4)}{(1-2)(1-3)(1-4)}\\ {\ell }_2\left(t\right)=\frac{(t-1)(t-2)(t-4)}{(1-2)(1-3)(1-4)}& {\ell }_3\left(t\right)=\frac{(t-1)(t-2)(t-3)}{(1-2)(1-3)(1-4)}\end{array}}$

2. Construct the Newton form of the polynomial interpolant of the above data set, presenting the table of divided differences.

   Solution. The Newton form of the interpolant is

   ${\displaystyle p\left(t\right)=\left[y_0\right]+[y_1,y_0](t-x_0)+\cdots +[y_n,..,y_0](t-x_0)(t-x_{n-1}).}$

   For the above data construct the divided difference table

   ${\displaystyle \begin{array}{llllll}i& x_i& \left[y_i\right]& [y_i,y_{i-1}]& [y_i,y_{i-1},y_{i-2}]& [y_i,y_{i-1},y_{i-3}]\\ 0& 1& 3& -& -& -\\ 1& 2& 4& 1& -& -\\ 2& 3& -1& -5& -3& -\\ 3& 4& -18& -17& -6& -1\end{array}}$

   The interpolant is

   ${\displaystyle p\left(t\right)=3+(t-1)\cdot 1+(t-1)(t-2)(-3)+(t-1)(t-2)(t-3)(-1)}$

3. Efficiently evaluate the Newton form of the polynomial interpolant determined above at $t=-1$, using Horner's scheme.

   Solution. The above interpolant is evaluated as

   ${\displaystyle p\left(t\right)=3+(t-1)(1+(t-2)(-3-(t-3)))}$ ${\displaystyle p(-1)=3+(-2)(1+(-3)(-3+4))=7}$

4. Replace the sampling points $x_i=1+i$, $i=0,..,3$ in the data set $𝒟$ so as to minimize the interpolation error over the interval $[1,4]$

   Solution. The interpolation error is minimized for the Chebyshev points, in this case the roots of $T_4\left(x\right)$, rescaled to cover the interval $[1,4]$

   ${\displaystyle t=\frac{3}{2}(x+1)+1}$

   First, determine $T_4\left(x\right)$ through the recursion

   ${\displaystyle T_{n+1}\left(x\right)=2x{T}_n\left(x\right)-T_{n-1}\left(x\right)}$ ${\displaystyle T_0\left(x\right)=1,T_1\left(x\right)=x,T_2\left(x\right)=2x^2-1}$ ${\displaystyle T_3\left(x\right)=2x(2x^2-1)-x=4x^3-3x}$ ${\displaystyle T_4\left(x\right)=2x(4x^3-3x)-(2x^2-1)=8x^4-8x^2+1}$

   Denote $z=x^2$ and find roots of quadratic

   ${\displaystyle 8z^2-8z+1=0\Rightarrow z_{1,2}=\frac{4\pm \sqrt{8}}{8}=\frac{2\pm \sqrt{2}}{4}}$ ${\displaystyle z_1=\frac{2+\sqrt{2}}{4}\cong \frac{2+1.4}{4}=0.85\Rightarrow x_{1,2}=\pm \sqrt{0.85}\cong \pm 0.92}$ ${\displaystyle z_2=\frac{2-\sqrt{2}}{4}\cong \frac{2-1.4}{4}=0.15\Rightarrow x_{1,2}=\pm \sqrt{0.15}\cong \pm 0.39}$

5. Quiz questions:

   1. True or false: a basis exists for all vector spaces.

      True

   2. True or false: a basis can be effectively constructed for all vector spaces.

      False

   3. What is the projection of $f:ℝ\to ℝ$ along $b_k\left(t\right)$ in a Hilbert space spanned by $\{b_1\left(t\right),b_2\left(t\right),..,b_k\left(t\right),..\}$?

      $(f,b_k)b_k\left(t\right)$, with $(f,g)$ denoting scalar product in the Hilbert space

   4. What is the error of a polynomial interpolant $p\left(t\right)$ of $f:ℝ\to ℝ$, sampled by $𝒟=\{(x_i,y_i=f\left(x_i\right)),i=0,\dots ,n\}$ when $t=x_i$?

      Zero

   5. What is the degree of the polynomial interpolant of data $𝒟=\{(x_i,y_i=f\left(x_i\right),y_i^{\text{'}}=f^{\text{'}}\left(x_i\right)),i=0,1\}$?

      The four conditions determine a cubic polynomial, degree=3.

2Track 2

1. Construct the Hermite interpolant of data $𝒟=\{(x_i,y_i=f\left(x_i\right),y_i^{\text{'}}=f^{\text{'}}\left(x_i\right)),i=0,1\}=\{(1,3,2),(4,-18,-25)\}$ in Newton form.

   Solution. The four conditions determine a polynomial of degree 3

   ${\displaystyle p\left(t\right)=y_0+[y_0,y_0](t-x_0)+[y_1,y_0,y_0]{(t-x_0)}^2+[y_1,y_1,y_0,y_0]{(t-x_0)}^2(t-x_1)}$

   For the repeated points

   ${\displaystyle [y_0,y_0]=y_0^{\text{'}}=2,[y_1,y_1]=y_1^{\text{'}}=-25}$ ${\displaystyle \begin{array}{llllll}i& x_i& \left[y_i\right]& [y_i,y_{i-1}]& [y_i,y_{i-1},y_{i-2}]& [y_i,y_{i-1},y_{i-3}]\\ 0& 1& 3& -& -& -\\ 0& 1& 3& 2& -& -\\ 1& 4& -18& -7& -3& -\\ 1& 4& -18& -25& -6& -1\end{array}}$

   The resulting polynomial is

   ${\displaystyle p\left(t\right)=3+2(t-1)-3{(t-1)}^2-{(t-1)}^2(t-4)}$

2. Construct the Hermite interpolant of the above data in Lagrange form.

   Solution. The Lagrange form of a first-order Hermite interpolant is

   ${\displaystyle p\left(t\right)=\sum _{i=0}^n[a_i\left(t\right)y_i+b_i\left(t\right)y_i^{\text{'}}],}$

   where $a_i\left(x_j\right)={\delta }_{ij}$, $a_i^{\text{'}}\left(x_j\right)=0$, $b_i^{\text{'}}\left(x_j\right)={\delta }_{ij}$, $b_i\left(x_j\right)=0$. A polynomial $q\left(t\right)$ has a simple root $r$ if

   ${\displaystyle q\left(r\right)=0,q^{\text{'}}\left(r\right)\ne 0,}$

   and a double root if

   ${\displaystyle q\left(r\right)=0,q^{\text{'}}\left(r\right)=0,q^{\text{'}\text{'}}\left(r\right)\ne 0.}$

   The Lagrange basis polynomials

   ${\displaystyle {\ell }_i\left(t\right)=\prod _{j=0}^n{}^{\text{'}}\frac{t-x_j}{x_i-x_j}}$

   satisfy ${\ell }_i\left(x_j\right)={\delta }_{ij}$.

   The conditions $a_i\left(x_j\right)={\delta }_{ij}$, $a_i^{\text{'}}\left(x_j\right)=0$ at $j\ne i$ state that $a_i\left(t\right)$ has $n$ double roots, $\{x_0,..,x_n\}\backslash \left\{x_i\right\}$, hence $a_i\left(t\right)$ is proportional to ${\ell }_i^2\left(t\right)$. Since $2{\ell }_i\left(t\right){\ell }_i^{\text{'}}\left(t\right)$ satisfies derivative conditions at $j\ne i$, increase degree by one for the additional derivative condition at $t=x_i$

   ${\displaystyle a_i\left(t\right)=(c_i+d_{{}_i}t){\ell }_i^2\left(t\right).}$

   Impose $a_i\left(x_i\right)=1$, $a_i^{\text{'}}\left(x_i\right)=0$ to obtain

   ${\displaystyle c_i+d_i{x}_i=1}$ ${\displaystyle a_i^{\text{'}}\left(t\right)=d_i{\ell }_i^2\left(t\right)+2(c_i+d_{i}t){\ell }_i\left(t\right){\ell }_i^{\text{'}}\left(t\right)\Rightarrow d_i+2(c_i+d_i{x}_i){\ell }_i^{\text{'}}\left(x_i\right)=0}$

   with solution

   ${\displaystyle d_i=-2{\ell }_i^{\text{'}}\left(x_i\right),c_i=1+2{\ell }_i^{\text{'}}\left(t\right)x_i,}$

   and

   ${\displaystyle a_i\left(t\right)=[1-2(t-x_i){\ell }_i^{\text{'}}\left(x_i\right)]{\ell }_i^2\left(t\right).}$

   The conditions $b_i^{\text{'}}\left(x_j\right)={\delta }_{ij}$, $b_i\left(x_j\right)=0$, state $\{x_0,..,x_n\}\backslash \left\{x_i\right\}$ are double roots and $x_i$ is a simple root, immediately satisfied by

   ${\displaystyle b_i\left(t\right)=A(t-x_i){\ell }_i^2\left(t\right).}$

   Evaluating the derivative $b_i^{\text{'}}\left(t\right)=A{\ell }_i^2\left(t\right)+2A(t-x_i){\ell }_i\left(t\right){\ell }_i^{\text{'}}\left(t\right)$ at $x_i$ gives

   ${\displaystyle b_i\left(x_i\right)=A}$

   hence $b_i^{\text{'}}\left(x_i\right)=1$ leads to $A=1$.

   For given data

   ${\displaystyle {\ell }_0\left(t\right)=\frac{t-x_1}{x_0-x_1},{\ell }_0^{\text{'}}\left(t\right)=\frac{1}{x_0-x_1},{\ell }_1\left(t\right)=\frac{t-x_0}{x_1-x_0},{\ell }_1^{\text{'}}\left(t\right)=\frac{1}{x_1-x_0}}$ ${\displaystyle a_0\left(t\right)=[1-2\frac{t-x_0}{x_0-x_1}]{\left(\frac{t-x_1}{x_0-x_1}\right)}^2,b_0\left(t\right)=(t-x_0){\left(\frac{t-x_1}{x_0-x_1}\right)}^2,}$ ${\displaystyle a_1\left(t\right)=[1-2\frac{t-x_1}{x_1-x_0}]{\left(\frac{t-x_0}{x_1-x_0}\right)}^2,b_1\left(t\right)=(t-x_1){\left(\frac{t-x_0}{x_1-x_0}\right)}^2.}$

3. Present a spline interpolant $S$ of data set $𝒟=\{(x_i=ih,y_i=f\left(x_i\right)),i=0,..,n\}$, $h=\pi /n$, where the restriction of $S$ to interval $[x_{i-1},x_i]$ is of the form

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

   Solution. There are $n$ intervals, hence $3n$ parameters $(a_i,b_i,c_i)$ to determine. At $i=1,..,n$ apply interpolation conditions

   ${\displaystyle S_i\left(x_i\right)=a_i+b_i\cos x_i+c_i\sin x_i=y_i.}$

   Add condition at $i=0$, $S_1\left(0\right)=a_1+b_1=y_0$, to define $n+1$ conditions. At $i=1,..,n-1$ continuity in derivatives

   ${\displaystyle S_i^{\text{'}}\left(x_i\right)=S_{i+1}^{\text{'}}\left(x_i\right),S_i^{\text{'}\text{'}}\left(x_i\right)=S_{i+1}^{\text{'}\text{'}}\left(x_i\right),}$

   defines another $2(n-1)$ conditions,

   ${\displaystyle -b_i\sin x_i+c_i\cos x_i=-b_{i+1}\sin x_i+c_{i+1}\cos x_i}$ ${\displaystyle -b_i\cos x_i-c_i\sin x_i=-b_{i+1}\cos x_i-c_{i+1}\sin x_i}$

   for a total of $3n-1$. One additional condition can be defined, say

   ${\displaystyle S_1^{\text{'}}\left(x_0\right)=S_n^{\text{'}}\left(x_n\right),}$

   to complete the system.

4. Find the best inf-norm approximant of $f:[0,\pi /2]\to ℝ$, $f\left(t\right)=\cos t$

   Solution. The family from which to take the approximant was not specified, hence can be freely chosen, for example a constant $g\left(t\right)=c$. By the equioscillation theorem $f\left(0\right)-g\left(0\right)=-(f\left(1\right)-g\left(1\right))$, leading to

   ${\displaystyle g\left(t\right)=\frac{1}{2}.}$

5. Quiz questions:

   1. True or false: The monomials $ℳ\left(t\right)=\{1,t,t^2,..\}$ are a basis for $C^{\infty }\left(ℝ\right)$

      False. Some functions require an infinite series, e.g., $e^t$.

   2. True or false: In a Hilbert space, Cauchy sequences converge to an element within the space

      True, by definition of a Hilbert space as a complete metric space.

   3. What is the degree of the polynomial interpolant of data $𝒟=\{(x_i,y_i=f\left(x_i\right),y_i^{\text{'}}=f^{\text{'}}\left(x_i\right),y_i^{\text{'}\text{'}}=f^{\text{'}\text{'}}\left(x_i\right)),i=0,1,2\}$?

      9 conditions, degree = 8

   4. True or false: A best inf-norm approximant within a finite subspace exists for all Banach spaces.

      True, theorem of best approximant.

   5. True or false: There are more polynomials than there are continuous functions.

      False, e.g., $e^t,\sin t,\cos t$ are not polynomials but are continuous.