Lab assignment 3: Due Friday April 13, 18:00 EST

• The weight of this assignment is double the usual lab assignment.
• This assignment invokes the outcome of Assignment 4 Question 1.
• Potentially useful reference: Lebesgue constants

Background material

Lagrange interpolation

Recall that the Lebesgue constants for Lagrange interpolation are defined as $$ \|L_n\| = \sup_{f\in C([a,b])} \frac{\|L_nf\|_\infty}{\|f\|_\infty} , $$ where $L_nf\in\mathbb{P}_n$ is the Lagrange interpolation polynomial for $f$, associated to the given set of (distinct) nodes $x_0,\ldots,x_n$. The Lebesgue constants are of importance because

• We have $$ \|f-L_nf\|_\infty\leq(1+\|L_n\|)\inf_{q\in\mathbb{P}_n}\|f-q\|_{\infty} , $$ which gives information on how the interpolation compares to the minimax approximation, and how we can use the theory of minimax approximation (Jackson's theorem, Taylor expansions, etc.) to derive error estimates for interpolation.
• $\|f-L_nf\|_\infty\to0$ as $n\to\infty$ implies that $\sup_n\|L_n\|<\infty$. So if the Lebesgue constants are not uniformly bounded, there is a function $f\in C([a,b])$ such that $L_nf\not\to f$ as $n\to\infty$.
• A large Lebesgue constant would indicate numerical instability (i.e., amplification of round-off errors).

In Assignment 4 Question 1a, we show that \begin{equation} \|L_n\| = \max_{x\in[a,b]} \sum_{k=0}^n |\phi_{n,k}(x)| , \qquad\qquad(*) \end{equation} where $\phi_{n,k}$ is the $k$-th Lagrange basis function associated to the nodes $x_0,\ldots,x_n$.

Least-squares approximations

Now consider the inner product and the corresponding norm $$ \langle f,g\rangle = \int_a^b f(x) g(x) w(x) dx , \qquad \textrm{and} \qquad \|f\| = \sqrt{\langle f,f\rangle} , $$ respectively, for functions defined on $(a,b)$, where $w\in C((a,b))$ is a (positive) weight function. For $f\in C((a,b))$ with $\|f\|<\infty$, let $S_nf\in\mathbb{P}_n$ be the least-squares approximation of $f$ with respect to the norm $\|\cdot\|$, i.e., $S_nf$ is the orthogonal projection of $f$ onto $\mathbb{P}_n$. Then the Lebesgue constant for the least-squares approximation is $$ \|S_n\| = \sup_{f\in C([a,b])} \frac{\|S_nf\|_\infty}{\|f\|_\infty} . $$ In terms of the Lebesgue constants, we have the error estimate $$ \|f-S_nf\|_\infty\leq(1+\|S_n\|)\inf_{q\in\mathbb{P}_n}\|f-q\|_{\infty} , $$ for the least-squares approximations, and other results analogous to those for interpolation. Given a sequence $\phi_0,\phi_1,\ldots$ of polynomials, such that $\{\phi_0,\ldots,\phi_n\}$ is an orthonormal basis of $\mathbb{P}_n$ with respect to the inner product $\langle\cdot,\cdot\rangle$ for each $n$, we have $$ S_nf = \sum_{k=0}^n \langle f,\phi_k\rangle\phi_k . $$ In this context, $S_nf$ is also called a truncation of the series of $f$ in terms of the polynomials $\{\phi_k\}$. For example, we can talk about Legendre truncation or Chebyshev truncation, depending on the polynomials under consideration.

For Chebyshev truncation, we have derived in class that \begin{equation} \|S_n\| = \int_0^\pi \Big|\frac{\sin((n+\frac12)\theta)}{2\sin(\frac12\theta)}\Big| d\theta .\qquad\qquad(**) \end{equation} In Assignment 4 Question 1b, we derive an expression of the form \begin{equation} \|S_n\| = \int_{-1}^1 \Big|\sum_{k=0}^na_kP_k(x)\Big| dx ,\qquad\qquad(\dagger) \end{equation} for the Lebesgue constants of the Legendre truncation, where $P_k$ are the Legendre polynomials.

Numerical integration

Finally, consider the quadrature formula $$ Q_n(f) = \sum_{k=0}^n \omega_kf(x_k) , $$ that is meant to approximate the integral $$ I(f) = \int_a^b f(x) w(x) dx , $$ where $w>0$ is a given weight function. Assuming that $Q_n(f)=I(f)$ for $f\in\mathbb{P}_m$, we can derive the error estimate $$ |Q_n(f)-I(f)| \leq (\|I\|+\|Q_n\|) \inf_{q\in\mathbb{P}_m}\|f-q\|_{\infty} , $$ where $$ \|I\| = \sup_{f\in C([a,b])} \frac{|I(f)|}{\|f\|_\infty} = \int_a^b w(x) dx , $$ and $$ \|Q_n\| = \sup_{f\in C([a,b])} \frac{|Q_n(f)|}{\|f\|_\infty} . $$ Therefore $\|Q_n\|$ plays the role of Lebesgue constants for quadrature formulas. It is easy to see that $\|Q_n\|=\|I\|$ if the weights $\omega_k$ are positive and the degree of exactness satisfies $m\geq0$. So the constants $\|Q_n\|$ may potentially grow with $n$ only if negative weights occur in the quadrature formula.

In Assignment 4 Question 1c, for interpolatory quadrature with the nodes $x_0,\ldots,x_n$, for approximating the integral over $(a,b)$ with weight $w(x)=1$, we show that \begin{equation} \|Q_n\| = \sum_{k=0}^n |\omega_k| = \sum_{k=0}^n \Big| \int_a^b\phi_{n,k}(x) dx\Big| ,\qquad\qquad(\dagger\dagger) \end{equation} where $\phi_{n,k}$ is the $k$-th Lagrange basis function associated to the nodes $x_0,\ldots,x_n$.

Exercises

1. For Chebyshev interpolation (cf. ($*$)), the function $$ \lambda_n(x)=\sum_{k=0}^n |\phi_{n,k}(x)| , $$ takes its maximum at $x=\pm1$, so in order to compute the Lebesgue constant $\|L_n\|$, we only need to be able to evaluate the Lagrange coefficients $\phi_{n,k}$. Plotting the graph (of a function) of $\|L_n\|$ against $n$, experimentally determine the constant $C$ in the assumed dependence $\|L_n\|=C\log n$.
2. For interpolation with equidistant nodes, the function $\lambda_n$ as above achieves its maximum in the 'outermost' subintervals, that is, in the intervals $(x_0,x_1)$ and $(x_{n-1},x_n)$. So in order to compute the Lebesgue constant $\|L_n\|$, we need to locate one of the global maximums. Implement the Newton-Raphson or another rootfinding method and apply it to the derivative $\lambda_n'$ to complete this task. One possible initial guess is to start at the midpoint of the interval $(x_0,x_1)$. Make sure that the method converges to the desired zero of $\lambda_n'$. Plot the graph (of a function) of $\|L_n\|$ against $n$, and experimentally confirm the law $\|L_n\|\sim2^n$.
3. To compute the Lebesgue constants for Chebyshev truncation, we need to evaluate the integrals ($**$). Design and implement composite trapezoidal or Simpson's rule for this task. When you design the quadrature rule, make sure that you take into account the behaviour of the integrand, which is very 'irregular' because of the absolute value sign, especially for large $n$. For example, one could choose the subintervals of the composite quadrature rule to be aligned with the zeroes of the integrand. Plotting the graph (of a function) of $\|S_n\|$ against $n$, experimentally determine the constant $C$ in the assumed dependence $\|S_n\|=C\log n$.
4. Design and implement a quadrature rule for the integrals ($\dagger$), to compute the Lebesgue constants for Legendre truncation. Plotting the graph (of a function) of $\|S_n\|$ against $n$, experimentally determine the constant $C$ in the assumed dependence $\|S_n\|=C\sqrt n$.
5. We want to show some evidence that for Newton-Cotes formulas, $\|Q_n\|$ grows with $n$. This would indicate that $Q_n(f)\not\to I(f)$ as $n\to\infty$. Design and implement a procedure to compute the weights $\omega_k$, and therefore the ``Lebesgue constant'' $\|Q_n\|$ for the Newton-Cotes formula with $n+1$ nodes, for the interval, say $[0,1]$. This can be done by a quadrature rule for the integrals in ($\dagger\dagger$), or by solving a Vandermonde type system. If you choose the latter, make sure that you do not run into a numerical instability problem due to the conditioning of the matrices. Plotting the graph (of a function) of $\|Q_n\|$ against $n$, make a guess on the functional dependence of $\|Q_n\|$ on $n$.

How and what to submit

• Include theory and commentaries in your Jupyter notebook, by using Markdown cells.
• Notebooks without sufficient commentaries will not be accepted.
• You can update your notebook up to the time limit, but please do not commit any overdue updates.

• [Math 387 Lab 3] Yourname