Past exam of the numerical linear algebra and continuous optimisation course of the University of Oxford / 2010 / A / 3

The off-diagonal Toeplitz matrix $T=A-I$ is symmetric and has row and column absolute sums bounded byFor an elementary Euclidean bound, apply the weighted Cauchy-Schwarz inequality in each row:Sum over $i$ and use both absolute-sum bounds to get $\Vert Tx{\Vert }_2^2\le r^2\Vert x{\Vert }_2^2$. ThereforeThe entry $t_1$ is unused because the diagonal of $A$ is fixed to one; including it only weakens the bound. This is the row-column bound for the matrix 2-norm.

A real symmetric matrix is positive-definite when $x^{T}Ax>0$ for every nonzero real vector $x$. The preceding matrix 2-norm bound givesThus $A$ is a symmetric positive-definite matrix, independently of the detailed positions of the nonzero entries of $t$.

An eigenvalue of $A$ is a scalar $\lambda$ for which $Az=\lambda z$ has a nonzero eigenvector. Allowing initially $z\in {\mathbb{C}}^m$, symmetry of the real matrix gives $A^{\ast }=A$, so $z^{\ast }Az$ is real. Since $z^{\ast }z>0$,This proves reality without presuming it when choosing the eigenvector. Once $\lambda$ is real, the real or imaginary part of $z$ supplies a nonzero real eigenvector.

For a unit eigenvector of $A$, $(A-I)x=(\lambda -1)x$. The matrix 2-norm bound from part (a) gives $|\lambda -1|\le 2/3$. Hence every eigenvalue lies inIn particular the condition number in the Euclidean operator norm satisfies ${\kappa }_2(A)={\lambda }_{\max }/{\lambda }_{\min }\le 5$.

The energy norm associated with this symmetric positive-definite matrix isIt is the norm induced by the inner product $⟨u,v{⟩}_A=u^{T}Av$. The conjugate gradient method minimizes this error norm over its successive affine Krylov subspaces.

The standard conjugate gradient convergence bound isHere $\kappa \le 5$, so the factor in parentheses is at most $q=(3-\sqrt{5})/2\simeq 0.381966$. Since $2q^{25}<10^{-10}$, 25 iterations suffice to reduce the energy-norm error by a factor exceeding $10^{10}$.

There are at most $m/20$ nonzero entries of $t$, and each contributes to at most two off-diagonals. Thus $A-I$ has at most $m^2/10$ nonzero entries. Initialize a matrix-vector product with the diagonal contribution $p$, which costs no arithmetic because the diagonal is one. Each off-diagonal term needs one multiplication and one addition, giving at most $m^2/5$ floating-point operations per product.

A standard conjugate gradient step adds two inner products, three vector updates and two scalar divisions, at most $10m$ further operations. Starting from $x_0=0$ makes $r_0=b$ and avoids an initial matrix-vector product; its squared norm needs $2m-1$ operations. The total for 25 steps is at mostThis supplies an explicit meaning of the paper's large-$m$ qualification. The quoted conjugate gradient convergence bound is the usual exact-arithmetic result.