Solving Linear equations using Conjugate gradient method

Question

Given this two linear equations $$\begin{cases} 3x-y=1 \\ -{ x }+2y=-1 \end{cases}\\ $$

How can this system be solved iteratively with the Conjugate Gradient method?

Answer 1

Following the algorithm on Wikipedia, we need to pick a starting vector $\boldsymbol x_0$. Typical choices would be $ \boldsymbol0$ or the RHS $\boldsymbol b$. Let's go for convenience with $ \boldsymbol x_0 = \boldsymbol0$. Consequently, $\boldsymbol r_0 =\boldsymbol b - A \boldsymbol x_0 = \boldsymbol b = \boldsymbol p_0 $.

Now compute the steplength $$\alpha_0 = \frac{\boldsymbol r_0^T \boldsymbol r_0}{\boldsymbol p_0^T A \boldsymbol p_0} = \frac{\boldsymbol b^T \boldsymbol b}{\boldsymbol b^T A \boldsymbol b}= \frac{2}{7}$$ Update current iterate $$\boldsymbol x_1 = \boldsymbol x_0 + \alpha_0 \boldsymbol p_0 = \boldsymbol 0 + \frac27 \boldsymbol b = \begin{pmatrix} 2/7 \\ -2/7 \end{pmatrix}$$ Compute next residual $$ \boldsymbol r_1 = \boldsymbol r_0 - \alpha_0 A \boldsymbol p_0 = \begin{pmatrix} -1/7 \\ -1/7 \end{pmatrix}$$ and step length of the search direction $$\beta_0 = \frac{\boldsymbol r_1 ^T \boldsymbol r_1}{\boldsymbol r_0^T \boldsymbol r_0} = \frac{1}{49}$$ Then, update the search direction as $$ \boldsymbol p_1 = \boldsymbol r_1 + \beta_0 \boldsymbol p_0 = \begin{pmatrix} -6/49 \\ -8/49 \end{pmatrix}$$ Now you have to exercise all the steps again, I will only give the results: $$\alpha_1 = 0.7, x_1 = \begin{pmatrix} 0.2 \\ -0.4 \end{pmatrix} r_1 = \boldsymbol 0.$$