追赶法ppt

追赶法构造过程追赶法仍然保持LU 分解特性,它是一种特殊的LU 分解。

追赶法充分利用了系数矩阵的三对角特点，而且使之分解更简单,得到对三对角线性方程组的快速解法。

解出。

及可由时，当，表示，则三对角方程的矩阵若记的计算公式，为：和的及的元素于是得计算，，，有：由矩阵乘法及相等定义y Ux d Ly LU A d Ax d d d d p b q n k c q a p b q q U p L n k c b p q a q p b q T n k k k k k k k k k i i i k k k k k k k k k =====-========+==--------),,,(),,3,2(),,3,2(21111111111111 γγγγγ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡----n n nn n n n n q q q p p p b a c b a c b a c b Doolittle 1221132111222111111γγγ 分解形式矩阵2) 追赶法算法1.输入变量个数n 、系数矩阵对应的三个向量a,b,c 、常数项b2. For k=2,3,…,n2.1 如果b k-1=0,则输出“追赶法失败”提示并终止2.2 a k ⇐ a k /b k-12.3 b k ⇐b k - a k *c k-12.4 d k ⇐d k - a k *d k-13.For k=n,n-1,…,13.1 x k ⇐ (d k - c k *x k+1)/b k时不能进行。

消元法的缺点，即当在消元法，因此也存来源于空间，但是因为追赶法节省了计算时间和存贮程，。

追赶法的特殊求解过法次数仅有较简单，计算量、乘除追赶法。

组的方法亦称为追赶法用这组公式解线性方程，，，分解的计算公式：综合以上，求解出计算公式为：0451,,1)(,,3,21,,2,1)(,,3,2111111111111=-⎪⎪⎪⎩⎪⎪⎪⎨⎧-=-==-==-====--=-===-==+---+-k k k k k k n n n k k k kk k k k k k k k k k k k nn n k k k k q Gauss Gauss n n k q x c y x q y x y p d y n k c p b q q a p d y b q Doolittle n n k q x c y x q y x nk y p d y d y注：因为三对角矩阵的非零元素都集中在三条对角线上，因此只用三个向量a,b,c来存储系数矩阵，这样可以把二维数据的存储变为一维数据存储。

1、 追赶法的数学理论设系数矩阵为三对角矩阵则方程组Ax=f称为三对角方程组。

设矩阵A非奇异，A有Crout分解A=LU，其中L为下三角矩阵，U为单位上三角矩阵，记可先依次求出L，U中的元素后，令Ux=y，先求解下三角方程组Ly=f 得出y，再求解上三角方程组Ux=y。

事实上，求解三对角方程组的2追赶法将矩阵三角分解的计算与求解两个三角方程组的计算放在一起，使算法吏为紧凑。

其计算公式为：二、追赶法的算法和流程图算法:1) u(1)=r(1)/a(1),v(1)=c(1)/a(1).2)dui k=2,3,…n-1,zuo yi xia cao zuo:(1)u(k)=(r(k)-u(k-1)*b(k))/(a(k)-v(k-1)*b(k)).(2)v(k)=c(k)/(a(k)-v(k-1)*b(k)).3)u(n)=r(n)-u(n-1)*b(n))/(a(n)-v(n-1)*b(n)).4)x(n)=u(n).5)dui k=n-1,…,2,1,ji suan x(k)=u(k)-v(k)*x(k+1).三、追赶法的Matlab实现functionx=chase (a,b,c,f)chasen=length(b);ifn-1==length(a)fori=n-1:-1:1a(i+1)=a(i);endend%将a设置为n维向量c(1)=c(1)/b(1);f(1)=f(1)/b(1);fori=2:n-1b(i)=b(i)-a(i)*c(i-1);c(i)=c(i)/b(i);f(i)=(f(i)-a(i)*f(i-1))/b(i);endf(n)=(f(n)-a(n)*f(n-1))/(b(n)-a(n)*c(n-1)); fori=n-1:-1:1f(i)=f(i)-c(i)*f(i+1);endx=f;四、追赶法的算例实现clear all;a=[-4,-4,-4,-4];b=[1,1,1];c=[1,1,1];r=[1,1,1,1]; n=length(a);b=[0,b];u(1)=r(1)/a(1);v(1)=c(1)/a(1);for k=2:n-1u(k)=(r(k)-u(k-1)*b(k))/(a(k)-v(k-1)*b(k)); v(k)=c(k)/(a(k)-v(k-1)*b(k));endu(n)=(r(n)-u(n-1)*b(n))/(a(n)-v(n-1)*b(n)); x(n)=u(n);for k=n-1:-1:1x(k)=u(k)-v(k)*x(k+1);endfprintf('Èý¶Ô½Ç·½³Ì×éµÄ½âΪ\n') for k=1:nfprintf('x(%1d)=%10.8f\n',k,x(k)) end>> li10_24fun三对角方程组的解为x(1)=-0.36363636x(2)=-0.45454545x(3)=-0.45454545x(4)=-0.36363636>>。

【附注】 解三对角方程组的追赶法设已知方程组AX D =是三对角方程组，其 矩阵形式为b c a b c a b c a b x x x x d d d d n n n n n n n n n 1122211112112100 -----⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥=⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥ (3-40) 可以证明，若系数矩阵A 满足如下条件：(1) b i ≠0(2) b a c i i i ≥++-11 ()0≤≤i n(3) b a c i i i ≥+ ()0≤≤i n则三对角方程组(3-40)用追赶法可以稳定求解。

这里的条件(2)、(3)称为“对角占优”。

考察三对角方程组具有如下特点：首尾两个 方程各只含两个未知数，其余方程各含三个未知 数，而且后一个方程包含前一个方程的两个未知 数。

追赶法的基本思想是采用依次消元的方法， 依次从前一个方程“解”出一个未知数代入到下 一个方程，谓之“追”；代到最末一个方程时， 只剩下一个未知数，于是该方程可解。

然后将所 得到的解依次回代到前面的方程，解出全部未知 数，谓之“赶”。

前后合一，故称追赶法。

为了导出追赶法的计算公式，将式(3-40)写 成方程组形式b xc xd a x b x c x d a x b x c x d a x b x c x d a x b x d i i i i i i i n n n n n n n n n n n n 111212122232111211111+=++=++=++=+=⎧⎨⎪⎪⎪⎪⎩⎪⎪⎪⎪-+------- (3-41) 由方程组(3-41)第一式解出x 1211111x b c b d x -= 令：u c b 111= ，v d b 111= (3-42)x v u x 1112=- (3-43) 将式(3-43)和(3-42)代入到方程组(3-41)第二式解 出x 2x v u x 2223=- (3-44) 其中：u c b a u 22221=- v d a v b a u 2221221=-- (3-45) 依次做下去，由方程组(3-41)第i 式解出x i x v u x i i i i =-+1 (3-46) 其中：u c b a u i i i i i =--1v d a v b a u i i i i i i i =----11 (3-47) 最后，由方程组(3-41)第n 式解出x nx d a v b a u v n n n n n n n n =--=--11(3-48) 因为最后一个方程只剩一个未知数x n ，所以只有 v n ，没有u n 。