Gaussian Elimination and condition number

Question

When we use Gaussian Elimination algorithm to linear system, do we care about the condition number of the matrix? Why or Why not?

Answer 1

The condition number $\kappa$ is a measure used to show loss of precision.

In the problem $Ax=b$ the problem of computing $b$ has the following condition number

$$ \kappa = \frac{\|A\| \|x\|}{\|b\|} \leq \| A\| \|A^{-1}\|$$

In general for $\kappa(A) = 10^{k}$ you will lose $k$ digits of accuracy so ill-conditioned matrices will throw off your solution.

In terms of Gaussian elimination specifically we care because Gaussian Elimination is fairly sensitive to the condition number. Without pivots it is fairly unstable. Consider the matrix $A$ given as

$$ A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$$

now if you apply a small perturbation like the following

$$ A = \begin{bmatrix} 10^{-20} & 1 \\ 1 & 1 \end{bmatrix}$$

then $A=LU$ is given as

$$ A = LU = \begin{bmatrix} 1 & 0 \\ 10^{20} & 1 \end{bmatrix} \begin{bmatrix} 1 & 10^{-20} \\ 0 & 1 - 10^{-20} \end{bmatrix} $$

Now consider that

$$ \|A \| \leq \| L \| \| U \| $$