ALAFF Conjugate Gradient Method Basics

Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js

Skip to main content

$\usepackage{array} \setlength{\oddsidemargin}{-0.0in} \setlength{\evensidemargin}{-0.0in} \setlength{\textheight}{8.75in} \setlength{\textwidth}{6.5in} \setlength{\topmargin}{-0.25in} \newcommand{\R}{\mathbb R} \newcommand{\Rm}{\mathbb R^m} \newcommand{\Rn}{\mathbb R^n} \newcommand{\Rnxn}{\mathbb R^{n \times n}} \newcommand{\Rmxn}{\mathbb R^{m \times n}} \newcommand{\Rmxm}{\mathbb R^{m \times m}} \newcommand{\Rmxk}{\mathbb R^{m \times k}} \newcommand{\Rkxn}{\mathbb R^{k \times n}} \newcommand{\C}{\mathbb C} \newcommand{\Cm}{\mathbb C^m} \newcommand{\Cmxm}{\mathbb C^{m \times m}} \newcommand{\Cnxn}{\mathbb C^{n \times n}} \newcommand{\Cmxn}{\mathbb C^{m \times n}} \newcommand{\Ckxk}{\mathbb C^{k \times k}} \newcommand{\Cn}{\mathbb C^n} \newcommand{\Ck}{\mathbb C^k} \newcommand{\Null}{{\cal N}} \newcommand{\Col}{{\cal C}} \newcommand{\Rowspace}{{\cal R}} \newcommand{\Span}{{\rm {Span}}} \newcommand{\rank}{{\rm rank}} \newcommand{\triu}{{\rm triu}} \newcommand{\tril}{{\rm tril}} \newcommand{\sign}{{\rm sign}} \newcommand{\FlaTwoByTwo}[4]{ \left( \begin{array}{c | c} #1 \amp #2 \\ \hline #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLine}[4]{ \left( \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} \right) } \newcommand{\FlaTwoByTwoSingleLineNoPar}[4]{ \begin{array}{c c} #1 \amp #2 \\ #3 \amp #4 \end{array} } \newcommand{\FlaOneByTwo}[2]{ \left( \begin{array}{c | c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaOneByTwoSingleLine}[2]{ \left( \begin{array}{c c} #1 \amp #2 \end{array} \right) } \newcommand{\FlaTwoByOne}[2]{ \left( \begin{array}{c} #1 \\ \hline #2 \end{array} \right) } \newcommand{\FlaTwoByOneSingleLine}[2]{ \left( \begin{array}{c} #1 \\ #2 \end{array} \right) } \newcommand{\FlaThreeByOneB}[3]{ \left( \begin{array}{c} #1 \\ \hline #2 \\ #3 \end{array} \right) } \newcommand{\FlaThreeByOneT}[3]{ \left( \begin{array}{c} #1 \\ #2 \\ \hline #3 \end{array} \right) } \newcommand{\FlaOneByThreeR}[3]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaOneByThreeL}[3]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \end{array} \right) } \newcommand{\FlaThreeByThreeBR}[9]{ \left( \begin{array}{c | c c} #1 \amp #2 \amp #3 \\ \hline #4 \amp #5 \amp #6 \\ #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\FlaThreeByThreeTL}[9]{ \left( \begin{array}{c c | c} #1 \amp #2 \amp #3 \\ #4 \amp #5 \amp #6 \\ \hline #7 \amp #8 \amp #9 \end{array} \right) } \newcommand{\diag}[1]{{\rm diag}( #1 )} \newcommand{\URt}{{\sc HQR}} \newcommand{\FlaAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaAlgorithmWithInit}{ \begin{array}{|l|} \hline \routinename \\ \hline \initialize \\ \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\FlaBlkAlgorithm}{ \begin{array}{|l|} \hline \routinename \\ \hline \partitionings \\ ~~~ \begin{array}{l} \partitionsizes \end{array} \\ {\bf \color{blue} {while}~} \guard \\ ~~~ {\bf choose~block~size~} \blocksize \\ ~~~ \begin{array}{l} \repartitionings \end{array} \\ ~~~ ~~~ \repartitionsizes \\ ~~~ \color{red} { \begin{array}{l} \hline \color{black} {\update} \\ \hline \end{array}} \\ ~~~ \begin{array}{l} \moveboundaries \end{array} \\ {\bf \color{blue} {endwhile}} \\ \hline \end{array} } \newcommand{\complexone}{ \begin{array}{|c|}\hline \!\pm\! \\ \hline \end{array}~ } \newcommand{\HQR}{{\rm HQR}} \newcommand{\QR}{{\rm QR}} \newcommand{\st}{{\rm \ s.t. }} \newcommand{\QRQ}{{\rm {\normalsize \bf Q}{\rm \tiny R}}} \newcommand{\QRR}{{\rm {\rm \tiny Q}{\bf \normalsize R}}} \newcommand{\deltaalpha}{\delta\!\alpha} \newcommand{\deltax}{\delta\!x} \newcommand{\deltay}{\delta\!y} \newcommand{\deltaz}{\delta\!z} \newcommand{\deltaw}{\delta\!w} \newcommand{\DeltaA}{\delta\!\!A} \newcommand{\meps}{\epsilon_{\rm mach}} \newcommand{\fl}[1]{{\rm fl( #1 )}} \newcommand{\becomes}{:=} \newcommand{\defrowvector}[2]{ \left(#1_0, #1_1, \ldots, #1_{#2-1}\right) } \newcommand{\tr}[1]{{#1}^T} \newcommand{\LUpiv}[1]{{\rm LU}(#1)} \newcommand{\maxi}{{\rm maxi}} \newcommand{\Chol}[1]{{\rm Chol}( #1 )} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

Subsection 8.3.3 Conjugate Gradient Method Basics

fit width

The idea behind the Conjugate Gradient Method is that in the current iteration we have an approximation,

$x^{(k)}$ to the solution to

$A x = b \text{.}$ By construction, since

$x^{(0)} = 0 \text{,}$

$\begin{equation*} x^{(k)} = \alpha_0 p^{(0)} + \cdots + \alpha_{k-1} p^{(k-1)} . \end{equation*}$

Also, the residual

$\begin{equation*} \begin{array}{l} r^{(k)} \\ ~~~=~~~~ \\ b - A x^{(k)} \\ ~~~=~~~~ \\ b - A ( \alpha_0 p^{(0)} + \cdots + \alpha_{k-1} p^{(k-1)} ) \\ ~~~=~~~~ \\ b - \alpha_0 A p^{(0)} - \cdots - \alpha_{k-1} A p^{(k-1)} \\ ~~~=~~~~ \\ r^{(k-1)} - \alpha_{k-1} A p^{(k-1)}. \end{array} \end{equation*}$

If

$r^{(k)} = 0 \text{,}$ then we know that

$x^{(k)}$ solves

$A x = b \text{,}$ and we are done.

Assume that

$r^{(k)} \neq 0 \text{.}$ The question now is "How should we construct a new

$p^{(k)}$ that is A-conjugate to the previous search directions and so that

$p^{(k)\,T} r^{(k)} \neq 0 \text{?}$ " Here are some thoughts:

We like the direction of steepest descent, $r^{(k)} = b - A x^{(k)} \text{,}$ because it is the direction in which $f( x )$ decreases most quickly.
Let us chose $p^{(k)}$ to be the vector that is A-conjugate to $p^{(0)}, \ldots , p^{(k-1)}$ and closest to the direction of steepest descent, $r^{(k)} \text{:}$

$\begin{equation*} \| p^{(k)} - r^{(k)} \|_2 = \min_{p \perp \Span( Ap^{(0)}, \ldots, Ap^{(k-1)} )} \| r^{(k)} - p \|_2. \end{equation*}$

This yields the algorithm in Figure 8.3.3.1.

$\begin{equation*} \begin{array}{l} {\bf Given:~} A, b \\ x^{(0)} := 0 \\ r^{(0)} := b \\ k := 0 \\ {\bf while~} r^{(k)} \neq 0 \\ ~~~ {\bf if~} k = 0 \\ ~~~ ~~~ p^{(k)} = r^{(0)} \\ ~~~ {\bf else} \\ ~~~ ~~~ p^{(k)} \mbox{ minimizes } \min_{p \perp \Span( Ap^{(0)}, \ldots, Ap^{(k-1)} )} \| r^{(k)} - p \|_2 \\ ~~~ {\bf endif} \\ ~~~ \alpha_k := \frac{p^{(k)\,T} r^{(k)}}{p^{(k)\,T} A p^{(k)}} \\ ~~~ x^{(k+1)} := x^{(k)} + \alpha_k p^{(k)} \\ ~~~ r^{(k+1)} := r^{(k)} - \alpha_k A p^{(k)} \\ ~~~ k := k + 1 \\ {\bf endwhile} \end{array} \end{equation*}$

Figure 8.3.3.1. Basic Conjugate Gradient Method.