HW 2 for CS 4220

You may (and probably should) talk about problems with the each other, with the TAs, and with me, providing attribution for any good ideas you might get. Your final write-up should be your own.

1: Box-Cox

The Box-Cox family of transformations is sometimes used in statistics to normalize non-negative data. The transformation has the form

$$g_{\lambda }(x)=\{\begin{array}{ll}\frac{x^{\lambda }-1}{\lambda },& \lambda \ne 0\\ \log (x),& \lambda =0\end{array}$$

The obvious implementation in Julia is

Unfortunately, this is prone to large errors when $|\lambda \log x|\ll 1$, as we can see from a simple plot.

Explain why, and suggest an alternative with better error in this case, coded in the function box_cox2. You may wish to use the function expm1 in your solution (though there are other approaches as well).

If you have done this right, you should be able to recreate the plot above without the numerical artifact for small $\lambda$ values. You may find it useful to also use a log scale for the y axis.

2: Pi, see!

The following routine estimates $\pi$ by recursively computing the semiperimeter of a sequence of $2^{k+1}$-gons embedded in the unit circle.

Unfortunately, something goes catastrophically wrong with this computation in floating point.

Explain what goes wrong in this computation in floating point, and rewrite the problematic formula in pi_estimator2 to avoid the issue.

3: Norm!

Let $\mathcal{L}:{\mathcal{P}}_d\to {\mathcal{P}}_{d+1}$ be defined by

$$(\mathcal{L}p)(t)={\int }_0^{t}p(x)dx$$

In this exercise, we will consider the $L^1([-1,1])$, $L^{\mathrm{\infty }}([-1,1])$, and $L^2([-1,1])$ norms on the spaces ${\mathcal{P}}_d$; recall these are

$$\parallel p{\parallel }_1={\int }_{-1}^1|p(x)|dx$$

$$\parallel p{\parallel }_{\mathrm{\infty }}=\underset{-1\le x\le 1}{max}|p(x)|$$

$$\parallel p{\parallel }_2=\sqrt{{\int }_{-1}^1|p(x){|}^{2}dx}$$

You may also find it useful to recall that

$$|{\int }_a^{b}p(x)dx|\le {\int }_a^b|p(x)|dx$$

$L^1$ case

Argue that for the norm induced by the $L^1$ norm on ${\mathcal{P}}_d$, we have $\parallel \mathcal{L}{\parallel }_1\le 1$. You do not need to cite any regularity results to change the order of integration (everything is nice enough that the relevant results hold).

$L^{\mathrm{\infty }}$ case

Argue that for the norm induced by the $L^{\mathrm{\infty }}$ norm on ${\mathcal{P}}_d$, we have $\parallel \mathcal{L}{\parallel }_{\mathrm{\infty }}\le 1$.

$L^2$ case

For the $L^2$ case, we will express write a matrix $A$ for the operator $\mathcal{L}$ with respect to the normalized Legendre polynomials $\{q_j(x){\}}_{j=0}^d$, which form an orthonormal basis for ${\mathcal{P}}^d$ (you can take my word for this). In particular, this means that if $p(x)=\sum _{j=0}^d{a}_j{q}_j(x)$, then $\parallel p{\parallel }_2=\sqrt{\sum _{j=0}^d{a}_j^2}$, and similarly if $\mathcal{L}p(t)=\sum _{j=0}^{d+1}{b}_j{q}_j(t)$ then $\parallel \mathcal{L}p{\parallel }_2=\sqrt{\sum _{j=0}^d{b}_j^2}$.

Explain why the facts above imply that $\parallel \mathcal{L}{\parallel }_2=\parallel A{\parallel }_2$.

It turns out that as $d\to \mathrm{\infty }$, the norm of the associated $\mathcal{L}$ operator increases monotonically (and very rapidly) to a limit. Using the following Julia code for the matrix $A$ as a function of the polynomial degree $d$, give an estimate of that limit. This part does not need to be rigourous – I am asking for a computational experiment! You may find it useful to use the Julia opnorm function.

(You do not need to understand the Julia code to form $A$, but it is probably within your grasp to do so if you are curious – the Wikipedia article on Legendre polynomials has all the relevant information!)