= Finite termination of conjugate directions
{title2=$x_{n+1}=A^{-1}b$}
Let $p_1,\ldots,p_n$ be <conjugate directions> for a <symmetric positive-definite matrix> $A$. Starting from any $x_1$, minimize $x^TAx/2-b^Tx$ successively along those full lines, stopping early if the <linear-system residual> $r_j=b-Ax_j$ vanishes. The <quadratic minimization along a line> uses $\alpha_j=p_j^Tr_j/(p_j^TAp_j)$ and gives $r_{j+1}=r_j-\alpha_jAp_j$.
This makes $p_j^Tr_{j+1}=0$. For $i<j$, conjugacy preserves $p_i^Tr_{j+1}=p_i^Tr_j$. By <mathematical induction>, $r_{j+1}$ is <orthogonal> to all preceding search <vectors>. The $n$ <conjugate directions> are <linearly independent> and hence form a <basis>, so $r_{n+1}=0$. Thus the method reaches the unique solution of the <linear system> in at most $n$ steps in exact arithmetic. The <conjugate gradient method> generates such directions without storing a complete prescribed <basis> in advance.
Back to article page
