10  Conjugate Gradient

Lecture 10

Published

February 23, 2026

Overview
  1. Recap
  2. Steepest Descent
  3. Conjugate Gradient
Note

I encourage you to play around with the juptyer notebook for this lecture - you can copy the code with the this notebook button on the side of this page.

Warning

These notes are mainly a record of what we discussed and are not a substitute for attending the lectures and reading books! If anything is unclear/wrong, let me know and I will update the notes.

Tip

This lecture is mostly based on Burden, Faires, and Burden (2015) sections 7.6.

using Plots, LaTeXStrings, LinearAlgebra

10.1 Recap

Last time, we saw simple examples of iterative techniques for solving Ax = b:

\begin{align} x^{(k+1)} = T x^{(k)} + c \tag{*} \end{align}

If \rho(T) < 1, then, for all x^{(0)} \in \mathbb R^n, (*) converges to the unique solution x = (I-T)^{-1}c as k\to\infty.

Examples: Jacobi, Gauss-Seidel, SOR:

function splitting(A,b,x; opt="GS", ω=1, Niter=100, tol=1e-10) 
    
    X = [x]

    L = -tril(A, -1)
    U = -triu(A, 1)
    D = Diagonal(diag(A))

    if (any(iszero, diag(D)))
        @warn "diagonal of A is not invertible"
        return X
    end

    for i ∈ 1:Niter
        if opt=="J"
            # Jacobi
            push!( X, inv(D)*( b + (L+U)*X[end] ) ) 
        elseif opt=="GS"
            # Gauss-Seidel
            push!( X, inv(D-L)*( b + U*X[end] ) )
        else 
            # SOR
            push!( X, inv(D-ω*L)*( ω*b + ((1-ω)D+ω*U)*X[end] ) )
        end
        r = norm(b - A*X[end])
        if (r < tol)
            return X
        end 
    end

    @warn "max iterations exceeded"
    return X
end;

Example 10.1 Applying the Jacobi and Gauss-Seidel iterations to Ax = b with

b = [6, 25, -11, 15];
A = [10 -1 2 0; 
    -1 11 -1 3; 
    2 -1 10 -1; 
    0 3 -1 8]

x0 = [0.,0.,0.,0.];

gives:

X = splitting(A,b,x0; opt="J")
Y = splitting(A,b,x0; opt="GS")

ω=1.15
Z = splitting(A,b,x0; opt="SOR", ω=ω);

In fact, we have the following error curves:

(ρJ, ρGS, ρSOR)
(0.42643661084234186, 0.08982305838804323, 0.17351995310029997)

10.2 Steepest Descent

Exercise 10.1 Show that

\begin{align} A = \begin{pmatrix} 5 & 1 \\ 1 & 3 \end{pmatrix} \end{align}

is symmetric and positive definite

function gradientDescent(A,b,x0; Niter=100, xlims=[-25,25], ylims=[-25,25])

    g(x,y) = dot([x;y], A*[x;y])/2 - dot([x;y], b)
    Dg(x,y) = A*[x;y] - b

    x_range = range(xlims[1], xlims[2], length=100)
    y_range = range(ylims[1], ylims[2], length=100)

    P = contour(x_range, y_range, g, 
        fill=true, 
        levels=50, 
        title="Steepest Descent",
        xlabel="x", ylabel="y", legend=false,
        colorbar=true)

    anim = @animate for i ∈ 0:Niter

        if (i==0)
            scatter!(P, [x0[1]], [x0[2]], markersize=5, color=:white)
        else 
            r = b - A*x0
            if (norm(r)<10-8)
                break;
            end
            # step size 
            α = dot(r,r)/dot(r,A*r)

            x1 = x0 - α*Dg(x0[1],x0[2])  
            plot!(P, [x0[1],x1[1]], [x0[2],x1[2]], color=:white, lw=2)
            scatter!(P, [x1[1]], [x1[2]], markersize=5, color=:white)
            x0 = x1 
        end
    end

    return anim
end

A = [5 1; 1 3]; b = [1; 3]; ξ = A \ b; x0 = [-22.5;5];
gif( gradientDescent(A,b,x0), fps=1 )
[ Info: Saved animation to c:\Users\math5\Math 5485\Math5486\tmp.gif

10.3 Conjugate gradient

Mainly based on 7.6 Burden, Faires, and Burden (2015).

[I will update the notes here…]

TipTO-DO
  • Assignment 3: Due Wednesday 11:59 PM,
  • (Sign-up to office hours if you would like)

Chapter 1 reading:

Chapter 2 reading:

  • Recap matrices: sections 7.1 - 7.2 of Burden, Faires, and Burden (2015)
  • Jacobi & Gauss-Seidel: section 7.3 Burden, Faires, and Burden (2015)
  • Today: section 7.6 Burden, Faires, and Burden (2015)

Next: other Kyrlov subspace methods

Burden, Richard L., Douglas J. Faires, and Annette M. Burden. 2015. Numerical Analysis. 10th ed. CENGAGE Learning.
Driscoll, Tobin A, and Richard J Braun. 2018. Fundamentals of Numerical Computation. https://fncbook.com/.