These exercises focus on midterm examination preparation.

1Track 1

1. Find the polynomial of least degree that interpolates the data $𝒟=\{(x_i,y_i),i=0,1,\dots ,n\}$$=\{(3,10),(7,146),(1,2),(2,1)\}$.

   Solution. Table of divided differences

   ${\displaystyle \begin{array}{llllll}i& x_i& y_i& [y_i,y_{i-1}]& [y_i,y_{i-1},y_{i-2}]& [y_i,y_{i-1},y_{i-2},y_{i-3}]\\ 0& 3& 10& -& -& -\\ 1& 7& 146& 34& -& -\\ 2& 1& 2& 24& 5& -\\ 3& 2& 1& -1& 5& 0\end{array},}$

   leads to $p_2\left(t\right)=10+34(t-3)+5(t-3)(t-7)$.

2. Find the polynomial of least degree that interpolates the data $𝒟=\{(x_i,y_i,y_i^{\text{'}}),i=0,1,\dots ,n\}=$$𝒟=\{(3,10,14),(1,2,-6)\}$.

   Solution. Table of divided differences with repetitions

   ${\displaystyle \begin{array}{llllll}i& x_i& y_i& [y_i,y_{i-1}]& [y_i,y_{i-1},y_{i-2}]& [y_i,y_{i-1},y_{i-2},y_{i-3}]\\ 0& 3& 10& -& -& -\\ 0& 3& 10& y_0^{\text{'}}=14& -& -\\ 1& 1& 2& 4& 5& -\\ 1& 1& 2& y_1^{\text{'}}=-6& 5& 0\end{array},}$

   leads to $p_2\left(t\right)=10+14(t-3)+5{(t-3)}^2$.

3. Find the polynomial of least degree that interpolates the data $𝒟=\{(x_i,y_i,y_i^{\text{'}},y_i^{\text{'}\text{'}}),i=0,1,\dots ,n\}=$$𝒟=\left\{(1,2,-6,10)\right\}$.

   Solution. Table of divided differences with repetitions

   ${\displaystyle \begin{array}{llllll}i& x_i& y_i& [y_i,y_{i-1}]& [y_i,y_{i-1},y_{i-2}]& [y_i,y_{i-1},y_{i-2},y_{i-3}]\\ 0& 1& 2& -& -& -\\ 0& 1& 2& y_0^{\text{'}}=-6& -& -\\ 0& 1& 2& y_0^{\text{'}}=-6& y_0^{\text{'}\text{'}}=10& -\end{array},}$

   leads to $p_2\left(t\right)=2-6(t-1)+\frac{10}{2}{(t-1)}^2$.

4. Find $a,b,c,d$ such that

   ${\displaystyle S\left(x\right)=\{\begin{array}{ll}1-2x& x\in (-\infty ,-3]\\ a+bx+c{x}^2+d{x}^3& x\in [-3,4]\\ 157-32x& x\in [4,\infty )\end{array}.,}$

   is a natural spline on the $[-3,4]$ interval.

   Solution. Continuity of function conditions:

   ${\displaystyle \mathrm{at}x=-3\Rightarrow 1-2(-3)=7=a+b(-3)+c{(-3)}^2+d{(-3)}^3}$

   ${\displaystyle \mathrm{at}x=4\Rightarrow a+b\left(4\right)+c{\left(4\right)}^2+d{\left(4\right)}^3=157-32\left(4\right)=29}$

   Continuity of function derivative conditions:

   ${\displaystyle \mathrm{at}x=-3\Rightarrow -2=b+2c(-3)+3d{(-3)}^2}$

   ${\displaystyle \mathrm{at}x=4\Rightarrow b+2c\left(4\right)+3d{\left(4\right)}^2=-32.}$

   Obtain system

   ${\displaystyle \{\begin{array}{lll}a-3b+9c-27d& =& 7\\ a+4b+16c+64d& =& 29\\ b-6c+27d& =& -2\\ b+8c+48d& =& -32\end{array}.,}$

   with solution $\{a\to \frac{12763}{343},b\to \frac{5056}{343},c\to -\frac{312}{343},d\to -\frac{282}{343}\}$.

5. Apply the Gram-Schmidt algorithm to orthonormalize the function set $\{1,t,t^2\}$ with respect to the scalar product

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

   Solution. Obtain ${\phi }_0\left(t\right)=1/(1,1)=1/\sqrt{2}$. Compute $v_1\left(t\right)=t-(t,{\phi }_0){\phi }_0=t$, and bring to unit norm

   ${\displaystyle {\phi }_1\left(t\right)=t/(t,t)=\sqrt{\frac{3}{2}}t.}$

   Finally, compute

   ${\displaystyle v_2\left(t\right)=t^2-(t^2,{\phi }_1){\phi }_1\left(t\right)-(t^2,{\phi }_0){\phi }_0\left(t\right)=t^2-1/3.}$

   Normalize to obtain

   ${\displaystyle {\phi }_2\left(t\right)=v_2\left(t\right)/(v_2,v_2)=\sqrt{\frac{45}{8}}(t^2-1/3).}$

6. Let $\{{\phi }_0\left(t\right),{\phi }_1\left(t\right),{\phi }_2\left(t\right)\}$ denote the orthonormalized set found above. Find the best $2$-norm approximant $g\left(t\right)=c_0{\phi }_0\left(t\right)+c_1{\phi }_1\left(t\right)+c_2{\phi }_2\left(t\right)$ of $f\left(t\right)=\sin (\pi t/2)$ on the interval $[-1,1]$.

   Solution. Since $f$ is odd and ${\phi }_0,{\phi }_2$ are even deduce $c_0=c_2=0$. For $c_1$ compute

   ${\displaystyle c_1=({\phi }_1,f)=\frac{8}{{\pi }^2}\sqrt{\frac{2}{3}}.}$

7. As above, find the best $2$-norm approximant of $f\left(t\right)=\cos (\pi t/2)$ on the interval $[-1,1]$.

   Solution. As above, now $c_1=0$, and compute

   ${\displaystyle c_0=({\phi }_0,f)=\frac{2\sqrt{2}}{\pi },c_2=({\phi }_2,f)=\frac{2\sqrt{10}({\pi }^2-12)}{{\pi }^3}.}$

8. Find the best approximant $g\left(t\right)=\lambda t$ of $f\left(t\right)=\sin t$ on the interval $[0,\pi /2]$ in the $\infty$-norm.

   Solution. The error $e\left(t\right)=\sin t-\lambda t$ has a local extremum at $e^{\text{'}}\left(\xi \right)=\cos \xi -\lambda =0\Rightarrow \xi =\arccos \left(\lambda \right)$, and an endpoint extremum at $t=\pi /2$. Best approximant obtained when $-e(\pi /2)=e\left(\xi \right)\Rightarrow$

   ${\displaystyle \lambda \pi /2-1=\sin \xi -\lambda \xi \Rightarrow \lambda \pi /2-1=\sqrt{1-{\lambda }^2}-\lambda \arccos \left(\lambda \right).}$

   A numerical procedure can be used to to find $\lambda$, the root of the above equation.

2Track 2

1. In the limit $x_1\to x_0$ the divided difference

   ${\displaystyle f[x_0,x_1]=[y_1,y_0]=\frac{y_1-y_0}{x_1-x_0},y_i=f\left(x_i\right),i=0,1,}$

   has limit $f[x_0,x_1]\to f^{\text{'}}\left(x_0\right)$. Write and establish the validity of the finite difference form of the product rule ${(fg)}^{\text{'}}=f^{\text{'}}g+f{g}^{\text{'}}$.

   Solution. Let $y_i=f\left(x_i\right),z_i=g\left(x_i\right),w_i=(fg)\left(x_i\right)=f\left(x_i\right)g\left(x_i\right)=y_i{z}_i$. The divided difference of the product is

   ${\displaystyle (fg)[x_0,x_1]=[w_1,w_0]=\frac{w_1-w_0}{x_1-x_0}=\frac{y_1{z}_1-y_0{z}_0}{x_1-x_0}.}$

   The product derivative rule suggests

   ${\displaystyle [w_1,w_0]=[y_1,y_0]z_j+y_k[z_1,z_0],}$

   leading to

   ${\displaystyle y_1{z}_1-y_0{z}_0=(y_1-y_0)z_j+y_k(z_1-z_0),}$

   and identification $j=1$, $k=0$ and product rule

   ${\displaystyle [w_1,w_0]=[y_1,y_0]z_1+y_0[z_1,z_0],}$

   or

   ${\displaystyle (fg)[x_0,x_1]=f[x_0,x_1]g\left[x_1\right]+f\left[x_0\right]g[x_0,x_1].}$

2. Repeat the above for second order finite differences and ${(fg)}^{\text{'}\text{'}}=f^{\text{'}\text{'}}g+2f^{\text{'}}{g}^{\text{'}}+f{g}^{\text{'}\text{'}}$.

   Solution. Generalize above result to

   ${\displaystyle (fg)[x_0,x_1,x_2]=f[x_0,x_1,x_2]g\left[x_2\right]+f[x_0,x_1]g[x_1,x_2]+f[x_1,x_2]g[x_0,x_1]+f\left[x_0\right]g[x_0,x_1,x_2]}$

3. A natural cubic spline has zero curvature at the end points. Prove that of all cubic spline interpolations of data $𝒟=\{(x_i,y_i=f\left(x_i\right)),i=0,1,\dots ,n\}$, the natural spline $S\left(t\right)$ curvature two-norm is bounded by the function curvature two-norm

   ${\displaystyle \underset{x_0}{\overset{x_n}{\int }}{\left[S^{\text{'}\text{'}}\left(t\right)\right]}^{2}dt⩽\underset{x_0}{\overset{x_n}{\int }}{\left[f^{\text{'}\text{'}}\left(t\right)\right]}^{2}dt.}$

   Solution. Consider the Hilbert space $L_2[x_0,x_n]=\{f|f:[x_0,x_n]\to ℝ,\exists M\in ℝ||f||⩽M.\}$ of square integrable functions with scalar product, norm

   ${\displaystyle (f,g)=\underset{x_0}{\overset{x_n}{\int }}f\left(t\right)g\left(t\right)dt,{||f||}^2=(f,f).}$

   The above statement is rewritten as

   ${\displaystyle {||S^{\text{'}\text{'}}||}^2⩽{||f^{\text{'}\text{'}}||}^2.}$

   Let $g=f-S$ to obtain

   ${\displaystyle {||f^{\text{'}\text{'}}||}^2=(g^{\text{'}\text{'}}+S^{\text{'}\text{'}},g^{\text{'}\text{'}}+S^{\text{'}\text{'}})={||S^{\text{'}\text{'}}||}^2+{||g^{\text{'}\text{'}}||}^2+2(S^{\text{'}\text{'}},g^{\text{'}\text{'}}),}$

   and the requested inequality holds if

   ${\displaystyle (S^{\text{'}\text{'}},g^{\text{'}\text{'}})⩾0.}$

   With $S_i:[x_{i-1},x_i]\to ℝ$, $S_i\left(t\right)=a_i{(t-x_{i-1})}^3+b_i{(t-x_{i-1})}^2+m_i(t-x_{i-1})+y_{i-1}$, integrate over subintervals

   ${\displaystyle \underset{x_0}{\overset{x_n}{\int }}{S}^{\text{'}\text{'}}\left(t\right)g^{\text{'}\text{'}}\left(t\right)dt=\sum _{i=1}^n\underset{x_{i-1}}{\overset{x_i}{\int }}{S}_i^{\text{'}\text{'}}\left(t\right)g^{\text{'}\text{'}}\left(t\right)dt.}$

   (1)

   Integrate by parts

   ${\displaystyle \underset{x_{i-1}}{\overset{x_i}{\int }}{S}_i^{\text{'}\text{'}}\left(t\right)g^{\text{'}\text{'}}\left(t\right)dt={\left[S^{\text{'}\text{'}}\left(t\right)g^{\text{'}}\left(t\right)\right]}_{x_{i-1}}^{x_i}-\underset{x_{i-1}}{\overset{x_i}{\int }}{S}_i^{\text{'}\text{'}\text{'}}\left(t\right)g^{\text{'}}\left(t\right)dt,}$

   note that $S_i^{\text{'}\text{'}\text{'}}\left(t\right)=c_i$ is constant, and replace in (1) to obtain

   ${\displaystyle \underset{x_0}{\overset{x_n}{\int }}{S}^{\text{'}\text{'}}\left(t\right)g^{\text{'}\text{'}}\left(t\right)dt=\sum _{i=1}^n[S^{\text{'}\text{'}}\left(x_i\right)g^{\text{'}}\left(x_i\right)-S^{\text{'}\text{'}}\left(x_{i-1}\right)g^{\text{'}}\left(x_{i-1}\right)]-\sum _{i=1}^n{c}_i\underset{x_{i-1}}{\overset{x_i}{\int }}{g}^{\text{'}}\left(t\right)dt\Rightarrow }$

   ${\displaystyle \underset{x_0}{\overset{x_n}{\int }}{S}^{\text{'}\text{'}}\left(t\right)g^{\text{'}\text{'}}\left(t\right)dt=[S^{\text{'}\text{'}}\left(x_1\right)g^{\text{'}}\left(x_1\right)-S^{\text{'}\text{'}}\left(x_0\right)g^{\text{'}}\left(x_0\right)]+[S^{\text{'}\text{'}}\left(x_2\right)g^{\text{'}}\left(x_2\right)-S^{\text{'}\text{'}}\left(x_1\right)g^{\text{'}}\left(x_1\right)]+\dots }$

   ${\displaystyle [S^{\text{'}\text{'}}\left(x_n\right)g^{\text{'}}\left(x_n\right)-S^{\text{'}\text{'}}\left(x_{n-1}\right)g^{\text{'}}\left(x_{n-1}\right)]-\sum _{i=1}^n{c}_i[g\left(x_i\right)-g\left(x_{i-1}\right)].}$

   At nodes $g\left(x_i\right)=f\left(x_i\right)-S\left(x_i\right)=0$ due to the interpolation condition and terms cancel out giving

   ${\displaystyle \underset{x_0}{\overset{x_n}{\int }}{S}^{\text{'}\text{'}}\left(t\right)g^{\text{'}\text{'}}\left(t\right)dt=S^{\text{'}\text{'}}\left(x_n\right)g^{\text{'}}\left(x_n\right)-S^{\text{'}\text{'}}\left(x_0\right)g^{\text{'}}\left(x_0\right).}$

   For natural end conditions $S^{\text{'}\text{'}}\left(x_n\right)=S^{\text{'}\text{'}}\left(x_0\right)=0$, hence

   ${\displaystyle (S^{\text{'}\text{'}},g^{\text{'}\text{'}})=\underset{x_0}{\overset{x_n}{\int }}{S}^{\text{'}\text{'}}\left(t\right)g^{\text{'}\text{'}}\left(t\right)dt=0\Rightarrow {||f^{\text{'}\text{'}}||}^2={||S^{\text{'}\text{'}}||}^2+{||g^{\text{'}\text{'}}||}^2⩾{||S^{\text{'}\text{'}}||}^2.}$

   Note that this leads to

   ${\displaystyle {||f^{\text{'}\text{'}}||}^2={||S^{\text{'}\text{'}}||}^2+{||g^{\text{'}\text{'}}||}^2,}$

   a Pythagorean theorem, stating that the projection of $f^{\text{'}\text{'}}$ onto space of first-degree splines $S^{\text{'}\text{'}}$ is orthogonal.

4. Find $a,b,c,d$ such that

   ${\displaystyle \left|e\left(1\right)\right|=\left|e\left(0\right)\right|\Rightarrow |\cosh 1-a-b|=|1-a|\Rightarrow }$ ${\displaystyle S\left(x\right)=\{\begin{array}{ll}1-2x& x\in (-\infty ,-3]\\ a+bx+c{x}^2+d{x}^3& x\in [-3,4]\\ 157-32x& x\in [4,\infty )\end{array}.,}$

   is a natural spline on the $[-3,4]$ interval.

   Solution. See above.

5. Present an analysis of the conditioning of quadratic spline interpolation.

   Solution. The problem of quadratic spline interpolation is stated as $(𝒙,𝒚){\to }^f𝒔$, and from L21 the slope system is

   ${\displaystyle s_{i-1}+s_i=\frac{2}{h_i}(y_i-y_{i-1}),i=1,2,\dots ,n,}$

   so the problem is linear with a condition number bounded by that of the above bidiagonal matrix $𝑺$

   ${\displaystyle {\kappa }_f⩽\kappa \left(𝑺\right),𝑺=\left[\begin{array}{lllll}1& & & & \\ 1& 1& & & \\ & 1& 1& & \\ & & \ddots & \ddots & \\ & & & 1& 1\end{array}\right],𝑨={𝑺}^T𝑺=\left[\begin{array}{llllll}2& 1& & & & \\ 1& 2& 1& & & \\ & 1& 2& 1& & \\ & & \ddots & \ddots & & \\ & & & 1& 2& 1\\ & & & & 1& 1\end{array}\right].}$

   Carry out a numerical experiment.

   ∴	using SparseArrays

   ∴	function S(m) spdiagm(0 => ones(m), -1 => ones(m-1)) end;

   ∴	collect(S(8))

   ${\displaystyle \left[\begin{array}{cccccccc}1.0& 0.0& 0.0& 0.0& 0.0& 0.0& 0.0& 0.0\\ 1.0& 1.0& 0.0& 0.0& 0.0& 0.0& 0.0& 0.0\\ 0.0& 1.0& 1.0& 0.0& 0.0& 0.0& 0.0& 0.0\\ 0.0& 0.0& 1.0& 1.0& 0.0& 0.0& 0.0& 0.0\\ 0.0& 0.0& 0.0& 1.0& 1.0& 0.0& 0.0& 0.0\\ 0.0& 0.0& 0.0& 0.0& 1.0& 1.0& 0.0& 0.0\\ 0.0& 0.0& 0.0& 0.0& 0.0& 1.0& 1.0& 0.0\\ 0.0& 0.0& 0.0& 0.0& 0.0& 0.0& 1.0& 1.0\end{array}\right]}$

   (2)

   ∴	r=10:10:100; cond.(Matrix.(S.(r))) ./ r

   ${\displaystyle \left[\begin{array}{c}1.3232029812481902\\ 1.3015595822121873\\ 1.2928867470799783\\ 1.2882662782812822\\ 1.2854017106315976\\ 1.2834532213987946\\ 1.2820423475124278\\ 1.2809737095514466\\ 1.2801363174342515\\ 1.279462470845778\end{array}\right]}$

   (3)

   ∴	r=100:25:250; cond.(Matrix.(S.(r))) ./ r

   ${\displaystyle \left[\begin{array}{c}1.279462470845778\\ 1.2782407173662882\\ 1.2774198940886343\\ 1.2768304891052986\\ 1.2763867360563506\\ 1.2760405866745244\\ 1.2757630315067576\end{array}\right]}$

   (4)

   ∴	r=250:250:1000; cond.(Matrix.(S.(r))) ./ r

   ${\displaystyle \left[\begin{array}{c}1.2757630315067576\\ 1.2745070304498798\\ 1.2740858129880002\\ 1.273874725330468\end{array}\right]}$

   (5)

   The above suggests $𝑺$ has a condition number $\kappa \left(𝑺\right)=𝒪\left(m\right)$, $\kappa \left(𝑺\right)\cong 1.27m$, a well-conditioned problem.

6. Apply the Gram-Schmidt algorithm to orthonormalize the function set $\{1,t,t^2\}$ with respect to the scalar product

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

   Solution. As above, obtain Chebyshev polynomials.

7. Find the best approximant $g\left(t\right)=a+bt$ of $f\left(t\right)=\sin t$ on the interval $[0,\pi /2]$ in the 2-norm and the $\infty$-norm.

   Solution. See Midterm2 solution.

8. Prove that best inf-norm approximant of $f:[-1,1]\to ℝ$, $f\left(t\right)=\cosh \left(t\right)$ by a quadratic polynomial has form $p_2\left(t\right)=a+b{t}^2$, with $b=\cosh 1-1$. Compute $a$.

   Solution. Since $f$ is even, $p_2$ is also even, and restrict to $t\in [0,1]$. Equioscillation theorem implies that error $e\left(t\right)=\cosh t-(a+b{t}^2)$ satisfies

   ${\displaystyle }$