Backward error for Crout factorization

Question

Ok, can someone please tell me what is the formula for the max error in LU decomposition of Crout factorization?

Answer 1

We want an approximation of $x$ s.t. $Ax=b$. We assume that the entries of $A,b$ are known with $p$ significant digits. Let $c$ be the condition number of $A$. Then the relative error on $x$ is $\dfrac{||\Delta x||}{||x||}\leq c.10^{-p}$.

If $c=10^k$, then $x$ is known with $p-k$ significant digits. In particular, if $k\geq p$, then we know nothing about $x$.

Moreover it is useless to calculate $c$ with a good precision ; it suffices to know $c$, up to a multiplicative factor $5$.

Unfortunately, Maple calculates the "exact" value of $c$, that is, it calculates $A^{-1}$ and deduces $c$. Golub and Van Loan (in "Matrix computations") gave a direct method (without calculation of $A^{-1}$) but I don't know the complexity of this method.

You can also proceed as follows: with LU, we obtain an approximation $\overline{x}$ of $x$ and you calculate $||A\overline{x}-b||$. It is faster than with Maple. Moreover, it is sometimes usefull because, in some cases, the true error is substantially smaller than that given by the above formula.