Past exam of the options II course of the University of Oxford / 2007 / P (Numerical Analysis)

The printed product omits the node with index zero. The correct cardinal polynomial isFor example, with two nodes zero and one, values zero and one, and both derivative data zero, the printed index range gives $L_1=1$ and its displayed interpolant is the constant one, which fails the value condition at zero. Thus the source formula cannot be proved literally.

With the corrected product, $L_k(x_j)={\delta }_{kj}$. For $j\ne k$, $L_k^2$ has a double zero at $x_j$, so both basis functions and their derivatives vanish there. At $x_k$, put $\ell =L_k^{\prime }(x_k)$. The value basis $H_k=L_k^2[1-2(x-x_k)\ell ]$ satisfies $H_k(x_k)=1$ and $H_k^{\prime }(x_k)=2\ell -2\ell =0$. The derivative basis $K_k=L_k^2(x-x_k)$ satisfies $K_k(x_k)=0$ and $K_k^{\prime }(x_k)=1$. Both have degree at most $2n+1$. Consequentlyhas every prescribed value and derivative, proving membership in the interpolation class after the required index correction. This corrected Hermite interpolant is used in the following parts.

The difference $d=p-q$ has $d(x_i)=d^{\prime }(x_i)=0$ at every node. Rolle's theorem supplies an additional zero of $d^{\prime }$ in each of the $n$ open intervals between successive nodes. Together with the $n+1$ nodal derivative zeros, these are $2n+1$ distinct zeros of $d^{\prime }$, including the two endpoints. But $d^{\prime }$ is a polynomial of degree at most $2n$, so it is identically zero. Since $d(x_0)=0$, $d$ is also identically zero.

Thus the interpolation polynomial is unique. Once $d^{\prime }=0$ identically, it indeed has arbitrarily many zeros in the open interval as requested. The initial Rolle count naturally includes the endpoints, rather than initially supplying $2n+1$ open-interval zeros. Equivalently, every node is a double root of $d$, so a nonzero difference would be divisible by the degree-$2n+2$ polynomial ${\prod }_i(x-x_i{)}^2$, exceeding its allowed degree.

Use the corrected interpolant from part (a). The error has $e(x_i)=e^{\prime }(x_i)=0$, and the chosen auxiliary function has $\varphi (x_i)={\varphi }^{\prime }(x_i)=0$ as well as $\varphi (x)=0$. There are $n+2$ distinct zeros of $\varphi$: all the nodes and the additional evaluation point. Rolle's theorem supplies $n+1$ zeros of ${\varphi }^{\prime }$ between these ordered zeros. Together with its $n+1$ nodal zeros, this gives $2n+2$ distinct derivative zeros. Repeated Rolle applications therefore give an interior $\xi$ such that ${\varphi }^{(2n+2)}(\xi )=0$.

The extra claim that $x$ itself must be a zero of ${\varphi }^{\prime }$ is false. For nodes zero and one and $f(t)=t^5$, the Hermite interpolant is $3t^3-2t^2$, so $e(t)=t^2(t-1{)}^2(t+2)$. The auxiliary function is then $\varphi (t)=t^2(t-1{)}^2(t-x)$, and ${\varphi }^{\prime }(x)=x^2(x-1{)}^2\ne 0$ at any interior evaluation point. The corrected zero count above is all that is needed.

Since $h$ has degree at most $2n+1$ and ${\pi }^2$ is monic of degree $2n+2$, differentiating the auxiliary function at the supplied $\xi$ givesHenceAt interpolation nodes the error and the prefactor are zero, so the formula remains valid there as well.

The cubic Hermite interpolant to the exponential at zero and one isIts endpoint values are one and $e$, and its endpoint derivatives are also one and $e$. The remainder formula gives $e^x-h(x)=e^{\xi }{x}^2(x-1{)}^2/24$ for an interior $\xi$. On this interval $e^{\xi }\le e$ and $x(1-x)\le 1/4$, so

Gershgorin's theorem states that every complex eigenvalue of a square matrix lies in at least one row discLet $Av=\lambda v$ with $v\ne 0$, and choose an index $i$ where $|v_i|$ is maximal. Its row equation givesDividing by the positive $|v_i|$ proves $\lambda \in D_i$. This proof applies to complex eigenvectors even when the matrix is real.

Gershgorin's second theorem states that a union of $k$ row discs separated from the union of all remaining discs contains exactly $k$ eigenvalues, counted with algebraic multiplicity. In particular a disc disjoint from every other disc contains exactly one eigenvalue. The same assertion holds for column discs by applying it to the transpose.

Assume $0<ϵ<1/4$, as implied by its stipulated smallness, and use the nontrivial matrix range $n\ge 3$. The row radii are $ϵ$ at one, $r=1/4+ϵ$ at each interior index, and $1/4$ at $n$. Since $2r<1$, all discs are disjoint. The second theorem therefore gives one eigenvalue in each disc. Each such eigenvalue is real: a nonreal eigenvalue would have its distinct complex conjugate in the same disc, contradicting its count of one. ThusThe eigenvalues are simple as well. An alternative reality argument is that a positive diagonal similarity makes this tridiagonal matrix symmetric, since its opposite off-diagonal entries have positive product.

The transpose has first radius $1/4$, interior radii $1/4+ϵ$, and last radius $ϵ$. These discs are again disjoint and each has one eigenvalue. Intersecting with the previous enclosures therefore improves the last bound toThe identification with the same last eigenvalue is justified by separation from all the other integer-centred discs.

Put $R=ϵ+\delta$. Only the first row disc changes: it now has radius $R$. The other discs keep radii $r_i=1/4+ϵ$ for $2\le i\le n-1$ and $r_n=1/4$. They remain mutually disjoint. As $R$ grows, the first disc joins an initial segment of these discs. Define $m$ as the largest index joined to it, or one if no other disc is joined. The joining condition for index $i$ isFor an interior index this starts at $\delta =i-5/4-2ϵ$, and for the final index at $\delta =n-5/4-ϵ$. Until its joining threshold, disc $i$ contains a unique real eigenvalue and retains the bound $|{\lambda }_i-i|\le r_i$.

After the first $m$ discs have joined, the second theorem places exactly $m$ eigenvalues in their union and exactly one in each remaining disc. The cluster is bounded, for instance, byand by $|z-1|\le R$ when $m=1$. The union of the actual discs is a sharper enclosure. Once discs overlap, one cannot assign one eigenvalue to each individual disc merely by its centre; the theorem counts the whole separated cluster.

The endpoint bounds printed in this part are false. Take $n=3$, $ϵ=1/100$ and $\delta =9/10$, which obey $\delta <(n-1)/2-ϵ=99/100$. The characteristic polynomial isIt has $P(101/100)=-31599/10^6<0$ and $P(5/4)=441/1600>0$, so it has a real root strictly between $1.01$ and $1.25$, outside the first printed interval. There is a unique eigenvalue in the transpose's isolated first disc of radius $1/4$, identifying it as the first eigenvalue. Similarly $P(301/100)=-40999/10^6<0$ and $P(13/4)=41/64>0$ give a root above $3.01$, violating the last printed interval. The approximate three roots are $1.02675615$, $1.94385374$ and $3.02939011$.

There is nevertheless a corrected enclosure proving the claimed reality. Under the stated condition write $R=ϵ+\delta <(n-1)/2$. The large first row disc is disjoint from the large last column disc, since their centres are $n-1$ apart and their radii are both $R$. Every eigenvalue lies both in the row union and in the column union. It cannot belong to both large discs, so it lies in at least one of the fixed small discsThese fixed discs are pairwise disjoint. At $\delta =0$ each contains one eigenvalue. Eigenvalues depend continuously, as a multiset, on the entries; throughout the connected allowed interval no eigenvalue can move between these separated fixed sets while remaining in their union. Thus each still contains one, counted with multiplicity. Complex-conjugate pairing now proves each is real. The valid conclusion isThe source's stronger width $ϵ$ at both endpoints does not persist after adding the corner entry; it was valid for the unperturbed matrix only.

The enclosure method is Complementary row and column Gershgorin isolation.