4.【线性代数】——矩阵的LU分解
四 矩阵的LU分解
- 1. AB的逆矩阵
- 2. 转置矩阵
- 3. A=LU
- 3.1 2x2矩阵
- 3.2 3x3矩阵
- 3.3 nxn的矩阵分解的次数？
1. AB的逆矩阵
{ ( A B ) ( B − 1 A − 1 ) = I ( B − 1 A − 1 ) ( A B ) = I ⇒ ( A B ) − 1 = B − 1 A − 1 \begin{cases} (AB)(B^{-1}A^{-1}) = I\\ (B^{-1}A^{-1}) (AB)=I \end{cases} \Rightarrow (AB)^{-1} = B^{-1}A^{-1} {(AB)(B−1A−1)=I(B−1A−1)(AB)=I⇒(AB)−1=B−1A−1
2. 转置矩阵
A
A
−
1
=
I
⇒
两边同时转置
(
A
A
−
1
)
T
=
I
⇒
(
A
B
)
T
=
B
T
A
T
(
A
−
1
)
T
A
T
=
I
\begin{aligned} AA^{-1}=I & \newline \xRightarrow{\text{两边同时转置}} (AA^{-1})^{T}=I &\newline \xRightarrow {(AB)^T = B^TA^T} (A^{-1})^TA^T=I \end{aligned}
AA−1=I两边同时转置(AA−1)T=I(AB)T=BTAT(A−1)TAT=I
转置矩阵的逆 = 逆矩阵的转置
3. A=LU
3.1 2x2矩阵
A矩阵进行消元，可以得到EA=U
[
1
0
−
4
1
]
⏟
E
[
2
1
8
7
]
⏟
A
=
[
2
1
0
3
]
⏟
U
\underbrace{\begin{bmatrix} 1&0\\ -4&1 \end{bmatrix}}_{E} \underbrace{\begin{bmatrix} 2&1\\ 8 &7 \end{bmatrix}}_{\text{A}}= \underbrace{\begin{bmatrix} 2&1\\ 0&3 \end{bmatrix}}_{U}
E
[1−401]A
[2817]=U
[2013]
两边同时乘以
E
−
1
E^{-1}
E−1，得到A=LU。其中L为下三角矩阵(lower),U为上三角矩阵(upper)。
[
2
1
8
7
]
⏟
A
=
[
1
0
4
1
]
⏟
L
[
2
1
0
3
]
⏟
U
\underbrace{\begin{bmatrix} 2&1\\ 8 &7 \end{bmatrix}}_{\text{A}}=\underbrace{\begin{bmatrix} 1&0\\ 4&1 \end{bmatrix}}_{L} \underbrace{\begin{bmatrix} 2&1\\ 0&3 \end{bmatrix}}_{U}
A
[2817]=L
[1401]U
[2013]
3.2 3x3矩阵
样例来源于 2.【线性代数】——矩阵消元的第三部分
其中
E
21
E_{21}
E21表示
r
o
w
2
−
3
r
o
w
1
row_2-3row_1
row2−3row1,
E
32
E_{32}
E32表示
r
o
w
3
−
2
r
o
w
2
row_3-2row_2
row3−2row2
[
1
0
0
0
1
0
0
−
2
1
]
⏟
E
32
[
1
0
0
−
3
1
0
0
0
1
]
⏟
E
21
[
1
2
1
3
8
1
0
4
1
]
⏟
A
=
[
1
2
1
0
2
−
2
0
0
5
]
⏟
U
\underbrace{\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&-2&1\\ \end{bmatrix}}_{E_{32}} \underbrace{\begin{bmatrix} 1&0&0\\ -3&1&0\\ 0&0&1\\ \end{bmatrix}}_{E_{21}} \underbrace{\begin{bmatrix} 1&2&1\\ 3&8 &1\\ 0&4&1 \end{bmatrix}}_{\text{A}}= \underbrace{\begin{bmatrix} 1&2&1\\ 0&2&-2\\ 0&0&5 \end{bmatrix}}_{\text{U}}
E32
10001−2001
E21
1−30010001
A
130284111
=U
1002201−25
A
=
(
E
21
)
−
1
(
E
32
)
−
1
U
A=(E_{21})^{-1}(E_{32})^{-1}U
A=(E21)−1(E32)−1U
逆矩阵的求法，参考 2.【线性代数】——矩阵消元的第五部分
L
=
[
1
0
0
3
1
0
0
0
1
]
⏟
(
E
21
)
−
1
[
1
0
0
0
1
0
0
2
1
]
⏟
(
E
32
)
−
1
=
[
1
0
0
3
1
0
0
2
1
]
L = \underbrace{\begin{bmatrix} 1&0&0\\ 3&1&0\\ 0&0&1\\ \end{bmatrix}}_{(E_{21})^{-1}} \underbrace{\begin{bmatrix} 1&0&0\\ 0&1&0\\ 0&2&1\\ \end{bmatrix}}_{(E_{32})^{-1}} =\begin{bmatrix} 1&0&0\\ \boxed{3}&1&0\\ 0&\boxed{2}&1\\ \end{bmatrix}
L=(E21)−1
130010001
(E32)−1
100012001
=
130012001
为什么用L矩阵？
- 因为在不存在行交换的额情况下，消元乘数可直接写入L
3.3 nxn的矩阵分解的次数？
[
a
b
c
d
]
⇒
[
a
b
c
−
a
∗
c
a
d
−
b
∗
c
a
]
,
c
−
a
∗
c
a
是一次操作。
\begin{bmatrix} a&b\\ c&d\\ \end{bmatrix} \Rightarrow \begin{bmatrix} a&b\\ c-a*{\frac c a}&d-b*{\frac c a}\\ \end{bmatrix}, \boxed{c-a*{\frac c a}}是一次操作。
[acbd]⇒[ac−a∗acbd−b∗ac],c−a∗ac是一次操作。
那么100x100的矩阵，获得第一个主元的估算操作数为
10
0
2
100^2
1002；获得第二个主元的估算操作数为
9
9
2
99^2
992；获得第三个主元的估算操作数是
9
8
2
98^2
982…
求和为
1
2
+
2
2
+
.
.
.
+
n
2
≈
1
3
n
3
1^2+2^2+...+n^2\approx{\frac 1 3}n^3
12+22+...+n2≈31n3