[proofplan]
We derive the error recurrence by expressing the exact line search step size in terms of the error $e^{(k)} = x^* - x^{(k)}$. The key observation is that the residual equals $A$ applied to the error: $r^{(k)} = Ae^{(k)}$. Substituting this into the optimal step size formula from the [Optimal Step Size via Exact Line Search](/theorems/1396) converts the numerator into an $A$-inner product, yielding $\alpha_k = \langle e^{(k)}, d^{(k)} \rangle_A / \langle d^{(k)}, d^{(k)} \rangle_A$. The error update $e^{(k+1)} = e^{(k)} - \alpha_k d^{(k)}$ then gives the stated formula, and $A$-orthogonality of $e^{(k+1)}$ and $d^{(k)}$ follows by direct substitution.
[/proofplan]
[step:Express the residual $r^{(k)}$ in terms of the error $e^{(k)}$]
Define the error $e^{(k)} := x^* - x^{(k)}$ where $x^* = A^{-1}b$ is the exact solution. Then:
\begin{align*}
r^{(k)} = b - Ax^{(k)} = Ax^* - Ax^{(k)} = A(x^* - x^{(k)}) = Ae^{(k)}.
\end{align*}
In particular, for any vector $v \in \mathbb{R}^n$:
\begin{align*}
\langle r^{(k)}, v \rangle = \langle Ae^{(k)}, v \rangle = \langle e^{(k)}, Av \rangle = \langle e^{(k)}, v \rangle_A,
\end{align*}
where $\langle u, v \rangle_A := \langle u, Av \rangle$ denotes the $A$-inner product (which is a valid inner product since $A$ is symmetric positive definite).
[/step]
[step:Rewrite the optimal step size in terms of the $A$-inner product with the error]
By the [Optimal Step Size via Exact Line Search](/theorems/1396):
\begin{align*}
\alpha_k = \frac{\langle r^{(k)}, d^{(k)} \rangle}{\langle d^{(k)}, Ad^{(k)} \rangle}.
\end{align*}
Applying the identity $\langle r^{(k)}, d^{(k)} \rangle = \langle e^{(k)}, d^{(k)} \rangle_A$ from the previous step:
\begin{align*}
\alpha_k = \frac{\langle e^{(k)}, d^{(k)} \rangle_A}{\langle d^{(k)}, d^{(k)} \rangle_A}.
\end{align*}
[/step]
[step:Derive the error recurrence and verify $A$-orthogonality]
The iterate update is $x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$. Subtracting both sides from $x^*$:
\begin{align*}
e^{(k+1)} = x^* - x^{(k+1)} = (x^* - x^{(k)}) - \alpha_k d^{(k)} = e^{(k)} - \alpha_k d^{(k)}.
\end{align*}
Substituting the expression for $\alpha_k$:
\begin{align*}
e^{(k+1)} = e^{(k)} - \frac{\langle e^{(k)}, d^{(k)} \rangle_A}{\langle d^{(k)}, d^{(k)} \rangle_A}\,d^{(k)}.
\end{align*}
To verify $A$-orthogonality, take the $A$-inner product of $e^{(k+1)}$ with $d^{(k)}$:
\begin{align*}
\langle e^{(k+1)}, d^{(k)} \rangle_A = \langle e^{(k)}, d^{(k)} \rangle_A - \frac{\langle e^{(k)}, d^{(k)} \rangle_A}{\langle d^{(k)}, d^{(k)} \rangle_A}\langle d^{(k)}, d^{(k)} \rangle_A = \langle e^{(k)}, d^{(k)} \rangle_A - \langle e^{(k)}, d^{(k)} \rangle_A = 0.
\end{align*}
[guided]
The error recurrence $e^{(k+1)} = e^{(k)} - \frac{\langle e^{(k)}, d^{(k)} \rangle_A}{\langle d^{(k)}, d^{(k)} \rangle_A}\,d^{(k)}$ has a geometric interpretation: $e^{(k+1)}$ is obtained from $e^{(k)}$ by subtracting its $A$-orthogonal projection onto $\operatorname{span}\{d^{(k)}\}$. This is exactly the formula for orthogonal projection in the $A$-inner product. After the step, $e^{(k+1)}$ has no component along $d^{(k)}$ in the $A$-inner product geometry — this is what $\langle e^{(k+1)}, d^{(k)} \rangle_A = 0$ says.
The verification is a direct calculation:
\begin{align*}
\langle e^{(k+1)}, d^{(k)} \rangle_A &= \left\langle e^{(k)} - \frac{\langle e^{(k)}, d^{(k)} \rangle_A}{\langle d^{(k)}, d^{(k)} \rangle_A}d^{(k)},\, d^{(k)} \right\rangle_A \\
&= \langle e^{(k)}, d^{(k)} \rangle_A - \frac{\langle e^{(k)}, d^{(k)} \rangle_A}{\langle d^{(k)}, d^{(k)} \rangle_A} \cdot \langle d^{(k)}, d^{(k)} \rangle_A = 0.
\end{align*}
This $A$-orthogonality is the engine that drives the conjugate direction method: at each step, the error becomes $A$-orthogonal to the search direction just used. If the search directions are themselves pairwise $A$-orthogonal (conjugate), then after $n$ steps in $\mathbb{R}^n$ the error is $A$-orthogonal to the entire space and must vanish.
[/guided]
[/step]
