Iterative Methods: Part 3

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”