Past exam of the approximation theory and finite element methods course of the University of Oxford

Original solutions to both sections and all six questions of the Approximation Theory and Finite Element Methods paper sat on 10 June 2010. Source: released Mathematics papers, Part C 2007 11.pdf. Question 1 gives the sharp bound for the printed functional; question 4 distinguishes the printed normal condition from the conormal condition needed for the requested symmetric variational construction. Statements are not reproduced.

Direct evaluation gives $X[1]=X[x]=X[x^2]=0$ and $X[x^3]=-13/16$. Hence the linear functional vanishes on every polynomial of degree at most two and is nonzero on every genuine cubic polynomial.

The Peano kernel theorem with order three gives $X[u]={\int }_{-1}^{1}K(t)u^{\prime \prime \prime }(t)dt$, whereThe first term comes from differentiating $(x-t{)}_{+}^2/2$ at $x=1/4$. On the integration interval this simplifies toIn particular $K\le 0$. Its L1 norm is $-\int K=-X[x^3/6]=13/96$, so the sharp bound isThe printed constant $1/12$ is false for the printed functional. The cubic $u=x^3/6$ has $\Vert u^{\prime \prime \prime }{\Vert }_{\infty }=1$ but $|X[u]|=13/96>1/12$, and it attains the corrected bound. This is an exact Peano kernel norm calculation, not an error from numerical quadrature.

A cubic spline that vanishes for $x\le 0$ and is twice continuously differentiable can be written using truncated power functions as $s(x)={\sum }_{j=0}^k{a}_j(x-jh{)}_{+}^3$. Vanishing for $x\ge kh$ imposes the four moment equations ${\sum }_j{a}_j{j}^r=0$ for $r=0,1,2,3$. Their Vandermonde matrix has rank $\min (4,k+1)$, so a nonzero coefficient vector first exists at $\boxed{k=4}$.

A normalized compact cubic cardinal B-spline isIt has nodal values $0,1/6,2/3,1/6,0$ at $0,h,2h,3h,4h$, so their sum is one. The alternating binomial coefficients meet the four moment equations, and the factor $1/6$ fixes the requested normalization.

For interpolation on $[-1,1]$, centre the translates as ${\beta }_j(x)=B_3(x/h-j+2)$, with $j=-n-1,\dots ,n+1$. Their restrictions form a basis for the cubic $C^2$ spline space on these knots. Write $S={\sum }_j{c}_j{\beta }_j$. The $2n+1$ interpolation equations areThe recurrence determines all remaining coefficients after choosing $c_{-n-1},c_{-n}$, giving exactly two free parameters. The two natural cubic spline conditions becomebecause $S^{\prime \prime }(rh)=h^{-2}(c_{r-1}-2c_r+c_{r+1})$.

For uniqueness, take the difference $s$ of two candidates. It vanishes at every knot and has $s^{\prime \prime }(\pm 1)=0$. Integrating by parts twice on each cubic piece gives ${\int }_{-1}^1(s^{\prime \prime }{)}^2=0$: terms involving $s$ vanish at the knots, and those involving $s^{\prime \prime }{s}^{\prime }$ cancel at internal knots and vanish at the endpoints. Thus $s^{\prime \prime }=0$; the remaining affine function vanishes at both endpoints and is zero. The square linear system for the coefficients is therefore nonsingular, giving existence as well as uniqueness of the natural cubic spline interpolant.

Let $e=u-p$. If $p$ minimizes the squared L2 norm error, then for any $q\in A$ the real quadratic $\Vert e-tq{\Vert }_2^2=\Vert e{\Vert }_2^2-2t(e,q)+t^2\Vert q{\Vert }_2^2$ has its minimum at $t=0$. Its derivative there is zero, giving $(e,q)=0$.

Conversely, if $e$ is orthogonal to $A$, then for every $q\in A$, $p-q\in A$ and the Pythagorean theorem for inner product spaces givesThis proves the equivalence and identifies $p$ as an orthogonal projection. It characterizes a minimizer whenever one exists; a general nonclosed vector subspace need not admit a projection for every $u$.

The orthogonal projection is $p_n={\sum }_{r=0}^n(u,{\varphi }_r){\varphi }_r$. Subtract it from $u$ and use the orthonormal basis relations to obtainThis is the requested Bessel inequality.

For the infinite tail, use completeness of the orthonormal polynomial family in the usual weighted L2 space. The relevant density facts are that continuous functions are dense for the finite measure $w(x)dx$, and the Weierstrass approximation theorem makes polynomials uniformly dense in continuous functions on the compact interval. Since $\int w<\infty$, uniform approximation also gives weighted L2 norm approximation. Parseval's identity therefore givesHere finiteness of the weight integral is also necessary for the constant polynomial to belong to the stated Hilbert space. Without completeness of the polynomial family, an additional squared component orthogonal to every polynomial would remain; Bessel inequality alone does not justify equality.

The moments are ${\int }_0^1{x}^{j+2}dx=1/(j+3)$. The Gram-Schmidt process first gives the constant ${\varphi }_0=\sqrt{3}$. Removing the constant component of $x$ gives $r_1=x-3/4$, with squared norm $1/80$, hence ${\varphi }_1=4\sqrt{5}(x-3/4)$.

For the quadratic, imposing orthogonality of $r_2=x^2+ax+b$ to one and $x$ gives $1/5+a/4+b/3=0$ and $1/6+a/5+b/4=0$. Thus $r_2=x^2-4x/3+2/5$, whose squared norm is $1/1575$. Taking positive leading coefficients, the first three orthonormal polynomials are

For $n\ge 1$, ${\varphi }_n$ is orthogonal to every polynomial in $P_{n-1}$, so $(u,{\varphi }_n)=(u-p_{n-1}^{\ast },{\varphi }_n)$. The Cauchy-Schwarz inequality givesUsing the tail identity from part (b) and shifting the index,For the stated power law and $n>1$, the decreasing-function integral test givesConsequentlyThe assumption $a>1$ is sufficient; this summation estimate itself only needs $a>1/2$.

Put $m={\min }_r|u(x_r)-q(x_r)|$ and $M={\max }_r|u(x_r)-q(x_r)|$. If the best uniform approximation had error below $m$, the values of $p_n^{\ast }-q$ would strictly alternate in sign at all $n+2$ reference points. The intermediate value theorem would give at least $n+1$ distinct roots of a polynomial of degree at most $n$, a contradiction. If $m=0$ the lower bound is immediate.

At least one reference point attains the global error maximum of $q$, so $M=\Vert u-q{\Vert }_{\infty }$. Optimality of $p_n^{\ast }$ gives the upper bound, and thereforeThis is the unequal-height version of the alternating-reference error bound.

Here the exchange point lies between adjacent reference points and has the same, positive error sign as the point it replaces. Hence the new set remains spatially ordered, and the old error at its points alternates in sign. Its magnitudes are $|h_0|$ everywhere except at $\eta$, where $M=u(\eta )-q(\eta )>|h_0|$.

Set $w_r={\prod }_{j\ne r}(z_r-z_j{)}^{-1}$. Apply the order-$(n+1)$ divided difference to $q$ and $v$; both vanish because their degrees are at most $n$. In the new alternation equations, all products $(-1{)}^r{w}_r$ have the same sign. Thus the single-point exchange in polynomial minimax approximation givesThe Remez algorithm repeatedly solves for the reference polynomial and common signed height, locates a larger error extreme, and performs an order-preserving exchange. The reference height bounds the optimum from below and the global error maximum bounds it from above. Their gap provides an optimality stopping certificate. A general implementation also needs the endpoint exchange rule when the new extreme lies outside the reference set.

For a line $p(x)=ax+b$, the error $e^x-ax-b$ is strictly convex. Its two endpoint maxima must agree, giving $a=e-1$. Its unique interior minimum is at $c=\log a\in (0,1)$. Equating its magnitude to the endpoint error givesThe errors at $0,c,1$ are respectively $E_1,-E_1,E_1$. The equioscillation theorem therefore certifies this best uniform approximation directly.

For degree above one, subtracting a general polynomial does not preserve convexity of the error. The required $n+2$ alternating extreme points include additional unknown interior points, and their derivative and equal-height equations form a coupled nonlinear problem. The simple endpoint-and-single-minimum calculation therefore does not extend as a direct higher-degree recipe.

The first-order Sobolev space is $H^1(\Omega )=\{v\in L^2(\Omega ):{\partial }_{1}v,{\partial }_{2}v\in L^2(\Omega )\}$, with derivatives understood as weak derivatives and norm squared ${\int }_{\Omega }(v^2+|\nabla v{|}^2)$.

The printed normal boundary condition must be distinguished from a conormal condition. Take $K$ symmetric positive definite, as required for the symmetric matrix requested later. Integration by parts givesThe natural boundary term contains the conormal derivative $\mathbf{n}\cdot K\nabla u$, not the ordinary normal derivative ${\partial }_{n}u$. On a smooth boundary, writing $\mathbf{t}$ for its unit tangent, the literal condition ${\partial }_{n}u=0$ leaves the term $b{\partial }_{\mathbf{t}}u$, where $b=\mathbf{n}\cdot K\mathbf{t}$. Its weak form therefore retains a boundary pairing:Here the tangential derivative of the Sobolev trace can be interpreted in $H^{-1/2}$ and paired against $H^{1/2}$ on a smooth boundary. This form is generally nonsymmetric; the requested usual symmetric energy construction does not follow from the literal boundary condition.

For an explicit failure of the claimed mean-zero compatibility, take the unit disk, $K=\mathrm{diag}(2,1)$ and $u=(x^2-y^2)[1-(x^2+y^2)/2]$. It has ${\partial }_{n}u=0$ on the circle, butThus replacing the printed normal condition by a zero conormal flux is not harmless.

For the intended zero-conormal derivative problem, the requested variational and finite element conclusions are as follows. Seek $u\in H^1(\Omega )$ withPutting $v=1$ gives ${\int }_{\Omega }f=0$. On a connected domain this condition permits a solution unique modulo constants; the Poincare-Wirtinger inequality gives coercivity after fixing the mean.

The energy is $J(v)=\frac{1}{2}a(v,v)-\ell (v)$. A minimizer satisfies $\frac{d}{dt}J(u+tv){|}_{t=0}=a(u,v)-\ell (v)=0$. Conversely, a weak solution satisfiesso it is a minimizer. Testing by $u$ gives the minimum valueThis value is independent of the arbitrary additive constant when $\int f=0$. If the compatibility fails, constant shifts make $J$ unbounded below.

Write $u_h={\sum }_j{c}_j{\varphi }_j$. The Galerkin method givesSymmetry of $K$ gives $A^T=A$. For $v_h={\sum }_j{z}_j{\varphi }_j$, $z^{T}Az={\int }_{\Omega }\nabla v_h\cdot K\nabla v_h\ge 0$. Equality forces $v_h$ constant by positive definiteness and connectedness. Since the basis sums to one, the coefficient vector $1=(1,\dots ,1{)}^T$ represents that constant, givingThus the stiffness matrix is symmetric positive semidefinite and singular; the displayed compatibility condition is necessary and sufficient for the finite system. Positive definiteness of $K$ controls every gradient direction, preventing additional zero-energy directions and supplying ellipticity. A degenerate coefficient can introduce further kernel modes, while an indefinite one destroys the minimizing-energy argument.

Take the affine trial space $V_1=\{v\in H^1(a,b):v(a)=1\}$ and the test space $V_0=\{v\in H^1(a,b):v(a)=0\}$. Multiplication by $v\in V_0$ and integration by parts incorporate the right Neumann boundary condition as a load:For the continuous piecewise-quadratic trial space, impose the left value exactly and use the same equation for every piecewise-quadratic test function vanishing at $a$. With a basis $({\psi }_j)$ of that test space and $u_h=1+{\sum }_j{c}_j{\psi }_j$, the finite element equations areThe Endpoint Poincaré inequality, reflected about the interval midpoint, makes the derivative norm a norm on $V_0$. Galerkin orthogonality then gives the exact best-approximation identity: for every admissible $v_h$,Therefore $u_h$ minimizes the derivative error over all admissible piecewise-quadratic functions.

To prove the requested error bound, assume $f\in H^1(a,b)$. Then $u\in H^3(a,b)$ and $u^{\prime \prime \prime }=-f^{\prime }$. We need an elementary Poincare-Wirtinger inequality on each element $I$ of length $h_I$: if $w\in H^1(I)$ has mean zero, its continuous representative has a zero somewhere, and the fundamental theorem of calculus and Cauchy-Schwarz inequality give $\Vert w{\Vert }_{L^2(I)}\le h_I\Vert w^{\prime }{\Vert }_{L^2(I)}$.

Choose an affine function $q_I$ whose slope is the average of $u^{\prime \prime }$ on $I$ and whose average equals the average of $u^{\prime }$. Then $w=u^{\prime }-q_I$ and $w^{\prime }=u^{\prime \prime }-q_I^{\prime }$ both have mean zero. Applying the just-proved bound twice yieldsDefine a quadratic interpolant on $I$ by integrating $q_I$ from the true left-endpoint value. The equal-average condition ensures that it reaches the true right-endpoint value, so these pieces join to an admissible continuous piecewise-quadratic function $I_{h}u$. Sum the squared estimates and use the best-approximation property:Only the maximum element length is used; equal spacing is unnecessary.

For the Aubin–Nitsche duality argument, let $e=u-u_h$ and solve $-z^{\prime \prime }=e$, $z(a)=0$, $z^{\prime }(b)=0$. Explicitly $z^{\prime }(x)={\int }_x^{b}e(t)dt$, so $\Vert z^{\prime \prime }{\Vert }_2=\Vert e{\Vert }_2$. Integration by parts and Galerkin orthogonality givewhere $J_{h}z$ is its nodal piecewise-linear interpolant, which belongs to the quadratic test space. On each element $(J_{h}z{)}^{\prime }$ is the average of $z^{\prime }$, so the same mean-zero inequality gives $\Vert z^{\prime }-(J_{h}z{)}^{\prime }{\Vert }_2\le h\Vert z^{\prime \prime }{\Vert }_2$. Canceling $\Vert e{\Vert }_2$ when nonzero proves the additional order:

The bilinear square finite element contains the terms $1,x,y,xy$. In anticlockwise corner order beginning at $(0,0)$, its shape functions areThe mass matrix has entries $M_{ij}={\int }_0^h{\int }_0^h{N}_i{N}_{j}dxdy$. Each product separates into one-dimensional factors, with ${\int }_0^1(1-s{)}^{2}ds={\int }_0^1{s}^{2}ds=1/3$ and ${\int }_0^{1}s(1-s)ds=1/6$. Diagonal, adjacent-corner and opposite-corner entries are respectively $h^2/9$, $h^2/18$, $h^2/36$. ThusNumber global grid nodes by $k=i+(n+1)j$, with $x_i=ih$, $y_j=jh$ and $0\le i,j\le n$. For an interior node, four elements contribute to its diagonal, two to each axial neighbour and one to each diagonal neighbour. Its global row therefore has the nine-point stencilIn the stated ordering the axial entries occur at columns $k\pm 1$ and $k\pm (n+1)$; the four diagonal ones occur at $k\pm (n+1)\pm 1$. No boundary degrees of freedom have been removed.

For general valid quadrilaterals, use an isoparametric finite element. Map the unit square to an element by $F(\xi ,\eta )={\sum }_{i=1}^4{\mathbf{x}}_i{N}_i(\xi ,\eta )$ and define physical shape functions $N_i\circ F^{-1}$. Require a one-to-one nondegenerate map and compatible common edges. On a shared edge the map and the trace of each shape function are linear between the same endpoints; the neighbouring traces therefore agree. The assembled functions are continuous and lie in $H^1$, giving a conforming finite element space. On a non-parallelogram the pulled-back functions are generally not bilinear polynomials in the physical coordinates themselves.

Define the Lagrange cardinal polynomialsDistinct nodes make every denominator nonzero. At $x_s$ these polynomials satisfy ${\ell }_r(x_s)={\delta }_{rs}$, so the Lagrange interpolation polynomial isIt has degree at most $n$ and takes the prescribed data values. If two such polynomials existed, their difference would have $n+1$ distinct roots but degree at most $n$, forcing that difference to be zero. This also proves uniqueness.

With $w_s=1/{\pi }_{n,s}(x_s)$, the Lagrange interpolation polynomial can be written, away from its nodes,Apply the same formula to the constant data $u_s=1$. Uniqueness of polynomial interpolation gives ${\sum }_s{\ell }_s=1$, and henceDivide the two identities to obtain the barycentric interpolation formulaAt $x=x_r$, use the continuous limiting value $u_r$. Multiplying every weight by the same nonzero constant cancels between numerator and denominator, so only relative weights are needed in computation.

For uniformly spaced nodes,There are $n-s$ negative factors, coming from $j>s$. Thus the weights fixed by part (b) satisfy this formula exactly. The printed sign $(-1{)}^s$ agrees for even $n$; for odd $n$ it differs by the common factor $-1$. Rescaling all weights by $(-1{)}^n$ gives the printed convention without changing the barycentric interpolation formula.

For even $n$, the required magnitude isStirling's formula givesThus central weights are exponentially larger in magnitude than endpoint weights. Their alternating signs can cause severe cancellation in polynomial interpolation at equispaced nodes; they reflect the unfavorable high-degree interpolation geometry associated with Runge's phenomenon. A barycentric evaluation formula improves the implementation but does not remove the intrinsic sensitivity or guarantee convergence for every smooth function. The comparison with the bounded relative weights at Chebyshev-Lobatto nodes is decisive.

Use the Chebyshev polynomial identities $T_0=1$, $T_1=x$, and $T_{j+1}=2x{T}_j-T_{j-1}$. Induction shows that $T_j$ has degree $j$ with leading coefficient $2^{j-1}$ for $j\ge 1$. The trigonometric definition also givesThereforeThe leading coefficient is $2^{1-n}{n}^{-1}\cdot n{2}^{n-1}=1$, and the degree is $n+1$. The endpoints are roots through $x^2-1$; the other $n-1$ points $\cos (s\pi /n)$ are roots through $T_n^{\prime }$. They are distinct, so this monic polynomial is exactly ${\pi }_n$.

Differentiating the product ${\pi }_n(x)=(x-x_s){\pi }_{n,s}(x)$ at $x_s$ gives ${\pi }_n^{\prime }(x_s)={\pi }_{n,s}(x_s)=w_s^{-1}$. For an interior node, differentiate the trigonometric form using $d/dx=-(\sin \theta {)}^{-1}d/d\theta$:At ${\theta }_s=s\pi /n$, this is $2^{1-n}n(-1{)}^s$. At either endpoint, taking the limit makes the two terms equal, doubling the value: ${\pi }_n^{\prime }(x_s)=2^{2-n}n(-1{)}^s$ for $s=0,n$.

After removing the common factor $2^{n-1}/n$, the barycentric interpolation formula therefore usesThese Chebyshev-Lobatto node weights differ in magnitude by only a factor of two.

Let $t_1,\dots ,t_m$ be the distinct roots in $(0,1)$ at which ${\varphi }_r$ changes sign, and put $q(x)={\prod }_{j=1}^m(x-t_j)$. Both ${\varphi }_r$ and $q$ change sign at each such point, while roots of even multiplicity do not change sign. Consequently ${\varphi }_{r}q$ has one constant sign on $(0,1)$ except at its zeros, and is not identically zero. Its integral cannot vanish.

If $m<r$, however, orthogonality of the monic orthogonal polynomial ${\varphi }_r$ to every polynomial of lower degree gives $({\varphi }_r,q)=0$, a contradiction. Hence $m\ge r$. Since $\mathrm{deg}{\varphi }_r=r$, there must be exactly $r$ such roots, each of multiplicity one. They exhaust the degree, leaving no complex, exterior, or endpoint roots. Thus all roots are simple and lie strictly in $(0,1)$, which proves the requested weaker inclusion in $[0,1]$. This is the sign-change proof of the zeros of orthogonal polynomials theorem.