0
$\begingroup$

I'm trying to LU decompose, with pivoting, the following matrix ($A=(a_{ij})$):

A = [2 1 2; 1 0 3; 4 -3 -1]; % matlab

I cannot make out from my literature (Chapra, "Applied Numerical Methods") or elsewhere in what order things should be done. The exercise I'm trying to do says to "Gauss eliminate using pivoting". I arrive at the same solution as Matlab

[L,U,P]=lu(A);
% here, L = [1 0 0; 0.5 1 0; 0.25 0.3 1]
% U = [4 -3 -1; 0 2.5 2.5; 0 0 2.5]
% P = [0 0 1; 1 0 0; 0 1 0]

if I first switch rows 1 and 3, then 2 and 3 to get

PA = [4 -3 -1; 2 1 2; 1 0 3]; % var name, not multiplication

upon which I perform Gauss elimination, putting $\ell_{21} = 2/4$, $\ell_{31}=1/4$ into $L=(\ell_{ij})$. However that is not how Chapra himself describes Gauss elimination with pivoting, seen here (fig 9.5, p 264 slider enumeration; without the back substitution).

Using his algorithm (applied here as: switch rows 1 and 3, gauss elim, switch rows 2 and 3, gauss elim), I get the same $U$ as with the above Matlab command, except that in my case,

K = [1 0 0; 0.25 1 0; 0.5 0.3 1]; % i.e. my decomp is K*U

However, $K*U \neq P*A$ with the above $P$. This is all a big mess. I've gone through Chapra's algorithm many times by now and I'm sure I've followed the algorithm correctly (point of the exercise is to do LU factorization by hand), what am I doing wrong? What is the correct way to do it? I'm afraid I don't find Chapra's explanations and examples very enlightening...

$\endgroup$
5
  • $\begingroup$ I just verified your and Matlab's solution and I get the same exact result and will now check his approach. $\endgroup$
    – Moo
    Jan 12, 2016 at 3:00
  • $\begingroup$ I can add the manual approach I used - which matches what you got, but I did it by hand. Also, can you try this matlab code (I cannot read matlab - and he does not show the algorithm, but only matlab code), rosettacode.org/wiki/… . Also try, mathworks.com/matlabcentral/fileexchange/… and stackoverflow.com/questions/15304012/… $\endgroup$
    – Moo
    Jan 12, 2016 at 3:16
  • $\begingroup$ When I look at Example 10.3, it mimics the approach exactly how I did it by hand. Section 9.6 is Gauss Elimination with Pivoting (maybe there is some other stuff required there to make that work correctly that is causing the confusion). I would look at CH 10 which is dedicated to $LU$ Decomposition. If you look at Algorithm 21.1, maybe you can mimic it to do GE w/pivot at: www4.ncsu.edu/~kksivara/ma505/handouts/lu-pivot.pdf $\endgroup$
    – Moo
    Jan 12, 2016 at 3:27
  • $\begingroup$ Naturally I've looked in ch 10 ;) Here is an excellent explanation, see p66 for algo: math.iit.edu/~fass/477577_Chapter_7.pdf From it, it seems my problem was with the actual pivoting. While the principle of pivoting is easy to understand, it's not as obvious how it works when calculating L,U. If you could write down your manual calculation, in an answer maybe, that'd be great. $\endgroup$ Jan 12, 2016 at 3:30
  • $\begingroup$ I added the manual solution with all steps. $\endgroup$
    – Moo
    Jan 12, 2016 at 4:01

0

You must log in to answer this question.