西华师范大学：《算法与程序设计》课程教学资源_第二章 解线性代数方程组的直接方法（2.4）追赶法（Thomas算法）

2-4追赶法( Thomas算法) 、对角占优矩阵 若矩阵A=(an)满足 an|∑|al i=12 j=1 J≠l 则称A为严格对角占优矩阵. 若矩阵A=(an)满足 an∑ 1 1 ≠ 则称A为弱对角占优矩阵

§ 2-4 追赶法(Thomas算法) 一、对角占优矩阵 若矩阵A = (aij) nn 满足   =  n j i j aii aij 1 | | | | i = 1,2,  ,n 则称A为严格对角占优矩阵. 若矩阵A = (aij) nn 满足  =  n j i j aii aij 1 | | | | i = 1,2,  ,n 则称A为弱对角占优矩阵

有一类方程组,形式为: Ax= 其中 f1 A x= f n-1 A称为三对角线矩阵,并且满足 (1)|b1c1卜0

有一类方程组, 形式为: Ax = f               = − − − n n n n n a b a b c a b c b c A 1 1 1 2 2 2 1 1                = n x x x x  2 1 其中             = n f f f f  2 1 A称为三对角线矩阵,并且满足 (1) |b1 ||c1 | 0

(2)|ba|+|c|,a1·c≠0=2…n-1 3)banpo A称为对角占优的三对角线矩阵 显然,A非奇异,即detA≠0 因此4任意阶顺序主子式非零,即detA≠0

(2) |bi ||ai |+|ci | , ai  ci  0 i = 2,  ,n − 1 (3) |bn ||an | 0 A称为对角占优的三对角线矩阵. 显然, A非奇异,即det A  0 因此A的任意k阶顺序主子式非零,即det Ak  0

二、解三对角线性方程组的追赶法 定理1:满足引理1条件的三对角方阵A有如下形式的 唯一的克劳特分解。 pI A =PQ 其中 q,=c/p( n1=b-a91(=2,3,…,n)

二、解三对角线性方程组的追赶法                 = − n n n a p p a a p p A 1 3 2 2 1                   − 1 1 1 1 1 2 1 n q q q   定理1：满足引理1条件的三对角方阵A有如下形式的 唯一的克劳特分解。 =PQ 其中 ( ) ( )      = − = = = − = p b a q − i n q c p i n p b i i i i i i i 2,3, , 1,2, , 1 1 1 1  

解三对角线方程组4x=何化为求解两个三角形 方程组 (1)解Py=f A (P,f)= f3 pI 得 1=1 G-a;y)/p(=2,3…,n)

方程组 解三对角线方程组Ax = f可化为求解两个三角形 Py = f Qx = y (1) 解Py = f                 − n n n n f f f f a p p a a p p    3 2 1 1 3 2 2 1 (P, f ) = 1 1 1 y = f / p y (f a y ) p (i n) i i i i i / 2,3, , = −  −1 =   得

(2)解O=y 得 Vi - xi =n-1,…,21

(2) 解Qx = y                 − 1 1 1 1 1 2 1 n q q q               n x x x  2 1             = n y y y  2 1 n n x = y +1 = −  i i i i x y q x i = n −1,  ,2,1      得

作业: P50习题11

作业： P50 习题11