Past exam of the numerical linear algebra and approximation course of the University of Oxford / 2008 / 3

Let $e_j=x-x^{(j)}$. The underlying Richardson iteration gives $e_j=(I-A{)}^j{e}_0$. The polynomials $1,(1-t),\dots ,(1-t{)}^k$ form a basis for polynomials of degree at most $k$. Thus writeDefine $y^{(k)}={\sum }_{j=0}^k{c}_j{x}^{(j)}$. Since the coefficients sum to one,The spectral theorem for real symmetric matrices supplies an orthonormal basis of eigenvectors. In that basis $p_k(A)$ has diagonal entries $p_k({\lambda }_i)$, soThe algebraic recombination is valid in exact arithmetic even if the original unaccelerated iterates themselves fail to converge.

Map $[a,b]$ to $[-1,1]$ by $z(r)=(2r-a-b)/(b-a)$. Since $a>0$, the normalization point $z(0)=-(a+b)/(b-a)$ lies outside that interval. The proposed Chebyshev polynomial ratio has degree $k$ and equals one at zero. On the spectral interval its maximum absolute value isThe Chebyshev minimax polynomial with exterior normalization minimizes this maximum among degree-at-most-$k$ polynomials with $p(0)=1$. One may quote the minimax property. Its reason is the alternating $k+1$ extremal values: a strictly better competitor would force their difference to have at least $k$ roots in $[a,b]$ and the additional root at zero outside it, impossible for degree at most $k$.

The paper uses a monic normalization of $T_k$ for $k\ge 1$, rather than the usual $T_k(1)=1$ convention. The common factor cancels in the ratio. With $\kappa =b/a>1$ and $q=(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$, the hyperbolic-cosine formula gives the error factor $\boxed{2q^k/(1+q^{2k})\le 2q^k}$. This tends rapidly to zero when the spectral interval is well-conditioned. If $a=b$, use $p(r)=1-r/a$ for exact one-step termination instead of the displayed interval map.

For $[a,b]=[1,2]$, $z(0)=-3$ and $\cosh \theta =3$ gives $e^{\theta }=3+2\sqrt{2}$. The normalization factors cancel, soIf the eigenvalues are known to be exactly $1,3/2,2$, use the more targeted annihilating polynomialIt equals one at zero and vanishes on the entire spectrum, so the spectral theorem gives $p_3(A)=0$. Thus $y^{(3)}=x$ in exact arithmetic. Degree three is the least degree that can vanish at all three distinct eigenvalues; a particular initial error supported on fewer eigenspaces can terminate earlier.