《研究生翻译第2讲》由会员分享，可在线阅读，更多相关《研究生翻译第2讲（97页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章 线性代数方程组的解法线性代数方程组的解法2.1 2.1 解线性方程组的直接法解线性方程组的直接法2.2 2.2 解线性方程组的迭代法解线性方程组的迭代法2.0 2.0 概述概述2.2 2.2 迭代法迭代法的收敛性的收敛性一、研究数值解法的必要性一、研究数值解法的必要性求：求：的解的解 的值，根据克莱姆的值，根据克莱姆( (GramerGramer) )法则可法则可表示为两个行列式之比：表示为两个行列式之比：2.0 2.0 概述概述如：如： , ,若用每秒完成万亿次（若用每秒完成万亿次（10101212）浮点乘法运算的计算机（几年前国内运算速度最快），浮点乘法运算的计算机（几年前国
2、内运算速度最快），按每天工作按每天工作24小时小时, ,完成这些计算约需完成这些计算约需3030年。若使用一年。若使用一般的个人电脑，每秒不外完成十亿次（般的个人电脑，每秒不外完成十亿次（10109 9）浮点乘法）浮点乘法运算，则完成这些计算约需运算，则完成这些计算约需3 3万年。万年。( (天河千万亿次天河千万亿次) ) 计算一个计算一个 阶行列式需要做阶行列式需要做 个乘法，求个乘法，求解上述方程共做解上述方程共做 次乘除法。次乘除法。二、线性代数方程组的常用解法二、线性代数方程组的常用解法1 1、直接法、直接法： 只包含有限次四则运算。若在计算过程中只包含有限次四则运算。若在计算过程中都
3、不发生舍入误差的假定下，计算结果就是原都不发生舍入误差的假定下，计算结果就是原方程组的精确解。方程组的精确解。2 2、迭代法：、迭代法： 把方程组的解向量看作是某种极限过程的把方程组的解向量看作是某种极限过程的极限，而且实现这一极限过程每一步的结果是极限，而且实现这一极限过程每一步的结果是把前一步所得的结果施行相同的演算步骤得到把前一步所得的结果施行相同的演算步骤得到的。的。Remark：由于运算过程中舍入误差的存在，实际由于运算过程中舍入误差的存在，实际上直接方法得到的解也是方程组的近始解。上直接方法得到的解也是方程组的近始解。2.12.1解线性方程组的直接法解线性方程组的直接法设有线性方程
4、组设有线性方程组为非奇异矩阵为非奇异矩阵。或写为矩阵形式或写为矩阵形式 ，其中，其中一、一、GaussGauss消去法消去法具体过程：具体过程：其中将 改为Step1Step1： 若若 令令 , ,用用 乘乘 第一个方程加到第第一个方程加到第 个方程个方程 ，并保留第，并保留第一一式，则得式，则得其中其中记为记为 若若 令令 ，乘第二个方程加到第乘第二个方程加到第i个方程个方程 ，则得，则得用Step2:Step2:记为记为其中其中设为设为第第k k-1-1步消元完成后，有步消元完成后，有Stepk： 若 ,令 , （i=k+1,k+2,)用用- - 来来乘乘以以第第k-1步步所所得得方方程程
5、中中的的第第k k个个方方程程，加加到到第第i i 个方程，并保留第个方程，并保留第k k个方程，则得：个方程，则得：（i=k+1,k+2,n）按上述做法，做完按上述做法，做完n-1n-1步步消元消元，原方程可化为同解的上原方程可化为同解的上三角方程组：三角方程组：其中其中(i,j=k+1,(i,j=k+1,n),n)（i=k+1,ni=k+1,n）上面的方程记为上面的方程记为记为记为最后，若最后，若 ，逐步回代可得到原方程组的解：，逐步回代可得到原方程组的解：（i=n-1,n-2,2，1） 上面的求解过程称为上面的求解过程称为GaussGauss顺序消去法。它通过一顺序消去法。它通过一系列消
6、元过程与最后的一步回代过程来得到方程组的系列消元过程与最后的一步回代过程来得到方程组的解。解。Remark1Remark1：在：在GaussGauss顺序消去法的消去过程中，可以将顺序消去法的消去过程中，可以将右端列向量视为方程组右端列向量视为方程组A A的第的第n n1 1列，直接对矩阵列，直接对矩阵A A（指现在的指现在的n n行，行，n n1 1列的增广矩阵）进行行初等变列的增广矩阵）进行行初等变换，将其变换为上三角形矩阵，从而回代求解得到方换，将其变换为上三角形矩阵，从而回代求解得到方程组的解。程组的解。Remark2Remark2：可以统计出，如果可以统计出，如果A A为为n n阶方
7、阵，则阶方阵，则GaussGauss顺顺序消去法消去过程所需的乘除运算次数为序消去法消去过程所需的乘除运算次数为回代过程所需的乘除运算次数为回代过程所需的乘除运算次数为故总的乘除运算次数为故总的乘除运算次数为 取取n n2020，则，则N N30603060，与，与GramerGramer法则相比，是天壤法则相比，是天壤之别。之别。Remark3Remark3：在消去过程中，也可以采用在消去过程中，也可以采用Gauss-JordanGauss-Jordan消消去法，将方程组化为对角形方程组，进而化为单位阵，去法，将方程组化为对角形方程组，进而化为单位阵，则右端列向量就化为方程组的解向量。该方法
8、不需回则右端列向量就化为方程组的解向量。该方法不需回代过程，但总的计算量为代过程，但总的计算量为n n3 3/2+n/2+n2 2-n/2-n/2，比，比GaussGauss顺序消顺序消去法有所增加。去法有所增加。Remark4Remark4：在消去过程中，消去过程能够进行的前在消去过程中，消去过程能够进行的前提条件是提条件是 。当。当detAdetA= = 时时方程组存在唯方程组存在唯一解，但未必能满足一解，但未必能满足 的条件。要使的条件。要使GaussGauss顺顺序消去法能够求得方程组的解，应满足如下的定序消去法能够求得方程组的解，应满足如下的定理：理： 定理定理：用高斯顺序消去法能够
9、求解方程组：用高斯顺序消去法能够求解方程组 的解的充要条件为的解的充要条件为A A的各阶顺序主子式均不为零。的各阶顺序主子式均不为零。算法见教材第27页：（1）消元过程.对k=1,2，n-1进行如下运算：对i=k+1.k+2,n;对j=k+1,n+1,(2)回代过程.按下述公式 此此时时高高斯斯顺顺序序消消去去法法能能进进行下去，但不能求出唯一解。行下去，但不能求出唯一解。当 detA=0,说明：说明：当当 高斯顺序消去法能进行下去，但当高斯顺序消去法能进行下去，但当 或相对于或相对于（k=1, ,2,，n) )均不为零时均不为零时 （i=k+1,k+2，n）比较小时，计算时产生的比较小时，计
10、算时产生的舍入误差将导致计算结果误差增大。舍入误差将导致计算结果误差增大。由于舍入误差的原因，由于舍入误差的原因，Gauss顺序消去法不是顺序消去法不是一个实用的方法，实用中应该采用选主元的一个实用的方法，实用中应该采用选主元的Gauss消去法。消去法。 在在计计算算过过程程中中舍舍入入误误差差增增大大迅迅速速，造造成成计计算算解解与与真真解解相相差差甚甚远远，这这一一方方法法就就是是不不稳稳定定的的方方法法，反反之之，在在计计算算过过程程中中的的舍舍入入误误差差增增大大能能得得到到控控制制，该该方方法法就就是是稳稳定定的的。小小主主元元是是不不稳稳定定的的根根源源，这这就就需需要要采采用用“
11、选选主主元元素素”技技术术，即即选选取取绝绝对对值值最最大大的的元元素素作作为为主主元。元。二、主元素消去法二、主元素消去法B= 1)1)列主元消去法列主元消去法一种常用的方法是列主元消去法。设增广矩阵为一种常用的方法是列主元消去法。设增广矩阵为在第一列中选取绝对值最大的元素在第一列中选取绝对值最大的元素, ,如若如若 = = 调换第一行与第调换第一行与第i i行，这时的行，这时的 就是原来的就是原来的 , ,再进再进行消去法的第一步，即行消去法的第一步，即再考虑再考虑 右下角矩阵，选取绝对值最大的元素作为右下角矩阵，选取绝对值最大的元素作为主元素主元素, ,经过行的对换把主元素移到经过行的对
12、换把主元素移到 ， 再按消元公式计算再按消元公式计算 （i,j=3,ni,j=3,n）。）。直直至至将将方方程程组组化化成成上上三三角角方方程程组组，再再进进行行回回代代就就可可求得解。求得解。然然后后每每一一步步类类似似的的都都在在右右下下角角方方阵阵中中的的第第一一列列中中选选主主元元，再再经经行行对对调调, , 将将主主元元素素换换到到右右下下脚脚方方阵阵中中左左上角的位置。再按下一步计算上角的位置。再按下一步计算（i,j=kn)算法见教材第27页：（1）消元过程.对k=1,2，n-1进行如下运算：选主元：找行号ikk,n使若为零，终止.交换A(k),b(k)中的第k,ik两行;对i=k
13、+1.k+2,n;令对j=k+1,n+1,(2)回代过程.按下述公式2)2)全主元消去法全主元消去法B= 列列在在A A中选取绝对值最大的元素作为主元素，如中选取绝对值最大的元素作为主元素，如 ,然后交换然后交换B B 的第一行与第的第一行与第 行，第一行，第一列，这时的列，这时的 就是元素的就是元素的 元法的第一步，即元法的第一步，即与第与第 ，然后进行消然后进行消都 换把主元素移到再按消元公式计算 （i,j=3,n）,然后每一步对再考虑 右下角矩阵，选取绝对值最大的元素作为主元素,经过行的对换和列的对 在右下角方阵中进行完全选主元，经过行的位置, 类似的调列对调将主元换到右下角方阵中左上角
14、的位置，再按下一步计算 （i,j=kn）直至将方程组化成上三角方程组，再进行回代就可得解。RemarkReamrk1Reamrk1：全主元消去法每一步所选取的主元的绝全主元消去法每一步所选取的主元的绝对值不低于列主元消去法的同一步所选主元的绝对值不低于列主元消去法的同一步所选主元的绝对值，因而计算结果更加可靠。对值，因而计算结果更加可靠。Reamrk2Reamrk2：全主元消去法每一步选主元要花费更多的全主元消去法每一步选主元要花费更多的机时，并且对增广矩阵做了列交换，从而未知量的机时，并且对增广矩阵做了列交换，从而未知量的次序发生了变化，对编程带来了困难。而列主元消次序发生了变化，对编程带来
15、了困难。而列主元消去法的计算结果已比较可靠，故实用中常用列主元去法的计算结果已比较可靠，故实用中常用列主元消去法。消去法。Reamrk3Reamrk3：选主元的消去法与选主元的消去法与GaussGauss顺序消去法的顺序消去法的乘除法的计算量是一样的，均为乘除法的计算量是一样的，均为n n3 3/3+n/3+n2 2-n/3-n/3。三、选主元素消去法的应用三、选主元素消去法的应用1.1.求解方程组系求解方程组系设设系数矩阵系数矩阵A A可逆，求解方程组系可逆，求解方程组系AXAXb bi i(i=1,2,(i=1,2,m m) )。将将方程组系的系数矩阵与右端向量写成增广矩阵方程组系的系数矩
16、阵与右端向量写成增广矩阵 A|bA|b1 1,b,b2 2,b bm m 按列选主元素后再用按列选主元素后再用Gauss-JordanGauss-Jordan消去法将左边的消去法将左边的矩阵矩阵A A化为单位矩阵，则得到化为单位矩阵，则得到右端的列向量就是方程组系的解向量。右端的列向量就是方程组系的解向量。2.2.求逆矩阵求逆矩阵在在1 1中令中令m mn n，且右端列向量组成单位阵，则当且右端列向量组成单位阵，则当A A化为单位阵时，右端矩阵即为化为单位阵时，右端矩阵即为A A的逆矩阵。这的逆矩阵。这是实用中求逆矩阵的可靠方法。是实用中求逆矩阵的可靠方法。3.3.求行列式求行列式若要求矩阵若
17、要求矩阵A A的行列式，可用主元素消去法将其化的行列式，可用主元素消去法将其化为上三角阵，对角元素设为为上三角阵，对角元素设为b b1111，b b2222，b bnnnn，于于是是A A的行列式为：的行列式为：det(det(A A)=(-1)=(-1)m m b b1111b b2222b bnnnn 其中其中m m为行列交换的次数。这是实用中求行为行列交换的次数。这是实用中求行列式的可靠方法。列式的可靠方法。四、四、矩阵三角分解法矩阵三角分解法1 1.Gauss.Gauss顺序消去法的矩阵形式顺序消去法的矩阵形式设方程组设方程组A A = = 中中A A的各阶顺序主子式均不为零，令的各阶
18、顺序主子式均不为零，令则则n-1n-1步消元过程为步消元过程为将上述将上述n-1n-1步消元过程合并，得，步消元过程合并，得，即 （1） 由 得：容易验证：每个 可逆，且 k=1,2,，n-1 令L= 则L= 又令 U= ,且 U= 则A=LU， 其中，其中，L为单位下三角矩阵，它的对角元素皆为为单位下三角矩阵，它的对角元素皆为1 1。( (三角分解与高斯消去法的关系三角分解与高斯消去法的关系) )即U为阵， 由（1）式，上三角矩 Gauss消消去去法法的的实实质质就就是是用用一一连连串串的的初初等等变变换换把把系系数数方方阵阵A化化成成上上三三角角方方阵阵U，同同时时把把右右端端向向量化量化
19、 为为 , 若矩阵若矩阵A=LU，则，则LU叫做矩阵叫做矩阵A的的LU分解分解 .AX=b即为即为LUX=b令令Y=UX，方程变为，方程变为LY=b.可先解可先解LY=b，求出，求出Y，再解，再解UX=Y即可即可2 2 . .矩阵的三角分解及条件矩阵的三角分解及条件 定定义义1.1.设设A A为为n n阶阶矩矩阵阵（n n 2 2）, ,称称A=LUA=LU为为矩矩阵阵的的三三角分解，其中角分解，其中L L是下三角矩阵，是下三角矩阵，U U是上三角矩阵。是上三角矩阵。 RemarkRemark：三角分解不唯一，可以有不同的形式三角分解不唯一，可以有不同的形式 。为。为确保唯一性，引入以下定义。
20、确保唯一性，引入以下定义。定义2.如如果果L L是是单单位位下下三三角角矩矩阵阵，U U是是上上三三角角矩矩阵阵，则则称称三三角角分分解解A=LUA=LU为为DoolittleDoolittle分分解解；如如果果L L是是下下三三角角矩矩阵阵，U U是是单单位位上上三三角角矩矩阵阵，则则称称A=LUA=LU为为CroutCrout分分解解。前前面面高高斯斯顺顺序序消消去去法法对对应应了了A=LUA=LU的的DoolittleDoolittle分解。（分解。（P32P32定义定义1 1） 定定 理理 1 1： 设设 A A为为 n n阶阶 可可 逆逆 矩矩 阵阵 ， 则则 A A有有 唯唯 一一
21、DoolittleDoolittle(or(or CroutCrout) )分分解解的的充充要要条条件件为为：A A的的前前n-n-1 1阶顺序主子式不为零。阶顺序主子式不为零。RemarkRemark：实际中对实际中对A A进行三角分解，不是利用初等变进行三角分解，不是利用初等变换矩阵，而是直接使用矩阵乘法得到。（若不加说明，换矩阵，而是直接使用矩阵乘法得到。（若不加说明，后面我们讲到的三角分解一律指后面我们讲到的三角分解一律指DoolittleDoolittle型分解。）型分解。）的求解过程为:可推导求可推导求解解单位下三角形方程组单位下三角形方程组 的递归公式为的递归公式为 : 求求解解
22、上三角形方程组上三角形方程组 的递归公式为：的递归公式为：3.直接三角分解法 设A=LU即Step1Step1： 比较第一行元素：比较第一行元素：比较第一列元素：比较第一列元素：解出解出Step2Step2： 比较第二行元素比较第二行元素： 算出：算出：比较第二列的元素：比较第二列的元素：得出得出：一般地，设一般地，设U U的前的前k k-1-1行以及行以及L L的前的前k-1k-1列已求出，则列已求出，则比较第比较第k k行元素行元素StepkStepk： 可以算出可以算出：比较第比较第k k列元素列元素(ik (ik 即行指标即行指标 列指标，为算列指标，为算 ,ik) 算出算出: :这组
23、公式可用下图记忆（紧凑格式）这组公式可用下图记忆（紧凑格式）: :P33的求解过程为:可推导求可推导求解解单位下三角形方程组单位下三角形方程组 的递归公式为的递归公式为 : :求求解解上三角形方程组上三角形方程组 的递归公式为的递归公式为: : (P34):对比计算对比计算 和和 公式，公式，发现计算发现计算 的规律与计算的规律与计算 的规律类似的规律类似, ,因此计因此计算算 的求方程组的过程可用三角分解的紧凑格的求方程组的过程可用三角分解的紧凑格式取代。事实上式取代。事实上, ,这只要把这只要把 做为做为A A的第的第n n1 1列列进行直接三角分解即可。进行直接三角分解即可。Reamrk
24、Reamrk：上述直接三角分解法所对应的是上述直接三角分解法所对应的是GaussGauss顺序顺序消去法，二者的乘除运算次数是相当的。实际中对消去法，二者的乘除运算次数是相当的。实际中对阶数较高的线性方程组，应采用选主元的三角分解阶数较高的线性方程组，应采用选主元的三角分解法求解，以保证计算结果的可靠性。法求解，以保证计算结果的可靠性。例求解F三角分解法的运算量与高斯消去法大体相当，但对于系数矩阵A不变而常数列b变化的的一类方程组来说，节省运算量F因为A=LU不用再分解，对于不同的bF直接解LY=b和UX=Y即可列主元三角分解法主要思想4.4.平方根法（平方根法（CholeskyCholesk
25、y分解）分解） 设设A为为n阶阶 对称正定矩阵，对称正定矩阵，L是非奇异下是非奇异下三角矩阵，称三角矩阵，称 为矩阵为矩阵A的的Cholesky分解。分解。n阶 对称正定矩阵A，一定存在如下的分解式 ，其中L为单位下三角阵，D是对角元全为正的对角阵，且这种分解式唯一; ，其中L为下三角阵，当限定L的对角元为正时， （Cholesky分解）的分解式唯一。定义：定义： 定理： 平方根法平方根法的计算的计算公式公式（为简单起见设（为简单起见设 ，L L为下三角矩阵）为下三角矩阵） 令令 我我们们可可以以通通过过矩矩阵阵乘乘法法比比较较来来求求L L的的下下三三角角部部分分元素。具体计算公式如下元素。
26、具体计算公式如下: :P28Remark1:Remark1:由于在上式分解过程中有由于在上式分解过程中有n n次次开方运算，开方运算，故故C Choledskyholedsky分解法分解法也称为也称为平方根法平方根法。 Remark3:可以证明，若用可以证明，若用Gauss顺序消去法求解对称正顺序消去法求解对称正定的方程组定的方程组Axb，则有则有Remark2: 因为 ，这说明放大受到控制，故用平方根法解对称正定的方程组放大受到控制，故用平方根法解对称正定的方程组时，不必考虑选主元的问题，算法本身数值稳定。时，不必考虑选主元的问题，算法本身数值稳定。的平方不会超过A的最大对角元，因而舍入误差
27、的其中是第是第k步步Gauss顺序消去过程所得元素。这说明顺序消去过程所得元素。这说明用用Gauss顺序消去法求解对称正定方程组也不用选主元。顺序消去法求解对称正定方程组也不用选主元。Remark4:Remark4:从运算量的角度看，平方根法是有利的。从运算量的角度看，平方根法是有利的。可以统计出，用平方根法求解可以统计出，用平方根法求解AxAxb b所需乘除法的所需乘除法的运算次数为：运算次数为：令有令有n n次开方运算。次开方运算。 n n次开方运算一般使用迭代法，次开方运算一般使用迭代法，所需乘除法的运算次数大约为所需乘除法的运算次数大约为n n的常数倍。故平方根的常数倍。故平方根法总的
28、乘除法运算次数大约为法总的乘除法运算次数大约为Remark5Remark5：为避免开方运算，也可对为避免开方运算，也可对A A做做 分解。分解。( (其中其中L L为单位下三角阵为单位下三角阵,D,D为对角阵为对角阵) )平方根法举例平方根法举例求解求解解解F先解4.4.改进的平方根法改进的平方根法 n阶对称矩阵A，一定存在如下的分解式A=LDLT，其中L为单位下三角阵，D是对角元全为正的对角阵，且这种分解式唯一改进的平方根法改进的平方根法的计算的计算公式公式 与P41不同对k=2,3,n,分别计算改进的平方根法举例改进的平方根法举例求解求解解解F先解五、解三对角方程组的追赶法五、解三对角方程
29、组的追赶法1.1.矩阵对角占优的概念矩阵对角占优的概念设设 类似地，也有类似地，也有按列对角占优按列对角占优和和按列严格对角占优按列严格对角占优的的概念。概念。若对于若对于 ，均有，均有 , ,则对称矩阵则对称矩阵A按行严格按行严格对角对角占优占优。 若对于若对于 ，不等式，不等式 均成立，且至少均成立，且至少对某个有，则称矩阵A按行对角占优。2.2.追赶法解三对角方程组追赶法解三对角方程组设设并满足严格对角占优条件并满足严格对角占优条件当当A A严格对角占优时，可以证明各阶顺序主子式非零。严格对角占优时，可以证明各阶顺序主子式非零。 当当A A为上述三对角阵时，为上述三对角阵时，A A有更特
30、殊的三角分解形式有更特殊的三角分解形式A=L UA=L U 即：即：事实上，比较第事实上，比较第i行的第行的第i1列，立刻可得列，立刻可得U的次上三的次上三角线元素为角线元素为 ，由矩阵相乘可得，由矩阵相乘可得 ，一般地比较，一般地比较第第i行第行第i1列列 , 比较第i行第i列即即等价于令即由 得由由 得得Remark：只要三对角矩阵按行严格对角占优，则追只要三对角矩阵按行严格对角占优，则追赶法定能进行下去，且计算过程是稳定的（不必选赶法定能进行下去，且计算过程是稳定的（不必选主元素），其乘除法运算次数为主元素），其乘除法运算次数为5n5n4 4。上述方法称上述方法称为解三对角方程组的为解三
31、对角方程组的追赶法追赶法，又称为，又称为ThomasThomas方法。方法。追赶法举例追赶法举例求解求解解解2.2 解线性方程组的迭代法解线性方程组的迭代法为非奇异矩阵为非奇异矩阵。线性方程组的矩阵形式线性方程组的矩阵形式AX=b,AX=b,若能等价的写成若能等价的写成X=X=MX+dMX+d, ,其中其中 例如，AX=B两边都加X得FX+AX=X+b即X=X-AX+b=IX-AX+bF合并右边前两项得X=(I-A)X+bF这里与原方程等价与原方程等价则当则当X(0)=X(1)时时, X(1)就是原方程的解就是原方程的解. 若若X(0)X(1)，但当二者差别非常小时，例但当二者差别非常小时，例
32、如当如当可认为可认为X(0)X(1)可将可将X(1)作为近似解作为近似解.否则否则若若X(0)满足满足X(0)=MX(0)+d,则则X(0)就就是原方程是原方程X=MX+d的解的解.若记若记则当则当X(2)=X(1)时, X(2)就是原方程的解.若X(2)X(1)，但当二者差别非常小时，例如当可认为X(2)X(1)可将X(2)作为近似.否则则则X X* *正是方程组正是方程组X=X=MX+dMX+d的精确解的精确解称称X X(k+1)(k+1)= =MXMX(k)(k)+d+d为迭代公式，为迭代公式， 称称M M为迭代矩为迭代矩阵阵. .对应的方法为一种迭代法对应的方法为一种迭代法. .一一.
33、 .雅可比（雅可比（JacobiJacobi）迭代法迭代法(1)(1)迭代格式迭代格式设有设有n n 阶方程组阶方程组其中系数矩阵非奇异，且 ，i=1,2，n将将上式变形为上式变形为建立迭代格式建立迭代格式上面的迭代式称为上面的迭代式称为雅可比（雅可比（JacobiJacobi）迭代格式迭代格式。用矩阵形式来表示方程组的迭代格式用矩阵形式来表示方程组的迭代格式 设设det(A) ，且且则则记记A=D+L+UA=D+L+U 雅可比迭代式成为：雅可比迭代式成为：令令则得则得举例举例用矩阵形式和分量形式！用矩阵形式和分量形式！称称B B为雅可比迭代矩阵为雅可比迭代矩阵雅可比雅可比高斯高斯- -塞德尔
34、塞德尔迭代格式迭代格式二、高斯-塞德尔（Gauss-Seidel）迭代法G-SG-S迭代式成为：迭代式成为：则则令令则得则得记记A=D+L+UA=D+L+U 举例举例用矩阵形式和分量形式！用矩阵形式和分量形式！称称G G为高斯为高斯- -赛德尔迭代矩阵赛德尔迭代矩阵 三、逐次超松弛迭代法三、逐次超松弛迭代法（SORSOR法法-Successive Over Relaxation-Successive Over Relaxation）1.1.迭代公式迭代公式将将G G-S-S迭代格式迭代格式改写为：改写为： 并记并记 一般地，一般地，残量残量( (余量余量) ) 。 这就是这就是逐次超松驰迭代法
35、（逐次超松驰迭代法（SORSOR方法方法) )， 称为称为松驰松驰因子。因子。SOR方法的计算公式也常写为：方法的计算公式也常写为：Remark：可见，SOR方法的得到的可以看成是G-S方法的结果与的加权平均。将将残量乘以一个修正量加到残量乘以一个修正量加到 上，作为新的结果上，作为新的结果P56例12.3迭代法的收敛性迭代法的收敛性一、向量的一、向量的范数范数和矩阵的范数和矩阵的范数 定义定义1 1 （向量范数）对任意（向量范数）对任意n n维向量维向量XXRn, ,若按一定若按一定规则对应一实数规则对应一实数|X|，并满足以下条件：，并满足以下条件：正定条件正定条件. .即对任意即对任意X
36、Rn, |X|0，只有当，只有当X=0时，时， |X|=0齐次性齐次性. .对任意实数对任意实数k k， |kX|=|k| |X| （可扩展到可扩展到复数）复数）三角不等式三角不等式. .对任意对任意X，YRn, |X+Y| |X|+ |Y|则称则称|为向量范数.例如设分别称为X的1范数，2范数，范数，F 定义定义2 （矩阵范数）若对任意（矩阵范数）若对任意nn矩阵矩阵A，按一，按一定规则对应一实数定规则对应一实数|A|，并满足以下条件：，并满足以下条件：F对任意对任意nn矩阵矩阵A， |A|0，只有当，只有当A=0时，时， |A|=0F对任意实数对任意实数k， |kA|=|k| |A|F对任
37、意对任意nn矩阵矩阵A，B, |A+B| |A|+ |B|F对任意对任意nn矩阵矩阵A，B, |AB| |A| |B|F则称则称|为矩阵范数.分别称为X的1范数（列范数），2范（谱范数）数，范数（行范数），Frobenius范数P60例2（纠错）定义3(P59)若有向量范数|u和矩阵范数|v,使得对任意nn矩阵A和n维向量X都有|AX|u|A|v|X|u则称向量范数|u与矩阵范数|v是相容的.注意特别当u=v=1,2,，向量范数|u与矩阵范数|v是相容的.二、迭代法的收敛性当 k 时， 与下式等价 或 与下式等价当 k 时， 或定义4向量序列的极限迭代矩阵的谱半径迭代矩阵的谱半径(1)(1)收
38、敛的充要条件收敛的充要条件定理定理1 1（P62P62）迭代法迭代法 ， ，对，对 任意初始向量任意初始向量 都收敛的充要条件是：都收敛的充要条件是：注意雅可比好和G-S迭代法对应的M为B,G定义5（P61）设nn矩阵A的所有特征值为1，2，n，称下式为矩阵A的谱范数雅可比、高斯-塞德尔迭代法举例：FP76：第9,10题 是判定收敛的根本法则(充分必要！)。 时，有可能存在某个初始向量 使简 单迭代法收敛。（该向量不好找）RemarkRemark： (2)(2)收敛的充分条件收敛的充分条件 证明：证明：则简单迭代格式关于任意初始向量则简单迭代格式关于任意初始向量 和和 收敛。且收敛。且若若 定
39、理定理2（P62）设迭代公式设迭代公式设是M的任一特征值，X是A的关于的特征向量，则有X=MX，根据范数相容性，有由于X0得根据的任意性知根据定理1得证F定理3（P63）若nn矩阵A=aijnn是严格对角占优矩阵，则A为非奇异矩阵.F证：用反正法.若|A|=0，则齐次线性方程组AX=0有非零解，设有一非零解为X 说明|A|0，A是非奇异的定理4（P64）若线性方程组AX=b的系数矩阵是严格对角占优矩阵，则解此线性方程组的雅可比迭代法收敛.解此线性方程组的高斯-塞德尔迭代法收敛.（按行）,（i=1,2,n）证（1）设A=aijnn，则有所以雅可比迭代法收敛.由严格对角占优矩阵的定义有（按行）由严
40、格对角占优矩阵的定义有（按行） i=1,2,，n证证（2 2）：用用反反正正法法. .设设G=-(L+D)G=-(L+D)-1 -1 U U是是高高斯斯- -塞塞德尔迭代矩阵德尔迭代矩阵, ,设设是是G G的任一特征值，假设的任一特征值，假设11，则有，则有即(L+D)+U严格对角占优，根据定理3得矛盾因此高斯-塞德尔迭代法对任意初始向量收敛。证毕注意：由此还可得到求高斯-塞德尔迭代矩阵G的特征值的一个简便方法P76作业题7,9,10F定理5（P65）若线性方程组AX=b的系数矩阵A为正定矩阵，则解此线性方程组的高斯-塞德尔迭代法收敛F（证明从略）2.SOR2.SOR方法的收敛性方法的收敛性（
41、1 1） SORSOR方法收敛的必要条件是方法收敛的必要条件是0 0 2 2（定理（定理6 6） 当当 1 1时，时，SORSOR方法就是方法就是SeidelSeidel迭代格式。当迭代格式。当00 111时，称为超松弛时，称为超松弛方法。适当选取松弛因子方法。适当选取松弛因子 的值，可以得到比的值，可以得到比G-SG-S方法方法更快的收敛格式。更快的收敛格式。关于方法的收敛性有以下结论关于方法的收敛性有以下结论：（2 2）若系数矩阵）若系数矩阵A A 对称正定，且对称正定，且0 0 22，则，则SORSOR方法方法收敛（定理收敛（定理7.P667.P66）。）。（3 3）若系数矩阵）若系数矩
42、阵A A 严格对角占优严格对角占优，且，且00 1 1，则，则SORSOR方法方法收敛（收敛（教材中为介绍此结论教材中为介绍此结论）。）。RemarkRemark：能使能使SORSOR方法收敛最快的松弛因子叫做最佳方法收敛最快的松弛因子叫做最佳松弛因子，记为松弛因子，记为 optopt。 对某些特殊类型的矩阵，可以建立对某些特殊类型的矩阵，可以建立SORSOR方法最佳方法最佳松弛因子理论。例如，对于具有对称正定，或严格对松弛因子理论。例如，对于具有对称正定，或严格对角占优等性质的矩阵角占优等性质的矩阵A A的的线性方程组，可以建立最佳线性方程组，可以建立最佳松弛因子松弛因子 其中其中 ( (J
43、 J) )为解为解AxAxb b的雅可比迭代法的迭代矩阵的的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定谱半径。一般情况下确定 optopt并不容易，实际计算时并不容易，实际计算时一般都是根据试算的情况确定一般都是根据试算的情况确定 optopt的一个近似值。的一个近似值。3.3.如果如果 , ,则用此判断法比用则用此判断法比用 方便。方便。RemarkRemark：使用迭代法求解线代数使用迭代法求解线代数方程组需注意的问题方程组需注意的问题1.1.迭代法的收敛性与初始向量的选取无关。但初始迭代法的收敛性与初始向量的选取无关。但初始向量的选取对迭代的工作量有重大影响。向量的选取对迭代的工作量有重大影响。2.2.在使用实用误差估计式在使用实用误差估计式 停止迭代时，停止迭代时， 要选的恰当。要选的恰当。4.4.对某些方程组，有时可适当作些变形，以使得迭对某些方程组，有时可适当作些变形，以使得迭代法收敛（交换方程或变元的次序）。代法收敛（交换方程或变元的次序）。
