Time constraints and clasas cancellation at time of H01 did not allow a computational assignment on least squares and minimax approximation. These are important topics to explore numerically so this assignment is offered as extra credit, with 4 course points for the first three questions. These correspond to a normal homework assignment effort. An additional 3 course points are awarded to correct solution of the fourth question on the Remez algorithm. For Track 1 a solution is to be sought by computer-aided calculation, and for Track 2 a general implementation is required. The effort requried for this single question is comparable to a full homework assignment.

1Track 1

1. Apply the Gram-Schmidt process to $\{1,t,t^2\}$ to obtain the first three Legendre polynomials $P_0,P_1,P_2$, orthonormal with respect to the scalar product

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

   Show intermediate steps. Check hand calculations with symbolic integration packages.

2. Find the best approximant of $f\left(t\right)=1+\cos (\pi t)+\sin (\pi t)$ in the Hilbert space $ℱ=(C^{\infty }\left(ℝ\right),ℝ,+,\cdot )$ with scalar product and norm

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

3. Find the best inf-norm approximant by $g\left(t\right)=a+bt$ of $f\left(t\right)=1+\cos (\pi t)+\sin (\pi t)$, $f:[0,1]$.

   1. By the equioscillation theorem, the solution is a line that intersects the graph of $f$ twice such that the error $e\left(t\right)=f\left(t\right)-g\left(t\right)$ has three extrema of equal absolute value at $0,x,1$, with $e$ stationary at $t=x$. Write the four equations that arise

   2. Solve the above problem, and plot $f,g$.

4. Extra credit (3 points). Apply the Remez algorithm to Q3

2Track 2

1. Find and plot the first six members of the orthonormal basis $ℒ$ obtained from applying the Gram-Schmidt algorithm to $\{1,t,t^2,\dots \}$ with the scalar product

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

2. Find and plot the best approximants of

   ${\displaystyle f\left(t\right)=\tan \left(\frac{\pi t}{2}\right),}$

   in span$\left({ℒ}_n\right)$ for ${ℒ}_n=\{l_0\left(t\right),l_1\left(t\right),\dots ,l_n\left(t\right)\}$ and scalar product from problem 1, for $n=1,2,3,4,5,6$.

   1. First, carry out analytical computations. Symbolic computation software (Maple, Mathematica, Maxima) is allowed. Maxima is available in the SciComp@UNC virtual machine.

   2. For each $n$, form the matrix $𝑳=\left[\begin{array}{llll}{l}_0\left(𝒕\right)& l_1\left(𝒕\right)& \dots & {𝒍}_n\left(𝒕\right)\end{array}\right]\in {ℝ}^{m\times n}$ at sample points $𝒕$ within [0,1] and $m\gg n$. Solve the least squares problem

      ${\displaystyle {min}_{𝒄}||𝑳𝒄-f\left(𝒕\right)||.}$

      in the Euclidean two-norm. Plot the numerically determined approximants

      ${\displaystyle p\left(t\right){=}_{}{ℒ}_n\left(t\right)𝒄}$

      together with the analytically determined approximants, and compare.

3. Apply the Remez algorithm to find the best inf-norm approximant by a quadratic of $f:[0,1]\to ℝ$, $f\left(t\right)=\sin (\pi t)$. Establish your own convergence criteria.

4. Extra credit (3points). Implement the Remez algorithm. Use whatever root-finding routine is available within the programming environment (e.g., Roots for Julia) to solve the extrema conditions $f^{\text{'}}\left(x\right)-p^{\text{'}}\left(x\right)$ needed in the Remez algorithm.