32第I部分数值分析 下面，我们给出求解三对角方程组(2-13)的追赶法的计算过程 算法2.7求解三对角方程组的追赶法. 1)三角分解过程，考虑三角分解 A-LU (2-14) 即 [bi C1 C2 an-1 6n-1 Cn- an 41 mn-i mn 比较上式两边的对应元素，可得m,l:,u:的计算公式： ,=b4=分 m=a=6-m-4=(i=2,3,-1 mn=am,ln=bn一mnu1-1 2)回代过程，利用三角分解式(2-14)，可以把方程组(2-13)化为如下的等价形式： (Ly=d Ux=y 这两个方程组都是三角方程组，因此，可以递推计算： d y= =(d,-my-）(i=2,3,…n y n=yn x:=y一x+1 (i=n一1，…，2,1)
32 I部分 数值分析 下面，我们给出求解三对角方程组 - 1 )的追赶法的计算过程. 算法 7求解三对角方程组的追赶法. 1)三角分解过程，考虑三角分解 A=LU (2-14) t!p: b1 C1 • • • - zl fu-4 • FOaz Cn a n- 1 bn- 1 - 1 a n b 1 U 1 • • • U z • • • l • • • - 2 • FL • m z • U n - 1 m ln-1 l n - 1 m n 1 比较上式两边的对应元素，可得叫， i ， i的计算公式: l ' U 1 ma= 川=bz-mAja=f(i=2 ，3 ，η-1) ，ln=hn-mnu n_ 2) 式(2-14) 组(2-13) 为如 价形 Ly=d Ux=y 这两个方程组都是三角方程组，因此，可以递推计算: d 1 Yl 俨士 - m Ci = 2 , 3 , … , n ) Xn=Yn = v ,-u,x (i=n-1 ,… , 2 , 1) • .)' i ""'i........ i+1
第二章解线性代数方程组的直接法 33 例2.6用追赶法求解三对角线代数方程组 Ax=b. 其中 「2 2 0 0 01 -11 2 0 A=0 -1 1 0 b= 0 0 -1 1 2 791 0 0 -1 1 1 解首先考虑追赶法的三角分解： 4100007「1 00 07 mz l2 00 0 o 1 0 0 A=0m3 00 1 0 =:工0， 0 0 0 0 0 1 us 0 0m5 000 1 比较两边系数，得 l1=2,41=1 m2=-1,42=2,44-1 m3=-1,L3=2,43=1; m,=-1, 4=2, 4=1; m5=-1,13=2. 于是 「2 000 07 「110007 -1 0 0 0 1 1 0 L- 0 -1 0 0 1 1 0 0 0 -1 2 0 0011 0 0 -12 o 001 (Ly=b Ux=y
第二章解线性代数方程组的直接法 3 3 赶法求 Ax = b. 其中 2 2 O O 01 r6 -1 l 2 O O 7 A= I 0 -1 1 2 O , b= 9 O O -1 1 2 11 O O O -1 l 1 解首先考虑追赶法的三角分解: O O O O 1 U 1 O O O O O O O 1 U z O O A= I 0 m 3 13 O O O O 1 U 3 ol=:[u, O O m4 14 O O O O l U 4 O O O m s O O O O 1 比较两边系数，得 lJ =2. U J= 1; mz=-1. lz =2. uz=1; m 3 =-1. 13 =2. U 3 =1; 14 =2 , U 4 =1; s- 1， Is =2. 于是 2 O O O O 1 1 O O O 2 O O O O l 1 O O L= I 0 2 O O , u一一 O O 1 1 oI . O O -1 2 O O O O 1 1 O O O 2 O O O O 1 Ly=b Ux=y
34第I部分数值分析 回代计算，得到 37 1 y= 79 X= 2345
34 回代计算，得到 3 1 5 2 y= 17 , x= 3 • • 9 4 5 5
第三章解线性代数方程组的选代法35 第三章解线性代数方程组的迭代法 在许多实际问题中，常常需要求解这样的线代数方程组，它的系数矩阵阶数很 高，但非零元素很少，人们称其为大型稀硫线代数方程组.对于这类方程组，如果它又 不具有带状性，那么，再用直接法求解就不太有效，因为用直接法进行消元或矩阵的 三角分解时，没有考虑到系数矩阵的稀疏性，破坏了系数矩阵的形状，导致了计算量 的增加和存储单元的浪费，于是，人们常用迭代法求解大型稀疏线代数方程组，迭代 法只需存储系数矩阵的非零元素，这样，占用内存单元较少，能解高阶线代数方程组！ 由于迭代法是通过逐次迭代来逼近方程组的解，因此，收敛性和收敛速度是构造迭代 法时要注意的问题，那么，是否可以构造一种适用于一般情况的迭代法呢？回答是否 定的，这是因为不同的系数矩阵具有不同的性态，一般地，每一种迭代法都具有一定 的适用范围，在本章的学习中将会看到，有时，某种方法对一类方程组迭代收敛，而对 另一类方程组进行迭代时就会发散，因此，我们应该学会针对具有不同性质的线代数 方程组，构造合适的迭代方法 本章主要介绍一些基本的迭代法，并在一定的范围内讨论其中几种方法的收敛 性 §3.1基本迭代法 考虑线性代数方程组 a11x1十a12x2+…+a1mxn=b1, a2x1十a2x2十…十a2axn=b2, (3-1) am1x1十am2x2十…十anEn=bn, 采用矩阵和向量记号，我们可以把式(3-1)写成 Ax=b, (3-2) 其中，A∈Rxm为非奇异矩阵，设ag牛0(i=1,2,…,n) 下面我们介绍Jacobi迭代、Gauss-Seidel迭代、SOR迭代的基本思想和算法，为
第三章 第三章解线性代数方程组的迭代法 3 5 解线性代数方程组的迭代法 在许多实际问题中，常常需要求解这样的线代数方程组，它的系数矩阵阶数很 高，但非零元素很少，人们称其为大型稀疏线代数方程组.对于这类方程组，如果它又 不具有带状性，那么，再用直接法求解就不太有效，因为用直接法进行消元或矩阵的 三角分解时，没有考虑到系数矩阵的稀疏性，破坏了系数矩阵的形状，导致了计算量 的增加和存储单元的浪费，于是，人们常用迭代法求解大型稀疏线代数方程组，迭代 法只需存储系数矩阵的非零元素，这样，占用内存单元较少，能解高阶线代数方程组. 由于选代法是通过逐次迭代来逼近方程组的解，因此，收敛性和收敛速度是构造选代 法时要注意的问题，那么，是否可以构造一种适用于一般情况的迭代法呢?回答是否 定的，这是因为不同的系数矩阵具有不同的性态，一般地，每一种迭代法都具有一定 的适用范围，在本章的学习中将会看到，有时，某种方法对一类方程组迭代收敛，而对 另一类方程组进行迭代时就会发散，因此，我们应该学会针对具有不同性质的线代数 方程组，构造合适的迭代方法. 本章主要介绍一些基本的迭代法，并在一定的范围内讨论其中几种方法的收敛 性. § 3. 迭代法 考虑线性代数方程组 allx 十a 2x =bJ , aZ1x1+azzxz … 十 =b2 , • •• XI +an2xZ … 十 n n 采用矩阵和向量记号，我们可以把式(3-1)写成 Ax = b , (3-1) (3-2) 其中 n为非奇异矩阵，设 (i 1， 2，…， n). 下面我们介绍 i迭代、 s s 选代、 R迭代的基本思想和算法，为
36第I部分数值分析 了方便地给出矩阵表示式，我们引进下列的矩阵分裂 A=-L+D-U (3-3) 其中 0 0 0 0 一a-1, 0 1)Jacobi迭代基本思想 从式(3-1)的第i个方程中解出x,(i=1,2,…,n): 无1=1(6-a12x2-a3x3…-a1nc)为 x:= 1(b。-a1z-aex-a-1z-）. 我们把迭代前的值代人上式右边，由计算得到等式左边的值作为一次迭代的新 值，然后再把这个新值代人右边，再从左边得到一个新值，如此反复，就得到了Jacob 迭代公式. 算法3.1 Jacobi迭代法. 选定初值xo∈R,对m=1,2,…,计算
36 数值分析 了方便地给出矩阵表示式，我们引进下列的矩阵分裂 A=-L 十D-U 其中 O (3-3) L= D= U= a 2l • • • anI all O O • • • ••• a22 a l2 O • • • ••• • • • ••• • • • • • • ann • • • an •n - 1 , al n • • • an-l ,n O • O , 1) Jacobi 从式 -1)的第 i个方程中解出 (i ，…， "II ••• 1 j-l n ZF 千(bi ←ZaizZi-ZG ) , Uii j=I" j=i+l' , ••• 1 , Zn= -anlxl -an2x2 ••• -an.n-IXn-I)· --nn 我们把迭代前的值代人上式右边，由计算得到等式左边的值作为-次迭代的新 值，然后再把这个新值代人右边，再从左边得到一个新值，如此反复，就得到了J a c 迭代公式. 算法 Jacobi 选定初值旷的ε R m = 1， 2