1. **State the problem:** Solve the system of linear equations given by $$\begin{bmatrix}3 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 3\end{bmatrix} \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} = \begin{bmatrix}1 \\ 0 \\ -1\end{bmatrix}$$ using the conjugate gradient method. 2. **Recall the conjugate gradient method:** It is an iterative method for solving systems $Ax = b$ where $A$ is symmetric positive definite. 3. **Check if $A$ is symmetric:** $$A = \begin{bmatrix}3 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 3\end{bmatrix}, \quad A^T = \begin{bmatrix}3 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 3\end{bmatrix}$$ Since $A = A^T$, $A$ is symmetric. 4. **Check positive definiteness:** - Leading principal minors: - $3 > 0$ - $\det \begin{bmatrix}3 & 0 \\ 0 & 1\end{bmatrix} = 3 \times 1 - 0 = 3 > 0$ - $\det A = 3(1 \times 3 - 1 \times 1) - 0 + 2(0 \times 1 - 1 \times 2) = 3(3 - 1) + 2(0 - 2) = 3 \times 2 - 4 = 6 - 4 = 2 > 0$ All positive, so $A$ is positive definite. 5. **Initialize:** - Start with $x^{(0)} = \begin{bmatrix}0 \\ 0 \\ 0\end{bmatrix}$ - Compute $r^{(0)} = b - A x^{(0)} = b = \begin{bmatrix}1 \\ 0 \\ -1\end{bmatrix}$ - Set $p^{(0)} = r^{(0)}$ 6. **Iteration 1:** - Compute $\alpha_0 = \frac{r^{(0)T} r^{(0)}}{p^{(0)T} A p^{(0)}}$ - $r^{(0)T} r^{(0)} = 1^2 + 0^2 + (-1)^2 = 2$ - $A p^{(0)} = A r^{(0)} = \begin{bmatrix}3 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 3\end{bmatrix} \begin{bmatrix}1 \\ 0 \\ -1\end{bmatrix} = \begin{bmatrix}3(1) + 0 + 2(-1) \\ 0 + 0 + 1(-1) \\ 2(1) + 0 + 3(-1)\end{bmatrix} = \begin{bmatrix}3 - 2 \\ -1 \\ 2 - 3\end{bmatrix} = \begin{bmatrix}1 \\ -1 \\ -1\end{bmatrix}$ - $p^{(0)T} A p^{(0)} = r^{(0)T} A r^{(0)} = \begin{bmatrix}1 & 0 & -1\end{bmatrix} \begin{bmatrix}1 \\ -1 \\ -1\end{bmatrix} = 1(1) + 0(-1) + (-1)(-1) = 1 + 0 + 1 = 2$ - So $\alpha_0 = \frac{2}{2} = 1$ - Update $x^{(1)} = x^{(0)} + \alpha_0 p^{(0)} = \begin{bmatrix}0 \\ 0 \\ 0\end{bmatrix} + 1 \times \begin{bmatrix}1 \\ 0 \\ -1\end{bmatrix} = \begin{bmatrix}1 \\ 0 \\ -1\end{bmatrix}$ - Update $r^{(1)} = r^{(0)} - \alpha_0 A p^{(0)} = \begin{bmatrix}1 \\ 0 \\ -1\end{bmatrix} - 1 \times \begin{bmatrix}1 \\ -1 \\ -1\end{bmatrix} = \begin{bmatrix}0 \\ 1 \\ 0\end{bmatrix}$ 7. **Iteration 2:** - Compute $\beta_0 = \frac{r^{(1)T} r^{(1)}}{r^{(0)T} r^{(0)}} = \frac{0^2 + 1^2 + 0^2}{2} = \frac{1}{2} = 0.5$ - Update $p^{(1)} = r^{(1)} + \beta_0 p^{(0)} = \begin{bmatrix}0 \\ 1 \\ 0\end{bmatrix} + 0.5 \times \begin{bmatrix}1 \\ 0 \\ -1\end{bmatrix} = \begin{bmatrix}0.5 \\ 1 \\ -0.5\end{bmatrix}$ - Compute $\alpha_1 = \frac{r^{(1)T} r^{(1)}}{p^{(1)T} A p^{(1)}}$ - $r^{(1)T} r^{(1)} = 1$ - $A p^{(1)} = \begin{bmatrix}3 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 3\end{bmatrix} \begin{bmatrix}0.5 \\ 1 \\ -0.5\end{bmatrix} = \begin{bmatrix}3(0.5) + 0 + 2(-0.5) \\ 0 + 1(1) + 1(-0.5) \\ 2(0.5) + 1(1) + 3(-0.5)\end{bmatrix} = \begin{bmatrix}1.5 - 1 \\ 1 - 0.5 \\ 1 + 1 - 1.5\end{bmatrix} = \begin{bmatrix}0.5 \\ 0.5 \\ 0.5\end{bmatrix}$ - $p^{(1)T} A p^{(1)} = \begin{bmatrix}0.5 & 1 & -0.5\end{bmatrix} \begin{bmatrix}0.5 \\ 0.5 \\ 0.5\end{bmatrix} = 0.5(0.5) + 1(0.5) + (-0.5)(0.5) = 0.25 + 0.5 - 0.25 = 0.5$ - So $\alpha_1 = \frac{1}{0.5} = 2$ - Update $x^{(2)} = x^{(1)} + \alpha_1 p^{(1)} = \begin{bmatrix}1 \\ 0 \\ -1\end{bmatrix} + 2 \times \begin{bmatrix}0.5 \\ 1 \\ -0.5\end{bmatrix} = \begin{bmatrix}1 + 1 \\ 0 + 2 \\ -1 - 1\end{bmatrix} = \begin{bmatrix}2 \\ 2 \\ -2\end{bmatrix}$ - Update $r^{(2)} = r^{(1)} - \alpha_1 A p^{(1)} = \begin{bmatrix}0 \\ 1 \\ 0\end{bmatrix} - 2 \times \begin{bmatrix}0.5 \\ 0.5 \\ 0.5\end{bmatrix} = \begin{bmatrix}0 - 1 \\ 1 - 1 \\ 0 - 1\end{bmatrix} = \begin{bmatrix}-1 \\ 0 \\ -1\end{bmatrix}$ 8. **Iteration 3:** - Compute $r^{(2)T} r^{(2)} = (-1)^2 + 0^2 + (-1)^2 = 2$ - Compute $\beta_1 = \frac{r^{(2)T} r^{(2)}}{r^{(1)T} r^{(1)}} = \frac{2}{1} = 2$ - Update $p^{(2)} = r^{(2)} + \beta_1 p^{(1)} = \begin{bmatrix}-1 \\ 0 \\ -1\end{bmatrix} + 2 \times \begin{bmatrix}0.5 \\ 1 \\ -0.5\end{bmatrix} = \begin{bmatrix}-1 + 1 \\ 0 + 2 \\ -1 - 1\end{bmatrix} = \begin{bmatrix}0 \\ 2 \\ -2\end{bmatrix}$ - Compute $A p^{(2)} = \begin{bmatrix}3 & 0 & 2 \\ 0 & 1 & 1 \\ 2 & 1 & 3\end{bmatrix} \begin{bmatrix}0 \\ 2 \\ -2\end{bmatrix} = \begin{bmatrix}3(0) + 0 + 2(-2) \\ 0 + 1(2) + 1(-2) \\ 2(0) + 1(2) + 3(-2)\end{bmatrix} = \begin{bmatrix}-4 \\ 0 \\ 2 - 6\end{bmatrix} = \begin{bmatrix}-4 \\ 0 \\ -4\end{bmatrix}$ - Compute $p^{(2)T} A p^{(2)} = \begin{bmatrix}0 & 2 & -2\end{bmatrix} \begin{bmatrix}-4 \\ 0 \\ -4\end{bmatrix} = 0(-4) + 2(0) + (-2)(-4) = 8$ - Compute $\alpha_2 = \frac{r^{(2)T} r^{(2)}}{p^{(2)T} A p^{(2)}} = \frac{2}{8} = 0.25$ - Update $x^{(3)} = x^{(2)} + \alpha_2 p^{(2)} = \begin{bmatrix}2 \\ 2 \\ -2\end{bmatrix} + 0.25 \times \begin{bmatrix}0 \\ 2 \\ -2\end{bmatrix} = \begin{bmatrix}2 \\ 2 + 0.5 \\ -2 - 0.5\end{bmatrix} = \begin{bmatrix}2 \\ 2.5 \\ -2.5\end{bmatrix}$ - Update $r^{(3)} = r^{(2)} - \alpha_2 A p^{(2)} = \begin{bmatrix}-1 \\ 0 \\ -1\end{bmatrix} - 0.25 \times \begin{bmatrix}-4 \\ 0 \\ -4\end{bmatrix} = \begin{bmatrix}-1 + 1 \\ 0 - 0 \\ -1 + 1\end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ 0\end{bmatrix}$ 9. Since $r^{(3)} = 0$, the method converges. **Final solution:** $$x = \begin{bmatrix}2 \\ 2.5 \\ -2.5\end{bmatrix}$$