数值分析-第6章-线性代数方程组的迭代法PPT课件.ppt

1、2022-4-20第6章 解线性方程组的迭代法16.1 迭代法的基本概念迭代法的基本概念6.2 雅可比迭代法与高斯雅可比迭代法与高斯-塞德尔迭代法塞德尔迭代法6.3 超松弛迭代法超松弛迭代法6.4 共轭梯度法共轭梯度法第第6 6章章 解线性方程组的迭代法解线性方程组的迭代法/* Iterative Techniques for Solving Linear Systems */2022-4-20第6章 解线性方程组的迭代法26.1 迭代法的基本概念迭代法的基本概念 考虑线性方程组考虑线性方程组 ,bAx （1.1）其中其中 为非奇异矩阵。为非奇异矩阵。A 迭代法通常都可利用迭代法通常都可利用

2、中有大量零元素的特点中有大量零元素的特点. . A6.1.1 引言引言 当当 为低阶稠密矩阵时，选主元消去法是有效方法为低阶稠密矩阵时，选主元消去法是有效方法. . A 迭代法适用于求解大型稀疏的线性方程组。迭代法适用于求解大型稀疏的线性方程组。基本思想：基本思想：通过构造迭代格式产生迭代序列，由迭代序列通过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组的解。来逼近原方程组的解。要解决的基本问题：要解决的基本问题：1. 如何构造迭代格式如何构造迭代格式 2.迭代序列是否收敛迭代序列是否收敛 , 2 , 1 , 0,)()1()0(kfBxxxkk，初初始始向向量量)(2022-4-20第6

3、章 解线性方程组的迭代法3 6.1.2 向量序列与矩阵序列的极限向量序列与矩阵序列的极限 ,2, 1lim)(nixxikikx则称向量序列则称向量序列 收敛于收敛于 ，记为，记为)(kx.lim)(xxkk 定义定义2 设有向量序列设有向量序列 如果存在如果存在 ，使，使,R),(,R)()(2)(1)()(nTknkkknkxxxxxnTnxxxxR),(21. 0limlim)()( xxxxkkkk其中其中 为任一种向量范数为任一种向量范数. . 定义定义3 设有矩阵序列设有矩阵序列 及及 , ,如果如果 个数列极限存在且有个数列极限存在且有 nnkijkaAR)()(nnijaAR)

4、(2n),2, 1,(lim)(njiaaijkijk则称则称 收敛于收敛于 ，kAA.limAAkk记为记为 Tkkkkx)1,1()( Tkkx)1 , 0(lim)( 2022-4-20第6章 解线性方程组的迭代法4 解解由于，当由于，当 时，有时，有 1.0000limlimkkkkAA.0limkk所以所以 例例1 设有矩阵序列设有矩阵序列 ,01A且设且设 ，考查其极限，考查其极限. . 1,02222A,0,1kkkkkA 证明证明.0limlimAAAAkkkk范数的等价性范数的等价性 定理定理1 0limlimAAAAkkkk其中其中为矩阵的任意一种算子范数为矩阵的任意一种算

5、子范数. . 2022-4-20第6章 解线性方程组的迭代法5 证明证明.xAxAkk 定理定理2 的充分必要条件是的充分必要条件是OAkk lim,R,0limnkkxxA（1.7）若若 ，则，则 ，OAkk lim0limkkA取取 为第为第 个坐标向量个坐标向量 ，则，则xjje,0lim jkkeA.limOAkk 必要性。必要性。nxR0limxAkk故对一切故对一切 ，有，有 . .kAj表示表示 的第的第 列元素极限均为零，列元素极限均为零，nj, 2 , 1当当 时，时，就得到就得到矩阵的算子范数满足矩阵的算子范数满足 充分性。充分性。.R, 0limnkkxxA .R, 0l

6、imnkkxxA 2022-4-20第6章 解线性方程组的迭代法6kB.RnnB 定理定理3 设设 ，下面下面3个命题等价：个命题等价：.RnnB（1 1） ；OBkk lim证明证明与迭代矩阵相关的结论与迭代矩阵相关的结论1)( B （2 2） ；.1 B（3 3）至少存在一种从属的矩阵范数）至少存在一种从属的矩阵范数 ，使，使)2()1(反证法。反证法。1B假定假定 有一个特征值有一个特征值 ，满足满足 , ,0 xxBx 则存在则存在 ，使，使 ，,xxBkk由此由此,. 0lim xBkk1由由定理定理2 2知（知（1）不成立，从而知）不成立，从而知 ，即（，即（2）成立）成立.)3(

7、)2(0)(BB对任意对任意 ，存在一种从属范数，存在一种从属范数 ，使，使 ，01B适当选择适当选择 ，可使，可使 ，即（，即（3 3）成立）成立. .)1()3(由矩阵范数由矩阵范数 ，1 B可得可得 ，从而有，从而有0limkkB.limOBkk ,kkBB又又2022-4-20第6章 解线性方程组的迭代法9 将将 分裂为分裂为 A,NMA（1.9）其中，其中， 为可选择的为可选择的非奇异矩阵非奇异矩阵，且使，且使 容易求解，容易求解，MdMx 称称 为为分裂矩阵分裂矩阵. . MbNxMxbAx .11bMNxMxbAx求解即求解即求解一阶定常迭代法一阶定常迭代法 ,2,1 ,0,)(

8、)1()0(kfBxxxkk，初初始始向向量量)(（1.11）即即,fBxx（1.10）迭代的构造迭代的构造其中其中 NMB1 .1bMf )(1AMM ,1AMI 迭代矩阵迭代矩阵2022-4-20第6章 解线性方程组的迭代法106.1.4 迭代法的收敛性迭代法的收敛性 研究研究 的收敛性的收敛性. . )(kx 引进误差向量引进误差向量 *,)1()1(xxkk 得得 ，),2, 1 ,0()()1(kBkk.*fBxx,2, 1 ,0,)()1(kfBxxkk)1()(kkB递推得递推得 .)0(kB研究研究 在什么条件下有在什么条件下有B0lim)(kk.lim零零矩矩阵阵）(OBkk

9、 )0( 是初始误差向量，是一个确定的值。是初始误差向量，是一个确定的值。对任意的初始向量对任意的初始向量 ，序列，序列 收敛收敛)0(x )(kx0lim)0( kkB2022-4-20第6章 解线性方程组的迭代法11 定理定理5 给定线性方程组给定线性方程组 ,fBxx 及一阶定常迭代法及一阶定常迭代法 .)()1(fBxxkk 对任意选取初始向量对任意选取初始向量 ，迭代法收敛的充要条件是矩阵，迭代法收敛的充要条件是矩阵 的谱半径的谱半径)0(xB.1)(B（1）迭代法是否收敛取决于迭代矩阵的迭代法是否收敛取决于迭代矩阵的谱半径谱半径，与初，与初始向量和常数项无关。始向量和常数项无关。（

10、2）而对于同一个方程组，不同的迭代法对应的迭代而对于同一个方程组，不同的迭代法对应的迭代矩阵的矩阵的谱半径谱半径一般不会相同，因而收敛性也不同。一般不会相同，因而收敛性也不同。注：注：.1 B注：注：至少存在一种从属的矩阵范数至少存在一种从属的矩阵范数 ，使，使迭代法收敛的判别准则迭代法收敛的判别准则2022-4-20第6章 解线性方程组的迭代法12 例例2 求解方程组求解方程组 .361236,33114,20238321321321xxxxxxxxx（1.2）记为记为 , , bAx ,12361114238A方程组的精确解是方程组的精确解是 . . Tx)1,2,3(* 其中其中 ,32

11、1xxxx.363320b现将现将(1.2)改写为改写为 ).3636(121),334(111),2023(81213312321xxxxxxxxx（1.3）或写为或写为 , , fxBx0,01231261110114828300 B其中其中 .12361133820 f2022-4-20第6章 解线性方程组的迭代法13 任取初始值，例如取任取初始值，例如取 . . Tx)0,0,0()0( 得到新的值得到新的值 ,) 3 , 3 , 5 . 2(),() 1 (3) 1 (2) 1 (1) 1 (TTxxxx,)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)

12、0( kkkkxxxxxxxxxxxx, 8/ )2023()(3)(2)1(1kkkxxx,11/ )334()(3)(1)1(2kkkxxx（1.4）.12/ )3636()(2)(1)1(3kkkxxx简写为简写为 ,)(0)1(fxBxkk其中其中 表示迭代次数表示迭代次数 k).,2, 1 ,0(k 迭代到第迭代到第10次有次有 ;)9998813.0,999838.1 ,000032.3()10(Tx*).(000187.0)10()10()10(xx2022-4-20第6章 解线性方程组的迭代法14 对于任何由对于任何由 变形得到的等价方程组变形得到的等价方程组 ，fBxxbAx

13、 迭代法产生的向量序列迭代法产生的向量序列 是否都能逐步逼近方程组是否都能逐步逼近方程组的解的解 ？ )(kx*x如方程组如方程组.53,521221xxxx构造迭代法构造迭代法.53,52)(1)1(2)(2)1(1kkkkxxxx对任何的初始向量，得到的序列都不收敛对任何的初始向量，得到的序列都不收敛. . 00)0(x 55)1(x 2015)2(x 5045)3(x2022-4-20第6章 解线性方程组的迭代法15例例3 考察线性方程组（考察线性方程组（1.21.2）给出的迭代法（给出的迭代法（1.4）的收敛性）的收敛性 .361236,33114,20238321321321xxxx

14、xxxxx（1.2）, 8/ )2023()(3)(2)1(1kkkxxx,11/ )334()(3)(1)1(2kkkxxx（1.4）.12/ )3636()(2)(1)1(3kkkxxx 041211110114418300B 先求迭代矩阵先求迭代矩阵 的特征值的特征值. . 由特征方程由特征方程0B041211111144183)det(0 BI可得可得, 0039772727. 0034090909. 0)det(30 BI解得解得,3245. 01541. 0,3245. 01541. 0,3082. 0321ii , 1, 13592. 0132 所以迭代法（所以迭代法（1.41.

15、4）是收敛的是收敛的. .1)(0B解解2022-4-20第6章 解线性方程组的迭代法16例例4 考察用迭代法解方程组考察用迭代法解方程组 fBxxkk)()1(的收敛性，的收敛性，解解.55,0320fB其中其中, 06)det(2BI特征方程为特征方程为特征根特征根 ,62, 1即即 . . 1)( B 这说明用此迭代法解此方程组不收敛这说明用此迭代法解此方程组不收敛. . .53,521221xxxx2022-4-20第6章 解线性方程组的迭代法17 定理定理6,R,nnBfBxx及一阶定常迭代法及一阶定常迭代法 .)()1(fBxxkk如果有如果有 的某种算子范数的某种算子范数 ，则，

16、则 B1 qB( (迭代法收敛的充分条件迭代法收敛的充分条件) ) 设有方程组设有方程组 (1) 迭代法收敛，即对任取迭代法收敛，即对任取 有有 )0(x.*lim)(fBxxxxkk 且且.*)2()0()(xxqxxkk .1*)3()1()()( kkkxxqqxx.1*)4()0()1()(xxqqxxkk 利用利用矩阵的范数判定迭代收敛只是一个充分条矩阵的范数判定迭代收敛只是一个充分条件，通常采用矩阵的件，通常采用矩阵的1- -范数、范数、 - -范数来判定。范数来判定。 事后估计事后估计估计迭代次数估计迭代次数2022-4-20第6章 解线性方程组的迭代法18 证明证明(2)(2)

17、.*)1()( kkxxqxx反复递推即得反复递推即得(2). (2). (1) (1) 是显然的是显然的. . 有有 (3) (3) )1()(* kkxxqxx即即 (3)(3)反复利用反复利用( (a) )1()()(1* kkkxxqqxx)(*)1()()( kkkxxqxxq.*)2()0()(xxqxxkk .1*)3()1()()(kkkxxqqxx.1*)4()0()1()(xxqqxxkk )*(*)1()( kkxxBxx由关系式由关系式)*(*)1()()()( kkkkxxxxqxx由由 )1()()1(* kkkxxxxq2022-4-20第6章 解线性方程组的迭代

18、法19 定理定理6 6只给出迭代法（只给出迭代法（1.111.11）收敛的充分条件，即使条）收敛的充分条件，即使条件件 对任何常用范数均不成立，迭代序列仍可能收敛对任何常用范数均不成立，迭代序列仍可能收敛. .1B 例例5 迭代法迭代法 , ,其中其中fBxxkk)()1(,8.03.009.0B,21f,54.1,043.1,2.1, 1.121FBBBBB 的各种范数均大于的各种范数均大于1 1，1)(B但但 ，)(kx故此迭代法产生的迭代序列故此迭代法产生的迭代序列 是收敛的是收敛的. .2022-4-20第6章 解线性方程组的迭代法20 下面考察迭代法下面考察迭代法的收敛速度的收敛速度

19、., 2, 1 , 0,()()1()0()kfBxxxkk，初始向量6.1.4 迭代法的收敛速度迭代法的收敛速度/* Rate of Average Convergence */ 假定迭代法是收敛的，即假定迭代法是收敛的，即 ，1)(B.0,)0()0()(kkB于是于是kkB)0()(根据从属范数定义，有根据从属范数定义，有,maxmax)0()(0)0()0(0)0()0(kkkBB 迭代迭代 次后误差向量次后误差向量 的范数与初始误差向量的范数与初始误差向量 的范数之比的最大值的范数之比的最大值. .kBk)(k)0( *,)0()0()0()(xxBkk 由由 ，得，得2022-4-

20、20第6章 解线性方程组的迭代法21平均每次迭代误差向量范数的压缩率平均每次迭代误差向量范数的压缩率kkB1,)0()()0()(kkkB即其中其中 ，可取，可取 . .1s 10 因为因为 ，故，故 ，1)(B11kkB,ln1ln1kBkk即即kkkkBsBk11ln10lnlnln（1.12）它表明迭代次数它表明迭代次数 与与 成反比成反比. .kkkB1lnk若要求迭代若要求迭代 次后有次后有kkkB11由由 两边取对数得两边取对数得越大越大kkkB1ln越小越小收敛越快收敛越快2022-4-20第6章 解线性方程组的迭代法22 定义定义4 迭代法（迭代法（1.111.11）的）的平均

21、收敛速度平均收敛速度定义为定义为.ln)(1kkkBBR（1.13） 定义定义5 迭代法迭代法(1.11)(1.11)的的渐近收敛速度渐近收敛速度定义为定义为 由由 ，)(lim1BBkkk).(ln)(BBR（1.14）)(10ln)(lnlnBRsBk （1.15）估计迭代次数估计迭代次数).(ln)(limBBRkk所以所以 与迭代次数及与迭代次数及 取何种范数无关，它反映了迭代次数趋取何种范数无关，它反映了迭代次数趋于无穷时迭代法的渐近性质。于无穷时迭代法的渐近性质。)(BRB)(B)(lnB当当 越小时越小时 越大，迭代法收敛越快越大，迭代法收敛越快。2022-4-20第6章 解线性

22、方程组的迭代法23迭代矩阵迭代矩阵 的谱半径的谱半径 0B,3592. 0)(0B,023876. 1)(ln)(00BBR,99.11)(10ln0BRsk即取即取 即可达到要求即可达到要求. .12k5)0()(10k若要求若要求 ，则由则由于是于是 041211110114418300B2022-4-20第6章 解线性方程组的迭代法24 nnaaaA2211 0000, 121, 211, 112nnnnnnaaaaaa（2.1）.ULD 00001,212 , 11 , 121nnnnnnaaaaaa6.2.1 雅可比迭代法雅可比迭代法 nnijaAR)(6.2 雅可比迭代法与高斯雅可

23、比迭代法与高斯-塞尔迭代法塞尔迭代法,bAx （1.1）设设 ，),2 , 1(0niaii 选取选取 ( (对角阵对角阵) )，DM NDA ,2,1 ,0,)()1()0(kfBxxxkk初初始始向向量量，（2.2）解解 的雅可比的雅可比(Jacobi)迭代法迭代法bAx 其中其中 ADIB1.1bDf)(1ULD,J雅可比迭代法的迭代阵雅可比迭代法的迭代阵2022-4-20第6章 解线性方程组的迭代法25,),()()()(1)(Tknkikkxxxx记记 雅可比迭代雅可比迭代,)()()1(bxULDxkk或或 )., 2 , 1(1)(11)()1(nibxaxaxainijkjij

24、ijkjijkiii ,2,1 ,0,)()1()0(kfBxxxkk初初始始向向量量，（2.2）其中其中 ADIB1.1bDf)(1ULD,J Tnxxx),()0()0(1)0(,/1)()1(iinijjkjijikiaxabx （2.3）).10(), 2 , 1(表表示示迭迭代代次次数数,kni 解解 的雅可比迭代法的的雅可比迭代法的分量计算公式分量计算公式bAx Jacobi方法是由方程组第方法是由方程组第i个方程解出个方程解出xi得到的等价方程组。得到的等价方程组。2022-4-20第6章 解线性方程组的迭代法26 每迭代一次只需计算一次矩阵和向量的乘法且计算过程中每迭代一次只需

25、计算一次矩阵和向量的乘法且计算过程中原始矩阵原始矩阵 始终不变始终不变. .A 6.2.2 高斯高斯-塞德尔迭代法塞德尔迭代法 分裂矩阵分裂矩阵 取为取为 的下三角部分，即的下三角部分，即 ( (下三角阵下三角阵) )，MALDM,NMA 解解 的的高斯高斯-塞德尔塞德尔(Gauss-Seidel)迭代法迭代法bAx , 2 , 1 , 0,)()1()0(kfBxxxkk），（初初始始向向量量（2.4）其中其中 ,G高斯高斯- -塞德尔迭代法的迭代阵塞德尔迭代法的迭代阵ULDG1)(.)(1bLDfULD1)(ALDIB1)(研究高斯研究高斯- -塞德尔迭代法的分量计算公式塞德尔迭代法的分量

26、计算公式. . 2022-4-20第6章 解线性方程组的迭代法27,),()()()(1)(Tknkikkxxxx记记 ,)()()1(bUxxLDkk高斯高斯- -塞德尔迭代塞德尔迭代或或 ,)()1()1(bUxLxDxkkk)., 2 , 1(1)(11)1()1(nixaxabxanijkjijijkjijikiii 即即 解解 的高斯的高斯- -塞德尔迭代法的分量计算公式塞德尔迭代法的分量计算公式 bAx (初始向量),Tnxxx),()0()0(1)0(,/1)(11)1()1(iinijkjijijkjijikiaxaxabx （2.5）).,1 ,0;,1( kni雅可比迭代法

27、的一种改进雅可比迭代法的一种改进2022-4-20第6章 解线性方程组的迭代法28或或 ,),()0()0(1)0(Tnxxx,)()1(ikikixxx ,/)(11)1(iinijkjijijkjijiiaxaxabx （2.6）).,1 ,0;,1( knixxxkk )()1()()()1(1)(kkkxUxLxbDx 2022-4-20第6章 解线性方程组的迭代法29), 1(0.0.1nixi 迭代一次，这个算法需要的运算次数至多与矩阵迭代一次，这个算法需要的运算次数至多与矩阵 的的非零元素的个数一样多非零元素的个数一样多. . A0,2, 1.2对于Nkni, 1对于iinijj

28、ijijjijiiaxaxabx/111 算法算法1 1 ( (高斯高斯- -塞德尔迭代法塞德尔迭代法) ) 设设 ，其中，其中 为非奇异矩阵且为非奇异矩阵且 本算法用高斯本算法用高斯- -塞德尔迭代法解塞德尔迭代法解 ，数组数组 开始存放开始存放 , ,后存放后存放 为最大迭代次数为最大迭代次数. . )(nx)0(x,)(kx0NbAx nnA R0iia),2, 1(nibAx 2022-4-20第6章 解线性方程组的迭代法30 例例6 用高斯用高斯- -塞德尔迭代法解线性方程组塞德尔迭代法解线性方程组(1.2). (1.2). 按高斯按高斯- -塞德尔迭代公式塞德尔迭代公式迭代迭代7

29、7次，得次，得 ，Tx)9999932.09999987.1000002.3()7(.361236,33114,20238321321321xxxxxxxxx（1.2）Tx)0,0,0()0(取取 ， , 8/ )2023()(3)(2)1(1kkkxxx,11/ )334()(3)1(1)1(2 kkkxxx) , 1 , 0(.12/ )3636()1(2)1(1)1(3 kxxxkkk.1002.2*6)7( xx且且 解解2022-4-20第6章 解线性方程组的迭代法31方程组的精确解为方程组的精确解为x*=(1,1,1)T.J迭代法计算公式为迭代法计算公式为 141035310214

30、310321321321xxxxxxxxx 57)(2103)(1101)1(321)(3103)(151)1(257)(3101)(2103)1(1kkkkkkkkkxxxxxxxxx取初始向量取初始向量x(0)=(0,0,0)T,迭代可得迭代可得4 . 1, 5 . 0, 4 . 1)1(3)1(2)1(1 xxx11. 1, 2 . 1,11. 1)2(3)2(2)2(1 xxx计算结果列表如下计算结果列表如下: :解解例例7 用用J法和法和G-S法求解线性方程组法求解线性方程组2022-4-20第6章 解线性方程组的迭代法32可见可见,迭代序列逐次收敛于方程组的解迭代序列逐次收敛于方程

31、组的解, 而且迭代而且迭代7次得到精确到次得到精确到小数点后两位的近似解小数点后两位的近似解.kx1(k)x2(k)x3(k)x(k)-x* 0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636x (6) -x(5) =0.011339,x(7) x(6) =0.00566952022-4-20

32、第6章 解线性方程组的迭代法33 同样取初始向量同样取初始向量x(0)=(0,0,0)T, 计算结果为计算结果为 由计算结果可见由计算结果可见,G-S迭代法收敛较快迭代法收敛较快.取精确到小数点后两取精确到小数点后两位的近似解位的近似解,G-S迭代法只需迭代迭代法只需迭代3次次,而而J迭代法需要迭代迭代法需要迭代7次次. 57)1(2103)1(1101)1(321)(3103)1(151)1(257)(3101)(2103)1(1kkkkkkkkkxxxxxxxxxkx1(k)x2(k)x3(k)x(k)-x* 012301.41.06340.995104400.781.020480.995

33、2756801.0260.9875161.0019068610.40.06340.0048956 G-S迭代法的计算公式为迭代法的计算公式为:不具有一般性不具有一般性2022-4-20第6章 解线性方程组的迭代法34 用用J迭代法求上例中方程组的解迭代法求上例中方程组的解,取取x(0)=(0,0,0)T,若使误差若使误差 x(k)-x* 10-5,问需要迭代多少次问需要迭代多少次?由上例知由上例知,x(1)=(1.4,0.5,1.4)T,于是有于是有 x(1)-x(0) =1.4 , B =0.5 .例例800010310110351101103Bk应满足应满足095.185 . 0ln/ )

34、4 . 1105 . 0ln(5 k故取故取k=19, 即需要迭代即需要迭代19次次.解解若使若使x(k) x* ,只需只需 )0()1(1xxBBk，即，即BkxxBln/ )ln(0)(1)(1 事前估计迭代次数事前估计迭代次数2022-4-20第6章 解线性方程组的迭代法35 定理定理7 设设 ，其中，其中 为非奇异矩为非奇异矩阵且阵且 非奇异，则非奇异，则 bAx ULDAD (1) (1) 解方程组的雅可比迭代法收敛的充要条件是解方程组的雅可比迭代法收敛的充要条件是 ，1)(J).(1ULDJ其中其中 (2) (2) 解方程组的高斯解方程组的高斯- -塞德尔迭代法收敛的充要条件是塞德

35、尔迭代法收敛的充要条件是, 1)(G.)(1ULDG其中其中 6.2.3 雅可比迭代与高斯雅可比迭代与高斯-塞德尔迭代法的收敛性塞德尔迭代法的收敛性雅可比迭代法收敛的充分条件是雅可比迭代法收敛的充分条件是. 1J. 1G高斯高斯- -赛德尔迭代法收敛的充分条件是赛德尔迭代法收敛的充分条件是2022-4-20第6章 解线性方程组的迭代法36例例9：说明用说明用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的收敛性：212 11x2x3x 31 111163 解：解：212 11 1111A 计算计算特征值特征值：12 3502, 12 120001 1 1212J法不收敛法不收敛1)

36、( J )(1ULDJG-S法的迭代矩阵为法的迭代矩阵为1()GDLU 202 1110101 0100001 01 12012 112 001200100001 01 12 000012 12 12 12 112( )G G-S法收敛法收敛2022-4-20第6章 解线性方程组的迭代法37例例9：说明用说明用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的收敛性：解：解： 531122111221321xxx 122111221A 0221012201ADIJ计算计算特征值特征值：0321 J法收敛法收敛ULDG1)( 0001002201220110011 0001002201

37、20011001 200320220计算计算特征值特征值：0; 2321 G-S法不收敛法不收敛10)( J 12)( G 2022-4-20第6章 解线性方程组的迭代法38其他收敛性结论其他收敛性结论1）对角占优矩阵的性质对角占优矩阵的性质 (1) (1) 如果如果 的元素满足的元素满足 A)., 2 , 1(1niaanijjijii 称称 为为严格对角占优阵严格对角占优阵. . A (2) (2) 如果如果 的元素满足的元素满足 A)., 2 , 1(1niaanijjijii 且上式至少有一个不等式严格成立，且上式至少有一个不等式严格成立，称称 为为弱对角占优阵弱对角占优阵. . A

38、定义定义6 ( (对角占优阵对角占优阵) ) 设设.)(nnijaA 定义定义7( (可约与不可约矩阵可约与不可约矩阵) ) 设设 , ,如果存在置换阵如果存在置换阵 使使)2()(naAnnijP,0221211 AAAAPPT（2.7）否则否则 称称 为为不可约矩阵不可约矩阵. . A其中其中 为为 阶方阵，阶方阵， 为为 阶方阵阶方阵 ，11Ar22Arn )1(nr 为为可约矩阵可约矩阵. .A则称则称进行一次行列重排进行一次行列重排2022-4-20第6章 解线性方程组的迭代法39 bAx,)(bPxPAPPTTT且记且记 2121,ddbPyyxPyTT11, dyr其中其中 为为

39、 维向量维向量. . .,22221212111dyAdyAyA由上式第由上式第2 2个方程组求出个方程组求出 , , 2y无零元素的矩阵是不可约矩阵。无零元素的矩阵是不可约矩阵。 .1y再代入第再代入第1 1个方程组求出个方程组求出 bAx例：例：矩阵矩阵可约矩阵可约矩阵1 1100011 2,11122211 nnnnnbacbacbacbA.4110140110410114 B 都是不可约矩阵都是不可约矩阵. . BA,2022-4-20第6章 解线性方程组的迭代法40 定理定理8 ( (对角占优定理对角占优定理) )如果如果 为严格对角为严格对角占优矩阵或占优矩阵或 为不可约弱对角占优

40、矩阵，则为不可约弱对角占优矩阵，则 为非奇异矩阵为非奇异矩阵. . nnijaA)(AA就就 为严格对角占优阵证明此定理为严格对角占优阵证明此定理. . A如果如果 ，则，则 有非零解，有非零解，0det A0Ax记为记为 , , Tnxxxx),(21 齐次方程组第齐次方程组第 个方程个方程 k,01njjkjxa则有则有 .0max1inikxx则则 证明证明,1 nkjjkjkkaa即即 与条件矛盾，故与条件矛盾，故 .0)det(A nkjjjkjkkkxaxa1反证法。反证法。 nkjjjkjxa1,1 nkjjkjkax2022-4-20第6章 解线性方程组的迭代法41 定理定理9

41、 设设 , ,如果：如果： bAx (1) (1) 为严格对角占优阵，则解为严格对角占优阵，则解 的雅可比迭的雅可比迭代法，高斯代法，高斯- -塞德尔迭代法均收敛塞德尔迭代法均收敛. . AbAx (2) (2) 为弱对角占优阵，且为弱对角占优阵，且 为不可约矩阵，则解为不可约矩阵，则解 雅可比迭代法，高斯雅可比迭代法，高斯- -塞德尔迭代法均收敛塞德尔迭代法均收敛. . AAbAx 2）系数矩阵）系数矩阵对角占优的对角占优的J和和G-S迭代的收敛性迭代的收敛性证明证明只证只证(1)(1)中高斯中高斯- -塞德尔迭代法收敛塞德尔迭代法收敛. . . 1)( G 由设可知，由设可知， ，), 1

42、(0niaii高斯高斯- -塞德尔迭代法的迭代矩阵为塞德尔迭代法的迭代矩阵为 )()(1ULDAULDG)(det()det(1ULDIGI).)(det()det(1ULDLD又又 , , 0)det(1LD于是于是0)(det(ULD2022-4-20第6章 解线性方程组的迭代法42ULDC )( 记记,212222111211 nnnnnnaaaaaaaaa 当当 时，时，1由由 为严格对角占优阵，为严格对角占优阵，Aiia有有 nijijijijaa111nijijijijaa111nijjijc1).,2, 1(ni因此，当因此，当 时，矩阵时，矩阵 为严格对角占优阵，为严格对角占优

43、阵，1C因此因此 .0det C即即 的特征值均满足的特征值均满足 ，G1高斯高斯- -塞德尔迭代法收敛塞德尔迭代法收敛. . iia nijijijijaa111 iic2022-4-20第6章 解线性方程组的迭代法43证明证明只证只证(1)(1)中中Jacobi迭代法收敛迭代法收敛. . . 1)( J 由设可知，由设可知， ，), 1(0niaiiJacobi迭代法的迭代矩阵为迭代法的迭代矩阵为 )()(1ULDAULDG )(det()det(1ULDIJI ).(det()det(1ULDD 又又 , , 0)det(1 D于是于是0)(det( ULD )(ULDC 记记,2122

44、22111211 nnnnnnaaaaaaaaa 当当 时，时，1由由 为严格对角占优阵，为严格对角占优阵，Aiia有有 nijijijijaa111).,2, 1(niiia nijijijijaa111 iic nijijijijaa111因此因此 .0det C2022-4-20第6章 解线性方程组的迭代法44定理定理10 设矩阵设矩阵 对称，且对角元对称，且对角元A),2, 1(0niaii (1) (1) 解线性方程组解线性方程组 的雅可比法收敛的充要条件的雅可比法收敛的充要条件是是 与与 均为正定矩阵，其中均为正定矩阵，其中bAx AAD 2).,(diag2211nnaaaD (

45、2) (2) 解线性方程组解线性方程组 的高斯的高斯- -塞德尔法收敛的充塞德尔法收敛的充分条件是分条件是 正定正定. .bAx A3）系数矩阵）系数矩阵对称正定的对称正定的J和和G-S迭代的收敛性迭代的收敛性例：例：说明用说明用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的收敛性：解：解： 6 . 26 . 26 . 218 . 08 . 08 . 018 . 08 . 08 . 01321xxx 18 . 08 . 08 . 018 . 08 . 08 . 01A 08 . 08 . 08 . 008 . 08 . 08 . 00)(1ULD计算计算特征值特征值：6 . 1;

46、 8 . 032, 1 18 . 08 . 08 . 018 . 08 . 08 . 012AD2022-4-20第6章 解线性方程组的迭代法45例例10 在线性方程组在线性方程组 中中bAx ,111 aaaaaaA证明当证明当 时高斯时高斯- -塞德尔法收敛，而雅可比迭代法塞德尔法收敛，而雅可比迭代法只在只在 时才收敛时才收敛. .121a2121a证明证明 由由 的顺序主子式的顺序主子式A011122 aaa1 a0)21()1(321det2233 aaaaA21 a当当 时，时， 正定，故高斯正定，故高斯- -塞德尔法收敛塞德尔法收敛. .121aA雅可比迭代雅可比迭代 1112aa

47、aaaaAD当当 时雅可比法收敛时雅可比法收敛. .21a011122 aaa0)21()1(3212233 aaaa1 a21 a2022-4-20第6章 解线性方程组的迭代法466.3 超松弛迭代法超松弛迭代法 6.3.1 逐次超松弛迭代法逐次超松弛迭代法 ,/1)(11)1()1(iinijkjijijkjijikiaxaxabx )()1()1()1(kikikixxx ,/)1 (1)(11)1()()1(iinijkjijijkjijikikiaxaxabxx )()()1()()1(kikikikixxxx )()1 ()()1()()1(kkkkUxLxbDxDx bxUDxL

48、Dkk )()1()1()(,)()1(fxLxkk 加速加速高斯高斯-塞德尔迭代塞德尔迭代)1()(1UDLDL ALDI1)( 设已知设已知 及已计算及已计算 的分量的分量 )(kx)1(kx).1,2, 1()1(ijxkj (1) (1) 首先用高斯首先用高斯- -塞德尔迭代法定义辅助量塞德尔迭代法定义辅助量 ,)1( kix (2) (2) 再由再由 与与 加权平均定义加权平均定义 ，)(kix)1( kix)1(kix,/)(11)1()()1(iinijkjijijkjijikikiaxaxabxx 2022-4-20第6章 解线性方程组的迭代法47选取分裂矩阵选取分裂矩阵 为为

49、M),(1LDM 其中其中 为可选择的为可选择的松弛因子松弛因子. . 0解解 的逐次超松弛迭代法的逐次超松弛迭代法(Successive Over Relaxation） bAx ,2,1 ,0,)()1()0(kfxLxxkk ），（ 初初始始向向量量（3.1）其中其中 ),)1()(1UDLDL.)(1bLDf解解 的的SORSOR方法的分量计算公式方法的分量计算公式 bAx ,),()0()0(1)0(Tnxxx,/)(11)1()()1(iinijkjijijkjijikikiaxaxabxx （3.2）.为松弛因子 ), 1 , 0;, 1( kni)1(1)(1UDLDNMA 2

50、022-4-20第6章 解线性方程组的迭代法48或或 ,),()0()0(1)0(Tnxxx,)()1(ikikixxx ,/)(11)1(iinijkjijijkjijiiaxaxabx （3.3）为松弛因子.), 1 ,0;, 1(kni注注(1) (1) 当当 时，时，SOR方法即为高斯方法即为高斯- -塞德尔迭代法塞德尔迭代法. . 1 (2) (2) 每迭代一次主要运算量是计算一次矩阵与向量的乘法每迭代一次主要运算量是计算一次矩阵与向量的乘法. . (3) (3) ，称为超松弛法；，称为超松弛法； 时，称为低松弛法时，称为低松弛法. . 11 (4) 在计算机实现时用在计算机实现时用