1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
Ax = b where A = mxn, x = 1xm, b = 1xn. x_i and b_i are defined to be in
the ith row of their corresponding vectors.
If C is an invertible mxm matrix, CAx = Cb is equivalent to Ax = b.
(1)
If x_0 satisfies Ax_0 = b, CAx_0 = Cb is satisfied.
(2)
If x_1 satisfies CAx_0 = Cb, C^{-1} CAx_0 = C^{-1} Cb \to Ax_0 = b
is satisfied.
(I believe this proof requires associativity)
LU Decomposition/Factorization
Goal: Factorize A into a lower triangular and upper triangular matrices
L and U respectively. (These are very non-unique)
A = LU. Conventionally, L is mxm, and U is mxn.
Ax = b ---> LUx = b ---> Y = Ux, LY = b.
If we assert that L is an invertible matrix (e.g. ones down the
diagonal), this is trivial to solve
1 0 0 y1 b1
( c21 1 0 ... ) * ( y2 ) = ( b2 )
c31 c32 1 y3 b3
... ... ...
Y has a unique solution by construction. ( ex: y1 = b1, c21*y1 + y2 = b2 ...)
U is upper triangular, meaning that it is strictly zero below the
diagonal started at the top-left. (However, we have no control over the
values of the diagonal or the values above the diagonal)
[Note] How do we ensure that L and U retain the properties of the
original matrix's solution? (i.e. not just matrices of zero)
Using a series of row operations (written as invertible matrices C_1,
C_2, ..., C_k -- that is, adding a multiple to a lower row) will turn A
into echelon (upper triangular), and C_1^{-1}C_2^{-1}*...*C_k^{-1} = L
(lower triangular). U is not reduced-echelon, but it is echelon/upper
triangular.
|
