Linear solution techniques; CG two iterations

Linear system $[A]\{x\}=\{b\}$ is solved by:

1. Direct methods (finite number of steps, exact apart from round-off): Gauss elimination (reduce to upper triangular form, back-substitute), Gauss-Jordan, LU decomposition, Cholesky decomposition $A=LL^T$ for symmetric positive definite $A$, and the matrix inverse. In FEM they use banded or skyline storage.
2. Iterative methods (start from a guess and improve): Jacobi, Gauss-Seidel, successive over-relaxation, and the conjugate gradient method. They suit very large sparse systems since the matrix is never changed and no fill-in occurs. Jacobi and Gauss-Seidel need diagonal dominance for convergence; CG needs a symmetric positive definite matrix.

Conjugate gradient, two iterations

$A=\begin{bmatrix}12&-6&0\\-6&12&-6\\0&-6&6\end{bmatrix}$, $b=\{24,24,0\}^T$, $x_0=\{4,4,0\}^T$.

$Ax_0=\{12(4)-6(4),\,-6(4)+12(4),\,-6(4)\}=\{24,24,-24\}^T$, so

$$r_0=b-Ax_0=\{0,0,24\}^T,\quad d_0=r_0$$

Iteration 1

$$\begin{aligned} Ad_0&=\{0,-144,144\}^T\\ \alpha_0&=\frac{r_0^Tr_0}{d_0^TAd_0}=\frac{576}{3456}=0.1667\\ x_1&=x_0+\alpha_0d_0=\{4,\,4,\,4\}^T\\ r_1&=r_0-\alpha_0Ad_0=\{0,\,24,\,0\}^T\\ \beta_0&=\frac{576}{576}=1,\quad d_1=r_1+\beta_0d_0=\{0,\,24,\,24\}^T \end{aligned}$$

Iteration 2

$$\begin{aligned} Ad_1&=\{-144,\,144,\,0\}^T\\ \alpha_1&=\frac{576}{3456}=0.1667\\ x_2&=x_1+\alpha_1d_1=\{4,\,8,\,8\}^T\\ r_2&=r_1-\alpha_1Ad_1=\{24,\,0,\,0\}^T \end{aligned}$$

Answer: after two iterations $x^{(2)}=\{4,\,8,\,8\}^T$ with residual $\{24,0,0\}^T$. A third iteration gives the exact solution $x=\{8,12,12\}^T$ (the system has $n=3$ unknowns).