第五章线性代数方程组的解法

1、上一页上一页下一页下一页湘潭大学数学与计算科学学院1上一页上一页下一页下一页湘潭大学数学与计算科学学院2nnnnnnnbxaxabxaxa1111111本章讨论求解线性方程组：本章讨论求解线性方程组：的数值方法的数值方法.上一页上一页下一页下一页湘潭大学数学与计算科学学院3,Axb 12,Tnxxxx 12,.Tnbbbb 其中其中111212122212,nnnnnnaaaaaaAaaa 上一页上一页下一页下一页湘潭大学数学与计算科学学院4 但当方程组的阶数但当方程组的阶数 很大时，计算量为很大时，计算量为n( !)O n假设假设系数矩阵行列式系数矩阵行列式|0, A由由Cramer法则法则

2、, ,方程组有唯一解，且解可表示为：方程组有唯一解，且解可表示为：1212,.nnDDDxxxDDD11111111111,detiininn inn innaabaaDaabaa 其其中中 上一页上一页下一页下一页湘潭大学数学与计算科学学院5 常用的计算方法常用的计算方法: 直接法和迭代法直接法和迭代法 直接法：直接法：若不考虑计算过程中的舍入误差，若不考虑计算过程中的舍入误差， 则通过有限步运算可以获得方程组的精确解则通过有限步运算可以获得方程组的精确解. Gauss 消去法、消去法、Gauss列主元消去法、矩阵分解法等列主元消去法、矩阵分解法等.上一页上一页下一页下一页湘潭大学数学与计算

3、科学学院6 迭代法：迭代法：采用逐次逼近的方法采用逐次逼近的方法, 即从一个初始即从一个初始 近似解出发近似解出发, 按某种迭代格式按某种迭代格式, 逐步逼近方程组逐步逼近方程组 的解的解, 直至满足精度要求为止直至满足精度要求为止. 经典迭代法有经典迭代法有： 迭代法、迭代法、 迭代法、迭代法、JacobiGaussSeidel 逐次超松弛（逐次超松弛（SOR）迭代法等）迭代法等.上一页上一页下一页下一页湘潭大学数学与计算科学学院7 上一页上一页下一页下一页湘潭大学数学与计算科学学院85.1.1 向量空间及相关概念和记号向量空间及相关概念和记号 1. 向量的范数向量的范数1/1|,1,),p

4、npipixxp 1211|nniixxxxx 1max(|,|)nxxx 1/2221niixx 上一页上一页下一页下一页湘潭大学数学与计算科学学院9例例 : 设设(1,3, 5,4) ,Tx ,1,2,pxp 求求根据定义根据定义:411|13iixx 1/2422151iixx 14max(|,|)5xxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院102( , ).xx x 上一页上一页下一页下一页湘潭大学数学与计算科学学院11定义定义 对于任意两种范数对于任意两种范数 | |A，| |B ，总存在常数，总存在常数 C1、C2 0 使得使得 ， 则称则称 | |A 和和| |B

5、 等价等价。（范数等价性）（范数等价性）BABxCxxC|21 对于常用的范数对于常用的范数 , , ,可以算出可以算出 px1,2,p 1211xxxn1xxn x 2xxn x上一页上一页下一页下一页湘潭大学数学与计算科学学院12定义定义向量序列向量序列 收敛收敛于向量于向量 是指对每一个是指对每一个 1 i n 都都有有 。)(kx*x*)(limikikxx 可以理解为可以理解为0|*|)( xxk可以理解为对任何向可以理解为对任何向量范数都成立。量范数都成立。2. 上一页上一页下一页下一页湘潭大学数学与计算科学学院13对于对于 上的任何向量范数上的任何向量范数,我们可以定义矩阵范数我

6、们可以定义矩阵范数.nR1. 1. 矩阵的范数矩阵的范数5.1.2 矩阵的一些相关概念及记号矩阵的一些相关概念及记号上一页上一页下一页下一页湘潭大学数学与计算科学学院14定理定理5.3 矩阵的从属范数具有下列基本性质：矩阵的从属范数具有下列基本性质：1） ，当且仅当，当且仅当 时，时， 0A 0A 0A ,R |AA 2)3),;n nABABA BR nxR AxAx 4)时时5),A BAB A、Bn nR 定理5.3中的性质 1), 2) 和 3)是一般范数所满足的基本性质，性质 4)、5) 被称为相容性条件，一般矩阵范数并不一定满足该条件. 上一页上一页下一页下一页湘潭大学数学与计算科

7、学学院15非从属范数的矩阵范数非从属范数的矩阵范数 例如，矩阵例如，矩阵 的的Frobenius范数（范数（F-范数）范数）()ijAa 2 1/211,nnijFijAa 可以证明可以证明Frobenius范数满足相容性条件范数满足相容性条件 对方阵对方阵 以及以及 有有nnRA nRx 22|xAxAF 上一页上一页下一页下一页湘潭大学数学与计算科学学院16三种重要的从属范数是：三种重要的从属范数是：（1）矩阵的）矩阵的1-范数范数(列和范数列和范数): 11max|nijjiAa （2）矩阵的）矩阵的 -范数范数(行和范数行和范数): 1max|nijijAa （3）矩阵的）矩阵的2-范

8、数范数: 12A 其中其中 : 的最大特征值的最大特征值1 TA A 上一页上一页下一页下一页湘潭大学数学与计算科学学院17 对任何对任何 11x 11111| |nnnnijjijjijijAxa xax 1111|max|,nnnjijijjjiixaax从而从而11max|nijjiAxa niijaAnj11|max|1（列和范数列和范数）上一页上一页下一页下一页湘潭大学数学与计算科学学院18现设现设11max|nnijikjiiaa 令令1,0,jjkyjk 若若若若12(,)Tnyy yy 显然显然11y 满足满足111111max|nnijjxijAxAya y 且且11| ma

9、x|nnikijjiiaa上一页上一页下一页下一页湘潭大学数学与计算科学学院191312101424341420TA A2101430401420TIA A 15221 2()152215.46TAA A 解：解：16A 7A 按定义按定义例例 已知矩阵已知矩阵 12,34A ,1,2,pAp 求求上一页上一页下一页下一页湘潭大学数学与计算科学学院20矩阵范数的矩阵范数的等价定理等价定理：A A 对对 、 ，存在常数，存在常数 和和 ，使得：，使得：mMm AAM A 几种常用范数的等价关系：几种常用范数的等价关系：22FAAn A 21AAn An1211AAn An上一页上一页下一页下一页

10、湘潭大学数学与计算科学学院212. 2. 谱半径谱半径2()TAA A 此时此时n nAR 2()AA 若若 为对称阵，为对称阵，2()()TA AA （ 因为因为 ）上一页上一页下一页下一页湘潭大学数学与计算科学学院22证明证明 首先证明（首先证明（1）. 关于矩阵的谱半径与矩阵的范数之间有如下关系.上一页上一页下一页下一页湘潭大学数学与计算科学学院23AxAx今设今设 为为 的特征值的特征值 A0,v 则有则有使得使得Avv | vvAvAv 从而从而即即 |A ()AA 由由 的任意性得的任意性得证毕证毕给定给定 的某一种范数的某一种范数 ， AAnxR 则对任何则对任何有有上一页上一页

11、下一页下一页湘潭大学数学与计算科学学院24 (2) 对对 A 做做 Jordan 分解，有分解，有 ，其中，其中 ， ， i 为为 A 的的 特征值。特征值。 令令 ，则有，则有 易证：易证： 是由是由 导出的从属范数。导出的从属范数。 所以只要取所以只要取 ，就有，就有| A | 0? 因为因为det(Ak) 02/1LDL 则则 仍是下三角阵仍是下三角阵TLLA nnRL 设矩阵设矩阵A对称正定，则存在非奇异下三角阵对称正定，则存在非奇异下三角阵 使得使得 。若限定。若限定 L 对角元为正，则分解唯一。对角元为正，则分解唯一。TLLA 定理定理上一页上一页下一页下一页湘潭大学数学与计算科学

12、学院611111121112112122212222211,11200nnnnnnnnnnnnnnnnlaaalllllaaalllllaaal 对于对称正定阵对于对称正定阵 A ，从，从 可知对任意可知对任意k i 有有 。即即 L 的元素不会增大，误差可控，不的元素不会增大，误差可控，不需选主元。需选主元。21 iiiikkaliiikal |上一页上一页下一页下一页湘潭大学数学与计算科学学院62 算法算法: Cholesky分解分解将对称正定将对称正定 n n n n矩阵矩阵 A A分解成分解成 LLLLT T, , 这里这里 L L是下三角阵是下三角阵 Input: 矩阵矩阵A A的维

13、的维数数n n; ; 矩阵矩阵A A的元素的元素 aij 1 i, j n .Output: 矩阵矩阵L 的元素的元素 lij ： 1 j i and 1 i n . Step 1 Set ;Step 2 For j = 2, , n, set ;Step 3 For i = 2, , n 1, do steps 4 and 5Step 4 Set ; Step 5 For j = i+1, , n, set ; Step 6 Set ;Step 7 Output ( lij for j = 1, , i and i = 1, , n ); STOP. 1111al 1111/laljj 12

14、1 iiiiiikklal( () )11 ijijijkikiiklal ll121 nnnnnnkklal运算量为运算量为 O(n3/6)， 比普通比普通LU分解少一半，但有分解少一半，但有 n 次开方。用次开方。用A = LDLT 分解，可省开方时间分解，可省开方时间。上一页上一页下一页下一页湘潭大学数学与计算科学学院63 解解三对角方程组三对角方程组的的追赶法追赶法 nnnnnnnfffxxxbacbacbacb212111122211步骤步骤1: 对对 A 作作Crout 分解分解 111121nnnA 直接比较等式两边直接比较等式两边的元素，可得到计的元素，可得到计算公式算公式。步

15、骤步骤2: 追追即解即解 ：fyL ,111 fy ),.,2()(1niyrfyiiiii 步骤步骤3: 赶赶即解即解 ：yxU )1,., 1(,1 nixyxyxiiiinn 与与Gauss消去法类似，一旦消去法类似，一旦 i = 0 则算法中断，故并非任何则算法中断，故并非任何三对角阵都可以用此方法分解。三对角阵都可以用此方法分解。上一页上一页下一页下一页湘潭大学数学与计算科学学院64 如果如果 A 是是严格严格对角占优阵，则不要求三对角线上的对角占优阵，则不要求三对角线上的所有元素非零。所有元素非零。根据不等式根据不等式 可知：分解过程中，矩阵元素不会过分增大，算法可知：分解过程中，

16、矩阵元素不会过分增大，算法保证稳定。保证稳定。运算量为运算量为 O(6n)。|,1|1iiiiiiiiabbab 若若 A 为为对角占优对角占优 的三对角矩阵，且满足的三对角矩阵，且满足 ，则追赶法可解以，则追赶法可解以 A 为系数矩阵的方程组。为系数矩阵的方程组。0,0, 0|, 0|11 iinncaabcb定理定理上一页上一页下一页下一页湘潭大学数学与计算科学学院65上一页上一页下一页下一页湘潭大学数学与计算科学学院66求解求解 时，时，A 和和 的误差对解的误差对解 有何影响？有何影响？bxA bx 设设 A 精确，精确， 有误差有误差 ，得到的解为，得到的解为 ，即，即bb xx b

17、bxxA )(bAx 1 |1bAx |xAxAb 又又|1bAx |1bbAAxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院67 设设 精确，精确，A有误差有误差 ，得到的解为，得到的解为 ，即，即bA xx bxxAA )( bxAAxAA )()(xAxAA )(xAxAAIA )(1xAAAAIx 111)( (只要只要 A充分小，使得充分小，使得)1|11 AAAA |1|1|1111AAAAAAAAAAAAxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院68注注: cond (A) 的具体大小与的具体大小与 | | 的取法有关。的取法有关。 cond (A) 取决

18、于取决于A，与解题方法无关。，与解题方法无关。 |)(1)(|bbAAAAAcondAcondxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院69精确解精确解为为.11 x例：例： 97.199.1,98.099.099.01bA计算计算cond (A)2 。 10000990099009800A 1 = 解：解：考察考察 A 的特征根的特征根 0)det(AI 000050504. 0980050504. 121 212)( Acond 39206 1给一个扰动给一个扰动b 3410106.01097.0b ，其相对误差为，其相对误差为%01.010513.0|422 bb 此时此时

19、精确解精确解为为 0203. 13*x 0203.22*xxx 22|xx 2.0102 200%上一页上一页下一页下一页湘潭大学数学与计算科学学院70 Gauss消去法的舍入误差消去法的舍入误差 舍入误差分析方法 1. 向前误差分析方法：按照所执行的运算次序而估计舍入误差积累的界限. 这种方法的好处是估计比较准确，但对复杂算法（如Gauss消去法）一般难以进行。 2. 向后误差分析方法：将实际计算过程的误差转换为关于原始数据的误差。 上一页上一页下一页下一页湘潭大学数学与计算科学学院71对对GaussGauss消去法消去法, ,其具体提法是：其具体提法是：对于系数矩阵扰动：对于系数矩阵扰动：

20、, AAA 求解求解 时时, , 所得的计算解所得的计算解 是是如下扰动方程如下扰动方程 Axb x ().AA xbd+=%的精确解。的精确解。上一页上一页下一页下一页湘潭大学数学与计算科学学院72GaussGauss消去法由两个独立算法所组成消去法由两个独立算法所组成: :一是一是对对A做做LU分解分解; ;二是二是求解三角方程组求解三角方程组. .这两个独立运算均会产生舍入误差这两个独立运算均会产生舍入误差. .如果是选主元的如果是选主元的GaussGauss消去法消去法, ,由于只增加了由于只增加了矩阵行、列的交换，并不产生新的舍入误差，矩阵行、列的交换，并不产生新的舍入误差，因此并不

21、影响误差分析。因此并不影响误差分析。上一页上一页下一页下一页湘潭大学数学与计算科学学院73(2),.()()()LLUUxbL ybAU xxbyAddd+=%(1),;AL UAEL U=+=上一页上一页下一页下一页湘潭大学数学与计算科学学院74上一页上一页下一页下一页湘潭大学数学与计算科学学院75上一页上一页下一页下一页湘潭大学数学与计算科学学院76由上可见，对由上可见，对GaussGauss消去法，消去法，3215()1.01(3)101()AxcondAnnAxcondAA 只要只要 不是很大，则不是很大，则GaussGauss消去法是消去法是数值稳定的数值稳定的 ()condA 结论

22、：条件数越大，扰动对解的影响越大结论：条件数越大，扰动对解的影响越大. .上一页上一页下一页下一页湘潭大学数学与计算科学学院774 4 解线性方程组的迭代法解线性方程组的迭代法 上一页上一页下一页下一页湘潭大学数学与计算科学学院78bxA 将将 等价等价bxA 改写为改写为 形式，建立迭代形式，建立迭代 。从初值从初值 出发，得到序列出发，得到序列 。fxBx fxBxkk )()1()0(x)(kx研究研究 内容：内容： 如何建立迭代格式？如何建立迭代格式？ 收敛速度？收敛速度？ 向量序列的收敛条件？向量序列的收敛条件？ 误差估计？误差估计？思思路：路：上一页上一页下一页下一页湘潭大学数学与

23、计算科学学院79 Jacobi 法和法和 Gauss - Seidel 法法 Jacobi 迭代方法迭代方法 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111( () )( () )( () ) nnnnnnnnnnnnbxaxaaxbxaxaaxbxaxaax11112212122211212111.1.1.10 iia ()()()nknnnknnnknknnkkknnkkbxaxaaxbxaxaaxbxaxaax)(11)(11)1(2)(2)(12122)1(21)(1)(21211)1(1.1.1.1上一页上一页下一页下一页湘潭

24、大学数学与计算科学学院80 nnnnnnnnnnbxaxaxabxaxaxabxaxaxa.22112222212111212111写成写成矩阵形式矩阵形式：A =LUDbxULxDbxULDbxA )()(bDxULDx11)( BfJacobi 迭代阵迭代阵bDxULDxkk1)(1)1()( 上一页上一页下一页下一页湘潭大学数学与计算科学学院81 例例求求1235131241246113xxx 的的Jacobi迭代格式。迭代格式。 解解 31164242135321321321xxxxxxxxx1232133121(13)51(22)41(346)11xxxxxxxxx 上一页上一页下一

25、页下一页湘潭大学数学与计算科学学院821232133121(13)51(22)41(346)11xxxxxxxxx (1)( )( )123(1)( )( )213(1)( )( )3121(13)51(22)41(346)11kkkkkkkkkxxxxxxxxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院83 算法算法: Jacobi: Jacobi迭代方法迭代方法 求解求解 给定初始值给定初始值 . .Input: 方程和未知量的个数方程和未知量的个数 n n; ; 矩阵元素矩阵元素 a a ; ; 元素元素 b b ; ; 初始近似值初始近似值 X X0 ; 0 ; 误差容限误差

26、容限 TOLTOL; ; 最大迭代次数最大迭代次数 N Nmaxmax. .Output: 近似解近似解 X 或失败的信息或失败的信息.Step 1 Set k = 1;Step 2 While ( k Nmax) do steps 3-6Step 3 For i = 1, , n Set ; /* 计算计算 xk */Step 4 If then Output (X ); STOP; /* 成功成功 */Step 5 For i = 1, , n Set X 0 = X ; /* 更新更新 X0 */ Step 6 Set k +;Step 7 Output (超过最大迭代次数超过最大迭代次

27、数); STOP. /* 失败失败 */bxA )0(xiinjijjijiiaXabX 1)0(TOLXXXXiini |0|max|0|1如果如果 aii = 0，怎么办怎么办?迭代过程中，迭代过程中，A 的元素的元素不改变，故可以不改变，故可以事先调整事先调整好好 A 使得使得aii 0，否则否则 A不可逆不可逆。必须等必须等X X( (k k) )完全计算完全计算好了才能计算好了才能计算X X( (k k+1)+1)，因此，因此需要需要两组向量两组向量存储。存储。上一页上一页下一页下一页湘潭大学数学与计算科学学院84 Gauss - Seidel 迭代方法迭代方法)(11)(1)(41

28、4)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 只存一组向量即可。只存一组向量即可。写成写成矩阵形式矩阵形式：bDxUxLDxkkk1)()1(1)1()( bxUxLDkk )()1()(bLDxULDxkk1)(1)1()()( BfGauss-Seidel 迭代阵迭代阵

29、上一页上一页下一页下一页湘潭大学数学与计算科学学院85例例 求方程组求方程组1235131241246113xxx 的的GaussSeidel迭代格式。迭代格式。上一页上一页下一页下一页湘潭大学数学与计算科学学院861235131241246113xxx 1232133121(13)51(22)41(346)11xxxxxxxxx (1)( )( )123(1)(1)( )213(1)(1)(1)3121(13)51(22)41(346)11kkkkkkkkkxxxxxxxxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院87 松弛法松弛法 换个角度看换个角度看Gauss - Seide

30、l 方法：方法： nijkjijijkiijiiikixaxabax1)(11)1()1(1iikikiarx)1()( 其中其中ri(k+1) = ijijkjijkjijixaxab)()1(残量残量相当于在相当于在 的基础上的基础上加个余项加个余项生成生成 。)(kix)1( kix下面令下面令 ，希望通过选取合适的，希望通过选取合适的 来来加速收敛，这就是加速收敛，这就是松弛法松弛法 。iikikikiarxx)1()()1( 0 1(渐次渐次)超松弛法超松弛法 上一页上一页下一页下一页湘潭大学数学与计算科学学院88 写成写成矩阵形式矩阵形式：iikikikiarxx)1()()1(

31、)1()()1(1)()1(bxUxLDxxkkkk bLDxUDLDxkk 1)(1)1()()1()( Hf松弛迭代阵松弛迭代阵 ijikjijijkjijiikibxaxaax)1()()1()( 上一页上一页下一页下一页湘潭大学数学与计算科学学院89例例 求方程组求方程组1235131241246113xxx 的的SOR迭代格式。迭代格式。1235131241246113xxx 解解上一页上一页下一页下一页湘潭大学数学与计算科学学院901232133121(13)51(22)41(346)11xxxxxxxxx (1)( )( )( )1231(1)(1)( )( )2132(1)(1

32、)(1)( )31231(13)(1)51(22)(1)41(346)(1)11kkkkkkkkkkkkxxxxxxxxxxxx 上一页上一页下一页下一页湘潭大学数学与计算科学学院91的收敛条件的收敛条件fxBxkk )()1(*)1()1(xxekk )()()(*)()*()(kkkeBxxBfxBfxB )0()(eBekk |.|)0() 1()(eBeBekkk 充分条件充分条件: |B| 1 kBk as0|0|)(ke必要条件必要条件:kkBke as0)(00 迭代法的收敛性迭代法的收敛性*xBxf 上一页上一页下一页下一页湘潭大学数学与计算科学学院920|xBk对对任意非零向

33、量任意非零向量 成立成立x迭代迭代证明：证明：Bk 0| Bk | 00|max0 xxBkx0 xBk对对任意非零向量任意非零向量 成立成立x从任意从任意 出发，出发， 记记 ，则，则)0(x*)0()0(xxe 0)0()( eBekkas k )( kx收敛收敛设设fxBx 存在唯一解，则从任意存在唯一解，则从任意 出发，出发， )0(xfxBxkk )()1(收敛收敛0kB ( ( B ) 1 ) 1定理定理上一页上一页下一页下一页湘潭大学数学与计算科学学院93 （充分条件）（充分条件）若存在一个矩阵范数使得若存在一个矩阵范数使得 | B | = q 1, 则则迭代收敛，且有下列误差估

34、计：迭代收敛，且有下列误差估计：证明：证明：)*()*(*)1()()()1()( kkkkkxxxxBxxBxx|)|*(|*|)1()()()( kkkkxxxxqxx )(.)()0()1(1)2()1()1()(xxBxxBxxkkkkk |)0()1(1)1()(xxqxxkkk |1|*|)1()()( kkkxxqqxx|1|*|)0()1()(xxqqxxkk 定理定理上一页上一页下一页下一页湘潭大学数学与计算科学学院94 证明：证明：首先需要一个引理首先需要一个引理 若若A 为严格对角占优阵，则为严格对角占优阵，则det(A) 0，且所有的，且所有的 aii 0。 证明：证明

35、：若不然，即若不然，即det(A) = 0，则，则 A 是奇异阵。是奇异阵。存在非零向量存在非零向量 使得使得 Tnxxxx),(210 .00 xA记记|max|1inimxx niiimxa10 miimmmiiimmmmaxxaxa|我们需要对我们需要对 Jacobi 迭代和迭代和 Gauss-Seidel迭代分别迭代分别证明：任何一个证明：任何一个| | 1 都都不可能不可能是对应迭代阵的是对应迭代阵的特征根，即特征根，即 | I B | 0 。Jacobi: BJ = D 1( L + U )| )(|1ULDIBI | | )(|11ULDDULDD aii 0ijaija nna

36、a 11如果如果 | | 1 则则 ijijiiiiaaa| 是严格对角占优阵是严格对角占优阵| I B | 0 关于关于Gauss-Seidel迭代的证明迭代的证明与此类似。与此类似。 （充分条件）（充分条件）若若A 为为严格对角占优阵，严格对角占优阵， 则解则解 的的Jacobi 和和 Gauss - Seidel 迭代均收敛。迭代均收敛。bxA 定理定理上一页上一页下一页下一页湘潭大学数学与计算科学学院95 （充分条件）（充分条件）若若A 为为不可约对角占优阵，不可约对角占优阵，则解则解 的的Jacobi 和和 Gauss - Seidel 迭代均收敛。迭代均收敛。bxA 定理定理上一页

37、上一页下一页下一页湘潭大学数学与计算科学学院96 若线性方程组若线性方程组 的系数矩阵的系数矩阵 是是对角元素为正的实对称阵，则对角元素为正的实对称阵，则Jacobi方法收敛的充方法收敛的充分必要条件是分必要条件是 和和 同时正定同时正定.AXb AA2DA 设线性方程组设线性方程组 的系数矩阵的系数矩阵 为为实对称正定的，则实对称正定的，则G-S方法收敛方法收敛 .AXb A定理定理定理定理上一页上一页下一页下一页湘潭大学数学与计算科学学院97 JacobiJacobi方法和方法和GSGS方法的收敛条件大多数是互不包含的方法的收敛条件大多数是互不包含的. . 二种方法都存在二种方法都存在收敛

38、性问题收敛性问题。 Gauss-Seidel方法收敛时，方法收敛时，Jacobi方法可能不收敛；方法可能不收敛； 而而Jacobi方法收敛时，方法收敛时， Gauss-Seidel方法也可能不收敛。方法也可能不收敛。上一页上一页下一页下一页湘潭大学数学与计算科学学院98例例：给出方程组：给出方程组 其中其中,iiA xb 1,2,i 1122111,221A 2211111112A 问问:Jacobi:Jacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法是否收敛？迭代法是否收敛？解：解：11A xb 对对022101,220JB 022021086GB 上一页上一

39、页下一页下一页湘潭大学数学与计算科学学院993det()0JIB ()0JB 2det()(44)0GIB 而而12,30, 22 2 ()22 2GB 即即所以，对所以，对11,A xb JacobiJacobi方法收敛，方法收敛，G-SG-S方法发散方法发散 同理，对于同理，对于22,A xb 2211111112A 其中其中上一页上一页下一页下一页湘潭大学数学与计算科学学院10001/21/2101,1/21/20JB 01/21/201/21/2001/2GB 35det()04JIB 2,35 / 2i 10 , ()5/2JB 即得即得2det()(1/2)0GIB 而而12,30

40、,1/2 上一页上一页下一页下一页湘潭大学数学与计算科学学院101()1/2GB 则则22,A xb 所以，对所以，对Jacobi方法发散，方法发散，G-S方法收敛方法收敛. 上一页上一页下一页下一页湘潭大学数学与计算科学学院102 设设 A 可逆，且可逆，且 aii 0，松弛法从任意松弛法从任意 出发对出发对某个某个 收敛收敛 ( ( H ) 1 ) 1。)0(x H 的计算是太复杂，的计算是太复杂， 谱半径难于获得谱半径难于获得! 定理定理上一页上一页下一页下一页湘潭大学数学与计算科学学院103 （Kahan 必要条件）必要条件）设设 A 可逆，且可逆，且 aii 0，松弛法松弛法 从任意

41、从任意 出发收敛出发收敛 0 0 2 2 。)0(x证明：证明：从从 出发出发)1()(1UDLDH niiH1)det( 利用利用，而且收敛，而且收敛 | | i | 1 | 1 总成立总成立可知收敛可知收敛 | | det(H ) | 1| 1 niiiaLDLD111)det(1)det( niiinaUD1)1()1det( nH)1()det( | | det(H ) | | 1 | | 1 |n 1 1 0 0 2 2 定理定理上一页上一页下一页下一页湘潭大学数学与计算科学学院104 （Ostrowski-Reich 充分条件）充分条件）若若A 对称正定，且有对称正定，且有 0 0 2 2，则，则松弛法从任意松弛法从任意 出发收敛出发收敛。)0(x定理定理上一页上一页下一页下一页湘潭大学数学与计算科学学院105Q: 什么因素决定收敛的速度什么因素决定收敛的速度?A: ( ( B )