| course |
course_year |
question_number |
tags |
title |
year |
Numerical Analysis |
II |
96 |
II |
2015 |
Numerical Analysis |
|
Paper 4, Section II, E |
2015 |
(a) Define the $m$ th Krylov space $K_{m}(A, v)$ for $A \in \mathbb{R}^{n \times n}$ and $0 \neq v \in \mathbb{R}^{n}$. Letting $\delta_{m}$ be the dimension of $K_{m}(A, v)$, prove the following results.
(i) There exists a positive integer $s \leqslant n$ such that $\delta_{m}=m$ for $m \leqslant s$ and $\delta_{m}=s$ for $m>s$.
(ii) If $v=\sum_{i=1}^{s^{\prime}} c_{i} w_{i}$, where $w_{i}$ are eigenvectors of $A$ for distinct eigenvalues and all $c_{i}$ are nonzero, then $s=s^{\prime}$.
(b) Define the term residual in the conjugate gradient (CG) method for solving a system $A x=b$ with symmetric positive definite $A$. Explain (without proof) the connection to Krylov spaces and prove that for any right-hand side $b$ the CG method finds an exact solution after at most $t$ steps, where $t$ is the number of distinct eigenvalues of $A$. [You may use without proof known properties of the iterates of the CG method.]
Define what is meant by preconditioning, and explain two ways in which preconditioning can speed up convergence. Can we choose the preconditioner so that the CG method requires only one step? If yes, is it a reasonable method for speeding up the computation?