（1）前代运算——求解 Lz=b
 )z = b ⇒ z = b - Lz  =b−∑L z (I + L i i
j = 1,..., n-1
i =1 n −1
⎡0 ⎤ ⎡0 ⎤ ⎡ z1 ⎤ ⎡ b1 ⎤ ⎡ 0 ⎤ ⎢ ⎥ ⎢ ⎥ ⎢ z ⎥ ⎢b ⎥ ⎢ L ⎥ 0 0 ⎢ ⎥ ⎢ ⎥ ⎢ 2 ⎥ ⎢ 2 ⎥ ⎢ 2,1 ⎥ ⎥ z n −1 ⎢ z3 ⎥ = ⎢ b3 ⎥ − ⎢ L3,1 ⎥ z1 − ⎢ L32 ⎥ z 2 − " − ⎢ 0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢# ⎥ ⎢# ⎥ ⎢# ⎥ ⎢# ⎥ ⎢ ⎢L ⎥ ⎢L ⎥ ⎢ z ⎥ ⎢b ⎥ ⎢ L ⎥ , 1 n n − ,2 n n n ⎣ ⎦ ⎣ ⎦ ⎣ n ,1 ⎦ ⎣ ⎦ ⎣ ⎦
⎡ ⎢* = ⎢ L ⎢* * ⎢ ⎣* * *
⎤ ⎥ ⎥ ⎥ ⎥ ⎦
i = j +1,..., n
z ←b
① z中下标小者只影响z中下标大者。

⎡loop j = 1, ", n − 1 ⎢ ②当zj等于零时的计算可省略。

⎢ ⎡loop i = j + 1, ", n ⎢ ⎢ zi = zi − Lij z j ③ z中下标大者的计算，还受L稀疏性的 ⎢ ⎢ 影响（遇L中零元，计算可省略 ）。

⎢ ⎢ ⎣end loop ⎢ ⎣end loop


常规程序
z ← b ⎡ j = 1, " , n − 1 ⎢ if z ≠ 0 th e n j ② ⎢ ⎢ ⎡ i = j + 1, " , n ① ⎢ ⎢ if L ≠ 0 th e n ⎢ ③ ij ⎢ ⎢ ⎢ z i = z i − L ij * z j ⎢ ⎢ ⎢ ⎢ e n d if ⎢ ⎢ e n d lo o p ⎢ ⎣ ⎢ ⎢ e n d if ⎢ ⎣ e n d lo o p
基于稀疏存储的程序
z ← b j = 1,", n −1 if z(j) ≠ 0 then
②
k = JL( j), JL( j +1) −1 ① ③ i = IL(k ) z(i) = z(i) − L(k )* z( j) end loop
end if end loop
① z中下标小者只影响z中下标大者。

②当zj等于零时的计算可省略。

③ z中下标大者的计算，还受L稀疏性的影响 （遇L中零元，计算可省略 ）。

a14 ⎤ ⎡a11 a12 ⎢a ⎥ a a 21 22 23 ⎢ ⎥ ⎢ ⎥ a33 ⎢ ⎥ a a a 42 43 44 ⎦ ⎣


（2）除法运算，求解 Dy=z
yi = zi / d ii
（3）回代运算——求解
Ux=y
2 j=n
⎧Lz = b ⎪ ⎨Dy = z ⎪Ux = y ⎩
⎡ ⎢  =⎢ U ⎢ ⎢ ⎣ * * *⎤ * *⎥ ⎥ *⎥ ⎥ ⎦
 = y−∑U x  )x = b ⇒ x = y - Ux (I + U j j
⎡U1,n-1 ⎤ ⎡U1,n−1 ⎤ ⎡U1,n ⎤ ⎫ ⎡U13 ⎤ ⎡ x1 ⎤ ⎡ y1 ⎤ ⎧⎡U12 ⎤ ⎢ ⎥⎢ ⎥ ⎢ ⎥ ⎪ ⎢U ⎥ ⎢ x ⎥ ⎢ y ⎥ ⎪⎢ ⎥ 0 ⎥ 23 ⎥ ⎢U2,n-1 ⎥ ⎢U2,n−1 ⎥ ⎢U 2,n ⎥ ⎪ ⎢ ⎢ 2 ⎥ ⎢ 2 ⎥ ⎪ ⎢ ⎪ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎢ # ⎥ = ⎢ # ⎥−⎪ ⎢ ⎥ xn ⎬ # xn−1 + # ⎨ # x2 + 0 x3 + "+ ⎢# ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎪⎢ ⎥ ⎪ 0 0 x y U # # ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ n − 1 n − 1 n − 1, n ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎪⎢ ⎥ ⎪ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢0 ⎥ ⎢ x ⎥ ⎢ y ⎥ ⎪⎢ 0 ⎥ 0 0 ⎪ ⎣ n ⎦ ⎣ n ⎦ ⎩⎣ ⎦ ⎣ ⎦ ⎦ ⎭ ⎣ ⎦⎣ ⎦ ⎣0


⎡U1,n−1 ⎤ ⎡U1,n ⎤ ⎫ ⎡U13 ⎤ ⎡ x1 ⎤ ⎡ y1 ⎤ ⎧⎡U12 ⎤ ⎢ ⎥ ⎢ ⎥ ⎪ ⎢U ⎥ ⎢ x ⎥ ⎢ y ⎥ ⎪⎢ ⎥ 0 ⎥ 23 ⎥ ⎢U2,n−1 ⎥ ⎢U2,n ⎥ ⎪ ⎢ ⎢ 2 ⎥ ⎢ 2 ⎥ ⎪ ⎢ ⎪ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ # ⎥ = ⎢ # ⎥ −⎪ ⎢ ⎥ ⎨ # x2 + 0 x3 + "+ ⎢ # ⎥ xn−1 + ⎢ # ⎥ xn ⎬ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎪⎢ ⎥ ⎪ # # x y U 0 ⎢ ⎥ ⎢ ⎥ 1 1 1, n − n − n − n ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎪⎢ ⎥ ⎪ ⎢ ⎥ ⎢ ⎥ ⎢0 ⎥ ⎢ x ⎥ ⎢ y ⎥ ⎪⎢ 0 ⎥ 0 ⎪ ⎣ n ⎦ ⎣ n ⎦ ⎩⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣0 ⎦ ⎭
j = n,...,2
i = j −1,...,1
常规程序
x← y ⎡ j = n," , 2 ⎢ ⎢ ⎡ i = j − 1, " ,1 ⎢ ⎢ x i = x i − U ij * x j ⎢ ⎢ ⎢ ⎢ ⎣ en d lo o p ⎢ ⎣ en d lo o p
基于稀疏存储的程序
x← y
i = n − 1,",1
k = IU (i + 1) − 1, IU (i ) j = JU ( k )
a14 ⎤ ⎡a11 a12 ⎢a ⎥ ⎢ 21 a22 a23 ⎥ ⎢ ⎥ a33 ⎢ ⎥ a42 a43 a44 ⎦ ⎣
X (i ) = X (i ) − U ( k ) * X ( j )
end loop end loop


3.3
3.3.1 定义、术语
稀疏矩阵的图论描述
z为什么要用图来描述？
Ax=b
图⇔矩阵:
如A=AT，则A=UTDU 因子表矩阵
矩阵A中非对角元 Æ电网络中串联支路Æ图中支路
图中网络拓扑 Æ A (或U)中非零元的分布 图中支路权重 Æ A (或U)中非零元素值
A图 因子图
有向A图 有向因子图
赋权有向A图 赋权有向因子图


A图：与矩阵A有相同拓扑的图
1 2 3 4 5 6 7 8 910 1112
1 2 3 4 5 6 7 8 9 10 11 12
x x 3 5 7 9
11
x x x x x x x x x x x x x x x x x x x
x
4
7
1
10
11
12
x
6 8 5
A=
3
9
2
x x x
A图


有向A图：在A图上，边的方向定义：由小号点→大号点； 赋权有向A图：互边赋权aij，自边赋权aii
a4 , 4
4 7 1 4 7
a1,1 a1, 7
1
a1,12
12
10
11
12
10
11
6
8
5
6
8
5
a2,5
3 9 2 3 9
a2,9
2
a2 , 2
有向A图
赋权有向A图


因子图：与因子表矩阵U有相同拓扑结构的图； 有向因子图：定义边的方向：由小号点→大号点；
x x 3 5 x x x x 7 9
11
x x x x O O x x x x O x x x x
x
4
7
1
10
11
12
x O
6 8
U=
5
x O O O x x O x x x
3 9 2
有向因子图
红点表示注入元素


赋权有向因子图：自边的权是dii，互边的权是Uij
x x 3 5 x x x x x x
4 7
u1,1
1
u1,2 u7,12
x x x x
x
u1,12
12
10
11
U=
7 9
11
O x x O x x O O x x x x O O O x x O x x x
6
8
5
u5,9
3 9
u2,5
2
u2,9
u2,2


3.3.2 因子分解过程的图上描述
因子分解的两操作（小→大）： ①规格化； ②消去
2
4 2 7 5
x x x x
x x x x x x o x
x o x x
4 5
赋权有向A图上操作 4 2 5 7
7


节点②发出边的对端节点的自边。