Skip to main content

Unit 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*}
Figure 8.2.4.1. Steepest descent algorithm, with indices and without indices.