Subsection 8.2.4 Method of Steepest Descent
¶For a function \(f: \R^n \rightarrow \R \) that we are trying to minimize, for a given \(x \text{,}\) the direction in which the function most rapidly increases in value at \(x \) is given by its gradient,
\begin{equation*}
\nabla f( x ) .
\end{equation*}
Thus, the direction in which it decreases most rapidly is
\begin{equation*}
- \nabla f( x ) .
\end{equation*}
For our function
\begin{equation*}
f( x ) = \frac{1}{2} x^T A x - x^T b
\end{equation*}
this direction of steepest descent is given by
\begin{equation*}
- \nabla f( x ) = - ( A x - b ) = b - A x,
\end{equation*}
which we recognize as the residual. Thus, recalling that \(r^{(k)} = b - A x^{(k)} \text{,}\) the direction of steepest descent at \(x^{(k)} \) is given by \(p^{(k)} = r^{(k)} = b - A x^{(k)} \text{.}\) These insights motivate the algorithms in Figure 8.2.4.1.
\begin{equation*}
\begin{array}{l}
{\bf Given:~} A, b, x^{(0)}
\\
r^{(0)} := b - A x^{(0)} \\
k := 0 \\
{\bf while~} r^{(k)} \neq 0 \\
~~~ p^{(k)} := r^{(k)} \\
~~~ q^{(k)} := A p^{(k)} \\
~~~ \alpha_k := \frac{p^{(k)\,T} r^{(k)}}{p^{(k)\,T}
q^{(k)}}
\\
~~~ x^{(k+1)} := x^{(k)} + \alpha_k p^{(k)}
\\
~~~ r^{(k+1)} := r^{(k)} - \alpha_k q^{(k)}
\\
~~~ k:= k+1 \\
{\bf endwhile}
\end{array}
\end{equation*}
\begin{equation*}
\begin{array}{l}
{\bf Given:~} A, b, x
\\
k:= 0 \\
r := b - A x \\
{\bf while~} r \neq 0 \\
~~~ p := r \\
~~~ q := A p \\
~~~ \alpha := \frac{p^T r}{p^T q}
\\
~~~ x := x + \alpha p
\\
~~~ r := r - \alpha q
\\
~~~ k:= k+1 \\
{\bf endwhile}
\end{array}
\end{equation*}