Preconditioner algorithms and residual metrics — Examples

Since $ϵ>0$, it is nonzero; [F2] gives its inverse ${ϵ}^{-1}$. With $M={ϵ}^{-1}$, commutativity gives $Mϵ=ϵM=1$, so $M^{-1}=ϵ$. The physical residual is $r=b-Ax=1-1\cdot 0=1$.

By [F1], the left-preconditioned residual is $M^{-1}r=ϵ$. Both $1$ and $ϵ$ are positive by [F3], so [F4] gives absolute values $1$ and $ϵ$, respectively.

Since $0<ϵ<1$, the left-preconditioned residual has strictly smaller absolute value than the physical residual. The ratio can be made as small as the chosen $ϵ$.

By [F4], the displayed matrix entries are in a field. Its nonzero pattern is the diagonal together with the four adjacent off-diagonal positions. It is canonical, sorted by column in every row, and contains all three diagonal positions, so the algorithm has no input-pattern or missing-diagonal failure.

In row 1 the factors are $U_{11}=4$ and $U_{12}=-1$. In row 2 the multiplier is $L_{21}=-1\mathrm{/}4$; the matching update at column 2 gives $U_{22}=4-(-1\mathrm{/}4)(-1)=15\mathrm{/}4$. The row-2 entry at column 3 remains $U_{23}=-1$ because row 1 has no position at column 3.

Row 3 has no position at column 1. Its multiplier at column 2 is $L_{32}=(-1)\mathrm{/}(15\mathrm{/}4)=-4\mathrm{/}15$. The matching update at column 3 gives $U_{33}=4-(-4\mathrm{/}15)(-1)=56\mathrm{/}15$. All three pivots are nonzero, so the procedure returns ok with the displayed factors.

By [F3], the product has rows $(4,-1,0)$, $(-1,1\mathrm{/}4+15\mathrm{/}4,-1)$, and $(0,-1,4\mathrm{/}15+56\mathrm{/}15)$, hence $LU=A$.

Take $A=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right)\mathrm{.}$ By [F4], this is a matrix over a field. Its canonical sorted CSR pattern is $P=\{(1,1),(1,2),(2,2),(3,1),(3,3)\}$, with all diagonal entries equal to $1$. Thus the input satisfies the algorithm's domain and has no missing diagonal.

The first row gives $U_{11}=U_{12}=1$. Row 2 has no strict-lower position and gives $U_{22}=1$. In row 3 the only strict-lower position is $(3,1)$, so $L_{31}=1$. The update from this multiplier can reach only a column $j>1$ present in both row 3 and row 1; no such column exists. Hence $L_{32}$ is not stored, $U_{33}=1$, and the procedure returns ok with $L=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right),U=\left(\begin{array}{ccc}1& 1& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right)\mathrm{.}$

By [F3], $(LU{)}_{32}=L_{31}{U}_{12}+L_{32}{U}_{22}+L_{33}{U}_{32}=1$, whereas $A_{32}=0$. Therefore $LU$ has a nonzero outside the input pattern, so the refuted statement is false.