Preconditioner

Remarks

All three systems have the same solution $x$ as $A x = b$. The definition is formal; a preconditioner is useful when two informal requirements hold. First, $P^{-1} r$ is cheap to compute for any $r$. Second, $P^{-1} A$ is close to the identity, for example it has a small condition number or few clusters of eigenvalues. The two extremes are $P = I$, which is cheap but changes nothing, and $P = A$, which is ideal but as costly as the original problem. Example: the Jacobi preconditioner $P = \operatorname{diag}(a_{11}, \dots, a_{nn})$ is invertible when all diagonal entries are nonzero. For $A$ with rows $(100, 1)$ and $(1, 1)$, the ratio of the extreme eigenvalues of $A$ is about $101$. The matrix $P^{-1} A$ has rows $(1, 0.01)$ and $(1, 1)$ and eigenvalues $0.9$ and $1.1$, with ratio about $1.2$. Non-example: the matrix $P$ with rows $(1, 1)$ and $(1, 1)$ is singular, so it is not a preconditioner. For a symmetric positive definite $A$ one takes $P$ symmetric positive definite, so that methods for symmetric systems still apply.