--- title: "CG algorithm; Gauss-Seidel numerical" subject: "Computational Techniques in Civil Engineering" chapter: 2 key: "semester_8/computational_techniques_in_civil_engineering:cg-algorithm-gauss-seidel-numerical" source: https://www.bctengineer.com/q/semester_8/computational_techniques_in_civil_engineering/cg-algorithm-gauss-seidel-numerical site: BCT Engineering --- # CG algorithm; Gauss-Seidel numerical Computational Techniques in Civil Engineering · Chapter 2: Solutions of linear equations - Asked in: 2073 Magh, 4+4 marks - Video: [Gauss Seidel Method | Iterative Method | Numerical Methods | Problems](https://www.youtube.com/watch?v=gxy6VI1hEfs) — Dr.Gajendra Purohit and 2 more - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/computational_techniques_in_civil_engineering/cg-algorithm-gauss-seidel-numerical - Whole chapter: https://www.bctengineer.com/md/semester_8/computational_techniques_in_civil_engineering/chapter-2 ## Question Write down the algorithm for the conjugate gradient method. Consider the system $$ \begin{bmatrix} 2 & -1 & 0 \\ 1 & 6 & -2 \\ 4 & -3 & 8 \end{bmatrix}\begin{Bmatrix} x_1 \\ x_2 \\ x_3 \end{Bmatrix} = \begin{Bmatrix} 2 \\ -4 \\ 5 \end{Bmatrix} $$ Solve the above system by using Gauss-Seidel iteration starting with $x^{(0)} = (0, 0, 0)^T$. ## Short answer CG repeats: alpha = r^T r/(d^T A d), x = x + alpha d, r = r - alpha A d, beta = r_new^T r_new/(r^T r), d = r + beta d, until the residual is small. Gauss-Seidel with newest values converges to x1 about 0.62, x2 about -0.76, x3 about 0.03. ## Answer #### Algorithm for the conjugate gradient method 1. Choose a starting vector $x_0$ (usually $0$). Compute the residual $r_0 = b - Ax_0$ and set the first search direction $d_0 = r_0$. 2. For $k = 0, 1, 2, \dots$ repeat: - Step length: $\alpha_k = \dfrac{r_k^T r_k}{d_k^T A d_k}$ - Update the solution: $x_{k+1} = x_k + \alpha_k d_k$ - Update the residual: $r_{k+1} = r_k - \alpha_k A d_k$ - Check convergence: stop if $\|r_{k+1}\| <$ tolerance. - Direction factor: $\beta_k = \dfrac{r_{k+1}^T r_{k+1}}{r_k^T r_k}$ - New direction: $d_{k+1} = r_{k+1} + \beta_k d_k$ 3. The last $x_{k+1}$ is the solution. The method needs a symmetric positive definite matrix and gives the exact solution in at most $n$ steps. #### Gauss-Seidel solution The matrix is diagonally dominant ($2>1$, $6>3$, $8>7$), so Gauss-Seidel converges. Rewrite the equations: $$ x_1=\frac{2+x_2}{2},\qquad x_2=\frac{-4-x_1+2x_3}{6},\qquad x_3=\frac{5-4x_1+3x_2}{8} $$ Start with $x^{(0)}=(0,0,0)$ and use the newest values at once. | Iteration | $x_1$ | $x_2$ | $x_3$ | |---|---|---|---| | 1 | 1.0000 | -0.8333 | -0.1875 | | 2 | 0.5833 | -0.8264 | 0.0234 | | 3 | 0.5868 | -0.7567 | 0.0479 | | 4 | 0.6217 | -0.7543 | 0.0313 | | 5 | 0.6228 | -0.7600 | 0.0286 | | 6 | 0.6200 | -0.7605 | 0.0298 | | 7 | 0.6198 | -0.7600 | 0.0301 | | 8 | 0.6200 | -0.7600 | 0.0300 | Example of iteration 1: $x_1=(2+0)/2=1$; $x_2=(-4-1+0)/6=-0.8333$; $x_3=(5-4+3(-0.8333))/8=-0.1875$. **Answer: $x_1\approx0.62,\ x_2\approx-0.76,\ x_3\approx0.03$.** ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In the conjugate gradient algorithm, how is the step length alpha_k computed? A. alpha_k = r_k^T r_k / (d_k^T A d_k) B. alpha_k = d_k^T A d_k / (r_k^T r_k) C. alpha_k = r_{k+1}^T r_{k+1} / (r_k^T r_k) D. alpha_k = b^T d_k / (r_k^T r_k) Answer: A. The step length is the squared residual norm divided by the energy norm d^T A d of the search direction. The ratio of successive residual norms is beta, not alpha. (Key point: CG step length) 2. After updating the residual, how is the new search direction d_{k+1} formed? A. d_{k+1} = r_{k+1} B. d_{k+1} = r_{k+1} - beta_k d_k with beta_k = d_k^T r_k C. d_{k+1} = r_{k+1} + beta_k d_k with beta_k = r_{k+1}^T r_{k+1} / (r_k^T r_k) D. d_{k+1} = A r_{k+1} + alpha_k d_k Answer: C. The new direction is the new residual plus beta times the old direction, with beta the ratio of new to old squared residual norms. This keeps the directions A-conjugate. (Key point: CG direction update) 3. What condition on A does the conjugate gradient method need, and how many steps does it take in exact arithmetic? A. Diagonally dominant A; infinite steps B. Any square A; n^2 steps C. Symmetric positive definite A; at most n steps D. Symmetric positive definite A; exactly 2n steps Answer: C. CG needs a symmetric positive definite matrix and gives the exact solution in at most n steps for an n x n system. Diagonal dominance is the Gauss-Seidel condition. (Key point: CG requirements) 4. For the Gauss-Seidel iteration, how is the first iteration's x2 obtained from x2 = (-4 - x1 + 2x3)/6 with x(0) = 0? A. Use x1 = 0 from the old iterate, giving -0.667 B. Use the newly computed x1 = 1 at once, giving (-4 - 1 + 0)/6 = -0.8333 C. Use x1 = 1 and x3 = -0.1875, giving -0.9 D. Average the old and new x1, giving -0.75 Answer: B. Gauss-Seidel uses the newest values immediately; x1 = 1 has just been found while x3 is still the old value 0, giving -0.8333. Using only old values would be Jacobi. (Key point: Gauss-Seidel update rule) ## Related in Computational Techniques in Civil Engineering - [Conjugate gradient numerical (3,0,2 system)](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-numerical-3-0-2) — Computational Techniques in Civil Engineering, chapter 2, asked 2× - [Conjugate gradient numerical (5 iterations)](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-numerical-3-0-1) — Computational Techniques in Civil Engineering, chapter 2 - [Direct, iterative methods; Gauss-Seidel numerical](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Adirect-iterative-gauss-seidel) — Computational Techniques in Civil Engineering, chapter 2 - [Conjugate gradient numerical (2,-1 system)](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-numerical-three-unknowns-a) — Computational Techniques in Civil Engineering, chapter 2, asked 2× - [Conjugate gradient method and algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-method-algorithm) — Computational Techniques in Civil Engineering, chapter 2, asked 2× - [Conjugate gradient three iterations (10,-6,0)](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-three-iterations-a) — Computational Techniques in Civil Engineering, chapter 2 ## Related in other subjects - [Gauss-Seidel: four unknowns](https://www.bctengineer.com/question.md?key=semester_4%2Fnumerical_method%3Agauss-seidel-four-unknowns) — Numerical Method, chapter 3 - [Gauss-Seidel: 10x+y-z=11.19](https://www.bctengineer.com/question.md?key=semester_4%2Fnumerical_method%3Agauss-seidel-10x-y-z) — Numerical Method, chapter 3 - [Gauss-Seidel: 20x+y-2z=17](https://www.bctengineer.com/question.md?key=semester_4%2Fnumerical_method%3Agauss-seidel-20x-y-2z) — Numerical Method, chapter 3 - [Line flows by G-S after one iteration](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Ags-line-flows-2071) — Power System Analysis II, chapter 2