Week 9 Self check questions and solutions

Question 1:

Let \(f\) be a function defined on the interval \([a,b]\). Let \(x_k\in [a,b]\), \(k=0,\dots,n\) with \(x_i \neq x_j\) for all \(i\neq j\). Write down the Lagrange interpolation polynomial \(p\) of degree \(n\) that interpolates \(f\) in the points \(x_k\).

Solution

We define

\[ L_k(x)=\prod_{j=0,\dots, n, j\neq k} \frac{(x-x_j)}{(x_k-x_j)}. \]

Then

\[ p(x)=\sum_{k=0,\dots,n} f(x_k)L_k(x). \]

Question 2:

State the general form of Newton-Cotes quadrature rules.

Solution

For a general Newton-Cotes formula consider the interpolation points \(x_j=a+jh\), \(j=0,\dots,n\) with \(h=(b-a)/n\). Let \(p_n\) be the corresponding Lagrange polynomial

\[ p_n(x)=\sum_{j=0}^nf(x_j)L_j(x) \]

for interpolating \(f\) at these points. Then the Newton-Cotes formula takes the form

\[ I(f)\approx \sum_{j=0}^nf(x_j)\omega_j,~\omega_j=\int_a^bL_j(x). \]

Question 3:

Explain the Runge phenomenon and state how it can be prevented.

Solution

Let \(p_n(x)\) be the Lagrange interpolation polynomial of a continuous function \(f\) in the interval \([-1,1]\). The Runge phenomenon states that as \(n\rightarrow\infty\) the error \(\max_{x\in[-1,1]}|f(x)-p_n(x)|\) may diverge to infinity for certain functions. The problem can be solved by using Chebychev points in \([-1,1]\) instead of equispaced points.

Question 4:

Explain why Newton-Cotes rules of increasing order will in general not converge to the exact integral of a function.

Solution

Since Newton-Cotes quadrature is based on interpolation in equispaced points the Runge phenomenon applies as well, preventing convergence as the order is increased.

Question 5:

A quadrature formula on the interval \([-1,1]\) uses the quadrature points\ \(x_0=-\alpha\), \(x_1=\alpha\), where \(0<\alpha\leq 1\).

\[ \int_{-1}^1f(x)dx\approx w_0f(-\alpha)+w_1f(\alpha). \]

The formula is required to be exact whenever \(f\) is a polynomial of degree \(1\). Show that \(w_0=w_1=1\), independent of the value of \(\alpha\). Show also that there is one particular value of \(\alpha\), such that the formula is exact also for all polynomials of degree \(2\). Find this \(\alpha\), and show that, for this value, the formula is also exact for all polynomials of degree \(3\).

Solution:

In order to integrate constant functions exactly we require

\[ \int_{-1}^11dx = 2 = w_0+w_1. \]

To integrate the linear function \(x\) exactly we require

\[ \int_{-1}^1xdx = 0 = -\alpha w_0+\alpha w_1. \]

Hence, \(w_0=w_1\) and since \(w_0+w_1=2\) we have \(w_0=w_1=1\) independently of \(\alpha\). For quadratic functions we need

\[ \int_{-1}^1x^2dx = \frac{2}{3}= 2\alpha^2, \]

and therefore \(\alpha=\frac{1}{\sqrt{3}}\). For \(x^3\) we have

\[ 0 = \int_{-1}^1x^3dx = -\alpha^3+\alpha^3. \]

Hence, also cubic functions are integrated exactly by this quadrature rule.

Question 6: Consider the integral \(I(f):=\int_a^bf(x)dx\). Assume that we want to approximate \(I(f)\) by a Newton-Cotes quadrature rule of the form \(I_2(f):=\omega_0f(a)+\omega_1f((a+b)/2)+\omega_2f(b)\). Derive the corresponding weights \(\omega_0\), \(\omega_1\), and \(\omega_2\).

Solution:

Let \(x_0 = a\), \(x_1 = \frac{a+b}{2}\), \(x_2 = b\). We have

\[\begin{split} \begin{aligned} \omega_0 &= \int_a^b\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}dx\nonumber\\ & = \int_{-1}^1\frac{t(t-1)}{2}\frac{b-a}{2}dt\nonumber\\ & = \frac{b-a}{6}. \end{aligned} \end{split}\]

We now use the symmetry of Newton-Cotes rules to derive that \(\omega_2 = \omega_0 = \frac{b-a}{6}\). Since the sum of all weights must be \((b-a)\) we obtain \(\omega_1 = \frac{4(b-a)}{6}\).