科学计算与数学建模第5章 小行星轨道方程计算问题-线性方程组求解的直接法-5.7 追赶法-2017-02.pptx

1、5.7 追赶法,在一些工程实际问题中常会遇到解三对角线性方程 组 Ax f的问题，即,11,2,c,ab,n 1,b1c1 bc, x f,a, x f,2 ,2 , x f,i ,i , xf, ,n ,n ,nn,22 aibici an 1bn 1,其中 A 满足条件：1| b1 | c1 |0 2| bi | ai | | ci |,(ai ci0,i 2,. .,n 1) 3| bn| an|0,对于具有条件(2)的三对角方程组，用追赶法求解。 追赶法具有计算量少，方法简单，算法稳定的特点。,1,1,22,bc,ab,b1b2 c1a2,0，否则,2,c1b2,c1b2,1 b1,a

2、2,ba 有1,，由条件(2)得,1，矛盾。,假设定理对n-1阶的满足条件(2)的三对角矩阵成立，求证对 满足条件(2)的n阶三对角矩阵定理亦成立。由条件b1 0，则 利用消元法的第1步有：,定理5.7.1设有三对角线性方程组 Ax f，且A满足条件(2)，,则A为非奇异矩阵，det A0。 证明 用归纳法证明。n 2时，det A ,2,2,2,3,3,3,0,0,0,0,c1,b,b1,a,b,c,c1,b1 0 , ,A ,A1, ,0,ac, an 1bn 1cn 1 ancn,0 ,bn, , 2c2 a3b3c3 B an1bn1cn1 an,记,，其中,。,2,c,a,1 b1,

3、2 b2 ,22,222222,b1b1,于是n-1阶的三对角矩阵 B 满足条件(2)，有归纳假设得 det B 0， 故det A 0 。,det A b1 det B,显然,且有 | bc1 a| b| | c1 | a| b| | a| c|0,定理5.7.2,设设三对角方程 Ax f ，A 满足条件(2)为三对角阵，,则A的所有顺序主子式都不为零，即det Ak, 0k 1, 2,.n。,证明 由于A是满足条件(2)的 n 阶三对角阵，因此A的任一个顺 序主子式Ak亦满足条件(2) 的 k 阶三对角矩阵。由定理 5.7.1 即 得 det Ak 0k 1, 2,.n。,bn,1, ,c

4、n1 ,1 n ,b1c1 a2b2c2 an1bn1 an,1 12 1,22 33 n,n1 1,根据这一定理和三角分解定理知，满足条件(2)的三对角 矩阵A可进行直接三角分解，即A=LU。在这里特别的有：,其中待定系数 i ,i ,i 可由矩阵乘法规则立即得出：,于是,111111,1,b , c c1,ii ,(i 2,.n),ai i ,bi i ii1 aii1 i ,(i 2,.n),ci,由,1,1111,1,c,b1,b 0,| b | c |0,1, 故 0 | |1 。,用归纳可证明 |i |bi aii1 |bi | | ai1 |bi | | ai |ci |0, 0

5、 | i |1。,i,ci,bi, , i 2, ., n ,ai i 1,i,iii 1,ba , i2, ., n ,i,ai , i2, ., n ,1,c1,1 b1 , 1b,i,ci,i, , i 2, ., n ,ibii i 1 , i2, ., n ,i,ai , i2, ., n ,1,c1,1 b1 , 1b,由此可得求解三对角线性方程组的追赶法: (1) 计算i 的递推公式:,1 i,ci,b1bi,c1 , , (i 2,.n 1),ai i 1,(2) 求解 Ly f的公式:,1 i,b1bi,yf1, yfiai yi 1, (i 2,.n),ai i 1,(3)

6、 求解Ux y 的公式: xnyn , xiyi i xi1,(i n1,n2,.1),将计算方程组的解,的过程称为赶的过程。,xn xn1 x1,将计算1 2 n 及 y1 y2 yn 的过程称为追的过程。,追赶法求解三对角方程 Ax f 仅需5n-4次乘除运算，工作量 较小。只需用3个一维数组分别存储A 的系数ai bi ci 以及两个一维数组保存计算的中间结果 i 和 yi或 xi。,例 用追赶法求方程,的解。,0 x2 ,0 , ,1 ,0121x3 0012 x4 ,解(1) 计算,：,i,0,0,2, 121 01,1,2,3,1,1,2,c3,c1,c2,b2,b2 a21 3,

7、3 b3 a32 4,2,2,2,1,2,00,0,1,1, 0,1,1,0,01,1 2,3 2,2 3,4 3,4,3 ,5 ,4,(2) 计算yi ：,(3) 计算xi ：,1,2,3,4,122i,f1,b2,f2 a2 y1,y, 1 , y,1 , y,1 , y1,b a 3 4,443334,21,4,x y1, x yx 1 3 1 1, x1, x1,4 ,0 | ci| bi| | ai| i| bi| | ai|, (i 2,.n 1) 0 | bn| | an| n| bn| | an| 因此，追赶法中不会出现中间结果迅速增长和舍入误差 产生积累现象，即追赶法是数值稳定的。,对于追赶法，由于已证明：0 | i |1，(i 1,2,n 1) 及,？,如果是五