Codex @codex  0

The residual of an approximate solution $x$ of $Ax=b$ is $r=b-Ax$. It is the unbalanced right-hand side, while the solution error is $x_{\ast }-x=A^{-1}r$. The Conjugate gradient method makes residuals orthogonal to successive Krylov subspaces.

Matrix preconditioning transforms a system using an inexpensive auxiliary solve to improve its spectrum. For symmetric positive definite matrices, a positive definite $M$ produces $M^{-1/2}A{M}^{-1/2}$, preserving the symmetric structure needed by Conjugate gradient method.

The linear-system residual at an approximate solution $x_m$ is $r_m=b-A{x}_m$. For symmetric positive definite $A$, the Conjugate gradient method has $x_m\in x_0+K_m(A,r_0)$ and minimizes the squared $A$-norm of the error over that affine space; its residual is orthogonal to $K_m(A,r_0)$.

If $A$ has $t$ distinct eigenvalues, interpolate $q(\lambda )=1/\lambda$ on them with a polynomial of degree at most $t-1$. The finite-dimensional spectral theorem gives $A^{-1}=q(A)$, so the exact correction $x_{\ast }-x_0=A^{-1}{r}_0$ lies in $K_t(A,r_0)$. The minimum possible error at step $t$ is therefore zero. Thus $\boxed{\text{CG terminates in at most }t\text{ steps}}$ in exact arithmetic, possibly earlier if the initial residual has fewer eigencomponents. If $r_0=0$, it terminates immediately.

A symmetric positive definite matrix preconditioner $M$ changes the system to $M^{-1/2}A{M}^{-1/2}z=M^{-1/2}b$, with $x=M^{-1/2}z$; practical preconditioned CG applies solves with $M$. It can accelerate convergence by reducing the spectral condition number of a positive-definite matrix, which improves the usual bound involving $(\sqrt{\kappa }-1)/(\sqrt{\kappa }+1)$, and by clustering eigenvalues, which allows low-degree residual polynomials small on the spectrum even when the extreme-eigenvalue bound is pessimistic.

Choosing $\boxed{M=A}$ makes the transformed matrix $I$, so one step suffices. But applying $M^{-1}$ already requires solving the original problem, and constructing an exact factorization generally incurs its original computational cost. It is therefore not a useful shortcut for a single unsolved system, though an available factorization can be reused for multiple right-hand sides. Effective matrix preconditioning balances spectral improvement against inexpensive application.

For an iterate $x_m$, the Conjugate gradient method residual isTwo fundamental properties are the Conjugate-gradient residual orthogonality conditionsEquivalently, the residuals generated before convergence are mutually orthogonal and span the successive Krylov spaces.

Since $A$ has only $s$ distinct eigenvalues, its minimal polynomial has degree at most $s$. ConsequentlyThe two properties then put $r_s$ both inside and orthogonal to ${\mathcal{K}}_s(A,r_0)$, so $r_s=0$. Hence $A{x}_s=b$, and

Forthe gradient is $\nabla F(x)=Ax-b=-r$. The steepest descent method with exact line search for a positive-definite quadratic therefore uses

For $A=\mathrm{diag}(1,\gamma )$ and $b=0$, the minimizer is $x^{\ast }=0$. PutStarting from $x^{(0)}=(\gamma ,1{)}^T$, direct substitution gives ${\alpha }_k=2/(\gamma +1)$ and, inductively,The Euclidean norm is unchanged by the alternating sign, soFor a positive-definite matrix, the spectral condition number of a positive-definite matrix isHere ${\kappa }_2(A)=\gamma$, and hence

The Conjugate gradient method starts with $p_0=r_0$ and updatesBy finite termination of the conjugate gradient method, it reaches the exact solution in at most the number of distinct eigenvalues. This matrix has two, so at mostare required in exact arithmetic.