Past exam of the approximation theory and finite element methods course of the University of Oxford / 2007 (C12.2, DMAC 2489)

Assume $A$ is nonempty, as is necessary for an approximating point to exist. The reverse triangle inequality givesThus the distance from the fixed point $u$ is a continuous, indeed Lipschitz continuous, real-valued function on $A$. A continuous function on a nonempty compact set attains its minimum, so some $p\in A$ satisfiesIf empty compact sets are allowed, the printed statement needs this nonemptiness qualification.

The vector subspace contains zero, whose approximation error is $\Vert u\Vert$. For any $q$ with $\Vert q\Vert >2\Vert u\Vert$, the triangle inequality gives $\Vert u-q\Vert \ge \Vert q\Vert -\Vert u\Vert >\Vert u\Vert$, so such points cannot improve on zero.

Restrict to $K=\{q\in A:\Vert q\Vert \le 2\Vert u\Vert +1\}$. This is nonempty, closed and bounded in a finite-dimensional normed space, hence compact. The continuous function $q\mapsto \Vert u-q\Vert$ attains a minimum on $K$ by part (a). Outside $K$ its value exceeds the error at zero, so that minimizer is best on all of $A$:Completeness of the ambient space is unnecessary; compactness is used only in the finite-dimensional vector subspace.

The geometry of a strictly convex normed space proves uniqueness whenever a best approximation exists. If distinct $p_1,p_2$ both have best error $E>0$, then their two residuals have norm $E$. The defining midpoint inequality givescontradicting best approximation because the midpoint lies in $A$. If $E=0$, both approximants equal $u$.

The printed existence assertion is false for an arbitrary vector subspace. For a concrete counterexample take $B={\ell }^2$ with its strictly convex Hilbert norm, let $A=c_{00}$ be its finite-support sequences, and take $u=(2^{-j}{)}_{j\ge 1}$. Truncations in $A$ tend to $u$, so the best-error infimum is zero, but $u\notin A$ and that infimum is not attained. If the finite-dimensional assumption of part (b) is retained, it supplies existence and the argument above supplies uniqueness.

For the estimate, suppose $Y$ is a projection operator onto $A$, as needed for a finite operator norm. Since $Yp=p$,The triangle inequality and operator norm giveThe estimate actually holds without attainment: apply it with any $q\in A$ instead of $p$ and take the infimum. Its proof applies in every normed space. This is strict convexity separates uniqueness from existence in best approximation.

Write the Fourier coefficients as $c_k=(2\pi {)}^{-1}{\int }_{-\pi }^{\pi }u(t)e^{-ikt}dt$. The partial sum through frequencies $-n,\dots ,n$ is therefore a convolution withThe last expression follows by summing a finite geometric series, with its removable value $2n+1$ at zero. Periodicity and the evenness of $D_n$ giveThis also proves linearity and that the image lies in $F_n$. We use the continuous periodic function space, consistent with the premise and the displayed maximum norm.

The convolution formula gives the upper boundTo prove sharpness within continuous functions, takeIt is continuous and periodic, with norm at most one. At $x=0$, dominated convergence gives $(S_n{u}_{ϵ})(0)\to (2\pi {)}^{-1}\int |D_n|$. Hence that upper bound is the actual operator norm. Evenness yieldsThe approximating continuous signs avoid assuming that the discontinuous sign of the kernel belongs to the domain space.

Use the usual approximation-space convention $P_n=\{p:\mathrm{deg}p\le n\}$. The source's phrase “degree $n$” must include lower degrees for its later space and interpolation statements; the consequence of a literal exact-degree reading is addressed in part (d).

Order the alternating points as $x_0<\cdots <x_{n+1}$. If $q$ had strictly smaller error than $E_n$, the valueswould have the alternating signs of $(u-p)(x_j)$: the second term has magnitude strictly less than $E_n$. The intermediate value theorem would then give at least $n+1$ distinct zeros of $q-p$, one in each gap. A nonzero polynomial of degree at most $n$ cannot have that many zeros. Thus no such $q$ exists, provingThe remainder of the equioscillation theorem says that a best uniform approximating polynomial exists, is unique, and is characterized by this $n+2$-point alternating extreme-error condition. For positive error, alternation is necessary as well as sufficient. If $u$ itself lies in $P_n$, the unique best polynomial is $u$ with zero error.

Let $\omega (t)={\prod }_{r=0}^n(t-x_r)$. For $x$ not one of the nodes, put $c=(u(x)-p_n(x))/\omega (x)$ and defineThis function has zeros at the $n+1$ interpolation nodes and at the additional point $x$. Repeated Rolle's theorem gives a point $\eta$ between the outermost of these points such that $F^{(n+1)}(\eta )=0$. Since $p_n^{(n+1)}=0$ and ${\omega }^{(n+1)}=(n+1)!$,Substitution yieldsAt an interpolation node both sides are zero, so any $\eta \in [-1,1]$ gives the identity there. The assumed $C^{n+1}$ regularity permits all applications of Rolle's theorem.

Choose the nodes as the $n+1$ roots of the Chebyshev polynomial $T_{n+1}$. Its leading coefficient is $2^n$, so the monic nodal product is $\omega =2^{-n}{T}_{n+1}$. Since $|T_{n+1}|\le 1$ on $[-1,1]$, part (b) bounds this particular interpolant byThe best error cannot exceed the error of a particular member of $P_n$. ThereforeThe choice of Chebyshev roots controls the maximum of the nodal product, not the size of any individual interpolation coefficient.

The polynomial $T_6$ isSubtract its monic version from $x^6$:This has degree four and hence belongs to the usual space $P_5$. The error is $T_6/32$, with norm $1/32$ and alternating extrema at the seven points $\cos (j\pi /6)$, $j=0,\dots ,6$. Part (a), followed by uniqueness, provesand that this is the unique best approximation of degree at most five.

If “degree five” is taken literally to exclude degree four, no best approximation exists in that nonclosed class: $p+ϵx^5$ approaches the error $1/32$ as $ϵ\to 0$, but uniqueness in $P_5$ excludes attainment by any degree-five polynomial. This is why the standard at-most-degree convention matters here.

If $(u-p,q)=0$ for all $q\in A$, then for any $a\in A$ the difference $p-a$ lies in $A$ and Pythagorean theorem givesThus $p$ is best.

Conversely, if $p$ is best, then for every $q\in A$ the real quadratichas its minimum at $t=0$. Its linear coefficient must vanish, giving $(u-p,q)=0$. Hence best approximation is equivalent to orthogonality of the residual to the approximation space. The weight is positive almost everywhere, so this is a genuine positive-definite inner product on continuous functions.

For the weighted inner product, $(x^j,x^k)=1/(j+k+2)$. Start Gram-Schmidt process with the monomials and choose monic normalization:Its squared norm is $1/4-4/9+2/9=1/36$. Next $(x^2,1)/(1,1)=1/2$ andThereforeSubtracting these orthogonal projections gives orthogonality by construction; independent nonzero rescalings would give equivalent unnormalized orthogonal polynomials.

Write $p=a+bx$. orthogonality of the residual to $1,x$ givesThe first integral follows from $t=1-x^2$; for the second use $x=\sin \theta$, giving ${\int }_0^{\pi /2}{\sin }^2\theta {\cos }^2\theta d\theta =\pi /16$. The coefficient matrix has determinant $1/72$, so solving yieldsPart (a) proves this is the unique best weighted $L^2$ approximation. The weight $x$ is essential; using ordinary unweighted normal equations would give different coefficients.

The endpoint chord is $l(x)=1-x$. Since the square-root function is concave, the gap $g(x)=\sqrt{1-x}-(1-x)$ is nonnegative. Put $t=\sqrt{1-x}$ to obtain $g=t-t^2$, whose maximum is $1/4$ at $t=1/2$, or $x=3/4$.

Shift the chord upward by half that maximum. ThenThe errors at $x=0,3/4,1$ are respectively $-1/8,+1/8,-1/8$. These are three alternating extrema, so equioscillation proves optimality and uniqueness for linear polynomials. This is minimax linear approximation of a square-root endpoint profile.

Use the Taylor expansion $\sqrt{1-x}=1-x/2-x^2/8+O(x^3)$. Expanding the rational form givesMatching through degree two yields $a_0=1$, $a_1-b_1=-1/2$, and $b_1^2-a_1{b}_1=-1/8$. The last equation becomes $b_1/2=-1/8$, soThis is the $[1/1]$ Padé approximant about zero. Its pole is at four, outside the interpolation interval; its order of matching is local and does not assert uniform minimax optimality.

Let $\beta (q)$ be the centered nondimensional cubic B-spline, even and supported on $[-2,2]$. The outer cubic must be $b(2-|q|{)}^3$ to make the function and its first two derivatives vanish at the support edge. Write its inner part as $A+B{q}^2+C|q{|}^3$. Matching the value and first two derivatives at $|q|=1$ gives $A=4b$, $B=-6b$, $C=3b$. Its nonzero knot values are then $4b,b,b$, so requiring their sum to be one fixes $b=1/6$. ThusIn particular $\beta (0)=2/3$, $\beta (\pm 1)=1/6$.

With $h=1/m$, represent the spline on $[0,1]$ as $s(x)={\sum }_{j=-1}^{m+1}{c}_j\beta (x/h-j)$. There are $m+3$ unknown coefficients. interpolation at $x_i=ih$, $0\le i\le m$, givesThe natural endpoint conditions, using ${\beta }^{\prime \prime }(0)=-2$ and ${\beta }^{\prime \prime }(\pm 1)=1$, giveThese $m+3$ equations are the required matrix system: the $m+1$ interpolation rows have coefficients $(1,4,1)$ at consecutive positions and right sides $6u(x_i)$; the two endpoint rows have $(1,-2,1)$ and zero right sides. No solution of that system is required. The scaling uses $\beta (x/h-j)$, without an extra $1/h$, because normalization is by knot values rather than by integral.

The Sobolev space and norm areIn one dimension these functions have continuous representatives and well-defined endpoint traces. integration by parts gives the weak problem: find $u\in H^1(a,b)$ such that $a(u,v)=\ell (v)$ for all $v\in H^1(a,b)$, whereIndeed the integration boundary term is $-u^{\prime }(b)v(b)+u^{\prime }(a)v(a)$; substituting $u^{\prime }(a)=u(a)-A$ and $u^{\prime }(b)=B-u(b)$ gives the two positive boundary terms on the left.

If $0\notin [a,b]$, put $m={\min }_{[a,b]}{x}^2>0$. Then $a(v,v)\ge \Vert v^{\prime }{\Vert }_2^2+m\Vert v{\Vert }_2^2\ge \min (1,m)\Vert v{\Vert }_{H^1}^2$. If $0\in [a,b]$, the supplied trace inequality givesThus the form is coercive in both cases. The trace theorem and boundedness of $x^2$ give continuity of $a$ and $\ell$, and the Lax-Milgram theorem gives existence and uniqueness.

Let $V_h$ be the continuous piecewise linear space including both endpoint hat functions. Robin conditions are natural conditions and do not restrict the endpoint values of this space. The finite element problem is $u_h\in V_h$, $a(u_h,v_h)=\ell (v_h)$ for all $v_h\in V_h$. coercivity restricted to $V_h$ gives existence and uniqueness.

Expanding $u_h={\sum }_{j=0}^N{U}_j{\varphi }_j$ gives $\mathsf{A}U=F$, whereThe stiffness contribution has diagonal $2/h$ at interior nodes, $1/h$ at endpoints, and adjacent entries $-1/h$. For completeness, the weighted mass contribution has interior diagonal $2h{x}_i^2/3+h^3/15$, left endpoint diagonal $h{a}^2/3+a{h}^2/6+h^3/30$, right endpoint diagonal $h{b}^2/3-b{h}^2/6+h^3/30$, and adjacent entry $h{x}_i^2/6+h^2{x}_i/6+h^3/20$. All more distant entries vanish. The Robin contribution adds one to each endpoint diagonal.

Symmetry follows from symmetry of the bilinear form. If $V\ne 0$, nodal independence makes $v_h={\sum }_i{V}_i{\varphi }_i$ nonzero, and $V^T\mathsf{A}V=a(v_h,v_h)\ge \gamma \Vert v_h{\Vert }_{H^1}^2>0$. Thus the matrix is symmetric positive definite.

The weak equation implies $u^{\prime \prime }=x^{2}u-f\in L^2(a,b)$ in distributions, hence $u\in H^2(a,b)$. Its nodal interpolant satisfiesThese follow interval by interval: the interpolation error vanishes at both endpoints, and its derivative has mean zero, so two Poincaré inequalities apply. If $M$ and $\gamma$ are the continuity and coercivity constants, Céa's lemma givesAll constants are independent of the mesh size.

Besides $A,B,C$, set $D=(1,2)$, $E=(2,1)$ and $F=(2,2)$. The four triangles are $ABD$, $BCE$, $BDE$ and $DEF$, each of area $1/2$. The nodal function is one at $B$, zero at every other node, and affine on each triangle. The vertex conditions giveThe formulas agree on every shared edge, proving continuity.

Let $V=\{v\in H^1(\Omega ):v=0\text{ on }{\Gamma }_D\}$, with boundary values interpreted as traces. The outward unit normal on ${\Gamma }_N$ is $(-1,-1)/\sqrt{2}$, so the stated derivative condition is precisely ${\partial }_{n}u=0$. integration by parts givesThe Dirichlet boundary has positive length, so the Poincaré inequality makes the form coercive. Let $V_h\subset V$ be the continuous piecewise affine space on the four triangles. The finite element approximation satisfies the same identity for every $v_h\in V_h$.

Nodes $A,C,D,E,F$ have zero values, leaving $V_h=\mathrm{span}\{{\varphi }_B\}$. Although isolated endpoints have zero boundary measure, continuity along the Dirichlet edges forces the nodal values at $A$ and $C$ to vanish.

Write $u_h=U_B{\varphi }_B$. On $ABD,BCE,BDE$, the gradients are $(0,-1)$, $(-1,0)$ and $(-1,-1)$, respectively. ThusThe integral of an affine nodal function over a triangle equals its area times the mean of its three vertex values. Each supported triangle therefore contributes $1/6$ to $\int {\varphi }_B$, giving total $1/2$. The reduced system is $[2][U_B]=[1/2]$, and the complete nodal answer isOnly one algebraic unknown remains despite the two-dimensional domain.

Taking $w=z$ in the dual problem, and using $e^x\ge 1$, givesHence $\Vert z{\Vert }_{H^1}\le \Vert \psi {\Vert }_2$. Testing with smooth compactly supported functions identifies $-z^{\prime \prime }+e^{x}z=\psi$ in distributions. Therefore $z^{\prime \prime }\in L^2$ and $z\in H^2(0,1)$, withintegration by parts with arbitrary endpoint test values also gives the natural Neumann boundary conditions $z^{\prime }(0)=z^{\prime }(1)=0$.

Put $e_h=u-u_h$ and $w=z-I_{h}z$. Galerkin orthogonality gives $a(e_h,I_{h}z)=0$, so the dual identity becomesOn $I_i=(x_{i-1},x_i)$, $u_h^{\prime }$ is constant and $w$ is zero at both endpoints. Consequently ${\int }_{I_i}{u}_h^{\prime }{w}^{\prime }=u_h^{\prime }[w{]}_{x_{i-1}}^{x_i}=0$. Defining the element residual bygivesNo derivative-jump terms survive, because this interpolation error vanishes at every mesh node. This is the mechanism of the explicit one-dimensional dual residual bound in L2.

Two interval Poincaré inequalities give $\Vert z-I_{h}z{\Vert }_{2,I_i}\le h_i^2\Vert z^{\prime \prime }{\Vert }_{2,I_i}/{\pi }^2$: the error has zero endpoint values and its derivative has zero mean. Apply Cauchy-Schwarz inequality on each interval and then to the sum:Here ${\eta }_h^2={\sum }_i{h}_i^4\Vert R(u_h){\Vert }_{2,I_i}^2$. Taking $\psi =u-u_h$ and cancelling its norm, unless it is zero already, yieldsFor adaptive refinement, solve the discrete problem, compute ${\eta }_i^2=h_i^4\Vert R(u_h){\Vert }_{2,I_i}^2$, and stop when $(e+1){\eta }_h/{\pi }^2\le \mathrm{TOL}$. Otherwise mark intervals carrying a fixed positive fraction of ${\eta }_h^2$, bisect them, and repeat. Residual integration must be exact or have a certified upper bound if the stopping test is to certify the requested tolerance.

Use residual adaptation with a uniform-refinement safeguard, for example global bisection every second refinement, to ensure eventual termination. Discrete energy stability gives $\Vert u_h{\Vert }_{H^1}\le \Vert f{\Vert }_2$, so $\Vert R(u_h){\Vert }_2\le (1+e)\Vert f{\Vert }_2$ independently of the mesh. Thus ${\eta }_h\le h_{\max }^2(1+e)\Vert f{\Vert }_2$ tends to zero under the safeguard. Other iterations concentrate work where the residual is large.

Use $V=\{v\in H^1(0,1):v(0)=0\}$ and its continuous piecewise linear subspace $V_h=\mathrm{span}\{{\varphi }_1,\dots ,{\varphi }_N\}$. The condition at $x=1$ is natural, so the last hat function remains free. Set $u_h^0$ to the $L^2$ orthogonal projection of $u_0$ onto $V_h$: the stated $L^2$ initial data need not have nodal values.

For each $m$, find $u_h^{m+1}\in V_h$ such thatThis applies Backward Euler method to diffusion and reaction together. The step bilinear form is coercive, so each step has a unique solution.

Test with $v_h=u_h^{m+1}$ and apply $2(a-b,a)=\Vert a{\Vert }^2-\Vert b{\Vert }^2+\Vert a-b{\Vert }^2$. The exact energy identity isThe printed identity omits the last reaction contribution while explicitly describing its last term as the $H^1$ seminorm. It requires the full $H^1$ norm instead of that seminorm. With the printed seminorm its left side equals $-\Vert u_h^{m+1}{\Vert }_2^2$, rather than zero. The source reaction term forces this correction.

All terms other than the difference of successive squared norms are nonnegative. ConsequentlyThe second inequality uses contractivity of the initial orthogonal projection. No restriction relates $\Delta t$ to $h$, giving unconditional stability. The retained reaction term strengthens dissipation.

Define the mass matrix $M_{ij}={\int }_0^1{\varphi }_j{\varphi }_i$ and stiffness matrix $K_{ij}={\int }_0^1{\varphi }_j^{\prime }{\varphi }_i^{\prime }$ for $1\le i,j\le N$. With coefficient vectors $U^m$, the step system isThe matrices are symmetric, and $V^T\mathsf{A}V=\Vert v_h{\Vert }_2^2+\Delta t(\Vert v_h^{\prime }{\Vert }_2^2+\Vert v_h{\Vert }_2^2)>0$ for nonzero $V$, proving positive definiteness.

For $h=1/2$, the first basis function is the full tent at $1/2$, and the last is the half tent ending at $1$. Integration givesSince $\Delta t=2/2=1$, the requested matrix in this normalization isHere the matrix symbol $M$ is distinct from the printed integer number of time steps.