PLU decomposition, when num. stability requires complete pivoting

250 Views Asked by At

I found this example both in class and in a book, but I'm struggling to understand why is the regular LU decomposition problematic here.
Given a matrix $$A=\left(\matrix{1 & 0 & 0 & 0 & 1\\ -1 & 1 & 0 & 0 & 1 \\ -1 & -1 & 1 & 0 & 1\\ -1 & -1 & -1 & 1 & 1\\ -1 & -1 & -1 & -1 & 1}\right)$$ the LU decomposition is$$A=LU\\ L=\left(\matrix{1 & 0 & 0 & 0 & 0\\ -1 & 1 & 0 & 0 & 0 \\ -1 & -1 & 1 & 0 & 0\\ -1 & -1 & -1 & 1 & 0\\ -1 & -1 & -1 & -1 & 1}\right) \\ U=\left(\matrix{1 & 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 & 2\\ 0 & 0 & 1 & 0 & 4\\ 0 & 0 & 0 & 1 & 8\\ 0 & 0 & 0 & 0 & 16\\ }\right) $$ and for a general $n,\ L$ will be similar, and $U$ will be the identity with powers of 2 in the last column.
Solving the system $Ax=b$ by using the decomposition gives $Ly=b\quad ,\quad Ux=y$. For a big $n$ this is said to be numerically unstable. It's clear for me that if we compute $x_n=\frac{y_n}{2^{n-1}}$, substitue $x_n$ for the computation of $x_{n-1}$ etc. we lose the LSBs which might be critical for the computation, thus losing accuracy. But if we compute $m_{in}=\frac{U_{in}}{U_{nn}}$ and calculate $x_i=y_i - m_{in}y_n$, I can't see why should it be unstable.