There's a big flaw in LU, factorization that we haven't yet exposed. Here's a little four-by-four system which is no problem to solve, can use the usual LU factorization, forward substitution, back substitution. And the x we get is perfectly fine. However, if I just change the rows around, I swap two rows in a and I swap the same rows and be. All I've done is change the order of the equations in the linear system. It doesn't even change the solution at all. However, now LU factorization completely fails. So here we have a non-singular matrix for which LU factorization gives a useless result. Infinities and not a number which usually comes from 0 over 0. We need to modify the original factorization. It's not hard to discover what goes wrong with the factorization. So here is how we started off as usual. And we've done what we set out to do. We've put zeros in the first column and the first row like we're supposed to. But now look what happens if we go on to the next step of the algorithm to work on the second column, we end up dividing by this number here, the 22 position, which is 0. And that causes all the grief. Once that happens, we can't continue. This number here is called the pivot element. And if we choose a 0 pivot, the algorithm is over. But fortunately, now that we've identified the problem, there's a fairly simple way out of it. So here let's start over again with one. But now instead of using the pivot row one like we normally where before, let's just choose a different row. So instead of always working in the first column, first row, let's work in the first column, fourth row for sake of argument. So everywhere before I was using the first row, I'm just going to use the fourth row instead. And when I do that, I put zeros in the first column and the fourth row. Now I just need to see why that works out. Well, if you think about this inner product or this outer product here, right? This is the i j element. And if i is equal to four, this term cancels out the denominator and you just get a copy of row four. Or if j is equal to one, then these terms cancel out and I just get a copy of column one. So I am just going to get a copy of column one and row four in the appropriate places. So when I subtract those out, I get the zeros. And now we could continue. As long as I avoid a 0 pivot element will be fine. So if I chose the third row, then I just have to operate with the third row and these two spots here. And we now have two rows and columns of all zeros and so on. So rather than continuing this example, let's just write a new function. Here's our modified form of LU factorization. And calling it PLU for pivoted. We start off much as seen before, but now we're going to keep track also of an array of row indices. So every time I pick a pivot row, I'm going to store it here. Now, how do I choose a pivot rows before I was just doing it by eyeballing. All we really have to do is avoid zeros. But for reasons we'll get into, it's actually better to just choose the largest element available in absolute value. How do I do that? Well, here's column k. That's the column that we're working with in iteration number k. I take the absolute value of every element. Remember I have to use the dots so that the absolute value function is applied to each element. And then out of that vector I want to pick the largest one. So that's the function called arg max. That gives us the index of the largest element in that vector. And that's what I'm going to call the kth pivot. Now we do everything else as before, we just use that row. When we do our new definitions for L and U, we subtract that off and everything finishes as before. Now, in our final version of LU factorization, we didn't operate on all the rows because that saved some computational effort. We can do that here too, but it's just a little bit more bookkeeping to do. And it clutters things up without being particularly interesting. Alright, so now if I do the pivoted LU factorization of a, I still get a factorization of a L times U is equal to a. U is upper triangular, just like before. But l, the price that we paid as L is no longer a unit lower triangular matrix. It's not even lower triangular at all. However, it's not very far from lower triangular. If I reorder the rows of l according to our pivots, it's once again unit lower triangular. There's a convenient algebraic notation for dealing with reordering the way we've been doing it. And then there's a permutation matrices. So if I let capital P be an identity matrix of size four, and I want to reorder its rows according to our pivot vector. Ok, this notation shows you where the ones are in that matrix. But if we want to see it as an ordinary matrix, we can just convert it to a regular matrix type. And whenever you have an identity matrix with rearranged rows or for that matter, with rearrange columns. It's a permutation matrix. And multiplying on the left by a permutation matrix is the same as reordering the rows of the matrix according to the pivot vector. So here's our original a. Here's the result of multiplying by the permutation matrix. You see all that does is take the original rows, any order 4321. And that's the same thing as direct a reordering the rows of a. And in fact, if you trace through what we've done, the pivoted LU factorization on the original a is identical to the LU factorization on the pivot a day with a reordered the permuted a. This is the same l that's returned by the pivoted LU factorization. Does finally. Alright. Now, why not just do that? Well, because we don't know this permutation matrix P until we've run the pivoting algorithm. So this is theoretically interesting and useful, but not quite practical as far as suggesting how the algorithm should work. Finally, then, how should we use this pivoted LU factorization to solve a linear system? So it's quite simple actually in practice, since we start with AX equals B, we can multiply both sides by any non-singular matrix. So we'll use the permutation matrix. And P times a is equal to L times U. That's a way of expressing how the pivoted LU works were now L and U are triangular matrices. So all I have to do is permute the rows of B the same way. And now I have triangular systems to solve as before. So we've got this permuted l, we permute it back to lower triangular. We permute the rows of B the same way, and we get a solution to the original system.
Section 2.6
From Tobin Driscoll September 02, 2020
3 plays
3
0 comments
0
You unliked the media.