0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It is not quite unstable in the usual sense, the point is that errors in $b$ can be multiplied by as much as $2^n$ or so in the resulting $x$. This is bounded for fixed $n$ but still large. $\endgroup$ – Ian Nov 10 '17 at 20:41
  • $\begingroup$ Thank you. As far as I see, this will happen also when a complete pivoting is applied, since the L matrix stays unchanged and only the U matrix changes. Am I correct? $\endgroup$ – galra Nov 10 '17 at 20:59
  • 1
    $\begingroup$ U is the problem here, not L. If you can get rid of the powers of 2 in U by using complete pivoting then you remove the problem. If I recall correctly this does work because in the second step you choose the 2 that you just created in the (2,n) entry as your new pivot, which avoids the creation of the 4, and it propagates like this. $\endgroup$ – Ian Nov 10 '17 at 21:13
  • 1
    $\begingroup$ By the way Trefethen and Bau is an excellent book and talks about this example a bit. It is rather classic and yet peculiar because usually in practice Gaussian elimination with partial pivoting has much better stability properties than this example. $\endgroup$ – Ian Nov 10 '17 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.