Symmetric positive-definite preconditioning ($B=M^{-1/2}A{M}^{-1/2},y=M^{1/2}x$)

Let $A$ and $M$ be real symmetric positive-definite matrices. The principal square root of a positive semidefinite matrix construction gives an invertible matrix for each. SetThen $Ax=b$ is equivalent to $By=c$. This is a matrix congruence, and $B$ is a symmetric positive-definite matrix: $B^T=B$, and for every nonzero vector $v$,since $S^{-1}v\ne 0$. This short proof establishes both requirements for applying the Conjugate gradient method to the transformed linear system.

The left transformed matrix has the same eigenvalues becauseIts correct geometry uses the weighted inner product $⟨u,v{⟩}_M=u^{T}Mv$: $⟨u,M^{-1}Av{⟩}_M=u^{T}Av=⟨M^{-1}Au,v{⟩}_M$. Thus it is symmetric in this inner product, even when it is not a symmetric matrix in ordinary coordinates. The spectral condition number governing the transformed symmetric problem is ${\kappa }_2(B)$, not generally ${\kappa }_2(M^{-1}A)$.

The Preconditioned conjugate gradient method realizes this transformation using auxiliary solves $M{z}_k=r_k$, without constructing $S$ or its matrix inverse. With fixed $M$, initialize $r_0=b-A{x}_0$ and $p_0=z_0$; while $r_k\ne 0$, usethen solve $M{z}_{k+1}=r_{k+1}$ and setStop at a zero linear-system residual before forming another ratio. Positive definiteness makes the denominators positive before termination.^[ref]

An invertible matrix alone is insufficient: with $A=I$ and $M=\mathrm{diag}(-1,1)$, the left transformed matrix has eigenvalues $-1,1$, and $M$ has no real symmetric positive-definite matrix square root. Even a valid symmetric positive-definite matrix can worsen conditioning if its scaling is unsuitable, as the next worked example shows.

For a symmetric positive-definite matrix $A$, solving $A{x}_{\ast }=b$ is equivalent to minimizing the quadratic form with linear termWriting the error vector $e=x-x_{\ast }$ and expanding gives the exact energy norm identityThe cross term vanishes because $A{x}_{\ast }=b$. With $\eta =Se$ and $B=S^{-1}A{S}^{-1}$, the same quantity is ${\eta }^{T}B\eta /2$. Symmetric positive-definite preconditioning changes coordinates without changing the energy assigned to a corresponding error vector.

In an orthonormal eigenbasis of $A$, the level set $e^{T}Ae=t>0$ has semiaxis lengths $\sqrt{t/{\lambda }_i}$. Its longest-to-shortest axis ratio is $\sqrt{{\kappa }_2(A)}$. A large spectral condition number of a positive-definite matrix therefore appears geometrically as a thin ellipsoid. Good scaling makes the transformed ellipsoid rounder, allowing a simple search direction to improve all coordinates together.

The negative gradient of $F$ is the linear-system residual $r$. Relative to the norm $\Vert v{\Vert }_M=\sqrt{v^{T}Mv}$, a steepest direction is $z=M^{-1}r$: the Cauchy-Schwarz inequality applied to $r^{T}v=(S^{-1}r{)}^T(Sv)$ shows that the greatest decrease per unit $M$-length occurs along this direction. Equivalently, ordinary gradient descent in $y=Sx$ becomes preconditioned steepest descent in $x$.^[ref]