Conjugate gradient descent when $A$ is non-singular but not symmetric

Question

If $A$ is a non-singular matrix that is not symmetric, will the $k$th update of CGD still yield an optimal guess $x_{k+1}$ for the system $Ax = b$?

Using the update rule $x_{k+1} = x_k + \alpha_k p_k,$ for $p_k$ the $k$th conjugate basis vector, CGD uses $\alpha_k = \frac{(b - Ax_k)^Tp_k}{p_k^TAp_k}$ to minimize $f(x_{k+1}) = x_{k+1}^TAx_{k+1} - 2b^Tx_{k+1}.$ When will CGD still compute the optimal $x_{k+1}$ here? Is there a straightforward example of CGD's update rule failing for a matrix $A$ that is non-singular, but just not symmetric?

Answer 1

CG does not converge to a solution, e.g., for $$A=\begin{bmatrix}1&1\\0&1\end{bmatrix}\text{ and } b=\begin{bmatrix}1\\1\end{bmatrix}.$$ The solution is $x=[0, 1]^T$, but CG stagnates at $x_k=[2/3, 2/3]^T$ starting from the first iteration, not by accident at the solution of the system with the matrix $\frac{1}{2}(A+A^T)$.