Skip to main content

Unit 8.3.2 Existence of A-conjugate search directions

The big question left dangling at the end of the last unit was whether there exists a direction \(p^{(k)} \) that is A-orthogonal to all previous search directions and that is not orthogonal to \(r^{(k)} \text{.}\) Let us examine this:

  • Assume that all prior search directions \(p^{(0)}, \ldots , p^{(k-1)} \) were A-conjugate.

  • Consider all vectors \(p \in \Rn \) that are A-conjugate to \(p^{(0)}, \ldots , p^{(k-1)} \text{.}\) A vector \(p \) has this property if and only if \(p \perp \Span( A p^{(0)}, \ldots , A p^{(k-1)} ) \text{.}\)

  • For \(p \perp \Span( A p^{(0)}, \ldots , A p^{(k-1)} ) \) we notice that

    \begin{equation*} p^T r^{(k)} = p^T ( b - A x^{(k)} ) = p^T ( b - A P^{(k-1)} a^{(k-1)} ) % = p^T b - p^T A P^{(k-1)} a^{(k-1)} \end{equation*}

    where we recall from (8.3.2) that

    \begin{equation*} P^{(k-1)} = \left( \begin{array}{c c c} p^{(0)} \amp \cdots \amp p^{(k-1)} \end{array} \right) \mbox{ and } a^{(k-1)} = \left( \begin{array}{c} \alpha_0 \\ \vdots \\ \alpha_{k-1} \end{array} \right). \end{equation*}
  • If all vectors \(p \) that are A-conjugate to \(p^{(0)}, \ldots, p^{(k-1)} \) are orthogonal to the current residual, \(p^T r^{(k)} = 0 \) for all \(p \) with \(P^{(k-1)\,T} A p = 0 \text{,}\) then

    \begin{equation*} 0 = p^T b - p A P^{(k-1)} a^{(k-1)} = p^T b \mbox{ for all } p \perp \Span( Ap^{(0)}, \ldots , A p^{(p-1)} ). \end{equation*}

    Let's think about this: \(b \) is orthogonal to all vectors that are orthogonal to \(\Span( Ap^{(0)}, \ldots , A p^{(p-1)} ) \text{.}\) This means that

    \begin{equation*} b \in \Span( Ap^{(0)}, \ldots , A p^{(k-1)} ) . \end{equation*}
  • Hence \(b = A P^{(k-1)} z \) for some \(z \in \R^k \text{.}\) It also means that \(x = P^{(k-1)} z \) solves \(A x = b \text{.}\)

  • We conclude that our method must already have found the solution since \(x^{(k)}\) minimizes \(f( x ) \) over all vectors in \(\Span( p^{(0)}, \ldots , p^{(k-1)} ) \text{.}\) Thus \(A x^{(k)} = b \) and \(r^{(k)} = 0 \text{.}\)

We conclude that there exist descent methods that leverage A-conjugate search directions as described in FigureĀ 8.3.1.3. The question now is how to find a new A-conjugate search direction at every step.