线性方程组
目录
1 Cramer 法则 2
2 消元法 2
2.1 Gauss 消元法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 列主元消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 全主元素消元法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 直接分解法 3
3.1 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.1.1 Doolittle 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.1.2 Crout 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.1.3 LDU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.1.4 Cholesky 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1
1 Cramer 法则
没有人会用 Cramer 法则解线性方程组
2 消元法
对角方程组的解是显然的
𝑎
11
𝑥
1
= 𝑏
1
𝑎
22
𝑥
2
= 𝑏
2
.
.
.
𝑎
𝑛𝑛
𝑥
𝑛
= 𝑏
𝑛
⇒ 𝑥
𝑖
=
𝑏
𝑖
𝑎
𝑖𝑖
下三角方程组的解可以通过回代法求得
𝑎
11
𝑥
1
= 𝑏
1
𝑎
21
𝑥
1
+ 𝑎
22
𝑥
2
= 𝑏
2
.
.
.
𝑎
𝑛1
𝑥
1
+ 𝑎
𝑛2
𝑥
2
+ · · · + 𝑎
𝑛𝑛
𝑥
𝑛
= 𝑏
𝑛
⇒
𝑥
1
=
𝑏
1
𝑎
11
𝑥
2
=
𝑏
2
− 𝑎
21
𝑥
1
𝑎
22
.
.
.
𝑥
𝑛
=
𝑏
𝑛
−
Í
𝑛−1
𝑖=1
𝑎
𝑛𝑖
𝑥
𝑖
𝑎
𝑛𝑛
2.1 Gauss 消元法
对于一般的方程组, 可以通过消元法将其化为上三角方程组, 然后通过回代法求解
1. 对于当前列 𝑖, 选定第一个非零的元素 𝑎
𝑗𝑖
( 𝑗 ≥ 𝑖) 作为主元素, 通过交换行将其移到对角线上
2. 通过消元将当前列的其他元素化为 0
3. 重复上述步骤, 直到矩阵变为上三角矩阵
Gauss 消元法是按自然顺序消去未知数, 也称为顺序消元法. 不过当主元较小时计算的舍入误差较大
2.2 列主元消去法
列主元消去法是在顺序消元法的基础上, 每次选取当前列的绝对值最大的元素作为主元素, 通过交换行将
其移到对角线上. 如
5𝑥
1
+ 4𝑥
2
+ 10𝑥
3
= 0
𝑥
1
+ 𝑥
2
+ 3𝑥
3
= 1
3𝑥
1
− 0.1𝑥
2
+ 2𝑥
3
= 2
2.3 全主元素消元法
全主元素消去法是在列主元消去法的基础上, 每次选取当前矩阵的绝对值最大的元素作为主元素, 通过交
换行和列将其移到对角线上. 如
3 直接分解法
3.1 LU 分解
利用顺序主子式可以证明
当且仅当 𝐴 的所有顺序主子阵非零时,𝐴 有 LU 分解并且唯一
事实上对于任意的可逆矩阵 𝐴, 可以利用置换使得 𝐴 的顺序主子阵非零, 从而得到 LU 分解
𝑃𝐴 = 𝐿𝑈
3.1.1 Doolittle 分解
考虑高斯消元过程, 采取如下的消元顺序
𝐴
11
→ 𝐴
21
, 𝐴
31
, · · · , 𝐴
𝑛1
𝐴
22
→ 𝐴
32
, 𝐴
42
, · · · , 𝐴
𝑛2
.
.
.
𝐴
𝑛𝑛−1
→
𝐴
𝑛,𝑛
将消元系数取反后写入对应位置即得到 𝐿 矩阵, 消元完成后的矩阵即为 𝑈 矩阵. 这样得到的 𝐿 矩阵的对
角线元素为 1,𝑈 矩阵的对角元不变
3.1.2 Crout 分解
如果要求 𝑈 矩阵的对角元为 1, 而不要求 𝐿 矩阵的对角元为 1, 即 Crout 分解
3.1.3 LDU 分解
如果要求 𝐿 矩阵和 𝑈 矩阵的对角元都为 1, 即 LDU 分解
𝐴 = 𝐿𝐷𝑈
其中 𝐷 是对角矩阵. 将 Doolittle 分解的 𝑈 矩阵的对角元全部提取出来; 或是将 Crout 分解的 𝐿 矩阵的
对角元全部提取出来即得到 𝐷 矩阵
3.1.4 Cholesky 分解
对于对称正定矩阵, 可以进行 Cholesky 分解
𝐴 = 𝐿𝐿
𝑇
这可以由待定系数法求解
©
«
𝑎
11
𝑎
12
· · · 𝑎
1𝑛
𝑎
21
𝑎
22
· · · 𝑎
2𝑛
.
.
.
.
.
.
.
.
.
.
.
.
𝑎
𝑛1
𝑎
𝑛2
· · · 𝑎
𝑛𝑛
ª
®
®
®
®
®
®
¬
=
©
«
𝑙
11
𝑙
21
𝑙
22
.
.
.
.
.
.
.
.
.
𝑙
𝑛1
𝑙
𝑛2
· · · 𝑙
𝑛𝑛
ª
®
®
®
®
®
®
¬
©
«
𝑙
11
𝑙
21
· · · 𝑙
𝑛1
𝑙
22
· · · 𝑙
𝑛2
.
.
.
.
.
.
𝑙
𝑛𝑛
ª
®
®
®
®
®
®
¬
对比系数得到
𝑙
𝑖𝑖
=
v
t
𝑎
𝑖𝑖
−
𝑖−1
Õ
𝑘=1
𝑙
2
𝑖𝑘
𝑙
𝑖 𝑗
=
1
𝑙
𝑗 𝑗
𝑎
𝑖 𝑗
−
𝑗−1
Õ
𝑘=1
𝑙
𝑖𝑘
𝑙
𝑗 𝑘
!
若不希望开平方根, 可以采用 𝐿𝐷 𝐿
𝑇
分解
©
«
𝑎
11
𝑎
12
· · · 𝑎
1𝑛
𝑎
21
𝑎
22
· · · 𝑎
2𝑛
.
.
.
.
.
.
.
.
.
.
.
.
𝑎
𝑛1
𝑎
𝑛2
· · · 𝑎
𝑛𝑛
ª
®
®
®
®
®
®
¬
=
©
«
1
𝑙
21
1
.
.
.
.
.
.
.
.
.
𝑙
𝑛1
𝑙
𝑛2
· · · 1
ª
®
®
®
®
®
®
¬
©
«
𝑑
1
𝑑
2
.
.
.
𝑑
𝑛
ª
®
®
®
®
®
®
¬
©
«
1 𝑙
21
· · · 𝑙
𝑛1
1 · · · 𝑙
𝑛2
.
.
.
.
.
.
1
ª
®
®
®
®
®
®
¬
