Present a concise formulation of the theoretical motivation of your answer, and then proceed to solve the following problems.

The specific course concept being verified in each question is listed below.

1. Consider

   ${\displaystyle S\left(x\right)=\{\begin{array}{ll}\sqrt{2}& x⩽0\\ f\left(x\right)& 0⩽x⩽1\\ 2-x& 1⩽x\end{array}..}$

   Determine $f\left(x\right)$ as the circular arc such that $S\left(x\right)$ is a spline function. With $S^{\left(k\right)}=d^{k}S/d{x}^k$ denoting the $k^{\mathrm{th}}$ derivative of $S\left(x\right)$, up to what $k$ is $S^{\left(k\right)}\left(x\right)$ continuous?

   Question.

   Course concept: understanding of spline as a piecewise interpolation with continuity up to some degree of the derivative.

   Solution. Sketch $S\left(x\right)$

   

   Circle $x^2+y^2=2$ passes through points $(0,\sqrt{2})$ and $(1,1)$, hence

   ${\displaystyle y=f\left(x\right)=\sqrt{2-x^2}}$

   Note that $S\left(0_{-}\right)=0,S\left(0_{+}\right)=-1$. Compute $y^{\text{'}}$ and obtain

   ${\displaystyle y^{\text{'}}=f^{\text{'}}\left(x\right)=-\frac{x}{\sqrt{2-x^2}},f^{\text{'}}\left(0\right)=0=S\left(0_{+}\right),f^{\text{'}}\left(1\right)=-1=S\left(0_{-}\right).}$

   Conclude that $S\left(x\right)$ exhibits continuity in derivative, $k⩾1$. Recall that second derivative indicates curvature, which a positive constant for a circle, zero for a line segment, hence $k=1$, $S\left(x\right)$ is continuous up to first derivative.

   Note: understanding the significance of a second derivative is more insightful and requires less computational effort than evaluating $y^{\text{'}\text{'}}.$

2. Recall the Chebyshev recurrence relation $T_{n+1}\left(x\right)=2x{T}_n\left(x\right)-T_{n-1}\left(x\right)$, $T_0\left(x\right)=1$, $T_1\left(x\right)=x$. Compute the zeros of $T_3\left(x\right)$ to an accuracy of 3 significant decimal digits.

   Question.

   Course concept: Chebyshev polynomial properties, need for identification of good initial approximation of a root, and understanding of quadratic convergence of Newton's method.

   Solution. Apply recurrence relation to find

   ${\displaystyle T_2\left(x\right)=2x^2-1,T_3\left(x\right)=2x(2x^2-1)-x=4x^3-3x.}$

   $T_3\left(x\right)$ has roots $x_{1,2}=\pm \sqrt{3}/2$ and $x_3=0$. To compute $\sqrt{3}$ to 3 significant digit start from initial guess

   ${\displaystyle z_0=\frac{7}{4},z_0^2=\frac{49}{16}=3+\frac{1}{16}\approx 3}$

   that is at distance $1/16<0.1$ from root, and already has two accurate significant digits $z_0\approx 1.7$. Since Newton's method to find roots of $f\left(z\right)=z^2-3$, converges quadratically, a single iteration will lead to at least three accurate significant digits. Newton's iteration is

   ${\displaystyle z_{n+1}=z_n-\frac{f\left(z_n\right)}{f^{\text{'}}\left(z_n\right)}=z_n-\frac{z_n^2-3}{2z_n}=\frac{1}{2}(z_n+\frac{3}{z_n}),}$

   and

   ${\displaystyle z_1=\frac{1}{2}(\frac{7}{4}+\frac{12}{7})=\frac{97}{56},}$

   leading to $x_{1,2}\cong \pm 97/112=0.866.$

3. Write the Lagrange form of the cubic interpolating polynomial $p_3\left(t\right)$of data

   ${\displaystyle 𝒟=\{(-\frac{\sqrt{3}}{2},0),(0,0),(\frac{\sqrt{3}}{2},0),(1,1)\}.}$

   What are the coefficients of $p_3\left(t\right)$ expressed in the monomial basis?

   Question.

   Course concept: Lagrange form, uniqueness of interpolating polynomial.

   Solution. The Lagrange form is

   ${\displaystyle p_3\left(t\right)=\sum _{i=0}^3{y}_i{\ell }_i\left(t\right)={\ell }_3\left(t\right)=\frac{(t+\sqrt{3}/2)t(t-\sqrt{3}/2)}{(1+\sqrt{3}/2)1(1-\sqrt{3}/2)}.}$

   Since the interpolating polynomial is unique and the data points contain roots and an additional point on the graph of $T_3\left(t\right)$, deduce that the monomial expansion of $p_3\left(t\right)$ is

   ${\displaystyle p_3\left(t\right)=T_3\left(t\right)=4t^3-3t.}$

4. Find $L_2\left(t\right)$, the quadratic polynomial within the set $\{L_0\left(t\right),L_1\left(t\right),L_2\left(t\right),..\}$ orthonormal with respect to the scalar product

   ${\displaystyle (f,g)=\underset{-1}{\overset{1}{\int }}f\left(t\right)g\left(t\right)dt.}$

   Question.

   Course concept: orthogonality and Gram-Schmidt process.

   Solution. Apply Gram-Schmidt to $\{1,t,t^2\}$

   Degree 0:

   ${\displaystyle L_0\left(t\right)=\frac{1}{{(1,1)}^{1/2}},(1,1)=\underset{-1}{\overset{1}{\int }}1\cdot 1dt=2\Rightarrow L_0\left(t\right)=\frac{1}{\sqrt{2}}.}$

   Degree 1:

   ${\displaystyle w\left(t\right)=t-(t,L_0)L_0,(t,L_0)=\frac{1}{\sqrt{2}}\underset{-1}{\overset{1}{\int }}tdt=0\Rightarrow w\left(t\right)=t}$ ${\displaystyle L_1\left(t\right)=\frac{w\left(t\right)}{{(w,w)}^{1/2}}}$ ${\displaystyle (w,w)=\underset{-1}{\overset{1}{\int }}t\cdot tdt=\frac{2}{3}\Rightarrow L_1\left(t\right)=\frac{t\sqrt{3}}{\sqrt{2}}}$

   Degree 2:

   ${\displaystyle w\left(t\right)=t^2-(t^2,L_0)L_0\left(t\right)-(t^2,L_1)L_1\left(t\right)}$ ${\displaystyle (t^2,L_1)=0(\mathrm{odd}\mathrm{integrand})}$ ${\displaystyle (t^2,L_0)=\frac{1}{\sqrt{2}}\underset{-1}{\overset{1}{\int }}{t}^{2}dt=\frac{2}{3\sqrt{2}}}$ ${\displaystyle w\left(t\right)=t^2-\frac{1}{3},(w,w)=\underset{-1}{\overset{1}{\int }}{(t^2-\frac{1}{3})}^{2}dt=\frac{8}{45}\Rightarrow }$
   ${\displaystyle L_2\left(t\right)=\frac{\sqrt{45}}{\sqrt{8}}(t^2-\frac{1}{3}).}$

5. The secant method to solve $f\left(x\right)=0$ can be interpreted as a modification of Newton's method

   ${\displaystyle x_{n+1}=x_n-\frac{f\left(x_n\right)}{f^{\text{'}}\left(x_n\right)}=x_n-\frac{f_n}{f_n^{\text{'}}},}$

   in which $f^{\text{'}}\left(x_n\right)\equiv f_n^{\text{'}}$ is approximated as

   ${\displaystyle f_n^{\text{'}}\cong \frac{f_n-f_{n-1}}{x_n-x_{n-1}},}$

   or the derivative of the interpolation of data $𝒟=\{(x_{n-1},f_{n-1}),(x_n,f_n)\}$. Construct another modification of Newton's method in which $f_n^{\text{'}}$ is approximated as the derivative of the interpolation of data $𝒟=\{(x_{n-2},f_{n-2}),(x_{n-1},f_{n-1}),(x_n,f_n)\}$. What is the expected order of convergence of this method?

   Question.

   Course concept: construction a numerical method using known interpolation forms.

   Solution. The interpolant of $𝒟$ in Newton form is

   ${\displaystyle p_2\left(t\right)=f_n+[f_n,f_{n-1}](t-x_n)+[f_n,f_{n-1},f_{n-2}](t-x_n)(t-x_{n-1}).}$

   Compute derivative

   ${\displaystyle p_2^{\text{'}}\left(t\right)=[f_n,f_{n-1}]+[f_n,f_{n-1},f_{n-2}](2t-(x_n+x_{n-1})).}$

   Evaluate at $t=x_n$

   ${\displaystyle f_n^{\text{'}}\cong p_2^{\text{'}}\left(x_n\right){=}_{}[f_n,f_{n-1}]+[f_n,f_{n-1},f_{n-2}](x_n-x_{n-1})}$ ${\displaystyle f_n^{\text{'}}\cong \frac{f_n-f_{n-1}}{x_n-x_{n-1}}+\frac{\frac{f_n-f_{n-1}}{x_n-x_{n-1}}-\frac{f_{n-1}-f_{n-2}}{x_{n-1}-x_{n-2}}}{x_n-x_{n-2}}(x_n-x_{n-1}).}$

   Alternatively, use Lagrange form

   ${\displaystyle p_2\left(t\right)=\sum _{k=0}^2{f}_{n-k}{\ell }_{n-k}\left(t\right)}$

   The derivative is

   ${\displaystyle p_2^{\text{'}}\left(t\right)=\sum _{k=0}^2{f}_{n-k}{\ell }_{n-k}^{\text{'}}\left(t\right)}$

   Evaluate ${\ell }_{n-k}^{\text{'}}\left(x_n\right)$

   ${\displaystyle {\ell }_n^{\text{'}}\left(x_n\right)=\frac{d}{dt}{\left[\frac{(t-x_{n-1})(t-x_{n-2})}{(x_n-x_{n-1})(x_n-x_{n-2})}\right]}_{t=x_n}=\frac{1}{(x_n-x_{n-1})(x_n-x_{n-2})}[x_n-x_{n-2}+x_n-x_{n-1}]}$ ${\displaystyle {\ell }_{n-1}^{\text{'}}\left(x_n\right)=\frac{d}{dt}{\left[\frac{(t-x_n)(t-x_{n-2})}{(x_{n-1}-x_n)(x_{n-1}-x_{n-2})}\right]}_{t=x_n}=\frac{1}{(x_{n-1}-x_n)(x_{n-1}-x_{n-2})}[x_n-x_{n-2}]}$ ${\displaystyle {\ell }_{n-2}^{\text{'}}\left(x_n\right)=\frac{d}{dt}{\left[\frac{(t-x_{n-1})(t-x_n)}{(x_{n-2}-x_{n-1})(x_{n-2}-x_n)}\right]}_{t=x_n}=\frac{1}{(x_{n-2}-x_{n-1})(x_{n-2}-x_n)}[x_n-x_{n-1}]}$

   Obtain

   ${\displaystyle f_n^{\text{'}}\cong f_n{\ell }_n^{\text{'}}\left(x_n\right)+f_{n-1}{\ell }_{n-1}^{\text{'}}\left(x_n\right)+f_{n-2}{\ell }_{n-2}^{\text{'}}\left(x_n\right)}$

   to replace $f^{\text{'}}\left(x_n\right)$ in Newton's method. Use of a higher degree interpolant implies that the expected convergence rate $p$ should be higher than secant, but lower than Newton which uses the exact $f^{\text{'}}\left(x_n\right)$, $\varphi <p<2$.