Have you done PA=LU factorization?

[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

 

[LongApple]

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

 

[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.

 

[statdad]

"... 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.

 

[LongApple]

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.

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 ?

 

[statdad]

"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

 

[LongApple]

"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

""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?

 

[statdad]

Take a look at http://en.wikipedia.org/wiki/LU_decomposition

 

[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

 

[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.

 

[statdad]

""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

Why do we want the LU decomposition? As one example - look up LU and solving systems of linear equations