Past exam of the numerical analysis course of the University of Oxford / 2017 / 1

For each interpolation node define the Lagrange cardinal polynomialAll denominators are nonzero because the interpolation nodes are distinct. Each polynomial has polynomial degree at most $n$, and ${\ell }_j(x_i)={\delta }_{ij}$, where ${\delta }_{ij}$ is the Kronecker delta. Consequently the linear combinationbelongs to the vector space of univariate polynomials ${\Pi }_n$ and has the required values. This proves existence of the Lagrange interpolation polynomial.

For uniqueness, suppose $p_n$ and $r_n$ both work. Their difference is a polynomial of polynomial degree at most $n$ with $n+1$ distinct roots of a polynomial. The root bound for a polynomial forces $p_n-r_n$ to be the zero polynomial.

The seven supplied values follow $f_i=i^2+1$. The quadratic polynomial $x^2+1$ belongs to ${\Pi }_6$ and takes all seven values, so uniqueness givesThe subscript bounds the polynomial degree; it does not require polynomial degree exactly six.

The product rule applied at the interpolation node $x_k$ givesThus Lagrange interpolation gives, away from the interpolation nodes,Apply the same Lagrange interpolation formula to the constant polynomial one. Since its interpolant is itself,Dividing the preceding two identities proves the barycentric interpolation formulaThe denominator is exactly $1/w(x)$, so is nonzero away from the interpolation nodes. At $x=x_j$, multiply numerator and denominator by $x-x_j$ and take the limit: their values tend to $w_j{f}_j$ and $w_j$, respectively. The removable singularity therefore has value $f_j$; in numerical evaluation return the stored value directly at an interpolation node.

A Newton-Cotes quadrature integrates a Lagrange interpolation polynomial at equally spaced quadrature nodes. For the Newton-Cotes closed quadrature, the endpoints are included: write $x_j=a+jh$, $h=(b-a)/n$, and useThese quadrature weights depend on the quadrature nodes, not on the sampled function. Open Newton-Cotes quadrature uses equally spaced interior quadrature nodes instead.

For Simpson's rule, use $n=2$ and set $x=a+ht$, so $0\le t\le 2$. The Lagrange cardinal polynomials becomeIntegrating these quadratic polynomials gives $1/3$, $4/3$, $1/3$, respectively. The change of variable contributes $h$, soIts degree of precision of a quadrature rule is three: it integrates every quadratic polynomial by construction, and also the cubic nodal polynomial $(x-a)(x-a-h)(x-b)$, whose integral vanishes by odd symmetry about $a+h$. Any cubic polynomial differs from its quadratic polynomial interpolant by a constant multiple of this nodal polynomial.

Read the differential order $dxdy$ literally: take quadrature nodes $X=(c,(c+d)/2,d)$ in $x$ and $Y=(a,(a+b)/2,b)$ in $y$. Applying Simpson's rule first in $x$ and then in $y$ multiplies the one-dimensional quadrature weights. With $s=(1,4,1)$, this tensor-product quadrature isEquivalently, the nine sampled function values have the quadrature weight arraywith rows indexed by the $x$ quadrature nodes and columns by the $y$ quadrature nodes. The quadrature weights sum to the rectangle's area. If the intended coordinate assignment is instead $x\in [a,b]$, $y\in [c,d]$, exchange $X$ and $Y$ in the formula. Both conventions give the same calculation on the unit square used below.

For the separable integrand, tensor-product quadrature factors into two one-dimensional applications of Simpson's rule:soThe exact double integral, evaluated by Fubini's theorem and the power rule for integration, isThe $x$ factor is always integrated exactly. All quadrature error therefore comes from applying Simpson's rule to the $y$ factor.

At $q=2$, the preceding tensor-product quadrature givesBoth factors of the separable integrand are quadratic polynomials, so exactness follows directly from the construction of Simpson's rule.

At $q=3$,The $y$ factor is now a cubic polynomial. Simpson's rule still integrates it exactly because its degree of precision of a quadrature rule is three. Exactness of tensor-product quadrature depends on the polynomial degree in each variable, rather than their sum.

At $q=4$,This is an overestimate, with signed quadrature errorThe relative error is $(1/720)/(1/30)=1/24$, approximately $4.17\%$. The quartic polynomial $y^4$ lies beyond the degree of precision of a quadrature rule of Simpson's rule, so the exactness of the previous cases no longer applies.