温师院数学与信息科学学院：《计算方法》课程教学资源（学习指导）计算方法学习指导（共六章）

以上过程称为消元过程 (2)回代过程 求解上述三角形方程组,得到 bm)/ x1=(b"-∑qx)/a0,(=n-1,n-2,,21) 此过程称为回代过程。 Gauss消去法算法简述: ①输入:系数矩阵(A,b) ②消去:对于k=1,2 a如果a)=0,找非零元,交换两行,若找不到非零元,则算法停止 b.消元 a"=a1-m2∞,(=k+1…,n,j=k+1…,m) ③回代 如果a(m)=0,算法停止 b按xn,xn1,…,x1的顺序回代求解 x=bm/a (b-∑ax,)/a,(=n ,2,1) ④输出:结果x1x2,…,xn。 Gaus消去法的运算量 第k步消元时,共运算乘法(n-k)(n-k+1)次,除次n-k次,故完成n-1步消元乘 除法总数为 (n-k)(n-k+2) 回代过程乘除法总数为 (n-i+1) 总数为n+n2-m="+Omn2) 3. Gauss列主元素消去法

              =                           ( ) (2) 2 (1) 1 2 1 ( ) (2) 2 (2) 22 (1) 1 (1) 12 (1) 11 n n n n nn n n b b b x x x a a a a a a O M M M L L 以上过程称为消元过程。 ⑵回代过程 求解上述三角形方程组，得到      = − = − − = ∑= + ( )/ , ( 1, 2, ,2,1) / ( ) 1 ( ) ( ) ( ) ( ) x b a x a i n n L x b a i ii n j i j i ij i i i n nn n n n 此过程称为回代过程。 Gauss 消去法算法简述： ①输入：系数矩阵(A,b) ②消去：对于 k = 1,2,L,n −1 a.如果 0 ，找非零元，交换两行，若找不到非零元，则算法停止。 ( ) = k akk b.消元 ( ) ( ) k kk k ik ik a a m = ，(i = k +1,L, n) ， ( 1) ( ) (k ) ik kj k ij k aij = a − m a + (i = k +1,L, n, j = k +1,L, n) b ，( ( 1) ( ) (k ) ik k k i k i = b − m b + i = k +1,L, n, j = k +1,L, n) ③回代： a.如果 0，算法停止。 ( ) = n ann b.按 xn , xn−1 ,L, x1的顺序回代求解。      = − = − − = ∑= + ( )/ , ( 1, 2, ,2,1) / ( ) 1 ( ) ( ) ( ) ( ) x b a x a i n n L x b a i ii n j i j i ij i i i n nn n n n ④输出：结果 x1 , x2 ,L, xn 。 Gauss 消去法的运算量 第 k 步消元时，共运算乘法(n − k)(n − k +1) 次，除次n − k 次，故完成 步消元乘 除法总数为 n −1 6 5 3 2 ( )( 2) 1 3 2 1 n n n n k n k n k ∑ − − + = + − − = 回代过程乘除法总数为 2 2 ( 1) 2 1 n n n i n i ∑ − + = + = 总数为 ( ) 3 3 3 2 3 2 3 O n n n n n + − = + 3. Gauss 列主元素消去法 9

显然,Gaus消去法能够进行的条件是各步消元的主元素a4)≠0,如果在消元过程中 发现某个主元素为零,即使det(A)≠0,则消元过程将无法进行;其次,即使主元素不为零, 但如果主元素a的绝对值很小,用它们作除数,将使该步消元的乘数绝对值很大,势必造 成舍入误差的严重扩散,以致于方程组解的精度受到严重的影响 因此,为避免小主元作除数,在 Gauss消去法中加入选主元过程,即在第k步 (k=1,…,n-1)消元时 a(2)b(2) 首先在A的第k列主对角元以下元素a)(k≤i≤n)中挑选绝对值最大者a (k≤i≤n),并通过交换(A,b)的第k行与第行对应元素,使aA位于主对角线上, 仍记为a,然后再进行消元计算。称每一步都按列选主元的 gauss消去法为Gaus列主元 素消去法。 4.系数矩阵的三角分解 从矩阵变换的角度来看,每一次消元都相当于矩阵A左乘一个初等行变换阵,最终将 原方程组系数矩阵化为简单的上三角阵。而所有初等行变换阵之积的逆是一个单位下三角 阵,所以,不带行交换的 gauss消元过程产生了一个单位下三角阵L和一个上三角阵U 它们的乘积等于A,即 称之为矩阵A的LU分解,又称为 Doolittel分解。 当然也可以将A分解为一个下三角阵L与一个单位上三角阵U的乘积,此时的LU分 解又称为 Crout分解 当A为n阶对称正定阵,则必有分解A=LL,其中L是对角元全为正的下三角阵, 称为正定阵的 Cholesky分解。 定理21设n阶方阵A的前n-1个顺序主子式都不为零,则A的LU分解存在且唯 定理22设A为非奇异矩阵,则必存在排列矩阵P以及单位下三角阵L和非奇异上三 角阵U,使PA=LU。 5.直接三角分解法 直接三角分解法的基本想法是,一旦实现了矩阵A的LU分解,那么求解方程组Ax=b 的问题就等价于求解两个三角形方程组Ly=b和Ux=y。 直接三角分解法的步骤 (1)实现 Doolittle分解A=LU,其中L为单位下三角阵,U为上三角阵。其分解公式

10 ( ) ( ) k nk k kk a a M 显然，Gauss 消去法能够进行的条件是各步消元的主元素 ，如果在消元过程中 发现某个主元素为零，即使 0 ( ) ≠ k kk a det(A) ≠ 0，则消元过程将无法进行；其次，即使主元素不为零， 但如果主元素 的绝对值很小，用它们作除数，将使该步消元的乘数绝对值很大，势必造 成舍入误差的严重扩散，以致于方程组解的精度受到严重的影响。 ) k ) k ) ( ai ) a (k kk a 因此，为避免小主元作除数，在 Gauss 消去法中加入选主元过程，即在第 步 (k = 1,L, n −1 消元时                     = ( ) ( ) ( ) ( ) (2) 2 (2) 2 (2) 22 (1) 1 (1) 1 (1) 12 (1) 11 ( ) ( ) ( , ) k n k nn k k k kn n n k k a b a b a a b a a a b A L M L O M M L L L L L L b 首先在 的 第 列主对 角元以下 元 素 中挑选绝对值 最大者 ，并通过交换 的第 行与第 行对应元素，使 位于主对角线上， 仍记为 ，然后再进行消元计算。称每一步都按列选主元的 Gauss 消去法为 Gauss 列主元 素消去法。 ( A ik ≤ n (k ) kk a k ( ) ( ) a k i n k ik ≤ ≤ ki k ) kk (k ≤ ( , ) (k ) (k ) A b k (k ) i kk 4. 系数矩阵的三角分解 从矩阵变换的角度来看，每一次消元都相当于矩阵 A 左乘一个初等行变换阵，最终将 原方程组系数矩阵化为简单的上三角阵。而所有初等行变换阵之积的逆是一个单位下三角 阵，所以，不带行交换的 Gauss 消元过程产生了一个单位下三角阵 和一个上三角阵U ， 它们的乘积等于 ，即 L A A = LU 称之为矩阵 A 的 LU 分解，又称为 Doolittel 分解。 当然也可以将 A 分解为一个下三角阵 L 与一个单位上三角阵 U 的乘积，此时的 LU 分 解又称为 Crout 分解。 当 A 为 n 阶对称正定阵，则必有分解 T A = LL ，其中 L 是对角元全为正的下三角阵， 称为正定阵的 Cholesky 分解。 定理 2.1 设 n 阶方阵 A 的前 n −1个顺序主子式都不为零，则 的 分解存在且唯 一。 A LU 定理 2.2 设 A 为非奇异矩阵，则必存在排列矩阵 P 以及单位下三角阵 和非奇异上三 角阵U ，使 。 L A PA = LU 5. 直接三角分解法 直接三角分解法的基本想法是，一旦实现了矩阵 A 的 分解，那么求解方程组 的问题就等价于求解两个三角形方程组 LU x = b Ly = b 和Ux = y 。 直接三角分解法的步骤： ⑴实现 Doolittle 分解 A = LU ，其中 L 为单位下三角阵，U 为上三角阵。其分解公式

为:对r=1,2,3 计算 lu(=r,r+1, L,u r十1.r十 (2)求解Ly=b,其计算公式为 y,=b lny2(r=2,3,…,n) (3)求解Ux=y,其计算公式为: y y,-∑unx 1,n-2,…,2,1) 事实上,计算U和解y的公式是一致的,因此系数矩阵的 Doolittle分解与解方程组 Ly=b可以同时进行,都归结为对数组A=(A,b)的分解计算,然后再解Ux=y,称这种 求解方式为紧凑格式。 6.部分选主元的 Doolittle分解 部分选主元的 Doolittle分解法与列主元消去法在理论上是等价的。具体步骤如下: (1)对于r=1,2,…,n进行(部分)选主元的分解计算。 (1.1)计算中间量S,(=r,r+1,…m)作为可能的主元,并存入an an←S1=an-∑h=an-∑aa(=,r+1…,n) 12选绝对值最大的S,即确定行号,使满足|S|=maNS! (1.3)交换两行:当i≠r时,交换A的第r行与第行的对应元素,交换后的元素以它 在A中所处的新位置记

为：对 r = 1,2,3,L,n ，计算 Ly = b x = y = b r = 1,2,L air ← ( , 1, , ) 1 1 u a l u i r r n r k ri = ri −∑ rk ki = + L − = , ( 1, 2, , ) 1 1 i r r n u a l u l rr r k ir ik kr ir = + + L − = ∑ − = ⑵求解 ，其计算公式为：      = − = = ∑ − = ( 2,3, , ) 1 1 1 1 y b l y r n y b r i r r ri i L ⑶求解U ，其计算公式为：        = − − − = = ∑= + ( 1, 2, ,2,1) / 1 r n n L u y u x x x y u rr n i r r ri i r n n nn 事实上，计算U 和解 y 的公式是一致的，因此系数矩阵的 Doolittle 分解与解方程组 Ly 可以同时进行，都归结为对数组 A = (A,b) 的分解计算，然后再解U ，称这种 求解方式为紧凑格式。 x = y 6. 部分选主元的 Doolittle 分解 部分选主元的 Doolittle 分解法与列主元消去法在理论上是等价的。具体步骤如下： ⑴对于 ,n 进行（部分）选主元的分解计算。 (1.1)计算中间量 Si (i = r,r +1,Ln)作为可能的主元，并存入 air ( , 1, , ) 1 1 1 1 S a l u a a a i r r n r k ir ik kr r k i = ir −∑ ik kr = −∑ = + L − = − = (1.2)挑选绝对值最大的 Si ，即确定行号ir ，使满足 i r i n Si S r ≤ ≤ = max 。 (1.3)交换两行：当ir ≠ r 时，交换 A 的第 r 行与第 行的对应元素，交换后的元素以它 在 A 中所处的新位置记。 ri 11

(14)分解计算(以下两步可调换次序,因an已计算) an←n=an-∑lu=an-∑aa(=r+1,…,n+1) 此处i=r+1,…,n+1意味着对增广矩阵(A,b)进行分解计算,即紧凑格式 ∑k k=1 S 按上述方法完成分解,便实现了系数矩阵分解PA=LU,P是排列阵,即是将分解过程中 所有的行交换依次作用在单位阵上的结果 (2)求解Ux y,/u a y a ari ai ier+l (r=n-1,n-2,…,2,1) 7.平方根法 平方根法是用于解系数矩阵为对称正定阵的线性代数方程组,其计算步骤如下: (1)对矩阵A进行 Cholesky分解A=LL,按列确定下三角阵L的元素,即对于 j=1,2,…,n,计算 1)2 (i=j+1, (2)求解下三角形方程组Iy=b 6,/11 b-∑l (3)求解上三角形方程组Lx=y

(1.4)分解计算（以下两步可调换次序，因 arr 已计算） ( 1, , 1) 1 1 1 1 ← = −∑ = −∑ = + + − = − = a u a l u a a a i r n r k ri rk ki r k ri ri ri rk ki L 12 此处i = r +1,L,n +1意味着对增广矩阵(A,b) 进行分解计算，即紧凑格式 , ( 1, 2, , ) 1 1 i r r n a a S S u a l u a l rr ir r i rr r k ir ik kr ir ir = = = + + L − ← = ∑ − = 按上述方法完成分解，便实现了系数矩阵分解 PA = LU ，P 是排列阵，即是将分解过程中 所有的行交换依次作用在单位阵上的结果。 ⑵求解Ux = y        = − − − = − = = = ∑ ∑= + + + + = + + + ( 1, 2, ,2,1) / / 1 , 1 , 1 , 1 1 , 1 , 1 r n n L a a a a a u y u x x x y u a a a rr n i r r n ri i n r n rr n i r r ri i r n n nn n n n n nn 7. 平方根法 平方根法是用于解系数矩阵为对称正定阵的线性代数方程组，其计算步骤如下： ⑴对矩阵 A 进行 Cholesky 分解 T A = LL ，按列确定下三角阵 的元素，即对于 ，计算 L j = 1,2,L,n ∑ − = = − 1 1 2 1/ 2 ( ) j k jj jj jk l a l , ( 1, 2, , ) 1 1 i j j n l a l l l jj j k ij ik jk ij = + + L − = ∑ − = ⑵求解下三角形方程组 Ly = b ，        = − = = ∑ − = ( 2,3, , ) / 1 1 1 1 11 i n l b l y y y b l ii i j i ij j i L ⑶求解上三角形方程组 x = y ， T L

y x (i=n-1,n-2,…,2,1) 平方根法是目前在计算机上解对称正定方程组的一个有效方法,应用较广泛,其计算量 和存贮量都比用消去法约节省近一半,且不需要选主元,便能求得较精确的数值解 8.解三对角方程组的追赶法 在一些实际问题中,例如用差分法解二阶线性常微分方程边值问题,解热传导方程以及 船体数学放样中建立三次样条函数等,都会要求解系数矩阵为对角占优的三对角线方程组 a2, 2 f3 6. c ∫n fn 记为Ax=f。其中A满足下列条件:(称为对角占优的三对角线矩阵) (1)>|>0 (2)≥+l,(ac1≠0,1=23,…,n-1) (3)|>{an}>0 追赶法的计算步骤如下: (1)对A进行 Crout分解。设将A分解为如下两个三角形矩阵的乘积

       = − − − = = ∑= + ( 1, 2, ,2,1) / 1 i n n L l y l x x x y l ii n j i i ji j i n n nn 平方根法是目前在计算机上解对称正定方程组的一个有效方法，应用较广泛，其计算量 和存贮量都比用消去法约节省近一半，且不需要选主元，便能求得较精确的数值解。 8. 解三对角方程组的追赶法 在一些实际问题中，例如用差分法解二阶线性常微分方程边值问题，解热传导方程以及 船体数学放样中建立三次样条函数等，都会要求解系数矩阵为对角占优的三对角线方程组                                   =                                                                     − − + − − − + − − − − n n n i i i n n n i i i n n n n n i i i f f f f f f f f f x x x x x x x x x a b a b c a b c a b c b c 1 2 1 1 3 2 1 1 2 1 1 3 2 1 1 1 1 2 2 2 1 1 M M M M O O O O O O O O O O O O O O O O O O 记为 Ax = f 。其中 A 满足下列条件：（称为对角占优的三对角线矩阵） （1） 0 b1 > c1 > （2） b ≥ a + c , (a c ≠ 0, i = 2,3, , n −1) i i i i i L （3） > > 0 n n b a 追赶法的计算步骤如下： ⑴对 A 进行 Crout 分解。设将 A 分解为如下两个三角形矩阵的乘积 L＝                           n n i i γ α γ α γ α α O O O O O O O O 2 2 1 13