Past exam of the Probability, statistics and options II course of the University of Oxford / 2007 / P

The printed product omits the node $x_0$: its lower index must be zero for the stated formula to hold. For example, with $n=1$, nodes $0,1$, and data $f_0=0,f_1=1,g_0=g_1=0$, the printed $L_{1,1}=1$ gives $h=1$, which fails the first value condition. Use the corrected Lagrange basis polynomialsThey satisfy $L_k(x_j)={\delta }_{kj}$. Define $H_k=L_k^2[1-2(x-x_k)L_k^{\prime }(x_k)]$ and $K_k=L_k^2(x-x_k)$. At a node with $j\ne k$, the double zero of $L_k^2$ gives $H_k(x_j)=H_k^{\prime }(x_j)=K_k(x_j)=K_k^{\prime }(x_j)=0$. At $x_k$, direct differentiation givesBoth polynomials have degree at most $2n+1$. Consequently $h={\sum }_k(f_k{H}_k+g_k{K}_k)$ has the specified values and derivatives, and is the required Hermite interpolating polynomial. The source product is retained literally in the private transcription; this solution identifies its necessary correction.

For $d=p-q$, all $d(x_i)$ and $d^{\prime }(x_i)$ vanish. Between each consecutive pair of nodes, Rolle's theorem gives one additional zero of $d^{\prime }$. Along with the $n+1$ nodal zeros, this supplies $2n+1$ distinct zeros on the closed interval. Since $d^{\prime }$ is a polynomial of degree at most $2n$, it must be the zero polynomial. Thus $d$ is constant, and $d(x_0)=0$ makes it zero. Hence the interpolating polynomial is unique.

The direct zero count includes the two endpoints; its guaranteed interior count before the degree argument is $2n-1$. After $d^{\prime }=0$ is proved, $d^{\prime }$ vanishes at every point of the open interval, so the stronger interior-zero assertion in the source follows as well. Another immediate uniqueness proof is that $d$ has a double zero at every node, so is divisible by ${\prod }_i(x-x_i{)}^2$ of degree $2n+2$, although its own degree is at most $2n+1$.

Use the corrected Hermite interpolating polynomial from part (a). The auxiliary function $\phi$ vanishes at all $n+1$ nodes and at the additional point $x$. Its derivative vanishes at all nodes, because both $e^{\prime }(x_i)$ and the derivative of ${\pi }^2$ vanish there. Rolle's theorem between the $n+2$ ordered zeros of $\phi$ gives $n+1$ further, distinct zeros of ${\phi }^{\prime }$. Thus ${\phi }^{\prime }$ has $2n+2$ distinct zeros on the closed interval. The printed phrase that these include $x$ is not generally true; the extra zeros lie in intervals between zeros of $\phi$, and ${\phi }^{\prime }(x)$ need not vanish.

Repeated application of Rolle's theorem gives ${\phi }^{(2n+2)}(\xi )=0$ for some interior $\xi$. Since $h$ has degree at most $2n+1$ and ${\pi }^2$ is monic of degree $2n+2$,Rearranging givesAt an interpolation node, both sides are zero, so the error formula extends to the whole closed interval. The false location claim about one zero is unnecessary for this result.

For nodes $0,1$ and $f(x)=e^x$, the cubic Hermite interpolating polynomial isIndeed its values at zero and one are $1,e$, and its derivatives there are also $1,e$. The Hermite interpolation error formula givessince $0\le \xi \le 1$ and $x(1-x)\le 1/4$ on $[0,1]$.

The Gershgorin circle theorem states that every complex eigenvalue of a square matrix $A$ lies in at least one closed disc $D_i=\{z:|z-a_{ii}|\le {\sum }_{j\ne i}|a_{ij}|\}$. To prove it, take a nonzero eigenvector $v$ for $\lambda$ and choose $i$ with $|v_i|$ maximal. The $i$th row of $Av=\lambda v$ givesDivision by $|v_i|>0$ proves the claim. The proof applies to real and complex matrices alike.

The second part of the Gershgorin circle theorem states that if a union of $k$ of the discs is disjoint from every remaining disc, that union contains exactly $k$ eigenvalues, counted with algebraic multiplicity. In particular, a single isolated disc contains precisely one eigenvalue. Connected components of the full union therefore carry the corresponding disc counts.

Write $q=1/4+ϵ$ and take $0<ϵ<1/4$, as intended by the small-parameter assumption. The row discs have centers $1,\dots ,n$ and radii $ϵ,q,\dots ,q,1/4$. They are pairwise disjoint because the sum of neighboring radii is below one. The second Gershgorin circle theorem places one eigenvalue in each disc. Since $A$ is real, nonreal eigenvalues occur in conjugate pairs; a disc centered on the real axis would have to contain both members, contradicting its count of one. Thus all eigenvalues are real andAlternatively, a positive diagonal change of basis symmetrizes the tridiagonal matrix, with transformed off-diagonal entries $\sqrt{ϵ}/2$, also proving reality.

The Gershgorin discs of $A^{\mathsf{T}}$ have radii $1/4,q,\dots ,q,ϵ$. They too are disjoint and have one eigenvalue each. The disc centered at $n$ therefore improves the final bound toIt selects the same eigenvalue as before because all other discs lie a fixed positive distance from the disc centered at $n$.

Assume $n\ge 3$, so the corner entry is separate from the superdiagonal. For $A(\delta )$, the row radii areThus every eigenvalue lies in the union ${\bigcup }_{i}D(i,r_i)$. The discs with centers $2,\dots ,n$ remain mutually disjoint. The expanding disc centered at one meets the disc centered at $j$ exactly when $j-1\le \delta +ϵ+r_j$.

Let $I_{\delta }=\{1\}\cup \{j\ge 2:j-1\le \delta +ϵ+r_j\}$. Then the union of discs indexed by $I_{\delta }$ contains exactly $|I_{\delta }|$ eigenvalues; every other disc contains exactly one. Every isolated eigenvalue is real by conjugation and obeys $|\lambda -j|\le r_j$. Once discs merge, the second Gershgorin circle theorem gives a bound and count for their whole component, rather than one eigenvalue per original disc. Eigenvalue branches coming from that component stay in its union, but may no longer be distinguished by individual discs. These statements describe the bounds through all merger thresholds as $\delta$ increases.

The claimed endpoint bounds with radius $ϵ$ are false for positive corner perturbations. For example, take $n=3$, $ϵ=1/1000$ and $\delta =9/10<1-ϵ$. The characteristic polynomial isThroughout $|\lambda -1|\le 1/1000$, the absolute value of the sum of its first two terms is below $0.003$, whereas $9/160=0.05625$. Hence this interval contains no root, contradicting the first requested bound. The actual eigenvalues are approximately $1.029144,1.943599,3.027257$, which also violate the last requested bound.

There is a valid real-eigenvalue conclusion with wider endpoint bounds. For $0<ϵ<1/4$ and $\delta <(n-1)/2-ϵ$, the Gershgorin discs from rows have one enlarged component on the left; the Gershgorin discs from columns have one enlarged component on the right. Each has an enlarged radius $r=\delta +ϵ<(n-1)/2$. A small disc that meets the enlarged left disc has index $j$ satisfying $j-1\le r+q<n/2$. A small disc meeting the enlarged right disc satisfies $n-j<n/2$. Thus, when $n=2m$, every disc with index at most $m$ is isolated in the column family and every disc with index at least $m+1$ is isolated in the row family. Their counts give all $n$ eigenvalues, one in each disjoint small disc, so all are real.

When $n=2m+1$, the same argument isolates the first $m$ discs in the column family and the last $m$ in the row family. It accounts for $2m$ real eigenvalues. The one remaining eigenvalue is real by conjugation, and belongs to the central small disc: the enlarged left and right discs are disjoint, and their two components can intersect only within the disc centered at $m+1$. Therefore the valid uniform bounds areThe sharper endpoint radii $ϵ$ hold in part (d) when $\delta =0$, and cannot simply be carried over to the perturbed matrix.