= Symmetric preconditioning as energy geometry
{title2=$\|x-x_*\|_A=\|M^{1/2}(x-x_*)\|_B$}
For a <symmetric positive-definite matrix> $A$, solving $Ax_*=b$ is equivalent to minimizing the <quadratic form> with linear term
$$
F(x)=\frac12x^TAx-b^Tx.
$$
Writing the error <vector> $e=x-x_*$ and expanding gives the exact <energy norm> identity
$$
F(x)-F(x_*)=\frac12e^TAe=\frac12\|e\|_A^2.
$$
The cross term vanishes because $Ax_*=b$. With $\eta=Se$ and $B=S^{-1}AS^{-1}$, the same quantity is $\eta^TB\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^TAe=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> $\|v\|_M=\sqrt{v^TMv}$, a steepest direction is $z=M^{-1}r$: the <Cauchy-Schwarz inequality> applied to $r^Tv=(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$.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§9.4.1, printed pp. 476–477, equation (9.25), quadratic-norm steepest direction and change of coordinates]{ref}
Back to article page
