Backward error analysis for LU

This is the backward error bound for LU:

$$\begin{array}{c}(A+E)\tilde{x}=b\\ |E|\le nu(2|A|+4|\tilde{L}||\tilde{U}|)+O(u^2)\end{array}$$

• $|\tilde{L}|$, $|\tilde{U}|$: matrices obtained by taking the absolute value of the entries of $\tilde{L}$ and $\tilde{U}$.
• We use the same notation for $|E|$ and $|A|$.
• The backward error can become very large when we have large entries in $L$ or $U$.
• The LU factorization is not a backward stable algorithm.

In our previous example:

$$\begin{array}{c}A=\left(\begin{array}{cc}ϵ& 1\\ 1& \pi \end{array}\right)\\ L=\left(\begin{array}{cc}1& 0\\ {ϵ}^{-1}& 1\end{array}\right),U=\left(\begin{array}{cc}ϵ& 1\\ 0& \pi -{ϵ}^{-1}\end{array}\right)\end{array}$$

• The backward error is $O(u{ϵ}^{-1})$, where $u$ is the unit roundoff.
• It can become arbitrarily large regardless of how small $u$ is.
• We can choose $ϵ$ as small as we want and make the backward error large.
• The factorization is not backward stable.

Where do these large entries come from?

Recall the LU factorization:

• $u_{k,}=a_{k,}$
• $l_{,k}=a_{,k}/a_{kk}$
• $A\leftarrow A-l_{,k}\ast u_{k,}$

We have a problem when the pivot $a_{kk}$ becomes very small.

LU algorithm, Stability of the LU factorization, Forward and backward error