In the conjugate gradient algorithm, how is the step length alpha_k computed?

alpha_k = r_k^T r_k / (d_k^T A d_k)

alpha_k = d_k^T A d_k / (r_k^T r_k)

alpha_k = r_{k+1}^T r_{k+1} / (r_k^T r_k)

alpha_k = b^T d_k / (r_k^T r_k)

After updating the residual, how is the new search direction d_{k+1} formed?

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_{k+1} = r_{k+1} - beta_k d_k with beta_k = d_k^T r_k

d_{k+1} = A r_{k+1} + alpha_k d_k

What condition on A does the conjugate gradient method need, and how many steps does it take in exact arithmetic?

Symmetric positive definite A; at most n steps

Diagonally dominant A; infinite steps

Symmetric positive definite A; exactly 2n steps

For the Gauss-Seidel iteration, how is the first iteration's x2 obtained from x2 = (-4 - x1 + 2x3)/6 with x(0) = 0?

Use the newly computed x1 = 1 at once, giving (-4 - 1 + 0)/6 = -0.8333

Use x1 = 0 from the old iterate, giving -0.667

Use x1 = 1 and x3 = -0.1875, giving -0.9

Average the old and new x1, giving -0.75

2073 Magh · 4+4 marks

CG algorithm; Gauss-Seidel numerical

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.

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$ .

Algorithm for the conjugate gradient method

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$ .
For $k = 0, 1, 2, \dots$ $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$
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$ .

✓ Answer checked by Claude Opus 5.5 (high effort)

Conjugate gradient numerical (3,0,2 system) · Computational Techniques in Civil Engineering, chapter 2 · asked 2×
Conjugate gradient numerical (5 iterations) · Computational Techniques in Civil Engineering, chapter 2
Direct, iterative methods; Gauss-Seidel numerical · Computational Techniques in Civil Engineering, chapter 2
Conjugate gradient numerical (2,-1 system) · Computational Techniques in Civil Engineering, chapter 2 · asked 2×
Conjugate gradient method and algorithm · Computational Techniques in Civil Engineering, chapter 2 · asked 2×
Conjugate gradient three iterations (10,-6,0) · Computational Techniques in Civil Engineering, chapter 2
Gauss-Seidel: four unknowns · Numerical Method, chapter 3
Gauss-Seidel: 10x+y-z=11.19 · Numerical Method, chapter 3
Gauss-Seidel: 20x+y-2z=17 · Numerical Method, chapter 3
Line flows by G-S after one iteration · Power System Analysis II, chapter 2

All Computational Techniques in Civil Engineering chapter 2 questions →

CG algorithm; Gauss-Seidel numerical

Algorithm for the conjugate gradient method

Gauss-Seidel solution

Related questions