Gilbert Strang's course notes on linear algebra - Lesson 4

The topic of lesson 4 is ： Matrix LU decompose A = LU And The complexity of elimination operation

---

Matrix LU decompose

In the second lesson matrix elimination , We know A The process of elimination can be E Express ,A The result of elimination can be U Express

To convert to A = LU, hold E Just put it on the right

How to make E Let it go ： take EA = U Multiply left by left , Available

Look at the left side of the equation , It is known that ,, that , Succeed in getting A = LU In the form of

If there are more than one E How to put it ： existing , To turn the left into A, Can be A The former part tries to become I, That is, multiply left ,（ because  ）

have to , Succeed in getting A = LU In the form of

matrix LU Explode instance

Now let's review with examples , Add a little more

Suppose the existing matrix

The process of elimination is expressed as ：

Now the E Put it on the right ：

So please E The inverse matrix ：

With A = LU The form of is ：

If the requirements are higher , We hope that the diagonal values of the diagonal matrix are 1, You can put U Split into ：

So the equation becomes ：

---

The complexity calculation of elimination

The knowledge about complexity needed here ：

1. When the operation does not involve a loop , Whatever happens in the middle , The complexity is 1, such as a + b The complexity of 1,a x b + c So is the complexity of 1（a、b、c All are numerical values ）

2. When the operation involves a loop , loop n The complexity of times is n; When a loop is nested in a loop , The complexity is n x n

Complexity knowledge complements ： The time and space complexity of the algorithm （ A look at will understand ） - You know

Suppose you want to be right about N x N Of matrix A Conduct Elimination

Review the process of elimination ：

1.  Take the elements in the first row and the first column as the fulcrum , Fix the first line

2.  The second line - first line * A coefficient , Eliminate the elements in the first column of the second row to 0; The third line - first line * A coefficient , Eliminate the elements in the first column of the third row to 0, The values below the fulcrum of the first column are all reduced to 0

3.  Turn to the second line , Take the elements in the second row and the second column as the fulcrum , Fixed second row , Downward elimination , And so on

4. Finally, we get the upper triangular matrix U

At every ” The second line - first line * A coefficient ” In the process of , For each pair of elements in the two lines , Perform multiplication and subtraction

in other words loop N Time , Multiply and subtract two elements at a time

In the process of the first line's downward elimination , A total of N-1 This operation , The complexity is N(N-1)

In the process of the second line's downward elimination , Since the first element of each column at the beginning of the second row has been eliminated as 0 了 , Therefore, the elements of operations between rows are reduced to N-1 individual , And eliminate from the second line , To be implemented N-2 operations , So the complexity is N(N-2)

And so on

Yes A The complexity of the whole process of elimination = N(N-1) + (N-1)(N-2)...2*1

When N When a large , The formula approximates Further approximation

 

about Ax = b in Column b Conduct Elimination ：

And A The elimination of is different , Every operation A Need to involve N Elements , and b It only needs to involve 1 individual

Then the first round of elimination needs to be carried out 1*(N-1) operations , The second round is 1*(N-2) operations , And so on

Yes b The complexity of the whole process of elimination =