Editing Conjugate gradient method (section)

=== Convergence theorem ===

Define a subset of polynomials as
:<math>
  \Pi_k^* := \left\lbrace \ p \in \Pi_k \ : \ p(0)=1 \ \right\rbrace \,,
</math>
where <math> \Pi_k </math> is the set of [[Polynomial ring|polynomials]] of maximal degree <math> k </math>.

Let <math> \left( \mathbf{x}_k \right)_k </math> be the iterative approximations of the exact solution <math> \mathbf{x}_* </math>, and define the errors as <math> \mathbf{e}_k := \mathbf{x}_k - \mathbf{x}_* </math>.
Now, the rate of convergence can be approximated as <ref name="BP" /><ref>{{Cite book |title=Iterative solution of large sparse systems of equations |last=Hackbusch |first=W. |isbn=978-3-319-28483-5 |edition=2nd |location=Switzerland |publisher=Springer |oclc=952572240|date=2016-06-21 }}</ref>
:<math>
\begin{align}
  \left\| \mathbf{e}_k \right\|_\mathbf{A}
  &= \min_{p \in \Pi_k^*}  \left\| p(\mathbf{A}) \mathbf{e}_0 \right\|_\mathbf{A}
  \\
  &\leq \min_{p \in \Pi_k^*} \,  \max_{ \lambda \in \sigma(\mathbf{A})} | p(\lambda) | \  \left\|  \mathbf{e}_0 \right\|_\mathbf{A}
  \\
  &\leq 2 \left( \frac{ \sqrt{\kappa(\mathbf{A})}-1 }{ \sqrt{\kappa(\mathbf{A})}+1 } \right)^k \ \left\|  \mathbf{e}_0 \right\|_\mathbf{A}
  \\
  &\leq 2 \exp\left(\frac{-2k}{\sqrt{\kappa(\mathbf{A})}}\right) \ \left\|  \mathbf{e}_0 \right\|_\mathbf{A}
  \,,
\end{align}
</math>
where <math> \sigma(\mathbf{A}) </math> denotes the [[Spectrum of a matrix|spectrum]], and <math> \kappa(\mathbf{A}) </math> denotes the [[condition number]].

This shows <math>k = \tfrac{1}{2}\sqrt{\kappa(\mathbf{A})} \log\left(\left\|  \mathbf{e}_0 \right\|_\mathbf{A} \varepsilon^{-1}\right)</math> iterations suffices to reduce the error to <math>2\varepsilon</math> for any <math>\varepsilon>0</math>.

Note, the important limit when <math> \kappa(\mathbf{A}) </math> tends to <math> \infty </math>
:<math>
  \frac{ \sqrt{\kappa(\mathbf{A})}-1 }{ \sqrt{\kappa(\mathbf{A})}+1 }
  \approx 1 - \frac{2}{\sqrt{\kappa(\mathbf{A})}}
  \quad \text{for} \quad
  \kappa(\mathbf{A}) \gg 1
  \,.
</math>
This limit shows a faster convergence rate compared to the iterative methods of [[Jacobi method|Jacobi]] or [[Gauss–Seidel method|Gauss–Seidel]] which scale as <math> \approx 1 - \frac{2}{\kappa(\mathbf{A})} </math>.

No [[round-off error]] is assumed in the convergence theorem, but the convergence bound is commonly valid in practice as theoretically explained<ref name="AG" /> by [[Anne Greenbaum]].