Conjugate Gradient – crunchingnumbers(a)live

Let’s look at one more way to solve the equation $A\vec{x} = \vec{b}$ . We assume that $A \in \mathbb{R}^{n \times n}$ is nonsingular, and define the $k$ -th Krylov subspace as follows:

$\mathscr{K}_{k} \,:=\, \mbox{span}\{\vec{b},\,A\vec{b},\,\cdots,\,A^{k - 1}\vec{b}\}$ .

Krylov subspace methods are efficient and popular iterative methods for solving large, sparse linear systems. When $A$ is symmetric, positive definite (SPD), i.e.

$\left\{\begin{array}{l} A^{T} = A \\[12pt] \vec{x}^{T}A\vec{x} > 0,\,\,\,\forall\,\vec{x} \neq \vec{0}, \end{array}\right.$

we can use a Krylov subspace method called Conjugate Gradient (CG).

Today, let’s find out how CG works and use it to solve 2D Poisson’s equation.

Continue reading “Iterative Methods: Part 3”

Share crunchingnumbers: