Have you done PA=LU factorization?

1. Feb 15, 2015

LongApple

I'm trying to figure out what this quote means and what our strategy is just looking at the matrix what kind of permutations we need to do.

Quotes: "The first permutation step is trivial (since the pivot element 10 is already the largest). The corresponding permutation matrix is the identity, and we need not write it down. The first elimination step is:"

Why do we need to do permutations at all? How do we know by looking?

https://www.student.cs.uwaterloo.ca/~cs370/notes/LUExample2.pdf

2. Feb 15, 2015

LongApple

So as a start, why do we care at all that 10 is the largest?

3. Feb 15, 2015

lurflurf

Dividing by small numbers is bad. We do permutations so we may divide by a big number. In step 1 10 is already the biggest available. In step 2 5/2 is larger than 1/10 so we do a permutation so we can divide by 5/2 instead of 1/10.

4. Feb 15, 2015

"... what kind of permutations we need to do."
Are you referring to what permutations have to do in this setting (I may be grossly misunderstanding the thrust of your question)? If so, they are referring to rearranging (permuting is rearranging) the rows in order to bring a more desirable value to the pivot location.

If that wasn't your question - apologies.

5. Feb 15, 2015

LongApple

1. Why is dividing by big numbers bad? Aside from inconvenient I don't see why big number necessarily necessitates row swaps

2. 10 is already the biggest available" <- available of _____ ? Of the numbers down the column

I'm a bit confused about P

Given a matrix A, does it always have a fixed P for LU factorization? Couldn't we have multiple different P's depending on how we RREF the problem ?

6. Feb 15, 2015

"Why is dividing by big numbers bad?"
Read again - dividing by small numbers is to be avoided

"Of the numbers down the column" Yes

"Given a matrix A, does it always have a fixed P for LU factorization? Couldn't we have multiple different P's depending on how we RREF the problem"
Yes, you can: each time rows are swapped there is another P: take a look here:
http://staff.imsa.edu/~fogel/LinAlg/PDF/17 Permutations and Row Swaps.pdf

7. Feb 15, 2015

LongApple

""Why is dividing by big numbers bad?"
Read again - dividing by small numbers is to be avoided"

Yup I read that the first time. Now - why do we want this or even if we want it why is it necessary? Maybe it is obvious to you

Aside from inconvenient I don't see why big number necessarily necessitates row swaps

____________

1. Why does L have 1's down the diagonal? Couldn't it have anything down the diagonal?

2. Is P is not unique, then LU is not unique right. So how have linear algebra people been grading tests all these years? They can't enumerate all possible LU's can they or take the time to manually multiply every studetn's answer out can they?

Attached Files:

File size:
97 KB
Views:
322
8. Feb 15, 2015

9. Feb 16, 2015

LongApple

""Why is dividing by big numbers bad?"
Read again - dividing by small numbers is to be avoided"

Yup I read that the first time. Now - why do we want this or even if we want it why is it necessary? Maybe it is obvious to you

not in wikipedia

10. Feb 16, 2015

lurflurf

The wikipedia gives a classic example of the need for pivoting consider two systems
$$\left[ \begin{array}{cc|c} 0.00300 & 59.14 & 59.17 \\ 5.291 & -6.130 & 46.78 \\ \end{array} \right] \\ \left[ \begin{array}{cc|c} 5.291 & -6.130 & 46.78 \\ 0.00300 & 59.14 & 59.17 \\ \end{array} \right]$$
If we work with 4 digits and no pivoting we get for the first system
{9873.3,4}
for the second
{10.00,1.000}
We see the two systems should have the same solution, but the first one came out wrong due to dividing by small numbers.
So we decide to divide by the largest number available.

Edit: I got something different when I checked the wikipedia result, I probably added wrong somewhere.

Last edited: Feb 16, 2015
11. Feb 16, 2015