## Unit8.3.2Existence 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.