1、第五章第五章解线性方程组的数值解法解线性方程组的数值解法引言引言 在自然科学和工程技术中在自然科学和工程技术中,很多问题很多问题归结为归结为解线性方程组解线性方程组.例如电学中的网络例如电学中的网络问题，船体数学放样中建立三次样条函问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、差分法或者有限元方法解常微分方程、偏微分方程边值问题等都导致求解线性偏微分方程边值问题等都导致求解线性方程组，而这些方程组，而这些方程组的系数矩阵大致方程组的系数矩
2、阵大致分为两种分为两种，一种是低阶稠密矩阵一种是低阶稠密矩阵(例如，例如，阶数不超过阶数不超过150). 另另一种是大型稀疏矩阵一种是大型稀疏矩阵(即矩阵阶数高且零元素较多即矩阵阶数高且零元素较多). 有的问题的数学模型中虽不直接表现为含线性有的问题的数学模型中虽不直接表现为含线性方程组方程组, ,但它的数值解法中将问题但它的数值解法中将问题“离散化离散化”或或“线性化线性化”为线性方程组为线性方程组. .因此因此线性方程组的求解是线性方程组的求解是数值分析课程中最基本的内容之一数值分析课程中最基本的内容之一. . 关于线性方程组的解法一般有两大类：关于线性方程组的解法一般有两大类： 但实际计
3、算中由于舍入误差的存在和影响，这但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解种方法也只能求得线性方程组的近似解. . 本章将阐本章将阐述这类算法中最基本的和具有代表性的算法就是高述这类算法中最基本的和具有代表性的算法就是高斯消元法斯消元法, ,以及它的某些变形和应用以及它的某些变形和应用. .这类方法是解这类方法是解低阶稠密矩阵方程组及某些大型稀疏矩阵方程组低阶稠密矩阵方程组及某些大型稀疏矩阵方程组( (例例如，大型带状方程组如，大型带状方程组) )的有效方法的有效方法. . 1. 直接法直接法 经过有限次的算术运算经过有限次的算术运算, ,可以求得方程组的精确可
4、以求得方程组的精确解解( (假定计算过程没有舍入误差假定计算过程没有舍入误差).).如线性代数课程中如线性代数课程中提到的克莱姆算法就是一种直接法提到的克莱姆算法就是一种直接法. .但该法对高阶方但该法对高阶方程组计算量太大程组计算量太大, ,不是一种实用的算法不是一种实用的算法. . 就是用某种极限过程去逐步逼近方程组精确解就是用某种极限过程去逐步逼近方程组精确解的方法的方法. 迭代法具有计算机的存储单元较少、程序设迭代法具有计算机的存储单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优计简单、原始系数矩阵在计算过程中始终不变等优点，但存在点，但存在收敛条件收敛条件和和收敛速度收敛
5、速度问题问题. .迭代法是解大迭代法是解大型稀疏矩阵方程组型稀疏矩阵方程组( (尤其是由微分方程离散后得到的尤其是由微分方程离散后得到的大型方程组大型方程组) )的重要方法的重要方法. . 2. 迭代法迭代法5.2 高斯消去法 本节介绍高斯消去法本节介绍高斯消去法( (逐次消去法逐次消去法) )及消去法及消去法和矩阵三角分解之间的关系和矩阵三角分解之间的关系. . 虽然高斯消去法是一虽然高斯消去法是一种古老的求解线性方程组的方法种古老的求解线性方程组的方法( (早在公元前早在公元前250250年年我国就掌握了解方程组的消去法我国就掌握了解方程组的消去法) )，但由它改进、，但由它改进、变形得到
6、的选主元素消去法、三角分解法仍然是目变形得到的选主元素消去法、三角分解法仍然是目前计算机上常用的有效方法前计算机上常用的有效方法. .我们在中学学过消去我们在中学学过消去法法, ,高斯消去法就是它的标准化的、适合在计算机高斯消去法就是它的标准化的、适合在计算机上自动计算的一种方法上自动计算的一种方法. .5.2.1 高斯消去法 设有线性方程组设有线性方程组)1 . 2(.,22112222212111212111 mnmnmmnnnnbxaxaxabxaxaxabxaxaxa或写成矩阵形式或写成矩阵形式.2121212222111211 mnmnmmnnbbbxxxaaaaaaaaa简记为简记
7、为Ax=b. nnnnnnnnbxubxuxubxuxuxu2222211212111,nnnnubx .,112111uxubxnjjj 如如: 上三角矩上三角矩阵阵所对应所对应的线性方的线性方程组程组,)1)(1()1(11 nnnnnnnuxubx解为解为 当当m=n时，对时，对三角形方程组三角形方程组的解非常容易，如的解非常容易，如 nnnnnnbylylylbylylbyl221122221211111,1111lby 下三角矩阵下三角矩阵所对所对应的线性方程组应的线性方程组,2212122lylby ,计算量（乘除法的主要部分）都为计算量（乘除法的主要部分）都为 n2/2.解为解为
8、nnnjjjnnlylby 111 因此，我们将一般的线性方程组化成等价的三因此，我们将一般的线性方程组化成等价的三角形方程组来求解角形方程组来求解. 首先举一个简单的例子来说明消去法的基本思想首先举一个简单的例子来说明消去法的基本思想. 例例1 用消去法解方程组用消去法解方程组 )4 . 2(. 122)3 . 2(, 54)2 . 2(, 632132321xxxxxxxx 解解 第第1步，将方程步，将方程(2.2)乘上乘上- -2加到方程加到方程(2.4)上上去，消去去，消去(2.4)中的未知数中的未知数x1，得到，得到)5 . 2(.11432 xx 第第2步，将方程步，将方程(2.3
9、) 加到方程加到方程(2.5)上去，消去上去，消去(2.5)中的未知数中的未知数x2，得到与原方程组等价的三角形，得到与原方程组等价的三角形方程组方程组 . 62)6 . 2(, 54, 6332321xxxxxx显然，方程组是显然，方程组是(2.6)是容易求解的，解为是容易求解的，解为.)3 , 2 , 1(Tx 上述过程相当于对方程的上述过程相当于对方程的增广阵做初等行变换增广阵做初等行变换 6200514061111114051406111112251406111)(bA132rr 23rr 其中其中ri用表示矩阵的第用表示矩阵的第i行行. 由此看出，用消去法解方程组的由此看出，用消去法
10、解方程组的基本思想基本思想是用是用逐次消去未知数的方法把原方程组逐次消去未知数的方法把原方程组Ax=b化为与其等化为与其等价的三角形方程组，而求解三角形方程组可用回代价的三角形方程组，而求解三角形方程组可用回代的方法求解的方法求解. 换句话说，上述过程就是用初等行变换句话说，上述过程就是用初等行变换将原方程组系数矩阵化为简单形式换将原方程组系数矩阵化为简单形式(上三角矩阵上三角矩阵)，从而求解原方程组从而求解原方程组(2.1)的问题转化为求解简单方程的问题转化为求解简单方程组的问题组的问题. 或者说，对系数矩阵或者说，对系数矩阵A施行一些行变换施行一些行变换(用一些简单矩阵左乘用一些简单矩阵左
11、乘A)将其约化为上三角矩阵将其约化为上三角矩阵. 这这就是就是高斯消去法高斯消去法. 下面讨论求解一般线性方程组的高斯消去法下面讨论求解一般线性方程组的高斯消去法.由由 mnmnmmnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 )1()1(2)1(21)1(1)1(2)1(22)1(221)1(21)1(1)1(12)1(121)1(11mnmnmmnnnnbxaxaxabxaxaxabxaxaxa .2121212222111211 mnmnmmnnbbbxxxaaaaaaaaa .)1()1(2)1(121)1()1(2)1(1)1(2)1(2
12、2)1(21)1(1)1(12)1(11 mnmnmmnnbbbxxxaaaaaaaaa 将将(2.1)记为记为A(1)x=b(1)，其中，其中 )1()1(2)1(1)1(2)1(22)1(21)1(1)1(12)1(11)1(mnmmnnaaaaaaaaaA )1()1(2)1(1)1(mbbbb.212222111211 mnmmnnaaaaaaaaa.21 mbbb (1) 第第1步步(k=1). .,)2()2(2)2(2)2(2)2(22)2(22)1(1)1(12)1(121)1(11mnmnmnnnnbxaxabxaxabxaxaxa 设设a11(1) 0，首先计算，首先计算乘
13、数乘数 mi1= ai1(1) /a11(1) (i=2,3,m).用用- -mi1乘乘(2.1)的第一个方程，加到第的第一个方程，加到第i个个(i=2,3, ,m)方程上，消去方程上，消去(2.1)的从第二个方程到第的从第二个方程到第m个方程中的个方程中的未知数未知数x1，得到与，得到与(2.1)等价的方程组等价的方程组.00)2()2(2)1(121)2()2(2)2(2)2(22)1(1)1(12)1(11 mnmnmnnbbbxxxaaaaaaa (2.7)简记为简记为 A(2)x=b(2)，其中其中A(2), b(2)的元素计算公式为的元素计算公式为 )., 2(), 2;, 2()
14、1(11)1()2()1(11)1()2(mibmbbnjmiamaaiiijiijij (2) 第第k次消元次消元(k=1,2,s, s=min(m- -1,n). 设上述第设上述第1步，步， ，第，第k- -1步消元过程计算已经步消元过程计算已经完成，即已计算好与完成，即已计算好与(2.1)等价的方程组，简记为等价的方程组，简记为A(k)x=b(k)，其中，其中)8 .2(.)()()2(2)1(121)()()2(2)1(1)()()2(2)2(22)1(1)1(12)1(11 kmkkmkkmnkknnnkmkkkkkkbbbbxxxxaaaaaaaaaaa 设设akk(k) 0，计算
15、，计算乘数乘数 mik= aik(k) /akk(k) (i=k+1, ,m).用用- -mik乘乘(2.8)的第的第k个方程加到第个方程加到第 i个个(i= k+1, , m)方方程上，消去从第程上，消去从第k+1个方程到第个方程到第m个方程中的未知数个方程中的未知数xk，得到与，得到与(2.1)等价的方程组等价的方程组A(k+1)x=b(k+1)，其中其中A(k+1), b(k+1)的元素计算公式为，的元素计算公式为， )9 . 2()., 1(), 1;, 1()()()1()()()1(mkibmbbnkjmkiamaakkikkikikkjikkijkij显然显然A(k+1)中从第中
16、从第1行到第行到第k行与行与A(k)相同相同. (3) 继续上述过程，且设继续上述过程，且设aii(i) 0 (i=1,2, ,s)，直，直到完成第到完成第s步消元计算步消元计算. 最后得到与原方程组等价的最后得到与原方程组等价的简单方程组简单方程组A(s+1)x=b(s+1) ，其中，其中A(s+1)为上阶梯为上阶梯. 特别当特别当m=n时，时，与原方程组等价的简单方程组为与原方程组等价的简单方程组为A(n)x=b(n)，即，即)10.2(.)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11 nnnnnnnnbbbxxxaaaaaa由由(2.1)约化为约化为(2.10
17、)的过程称为的过程称为消元过程消元过程. 如果如果A是非奇异矩阵，且是非奇异矩阵，且akk(k) 0 (k=1,2,n- -1)，求解三角形方程组求解三角形方程组(2.10)，得到求解公式，得到求解公式)11. 2 ().1 , 2, 1(/ )(,/)(1)()()()( nnkaxabxabxkkknkjjkkjkkknnnnnn(2.10)的求解过程的求解过程(2.11) 称为称为回代过程回代过程. 注意：设注意：设Ax=b，其中，其中ARnn为非奇异矩阵，如为非奇异矩阵，如果果a11(1)=0，由于，由于A为非奇异矩阵，所以为非奇异矩阵，所以A的第的第1列一定列一定有元素不等于零，例如
18、有元素不等于零，例如al1 0，于是可交换两行元素，于是可交换两行元素(即即r1rl)，将，将al1 调到调到(1,1)位置，然后进行消元计算，位置，然后进行消元计算，这时这时A(2)右下角矩阵为右下角矩阵为n- -1阶非奇异矩阵，继续这过阶非奇异矩阵，继续这过程，高斯消去法照样可进行计算程，高斯消去法照样可进行计算. 总结上述讨论即有总结上述讨论即有 定理定理5 设设Ax=b，其中，其中ARnn. (1) 如果如果akk(k) 0 (k=1,2,n)，则可通过高斯消去，则可通过高斯消去法将法将Ax=b约化为等价的三角形方程组约化为等价的三角形方程组(2.10)，且计算，且计算公式为公式为 (
19、a) 消元计算消元计算(k=1,2, ,n- -1) )., 1(), 1,(), 1(/)()()1()()()1()()(nkibmbbnkjiamaankiaamkkikkikikkjikkijkijkkkkikik (b) 回代计算回代计算 ).1 , 2 , 1(/ )(,/)(1)()()()(nkaxabxabxnnnnkjjkkjkkknnnnnn (2) 如果如果A为非奇异矩阵，则可通过高斯消去法为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换及交换两行的初等变换)将方程组将方程组Ax=b约化为等价的约化为等价的三角形方程组三角形方程组(2.10).例子例子 解方程组解
20、方程组 02115472321321321xxxxxxxxx解解：消元：消元 0121111547112回代得回代得, 3263 x 3235 . 2rr 620033307112 5 . 35 . 05 . 203330711231212124rrrr , 233332 xx. 127321 xxx5.3 高斯主元素消元法 由高斯消去法知道由高斯消去法知道, 在消元过程中可能有在消元过程中可能有akk(k)0的情况，这时消去法将无法进行；即使主元素的情况，这时消去法将无法进行；即使主元素akk(k) 0但很小时，用其作除数，会导致其它元素数量级的严但很小时，用其作除数，会导致其它元素数量级的
21、严重增长和舍入误差的扩散，最后也使得计算解不可靠重增长和舍入误差的扩散，最后也使得计算解不可靠. 高斯消去法也称高斯消去法也称主元素消去法主元素消去法 (条件条件det A 0) 即即当当akk(k)=0 时，高斯消元法时，高斯消元法无法进行无法进行；或；或 | akk(k) |1时，带来时，带来舍入误差的扩散舍入误差的扩散。（小主元）（小主元）5.3.1 列主元素消去法.212n12122211211 nnnnnnbbbaaaaaaaaaB 设方程组设方程组(2.1)的增广矩阵为的增广矩阵为 首先在首先在A的第的第1列中选取绝对值最大的元素作为列中选取绝对值最大的元素作为主元素，例如主元素，
22、例如, 0|max|1111 iniiaa1111maxiniaannnnniiniinbaaabaaabaaabaaa.21212112221111211交换1A EEA 消消元元法法消元法的应用消元法的应用1. 求行列式求行列式 高斯高斯消元法消元法( )( )1det()det()nniiiiAAa 2. 求逆矩阵求逆矩阵(用高斯用高斯-若当消去法若当消去法) 例子例子 分别用高斯分别用高斯消元法和列主元消元消元法和列主元消元法求矩阵的行列式法求矩阵的行列式. . 643. 5072. 12623. 4712. 3132108A 99998106 . 0104 . 00103 . 010
23、2 . 003210A解：解：高高斯斯消消元元法法92110rr 913102 rr232rr 大数大数“吃掉吃掉”了小数！了小数！ 000103 . 0102 . 0032109980det A列列主主元元消消元元法法 3210623. 4712. 31643. 5072. 128 103 . 0102 . 001018018. 0103176. 00643. 5072. 12 10186555. 0001018018. 0103176. 00643. 5072. 12 643. 5072. 12623. 4712. 313210831rr 84997.11det A5.3.2 高斯-若当消
24、去法 高斯高斯-若当消去法是高斯消去法的一种变形若当消去法是高斯消去法的一种变形. 高高斯消去法斯消去法是消去对角元素下方的元素是消去对角元素下方的元素. 如果同时消如果同时消去对角元素上方和下方的元素，而且将对角元素化去对角元素上方和下方的元素，而且将对角元素化为为1，这种方法就称为，这种方法就称为高斯高斯-若当若当(Gauss-Jordan)消去消去法法. 设高斯设高斯-若当消去法已完成若当消去法已完成k- -1步，于是步，于是Ax=b化化为等价方程组为等价方程组A(k)x=b(k)，其中增广阵，其中增广阵 .101001|121, 121, 121)()( nkknnknnknnnkkk
25、kkkkkkbbbbbaaaaaaaaaabA 在第在第k步计算时步计算时(k=1,2,n),考虑将第考虑将第k行上、下行上、下的第的第k列元素都进行消元计算化为零，且列元素都进行消元计算化为零，且akk化为化为1. 1. 按列选主元素，即确定按列选主元素，即确定ik使使.max,iknikkiaak 2. 换行换行(当当ikk时时)，交换第，交换第k行与第行与第ik行元素行元素jikjkaa,kikbb (j=k,k+1,n), 3. 计算乘数计算乘数 mik=- -aik/akk(i=1,2,n, ik) mkk=1/akk . (mik可保存在存放可保存在存放aik的单元中的单元中).
26、4. 消元计算消元计算 aijaij+mikakj(i=1,2,n,且且ik,j=k+1,n) bibi+mikbk (i=1,2,n,且且ik) 5.计算主行计算主行 akjakjmkk (j=k,k+1,n)， bkbkmkk .上述过程结束后，即当上述过程结束后，即当k=n时有时有显然显然xi=bi,i=1,2,n 就是就是 Ax=b的解的解. .111|21)()( nnnbbbbAbA 说明用高斯说明用高斯-若当消去法虽比高斯消去法略复杂若当消去法虽比高斯消去法略复杂些，但将些，但将A约化为单位矩阵，约化为单位矩阵，计算解就在常数项位计算解就在常数项位置得到置得到，因此用不着回代求解
27、，故也称为，因此用不着回代求解，故也称为无回代的无回代的高斯消元法高斯消元法. 它的计算量大约需要它的计算量大约需要n3/2次乘除法，要次乘除法，要比高斯消去法大，但用高斯比高斯消去法大，但用高斯-若当消去法若当消去法求一个矩阵求一个矩阵的逆矩阵的逆矩阵还是比较合适的还是比较合适的. 定理定理9(高斯高斯-若当法求逆矩阵若当法求逆矩阵) 设设A为非奇异矩阵，为非奇异矩阵，方程组方程组AX=In的增广矩阵为的增广矩阵为C=(A|In)，如果对，如果对C应用高应用高斯斯-若当方法化为若当方法化为(In|T) ，则，则A- -1=T. 事实上事实上, 求求A的逆矩阵的逆矩阵A- -1, 即求即求n阶
28、矩阵阶矩阵X使使AX=In, 其中其中In为单位矩阵，将为单位矩阵，将X按列分块按列分块X=(x1,x2,xn)， I=(e1,e2,en)，于是求解于是求解AX=In等价于求解等价于求解n个方程组个方程组Axj=ej (j=1,2,n).我们可用高斯我们可用高斯-若当方法求解若当方法求解AX=In. 例例4 用高斯用高斯-若当方法求下列矩阵的逆矩阵若当方法求下列矩阵的逆矩阵.121322011 A 解解 由分块矩阵由分块矩阵 10000101012101132210001000112132201121rrC 100100302011212121252323第一次消元第一次消元 0110002
29、0301121212123252332rr 416315314100010001100001001326131613131616532第三次消元第三次消元第二次消元第二次消元.4163153141 A所以得所以得小节小节 比较而言,Gauss顺序消去法条件苛刻,且数值不稳定; Gauss全主元消去法工作量偏大，需要比较 个元素及行列交换工作，算法复杂；对于Gauss-Jordan消去法形式上比其他消元法简单，且无回代求解，但计算量大,比Gauss顺序消去法多 计算量。因此从算法优化的角度考虑， Gauss列主元消去法比较好。nkk22)61(3nO5.4 矩阵的三角分解法矩阵的三角分解法 我们
30、知道对矩阵进行一次初等变换，就相当于用相应的初等矩阵去左乘原来的矩阵。因此我们这个观点来考察Gauss消元法用矩阵乘法来表示，即可得到求解线性方程组的另一种直接法：矩阵的三角分解。 5.4.1 Gauss消元法的矩阵形式为上三角阵为单位下三角阵，其中分解U1.111.).(1213231211112121111221LLUUllllllULLLLULLLLALUnnnnnnnn分解。行直接进否对矩阵因此，关键问题在于能程：就等价于解两个三角方由此解线性方程组LUAyUxbLyULAbxbx)(5.4.2 Doolittle分解分解11313131113111212121112111112323
31、22131211323121333231232221131211)3 , 2 , 1(11113,ualluaualluajauuakuuuuuulllaaaaaaaaanULjjjj得由；得由时：为例的各元素，以此分解在于如何算出)(322332133133333323321331332212313232233212313213212323231321231221222222122122ululauuululakuulalululaulauuulaulauuulak得时：由得由；得由；得时：Doolittle分解分解 若矩阵A有分解：A=LU，其中L为单位下三角阵，U为上三角阵，则称该分解为
32、Doolittle分解，可以证明，当A的各阶顺序主子式均不为零时，Doolittle分解可以实现并且唯一。 A的各阶顺序主子式均不为零，即),.2 , 1(0.1111nkaaaaAkkkkkDoolittle分解分解各元素方法逐行逐列求解用比较等式两边元素的令ULuuuuuulllaaaaaaaaannnnnnnnn,.1.11.222112112121n2n1n2222112111Doolittle分解分解。得再由；得由时：。得再由；得由时),.,4 , 3(),.,3 , 2(12),.,3 , 2(),.2 , 1(1:12212122222121212222121211111111
33、i1111niuulalululanjulauuulakniualluanjauuakiiiiiijijjjjjiiijjjjDoolittle分解分解(看看就可看看就可)1111211211,.1,000.10.,.,kttjktkjkjktkjtjktjjjjkkkkkjknkkkknkkjulauuuluuulllakjuuuk）（有步时：计算第Doolittle分解分解11111111,.1/)(000.0, 1 ,.,.,ktkktkitikikktkkiktkitkkkikiiknkkknkiuulalululuullakill）（得，于是由由于计算Doolittle分解分解nnn
34、nnnkkkttkitikikkttjktkjkjulluuluuunkuulalnkinkjulau.A,.,2 , 1/ )(),.,1;,.,(2122221112111111的各位各元素在计算机内存于即Doolittle分解分解。可获解得及再由TniinijjijiiijjijiixxxnniuxuyxniylbyULxyxby),.,(1,.1,/ )(,.,2 , 121111例题30191063619134652.D. 1321xxxoolittle分解求解方程组试用例例题。，；，令、分解解：32624652110100163619134652131112113121133232
35、2131211323121luluuukuuuuuulllALU例题LUAululaukuulalulauulauk473652143121434/ )(7)6(21935213223321331333322123132321321232312212222所以时：，时：例题TyyyyyyybLy)4 , 1,10(43034, 12019,1030191014312112321321即得）解（、解方程组例题。所以方程组的解为解得：解TxxxxxxxyUx) 1 , 2 , 3(3, 2, 14110473652)2(123321上机 P27 例题第六章 解线性方程组的迭代方法 6.1 引言引言
36、 6.2 基本迭代法基本迭代法 6.3 迭代法的收敛性迭代法的收敛性 例例1 求解方程组求解方程组)2 . 1(.361236,33114,20238321321321 xxxxxxxxx记为记为Ax=b，其中，其中.363330,12361114238321 bxxxxA方程组的精确解是方程组的精确解是x*=(3,2,1)T. 现将改写为现将改写为)3 . 1().3636(121),334(111),2023(81213312321 xxxxxxxxx或写为或写为x=B0 x+f，其中，其中.,0001236113382012312611111482830 fB 我们任取初始值，例如取我们
37、任取初始值，例如取x(0)=(0, 0, 0)T. 将这些值将这些值代入代入(1.3)式右边式右边(若若(1.3)式为等式即求得方程组的解，式为等式即求得方程组的解，但一般不满足但一般不满足)，得到新的值，得到新的值x(1)=(x1(1), x2(1), x3(1)T=(3.5, 3, 3)T ，再将，再将x(1)分量代入分量代入(1.3)式右边得到式右边得到 x(2)，反复利用这个计算程序，得到一向量序列和一般的计反复利用这个计算程序，得到一向量序列和一般的计算公式算公式(迭代公式迭代公式),)(3)(2)(1)()1(3)1(2)1(1)1()0(3)0(2)0(1)0( kkkkxxxx
38、xxxxxxxx)4 . 1(.12/ )3636(,11/ )334(, 8/ )2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1 kkkkkkkkkxxxxxxxxx简写为简写为 x(k+1)=B0 x(k) +f，其中其中k表示迭代次数表示迭代次数(k=0,1,2,). 迭代到第迭代到第10次有次有;)999813. 0,999838. 1,000032. 3()10(Tx ).(000187. 0)10()10()10( xx 从此例看出，由迭代法产生的向量序列从此例看出，由迭代法产生的向量序列x(k)逐步逐步逼近方程组的精确解是逼近方程组的精确解是x*=(3,2
39、,1)T. 即有即有 对于任何一个方程组对于任何一个方程组x=Bx+f(由由Ax=b变形得到的变形得到的等价方程组等价方程组)，由迭代法产生的向量序列，由迭代法产生的向量序列x(k)是否一定是否一定逐步逼近方程组的解逐步逼近方程组的解x*呢？回答呢？回答是不一定是不一定. 请同学们请同学们考虑用迭代法解下述方程组考虑用迭代法解下述方程组 . 53, 521221xxxxx(k)x* xxkk)(lim6.2 基本迭代法其中，其中，A=(aij)Rnn为非奇异矩阵，下面研究任何建为非奇异矩阵，下面研究任何建立立Ax=b的各种迭代法的各种迭代法. 设线性方程组设线性方程组 Ax=b， (2.1)
40、其中，其中，M为可选择的非奇异矩阵，且使为可选择的非奇异矩阵，且使Mx=d容易求容易求解，一般选择解，一般选择A的某种近似，称的某种近似，称M为为分裂矩阵分裂矩阵. 将将A分裂为分裂为 A=M- -N. (2.2) 于是，求解于是，求解Ax=b转化为求解转化为求解Mx=Nx+b ，即求解，即求解.11bMNxMxbAx 求解求解可构造一阶定常迭代法可构造一阶定常迭代法)3 . 2(), 1 , 0()()()1()0( kfBxxxkk，初始向量初始向量其中其中 B=M- -1N=M- -1(M- -A)=I- -M- -1A ， f=M- -1b. 称称 B=I- -M- -1A为迭代法的为
41、迭代法的迭代矩阵迭代矩阵，选取，选取M矩阵，就得矩阵，就得到解到解Ax=b的各种迭代法的各种迭代法. 设设aii 0 (i=1,2,n)，并将，并将A写成三部分写成三部分.00000000, 121,211, 1121,212, 11 , 1212211ULDaaaaaaaaaaaaaaaAnnnnnnnnnnnnnn 111212122212nnnnnnaaaaaaAaaa 1122nnaaDa 2112000nnaLaa1212000nnaaaU即即A=D- -L- -U6.2.1 雅可比(Jacobi)迭代法 设设aii 0 (i=1,2,n)，选取，选取M为为A的对角元素部分的对角元素
42、部分,即选取即选取M=D(对角阵对角阵)，A=D- -N，由，由(2.3)式得到解方式得到解方程组程组Ax=b的的雅可比雅可比(Jacobi)迭代法迭代法. 又称又称简单迭代法简单迭代法.其中其中B=I- -D- -1A=D- -1(L+U)=J, f=D- -1b. 称称J为解为解Ax=b的的雅可比迭代法的迭代矩阵雅可比迭代法的迭代矩阵.)5 . 2(), 1 , 0()()()1()0( kfBxxxkk，初始向量初始向量于是雅可比迭代法可写为于是雅可比迭代法可写为矩阵形式矩阵形式bDxULDxkk1)(1)1()( 其其Jacobi迭代矩阵迭代矩阵为为 )(1ULDBJ 00021222
43、22211111112nnnnnnnnaaaaaaaaaaaa等等价价方方程程组组其中其中 aii(i) 0 (i=1,2,n)11221111221122221122111nnnnnnnnnnxa xa xbaxa xa xbaxa xa xba 即由方程组即由方程组Ax=b得到的得到的建立的雅可比迭代格式为建立的雅可比迭代格式为 )(1)(1)(1)(11)(11) 1(2)(2)(323)(12122) 1(21)(1)(313)(21211) 1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax于是，解于是，解Ax=b的雅可比迭代法的计
44、算公式为的雅可比迭代法的计算公式为)6 . 2()., 1 , 0(), 2 , 1(,/ )(,),(1)()1()0()0(1)0( 表示迭代次数表示迭代次数kniaxabxxxxiinijjkjijikiTn 由由(2.6)式可知，雅可比迭代法计算公式简单，式可知，雅可比迭代法计算公式简单，每迭代一次只需计算一次矩阵和向量的乘法且计算每迭代一次只需计算一次矩阵和向量的乘法且计算过程中原始矩阵过程中原始矩阵A始终不变始终不变. 6.2.2 高斯赛德尔迭代法在在 Jacobi 迭代中，计算迭代中，计算 xi(k+1)(2 i n)时时，使用使用xj(k+1)代替代替xj(k) (1 j i-
45、 -1)，即有即有 )(1)(1)(1) 1(11) 1(11) 1(2)(2)(323) 1(12122) 1(21)(1)(313)(21211) 1(1nknnnknnnknknnkkkknnkkkbxaxaaxbxaxaxaaxbxaxaxaax建建立立迭迭代代格格式式或缩写为或缩写为称为称为高斯高斯塞德尔塞德尔(Gauss Seidel)迭代法迭代法.)., 2 , 1()(11)(11)1()1(nibxaxaaxinijkjijijkjijiiki )7 . 2(), 1 , 0()()()1()0( kfBxxxkk，初始向量初始向量解解Ax=b的的高斯高斯塞德尔迭代法的计算公
46、式为塞德尔迭代法的计算公式为)8 . 2()., 1 , 0(), 2 , 1(,/ )(),(),(1)(11)1()1()0()0(1)0( 表示迭代次数表示迭代次数初始向量初始向量kniaxaxabxxxxiinijkjijijkjijikiTn或或)9 . 2()., 1 , 0(), 2 , 1(,/ )(,),()(11)1()()1()0()0(1)0( kniaxaxabxxxxxxxiinijkjijijkjijiiikikiTn 雅可比迭代法雅可比迭代法不使用变量的最新信息计算不使用变量的最新信息计算xi(k+1)，而由而由高斯高斯塞德尔迭代公式塞德尔迭代公式(2.8)可知
47、，计算可知，计算x(k+1)的的第第 i个分量个分量xi(k+1)时，利用了已经计算出的最新分量时，利用了已经计算出的最新分量xj(k+1) (j=1,2,i- -1). 可看作可看作雅可比迭代法雅可比迭代法的一种改的一种改进进. 由由(2.8)可知，可知，高斯高斯塞德尔迭代公式塞德尔迭代公式每迭代一次每迭代一次只需计算一次矩阵与向量的乘法只需计算一次矩阵与向量的乘法. 例例2 用用高斯高斯塞德尔迭代法塞德尔迭代法解例解例1的方程组的方程组(1.2).)., 2 , 1 , 0(.12/ )3636(,11/ )433(, 8/ )2320()1(2)1(1)1(3)(3)1(1)1(2)(3
48、)(2)1(1 kxxxxxxxxxkkkkkkkkk 解解 用用高斯高斯塞德尔迭代公式：塞德尔迭代公式：取取x(0)=(0, 0, 0)T.迭代到第迭代到第7次有次有;)9999930. 0,9999987. 1,000002. 3()7(Tx .1002. 24)7()7( xx 由此例可知，用由此例可知，用高斯高斯塞德尔迭代法塞德尔迭代法，雅可比雅可比迭代法迭代法解线性方程组解线性方程组(1.2)(且取且取x(0)=0)均收敛，而均收敛，而高高斯斯塞德尔迭代法塞德尔迭代法比比雅可比迭代法雅可比迭代法收敛较快收敛较快(即取相即取相同的同的x(0)，达到同样精度所需迭代次数较少，达到同样精度
49、所需迭代次数较少)，但这结，但这结论只当论只当A满足一定条件时才是对的满足一定条件时才是对的. 例例1 用雅可比迭代法解方程组用雅可比迭代法解方程组 2 . 453 . 82102 . 7210321321321xxxxxxxxx )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx.3 . 12 . 11 . 1 x解解确确精精 解：解： Jacobi 迭代格式为迭代格式为kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15111.0999931.199
50、9931.299991121.0999981.1999981.299997 )2 . 4(51)3 . 82(101)2 . 72(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx取取 x(0)=(0,0,0)T 计算计算结果结果如下：如下： 解：解：Gauss-Seidel 迭代格式为迭代格式为 )2 . 4(51)3 . 82(101)2 . 72(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx 例例2 用用GaussSeidel 迭代法解上题迭代法解上题. 2 . 453
