第二章 解线性方程组的直接法 2.6 追赶法§ 2.6 追赶法 (Thomas算法 )§ 对角占优矩阵 : 满足若矩阵 nnijaA ×= )( ∑ ≠ = > n ij j ijii aa 1 |||| ni ,,2,1 L= .为严格对角占优矩阵则称 A 满足若矩阵 nnijaA ×= )( ∑ ≠ = ≥ n ij j ijii aa 1 |||| ni ,,2,1 L= .为弱对角占优矩阵则称 A 补充 有一类方程组 ,在今后要学习的插值问题和边值问题中 有着重要的作用 ,即三对角线方程组 ,其形式为 : ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ??? nn nnn ba cba cba cb A 111 222 11 OOO ?? ? ? ? ? ?? ? ? ? ? = nx x x x M2 1 fAx = 其中 ?? ? ? ? ? ?? ? ? ? ? = nf f f f M2 1 并且满足称为三对角线矩阵 ,A 0||||)1( 11 >> cb --------(1) 0,||||||)2( ≠?+≥ iiiii cacab 1,,2 ?= ni L 0||||)3( >> nn ab .线矩阵称为对角占优的三对角A 0det,, ≠AA 即非奇异显然 0det, ≠kAkA 即阶顺序主子式非零的任意因此 分解进行可以将所以 LUA, 分解为为上三角阵时为单位下三角阵 DoolittleUL ,, 分解为为单位上三角阵时为下三角阵 CroutUL ,, 以下以 Doolittle分解导出三对角线方程组的解法 以 Crout分解的三对角线方程组的解法请参考教材 设 LUA = ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ??? nn nnn ba cba cba cb A 111 222 11 OOO 用紧凑格式的 Doolittle分解 1=→?r ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??? nn nnn ba cba cbl cb 111 222 11 OOO ju1 ja1= 11 1 1 u al i i = 2=→?r ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? nn nn ba cb l cul cb 11 3 222 11 O OO ∑? = ?= 1 1 r k kjrkrjrj ulau rr r k krikir ir u ula l ∑? = ? = 1 1 1?= →?→ nrL ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? nn nn ul cu l cul cu 11 3 222 11 O OO ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 1 1 1 1 3 2 nl l l L O O ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ?? n nn u cu cu cu U 11 22 11 OO因此 二对角阵 ---(2) LUA =由 11 bu = 1? = i i i u al 1??= iiii clbu ni ,,2 L= { 的乘积后分解成两对角阵将系数矩阵 LUA 方程组可化为求解两个三角形解三对角线方程组 fAx = fLy = yUx = --------(3) --------(4) --------(5) --------(6) 的元素的计算公式和可得 UL fLy =解)1( ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? nn f f f f l l l MO O 3 2 1 3 2 1 1 1 1 =),( fL 11 fy = 1???= iiii ylfy { ni ,,3,2 L=得 --------(7) yUx =解)2( ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? n nn u cu cu cu 11 22 11 OO ?? ? ? ? ? ?? ? ? ? ? nx x x M 2 1 ?? ? ? ? ? ?? ? ? ? ? = ny y y M 2 1 n n n u yx = i iii i u xcyx 1+??= 1,2,,1 L?= ni?? ???得 --------(8) 的追赶法式为解称由 fAx =)8(~)3( 也称 Thomas法 例 1. 用追赶法解三对角线方程组 ?? ? ? ? ? ?? ? ? ? ? = ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? 0 1 0 1 31 132 132 13 4 3 2 1 x x x x 解 : 11 bu = 1? = i i i u al 1??= iiii clbu 11 fy = 1???= iiii ylfyTaaaa ),,( 432=设 T)1,2,2(= Tbbbbb ),,,( 4321= T)3,3,3,3(= Tfffff ),,,( 4321= T)0,1,0,1(= Tcccc ),,( 321= T)1,1,1(= 11 bu = 1 2 2 u al = 1222 clbu ?= 3= 3 2= 3 7 3 23 =?= 2 3 3 u al = 7 6= 2333 clbu ?= 7 15 7 63 =?= 3 4 4 u al = 15 7= 3444 clbu ?= 15 38 15 73 =?= 分解的作 LUA)1( 11 fy = 1222 ylfy ??= fLy =解)2( 1= 1320 ??= 32?= 2333 ylfy ??= )3 2( 7 61 ??= 7 11= 3444 ylfy ??= 7 11 15 70 ?= 15 11?= yUx =解)3( 4 4 4 u yx = 38 11?= 3 433 3 u xcyx ??= 15 7) 38 11 7 11( += 38 33= 2 322 2 u xcyx ??= 7 3) 38 33 3 2( ??= 38 25?= 1 211 1 u xcyx ??= 3 1) 38 251( += 38 21= 因此原线性方程组的解为 Tx ) 38 11, 38 33, 38 25, 38 21( ??= ? ? ? ? ? ? ? ? ? ? ? ? = 0 1 0 1 31 132 132 13 ),( fA a b c f ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? → 15 117 113 21 15 38 15 7 171576 13732 13 解法 2. 紧凑格式 (含存储格式 ) l u yc Tx ) 38 11, 38 33, 38 25, 38 21( ??=