= Solution
For a <symmetric positive-definite matrix>, the <conjugate gradient method> chooses the unique point in $x_0+K_k(A,r_0)$ minimizing the <energy norm> of the error. Equivalently it minimizes $\tfrac12y^TAy-b^Ty$ on that affine space. Here $x_0=0$ and $r_0=b$.
Choose the eigenbasis orthonormally, as the <spectral theorem> permits, and write $x=\sum_i\alpha_iv_i$. By part (a), every admissible error is $p(A)x=\sum_i\alpha_ip(\lambda_i)v_i$, $\deg p\leq k$, $p(0)=1$. Orthogonality then gives
$$
\boxed{\|p(A)x\|_A^2=\sum_i\alpha_i^2\lambda_i[p(\lambda_i)]^2.}
$$
Thus the implicit CG polynomial minimizes exactly the displayed weighted sum. Strictly, the printed hypothesis that the eigenvectors are individually normalized must be supplemented by mutual orthogonality when eigenvalues repeat. Otherwise cross terms within a repeated-eigenvalue eigenspace need not vanish. An orthonormal eigenbasis always supplies the intended formulation.
If at most $\ell$ eigenvectors contribute to $x$, a polynomial with one factor $1-t/\lambda$ for each distinct contributing <eigenvalue> is admissible by step $\ell$ and makes that error zero. CG minimizes a nonnegative quantity, so $\boxed{\text{exact termination occurs in at most }\ell\text{ steps}}$.
For the last question, write $x=\alpha v_1+\beta v_2$ with eigenvalues $1,L$, $L=10^6$. The first polynomial has the form $p_1(t)=1-\eta t$. Differentiating its weighted objective gives
$$
\boxed{\eta=\frac{\alpha^2+\beta^2L^2}{\alpha^2+\beta^2L^3},\qquad p_1(1)=1-\eta.}
$$
If the high-eigenvalue component is not exceptionally small, the $L$-weighted terms dominate and $\eta\approx1/L$, so $p_1(1)\approx1-10^{-6}\approx1$: the first step mainly removes the high-eigenvalue error. This is the <spectral weighting of conjugate gradient error>. The expectation is conditional on the coefficients, not guaranteed by the two <eigenvalues> alone; if $\beta=0$, the first step instead solves the low-eigenvalue component exactly.
Back to article page
