1 u11 u1n A l21 ln1 1 unn
因为 k u11u22 ukk 0 k 1,2,n ukk 0
1 u11 l u22 21 A ln1 ln 2 1
• 追赶法解三对角方程组
b1 a 2 c1 b2 a3 c2 b3 c3 ai bi ci an an 1 bn 1 x1 d1 x d 2 2 x3 d 3 xi d i cn 1 xn 1 d n 1 bn xn d n
分解公式
k 1 m 1
2 2 akk lkm lkm lkm lkk
k 1
2 lkk akk lkm m 1
第一步 ： a l 2 l a 11 11 11 11
ai1 l11 li1 li1 ai1 / l11
ik
aik lim lkm
其中L为单位下三角阵，D是对角元全为正的对角 阵且这种分解式唯一;
2A LLT
其中L为下三角阵，当限定L的对角元为正时的分 解式唯一（Cholesky分解）.
August 5, 2013 yfnie@ 5
平方根法（Cholesky分解）
定理证明
证明： 因为 A对称正定，故其顺序主式 k 0k 1,2,n ， 从而A 有唯一的Doolittle分解
August 5, 2013
yfnie@
8
平方根法（Cholesky分解）：
l11 l11 l21 ln1 l l22 l22 A 21 ln1 lnn lnn
n m 1
August 5, 2013
yfnie@
2
3.3 列主元直接三角分解法
设对 Ab的分解已完成k-1步，即L 的前k-1列,U之 的前k-1行已求出：
u11 l21 lk 1 ln1 u12 u22 lk 2 ln 2 u1,k 1 u 2,k 1 lk ,k 1 ln ,k 1 u1k u2 k akk ank u1,n 1 u2,n 1 ak ,n 1 an ,n 1
方程求解公式
y1 d1 i 2,3,, n 得 yi d i li yi 1
由
u1 c1 x1 y1 u2 x2 y 2 cn 1 un xn yn
m 1
n
i 2,3n
设L前k-1列元素已求出，则 第k步
August 5, 2013
lim lkm lik lkk
m 1 k 1
k 1
m k 1
l
n
im km
l
lim lkm lik lkk
m 1
yfnie@
9
平方根法（Cholesky分解）
lk 1,1 lk 1, 2 uk 1,k 1 uk 1,k
u k 1,n 1
第k步计算：先选主元，再计算列，最后计算行
August 5, 2013 yfnie@ 3
k 1 u kj akj lkm u mj m 1 k 1 aik lim u mk m 1 lik u kk
满足严格 对角占优 条件
August 5, 2013
b1 c1
bn an
严格对角 占优的矩 阵行列式 不等于零 ， 故该系数 矩阵的各 级顺序主 子式不等 于零。
bi ai ci
i 2,3,, n 1
yfnie@
14
追赶法解三对角方程组
分解公式
若A为上述三对角阵时，则A有三角分解：
a
n
ij
i , 且存在某一 i0 使得有
ai0i0
j 1且j i0
a
n
i0 j
则称矩阵A按行对角占优。
若满足 aii
j 1且j i
a
n
ij
i ,
则称矩阵A按行严格对角占优。 类似地，也可定义按列对角占优和按列严格对角 占优的概念。通常的对角占优是指按行或者按列。
August 5, 2013 yfnie@ 13
k
m 1
用平方根法解对称正定的方程组时，不必考虑选主 元的问题，算法本身数值稳定。 • 用Gauss顺序消去法求解对称正定的方程组Ax＝b，
max
1i , j n
( aijk ) max aii 1i , j n
(k 1,2,, n)
这表明用Gauss顺序消去法求解对称正定方程组也不 用选主元。
7
平方根法（Cholesky分解） 改写
u11 D D D
T T
续2
L LD

u1 unn
unn
则 A LD D L LD LD L LT 这时 L 为一般的下三角矩阵，故 A L LT，若 L 的对角 元全为正时，由Doolittle分解的唯一性及上述分解 的推理过程，可以得到Cholesky分解的唯一性。
b1 c1 1 u1 c1 a b l 1 c2 u 2 c2 2 2 2 l3 1 an 1 bn 1 cn ln 1 un
aik lim l km
m 1 k 1 k 1 aik lim l km m 1 lik l kk lik
i k 1, k 2,, n
l kk
l11 l 21 l31 A l41 ln1
l11 l21 l31 l22 l22 l32 l32 l33 l33 l42 l43 l44 ln 2 ln 3 ln 4 lnn
xn yn / unn
n yk ukm xm m k 1 xk


k n 1, n 2,,1
ukk
yfnie@ 1
August 5, 2013
直接三角分解法
ukj akj lkm umj ,
m 1 k 1
续
k 1 m 1
y k bk l km y m
发现计算 y k 的规律与计算 u kj 的规律相同,因此计 算 y 的求方程组的过程可用三角分解的紧凑格 式取代。事实上，这只要把 b 做为A的第n＋1列 进行直接三角分解即可。
Reamrk：上述直接三角分解法所对应的是Gauss 顺序消去法，二者的乘除运算次数是相当的。实 际中对阶数较高的线性方程组，应采用选主元的 三角分解法求解，以保证计算结果的可靠性。
August 5, 2013
u 1 u12 1n u11 u11 u2 n 1 u22 LDR unn 1
yfnie@ 6
平方根法（Cholesky分解）
AT A LDR T RT DT LT RT ( DLT ) L( DR )
j k , k 1, n 1 i k 1,n
参选主元量
k 1 sik aik lim u mk m 1 i k , k 1, n.
k 1 若 skk max sik , 则无需交换，且skk akk lkm umk ukk m 1 lik sik / skk , i k 1, , n,
•三角分解解线性方程组的公式
Ax b 的求解过程为: Ly b Ux y
yk bk lkm ym
m 1 k 1
可推导求解单位下三角形方程组 Ly b 的递归公式为 :
y1 b1
k 2,3,, n
求解上三角形方程组Ux y 的递归公式为:
续1
由Doolittle分解的唯一性有
L R T R L （D可逆） T R LT DL DR
T
即 A LDLT ,由Doolittle分解的唯一性，及 的分解过程可知该分解式的唯一性。
U DR
August 5, 2013
yfnie@
yfnie@
l41 ln1 l42 ln 2 l43 ln 3 l44 ln 4 lnn
10
August 5, 2013
几点说明
• 在分解过程中有n次开方运算，故Cholesky分解法 也称为平方根法。 •由
2 2 akk lkm lkm akk max aii 1 i n
1 3 1 3 2 n 9n cn n 6 6


•为避免开方运算，也可对A做 A LDL 分解。
T
August 5, 2013 yfnie@ 12
3.5 三对角线性方程组求解
矩阵 A aij nn 若满足
• 矩阵对角占优的概念
aii
j 1且j i
之后按原公式计算第k行中u的其它元素uk ,k 1 , , uk ,n 1
若 si k max sik ,则需将第k行与第ik行完全交换，这样 满足前面情形，按第一种情形实施计算。
k
3.4 平方根法（Cholesky分解）
1. 正定矩阵的Cholesky分解 定义：设A为n阶n 2 对称正定矩阵，L是非奇异下 A LLT 为矩阵A的Cholesky分解。 三角矩阵，称 定理: n阶n 2 对称正定矩阵A一定存在分解: 1A LDLT