= Solution
Nonzero <vectors> $p_1,\ldots,p_k$ are <conjugate directions> with respect to $A$ when $p_i^TAp_j=0$ for $i\ne j$. They are <linearly independent>: if $\sum_i c_ip_i=0$, multiplication by $p_j^TA$ gives $c_jp_j^TAp_j=0$, hence $c_j=0$ by <positive definiteness>. There are consequently at most $n$ such directions.
The <finite termination of conjugate directions> follows from the residual orthogonality maintained by the exact line minimizations. At step $j$,
$$
r_{j+1}=r_j-\alpha_jAp_j,\qquad p_j^Tr_{j+1}=0.
$$
For $i<j$, conjugacy gives $p_i^Tr_{j+1}=p_i^Tr_j$. By <mathematical induction>, $r_{j+1}$ is <orthogonal> to every $p_1,\ldots,p_j$. After $n$ nonzero conjugate directions they form a <basis> of $\mathbb R^n$, forcing $r_{n+1}=0$. Thus \b[the method reaches $Ax=b$ in at most $n$ steps], and <positive definiteness> makes that solution unique. The claim is in exact arithmetic; rounding errors need not preserve exact conjugacy.
Back to article page
