天津大学：《数值计算》课程教学资源（讲稿）第二章 解线性方程组的直接法（2.6）追赶法

计算方法 第二章解线性方程组的直接法 §26追赶法

第二章 解线性方程组的直接法 § 2.6 追赶法

§2.6追赶法 Thomas算法) 对角占优矩阵 补充 若矩阵A=(an)xn满足 an|∑ i=1,2…,n 则称为严格对角占优矩阵若矩阵A=(an)m满足 a∑ =1,2 则称A为弱对角占优矩阵

§2.6 追赶法(Thomas算法) 对角占优矩阵: 若矩阵A = (aij)n´n满足 å ¹ = > n j i j ii ij a a 1 | | | | i = 1,2,L,n 则称A为严格对角占优矩阵. 若矩阵A = (aij)n´n满足 å ¹ = ³ n j i j ii ij a a 1 | | | | i = 1,2,L,n 则称A为弱对角占优矩阵. 补充

有一类方程组在今后要学习的插值问题和边值问题中 有着重要的作用,即三对角线方程组,其形式为 Ix=f 其中 X 2 WX fn A称为三对角线矩阵,并且满足 (1)|b1|c}>0

有一类方程组,在今后要学习的插值问题和边值问题中 有着重要的作用,即三对角线方程组,其形式为: ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ = - - - n n n n n a b a b c a b c b c A 1 1 1 2 2 2 1 1 O O O ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ = n x x x x M 2 1 Ax = f 其中 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ = n f f f f M 2 1 A称为三对角线矩阵,并且满足 (1) |b1|>|c1|> 0 --------(1)

(2)|b|a1|+|c; ≠0 i=2,…,n-1 (3)|bn|an|>0 A称为对角占优的三对角线矩阵 显然,A非奇异,即detA≠0 因此4的任意阶顺序主子式非零,即detA≠0 所以,可以将A进行LU分解 L为单位下三角阵U为上三角阵时,为 Doolittle分解 L为下三角阵,U为单位上三角阵时,为 Crout分解

(2) | |³| |+| | , × ¹ 0 i i i i i b a c a c i = 2,L,n - 1 (3) | |>| |> 0 n n b a A称为对角占优的三对角线矩阵. 显然, A非奇异,即det A ¹ 0 因此A的任意k阶顺序主子式非零,即det Ak ¹ 0 所以,可以将A进行LU分解 L为单位下三角阵,U为上三角阵时,为Doolittle分解 L为下三角阵,U为单位上三角阵时,为Crout分解

以下以 Doolittle分解导出三对角线方程组的解法 以 Crout分解的三对角线方程组的解法请参考教材 设A=LU用紧凑格式的 Doolittle分解 2 r=1 A= b

以下以Doolittle分解导出三对角线方程组的解法 以Crout分解的三对角线方程组的解法请参考教材 设 A = LU ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ = - - - n n n n n a b a b c a b c b c A 1 1 1 2 2 2 1 1 O O O 用紧凑格式的 Doolittle分解 =1 - ® r ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ - - - n n n n n a b a b c l b c b c 1 1 1 2 2 2 1 1 O O O u1 j = a1 j 11 1 1 u a l i i =

GLg3 ∑ k=1 F7 因此L 1 二对角阵

=2 - ® r ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ - - n n n n a b b c l l u c b c 1 1 3 2 2 2 1 1 O O O å - = = - 1 1 r k rj rj rk kj u a l u rr r k ir ik kr ir u a l u l å - = - = 1 1 = -1 ® - ® r n L ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ - - n n n n l u u c l l u c u c 1 1 3 2 2 2 1 1 O O O ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ = 1 1 1 1 3 2 n l l l L O O ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ = - - n n n u u c u c u c U 1 1 2 2 1 1 因此 O O 二对角阵 ---(2)

由 A= U (3) 可得L和U的元素的计算公式 -1 将系数矩阵A分解成两对角阵L的乘积后 解三对角线方程组Ax=何化为求解两个三角形方程组 6

由 A = LU 1 1 u = b -1 = i i i u a l i = i - i i-1 u b l c i = 2,L,n { 将系数矩阵 A分解成两对角阵 LU的乘积后 解三对角线方程组Ax = f可化为求解两个三角形方程组 Ly = f Ux = y --------(3) --------(4) --------(5) --------(6) 可得L和U的元素的计算公式

(1)解Ly=f 得 f-l·y

( 1 ) 解Ly = f ÷÷÷÷÷÷øö ççççççèæ n nffff l l l O M O 321 3 2 1 1 1 1 ( L , f ) =1 1 y = f - 1 = - × i i i i y f l y { i = 2 , 3 , L , n 得 --------(7)

(2)解Ux=y 得 -(8) -Cx+1i=n-1…,2,1 称由(3)~(8)式为解Ax=f追赶法也称 Thomas法

(2) 解Ux = y ÷ ÷ ÷ ÷ ÷ ø ö ç ç ç ç ç è æ - - n n n u u c u c u c 1 1 2 2 1 1 O O ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ n x x x M 2 1 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ = n y y y M 2 1 n n n u y x = i i i i i u y c x x +1 - × = i = n - 1,L,2,1 ï î ï í ì 得 --------(8) 称由(3) ~ (8)式为解Ax = f的追赶法 也称Thomas法

例1.用追赶法解三对角线方程组 132 1010 C y1=f1 解:设a=(a2,a3,a)=(2,2,1) y=f-1…y-1 b=(b1,b2,b2b)=(33,33) T 1/c2/03 f=(/1,/2,/3,f)y=(10,10)

例1. 用追赶法解三对角线方程组 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ = ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ 0 1 0 1 1 3 2 3 1 2 3 1 3 1 4 3 2 1 x x x x 解: u1 = b1 -1 = i i i u a l i = i - i i-1 u b l c 1 1 y = f -1 = - × i i i i T y f l y a (a ,a ,a ) 设 = 2 3 4 T = (2,2,1) T b (b ,b ,b ,b ) = 1 2 3 4 T = (3,3,3,3) T f ( f , f , f , f ) = 1 2 3 4 T = (1,0,1,0) T c (c , c , c ) = 1 2 3 T = (1,1,1)